英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

arXiv：1903.00768v2 [quant-ph] 2019年3月6日

基于IBM Q的Shor分解算法的实验研究

Mirko Amico，1 Zain H. Saleem，2和Muir Kumph3

^{1纽约城市大学研究生院和大学中心，纽约，纽约10016，美国2巴基斯坦科学院理论研究所，巴基斯坦伊斯兰堡440003IBM T.J.沃森研究中心，约克镇高地，NY 10598，美国}

我们研究了ibmqx5超导芯片上Shor分解算法的编译版本的结果，针对N = 15,21和35的特殊情况。半经典量子傅里叶变换用于实现只有少量的算法。物理量子位和电路旨在将门数减少到最小。我们通过统计重叠的平方（SSO）给出实验获得的分布与对应于周期的阶段的预测理论分布之间的相似性的定量测量。这允许我们在不使用连续分数算法的情况下为实验数据分配周期。此外，通过使用重叠系数（OVL）给出了我们的周期分配中的误差的定量估计。

1. 介绍

Shor的因子分解算法[1]是一个众所周知的量子算法的例子，它超越了最着名的经典算法。然而，由于执行算法所需的大量量子位和门所引入的误差，具有物理量子位的算法的实验实现仍然是一个挑战。在本文中，我们提供了Shor分解算法的编译版本的原理验证演示，分别使用五个，六个和七个超导量子比特来计算N = 15,21和35的数字。类似的实验已经完成了像NMR [2]，被捕获的离子[3]，光子[4-6]，光子芯片[7]和超导量子位[8,9]这样的设置。但是，除了Refs。 [3,5]，所有这些实现涉及算法的过度简化版本，相当于硬币翻转[10]并且不需要量子硬件来获得相同的结果。

该算法将因子分解问题转化为订单发现问题，其中存在量子加速。实际上，找到数N的素因子等价于找到函数axmodN = 1的指数x，其中a是小于随机选取的N的整数。这种指数称为a的顺序或周期。在深入研究实验的细节之前，让我们简要回顾一下算法的量子部分。计算需要两个量子寄存器。一个寄存器用于存储周期，称为周期寄存器，另一个存储计算结果，称为计算寄存器。两个寄存器的大小取决于要考虑的数量N.特别是，周期寄存器应该在区间log2（N2）lt;np lt;log2（2N2）中具有多个量子位np，并且计算寄存器应该足够大以能够表示数字N-1，这是由模块化产生的。取幂函数（MEF）axmodN，因此需要nq = log2N量子位。

在量子算法的开始，两个寄存器被初始化为状态100 ... 0} p 100 ... 0} q，其中下标p和q表示周期寄存器

和计算寄存器。周期寄存器存储指数x的所有可能值，它将通过在所有qubitsSQ = o1 | x} P上通过Hadamard门创建所有可能位串的均匀叠加来给出周期的估计，其中Q =

2” 页。而计算寄存器存储MEF的结果，axmodN。在第一步之后，两个寄存器处于状态^ Q = o | x} p | axmodN} q。然后，

量子傅里叶变换（QFT）应用于周期寄存器，使得| x} p ^ S2-1 e Q | s} p。作为一个

QFT的结果，发生所有可能状态之间的干扰。如果然后测量周期寄存器，则将观察到s的值，使得Q = d，其中d是整数并且r是周期。更具体地，周期寄存器的测量允许我们以高概率找到与1成比例的分数Q的近似。算法的最后部分涉及在量子部分中获得的测量的经典处理。可以通过使用连续分数算法从分数Q中找到周期r的值。如果以这种方式计算的周期r是奇数或r = 0，则算法失败并且通过选择不同的基数a重新开始。如果r是偶数，则（ar-1）modN可以被分解为（a2-1）（a2 1）modN。最后一步是通过检查gcd（a2 1，N）= 1来检查（a2 1）modN是否具有N的公约数。如果这是真的，那么N的两个因子是gcd（a2 1， N）和gcd（a 2 - 1，N）。

如前所述，该算法版本的执行要求计算寄存器中的nq = log2（N）量子位执行模幂运算，并且在周期寄存器中至少需要另外的np = 2log2（N）量子位以执行QFT。因此，完整的算法需要总数为3log2（N）的量子位。即使将N = 15的数量因子分解在输入寄存器中也需要12个量子比特来执行该算法，这仍然是当今量子计算机物理实现的挑战。然而，Kitaev [11]观察到，对于像Shor这样的算法，人们不需要关于相对阶段的信息。

2

输出状态只有它们测量的概率幅度，可以用半经典量子傅里叶变换（sc-QFT）代替完全相干量子傅里叶变换。在sc-QFT中，每次测量周期寄存器的一个量子位。然后使用量子位的测量结果来确定下一个量子位的测量类型。这使得能够用多次测量的单个控制量子位替换周期寄存器的2log2（N）量子位。对于因式N = 15的情况，Kitaev的方法分别减少了n = 5所需的量子位总数，并且对于N = 21和N = 35到n = 6和n = 7的情况，它们的数量足够小目前可用的硬件处理。然而，系统尺寸的这种减小带来的缺点是需要按顺序单量子位读出和状态重新初始化以及基于先前测量结果的门设置的前馈。 sc-QFT的实现已在[12,13]中描述并在[3]中实现。目前，IBM量子计算机不执行顺序单量子位读出和量子位重新初始化。在本文中，我们提供了绕过这个障碍来实现sc-QFT的过程。

该文章按以下方式组织。秒。 II描述了用于实验的硬件。在第二节图3分别描述了N = 15,21和35的保理实验的实施。在ibmqx5量子处理器上运行算法得到的结果将在第二部分进行分析和讨论。 IV。结论如下。 V.

II。硬件

我们使用具有16个超导量子比特的IBM ibmqx5芯片来实现我们的实验，用于将数量N = 15,21和35分解。量子位分布在平面上，作为两个相邻的八个量子位的阵列。量子比特的耦合图如图1所示。

图。 1：ibmqx5器件的量子位之间的耦合映射。

量子比特的弛豫时间T在25~60 ^ s之间，其相移时间T2在20~100 ^ s之间。单量子比特门具有高保真度，在实验时测量为~99.8％。根据所考虑的量子比特对，测量的多量子比特门保真度约为95％-98％。另一个误差源来自量子位状态的读出，大约相当于5％的误差。使用这些

参数，噪声可以包含在模拟中，获得更准确的设备输出预测。

1. 实验

按照[3]中给出的例子，我们使用图2所示的电路实现Shor的因子分解算法的量子部分。

对于N = 15的情况，需要五个输入量子位。一个量子位初始化为 0} p用于周期寄存器，用作控制量子位，所有其他量子位初始化为属于计算寄存器的状态 ^gt;} = 10001} q。除了量子寄存器之外，我们还需要一个三位经典寄存器来存储控制量子位的测量结果，该量子位编码周期的值。重要的是要注意，对于这种情况，任何基数a的可能周期r都是2的倍数。这意味着从周期寄存器测量的相位s的任何偶数值将给出与1成比例的分数QQ，这总是允许我们找到周期。通过分析沿着电路的量子寄存器的状态，可以看出在计算寄存器中的状态之间没有发生量子干扰。因此，无论器件的纠缠栅极的质量如何，都可以获得正确的结果，只要可以将周期寄存器与计算寄存器纠缠在一起即可。

图。 2：在[3]中实现的用于分解N = 15,21和35的电路。

从图2中的电路图中可以看出，控制量子位的旋转取决于前面步骤中每次测量的结果。由于ib-mqx5芯片不允许基于测量的量子位复位和条件操作，这是实现Kitaev建议的sc-QFT所必需的，因此我们在三个独立的部分中实现该算法。通过将前一部分的计算寄存器的输出量子状态输入下一部分（详见附录A）并基于先前测量的结果在周期量子位上添加右旋转门，可以连接不同的部分。

N = 15的情况是最简单的情况，并且它没有提供计算寄存器的状态之间的量子干扰为计算带来优势的示例。由于这个原因，我们试图计算第二个最小数，它是两个质数的乘积，N = 21.在这种情况下，存在基数a，其周期不是2的倍数，因此状态之间的建设性量子干涉

3

需要在计算寄存器中增加找到正确结果的可能性。这种情况的一个例子首先在参考文献中得到证实。 [5]。

我们使用三位精度来实现一个算法N = 21，其中基数o = 2，用于估计编码周期的相位。在这种情况下，量子寄存器由计算寄存器中的五个量子位和周期寄存器中的一个量子位组成。我们采用与先前相同的方法，打破模幂运算的每个阶段，并手动将每个部分的输出作为输入提供给下一个（详见附录A）。这意味着该电路将具有三个模幂运算阶段，其中在每个阶段估计编码该周期的相位的单个比特。因此，电路看起来像图2中的那个。模幂运算电路专门设计用于计算ax mod 21，其中我们选择基数a = 2.这个基数有周期r = 6，因此1 / r不容易用二进制表示。因此，周期估计的准确性取决于用于相位估计的比特数。

相同的方法应用于因子N = 35，基数a = 4.在这种情况下，我们需要计算寄存器中的六个量子位和周期寄存器中的一个量子位。如在N = 21的情况下，4x mod 35的周期是r = 6，因此1 / r不能容易地以二进制表示。作为运行量子算法的结果，我们获得估计相位s的概率分布，其在1 / r的倍数附近达到峰值。我们使用三位寄存器来估计编码周期的相位。同样，如图2所示实现用于运行算法的电路，估计相位的一个比特的每个级分别实现，然后通过经典算法连接。在不同阶段计算MEF的各个电路可以在附录A中找到。

IV。结果和数据分析

图图3a，4a，5a和6a示出了在ibmqx5超导装置上运行因子分解算法所获得的结果。描述的是实验的相对概率（蓝色）与期望值并排，其中可以在理论上（绿色）计算所使用的碱a的估计相s的每个值。该算法每个基地运行1000次。

以两种不同的方式评估实验的成功。我们使用概率图来给出结果正确性的定性估计，而统计重叠的平方（SSO）用作定量测量。概率图[14]是在视觉上比较两个分布的有用工具。在概率图中，一个分布相对于另一个绘制。如果两个分布相同，则图将显示一条直线（y = x）。在概率图中与直线y = x线的偏差量是指示

图。 3：（a）找到N = 15的给定相位的概率，基数a = 2，和（b）理论分布和r = 4的实验分布的概率图。通过数据收集描述实验分布以及数据的拟合。 （c）实验数据的SSO，其理论概率分布对应于周期r的所有可能值。

绘制的两个概率分布之间的差异。对于每种情况，实验分布与预期理论分布之间的概率图显示在图4和图5中。 3b，4b，5b和6b。在N = 15的情况下，图5和图6中的数据相同。 3b和4b位于非常接近y = x线的直线上（标记为“理想”）

4

图。 4：（a）找到N = 15的给定相位的概率，其中a = 11，以及（b）理论分布和实验分布的概率图。通过数据收集和数据拟合描述实验分布。 （c）实验数据的SSO，其理论概率分布对应于所有可能的周期。

地块）。对于N = 21的情况，数据位于与y = x理想线平行的直线上，如图5b所示。这意味着我们的实验分布存在偏移，但总体形状与理论分布一致。最后，对于N = 35，图6b中的数据位于一条非常远的直线上

图。 5：（a）找到N = 21的给定相位的概率，基数a = 2，和（b）理论分布和实验分布的概率图。通过数据收集和数据拟合描述实验分布。 。 （c）实验数据的SSO，其理论概率分布对应于所有可能的周期。

y = x线，表示实验结果与理论预期结果的重要偏差。在概率图中，我们添加了一个带有误差条的数据。可以看出，对于N = 15和N = 21，拟合接近理想线（在误差条内），但是对于N = 35，则不是。我们认为概率图提供了良好的定性测量

5

图。 6：（a）找到N = 35的给定相位的概率，其中a = 4，以及（b）理论分布和实验分布的概率图。通过数据收集和数据拟合描述实验分布。 （c）实验数据与r的不同值的所有可能的理论分布之间的SSO图。

概率分布之间的相似性，因为它们正确地描述了通过比较分布的直方图而显而易见的相似性。

接下来，我们给出算法性能的定量测量。特别是，我们想回答这个问题：给出实验数据，得到什么

这个数据是否来自给定的概率分布？这个问题的答案将揭示我们实验的两个方面。首先，它允许我们为结果分配一个句点，而不需要连续的分数算法。其次，它将为我们提供衡量我们在任务中所犯错误的指标。

为了给数据分配一个周期，我们将实验获得的概率分布与对应于与3位精度估计兼容的周期的可能值的预期概率分布进行比较（因此r的范围从2到7）。这可以这样做，因为存在对应于每个周期的独特理论概率分布，与实验中使用的基

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[20840]，资料为PDF文档或Word文档，PDF文档可免费转换为Word