基于IBM Q平台的量子算法研究
2019-01-02江文兵
卫 佳,倪 明,周 明,江文兵
(中国电子科技集团公司第三十二研究所,上海 201808)
0 概述
近年来,随着多比特超导量子技术的发展[1]以及量子模拟器的相继推出,量子算法的研究获得高速发展。文献[2]提出Shor因子分解算法,在量子计算领域具有里程碑式的意义。Shor因子分解算法只需多项式步长计算就能完成一个整数的因子分解,其设计核心是量子傅里叶变换。量子傅里叶变换应用较广泛[3],其不仅在密码领域有丰富的应用,还在信号处理等领域有着举足轻重的地位。在多项式时间内部分经典算法不能解决的问题,可用量子傅里叶变换来解决,如求阶问题、隐含子群问题、离散对数问题等。只要解决了求阶问题,RSA加密算法就非常容易被破解。
量子随机行走算法[8]既有经典随机行走的背景,又具备量子计算的并行性[9]。在解决一些实际问题,比如寻找三角形、区分元素时,量子随机行走算法相比经典计算有更快的多项式分解速度。近年来,量子随机行走算法实现了搜索算法、模拟退火算法、公式估计[10]等,其被认为是其他量子算法的设计工具之一,原因是经典随机行走在经典算法中有很重要的地位,很多数学问题都可以归结为经典随机行走问题。
IBM于2016年开放量子云计算平台[11]并上线5 bit超导量子芯片,研究者可以通过互联网使用该量子平台进行算法研究、模拟以及量子芯片运行。本文在IBM Q的5 bit超导量子芯片上分别以1 024 shots和8 192 shots的次数运行2 bit Grover搜索算法和2 bit量子随机行走算法,比较测量次数对真实量子计算机运行结果的影响。然后在该平台上用模拟器以8 192 shots分别运行2 bit Grover搜索算法和2 bit量子随机行走算法,并与上述量子芯片运行结果作比较。最后采用IBM Q的量子模拟器运行5 bit量子傅里叶变换算法和3 bit Grover搜索算法,并与数学分析结果进行比较。
1 IBM Q量子芯片与量子模拟器对比实验
1.1 Grover搜索算法
Grover搜索算法的设计流程[12]如图1所示。
图1Grover搜索算法设计流程
Grover搜索算法具体步骤如下:
步骤2将目标位态|x0>进行旋转,使其获得一个π相位,即Uf|x0>=-|x0>,其他量子态不受影响。在量子计算机中,这个变换可以由量子黑盒(Oracle)来执行,命名为O,Oracle电路通过改变解的相位标记来搜索问题的解,由图2中的实线框实现电路。
步骤3执行Hadamard变换H⊗n,即对每个比特进行如下操作:
步骤4构造酉算子Us=2|0><0|-I,执行条件相移,实现|x>→-(-1)f(x)|x>,如图2中的虚线框所示。例如,该步骤对|x>态进行旋转,使得|x>态的相位在原来的基础上增加π,此时|x>态变成-|x>态。
步骤5执行Hadamard变换H⊗n。
图2 Grover搜索算法电路示意图
在图2的Grover搜索算法量子电路中,算法目标是从|00>、|01>、|10>、|11> 4个量子态中寻找|00>态出现的概率。该算法电路由一系列单比特门和多比特门构成。单比特门有H门、S门(相位门)、X门,双比特门主要是CNOT门。各量子门的矩阵表示分别为:
在Grover搜索算法量子电路中:首先,量子比特q0和q1经过H门,形成量子叠加态|s>,幅值都相等且为正值,再通过由S门、H门以及CNOT门组成的量子黑盒,获得一个π相位,使得|00>态(目标位态)的幅值为负值,从而降低平均幅度;然后,通过由H门、酉算子Us=2|0><0|-I、H门构成的2|s>
本文使用IBM Qx2量子芯片,可通过选择不同的次数运行电路得到结果:
1)在单次1 024 shots的情况下,重复运行3次上述量子Grover搜索算法。此时测量结果为:|00>态出现的概率分别为0.816、0.888、0.927,平均概率为0.877;|01>态出现的概率分别为0.092、0.027、0.032,平均概率为0.050;|10>态出现的概率分别为0.061、0.074、0.020,平均概率为0.052;|11>态出现的概率分别为0.031、0.011、0.021,平均概率为0.021。此时大概率出现的是|00>态。
2)在8 192 shots的情况下重复运行3次量子Grover搜索算法。测量结果为:|00>态出现的概率分别为0.872、0.920、0.917,平均概率为0.903;|01>态出现的概率分别为0.064、0.033、0.034,平均概率为0.044;|10>态出现的概率分别为0.042、0.024、0.028,平均概率为0.031;|11>态出现的概率分别为0.021、0.023、0.021,平均概率为0.022。数据结果对比如图3所示。
图3 在IBM Qx2量子芯片上运行Grover搜索算法结果
下一步采用IBM Q量子模拟器运行图2所示算法,在8 192 shots的情况下进行3次模拟,结果为:|00>态出现的概率分别为1、1、1,平均概率为1;|01>态出现的概率分别为0、0、0,平均概率为0;|10>态出现的概率分别为0、0、0,平均概率为0;|11>态出现的概率分别为0、0、0,平均概率为0。IBM Qx2量子芯片与模拟器实验结果对比情况如图4所示。
图4 在IBM Qx2量子芯片和模拟器上运行Grover搜索算法结果对比(8 192 shots)
1.2 量子随机行走算法
本文所研究的量子随机行走算法是基于图的随机行走。图上的随机行走是指定一个图和一个起始点,随机选择一个相邻节点,转移到相邻节点上后把该节点设定为新的起始点,不断重复上述过程,由随机行走经过的节点序列即构成一个随机行走过程[15]。2个量子比特随机行走算法示意图如图5所示。
图5 量子随机行走算法示意图
在图5中,设定起始点为|00>,经过第1次随机行走后为|01>或|10>,再经过第2次随机行走后变为|11>,第3次依然为|01>或|10>,第4次随机行走之后回到|00>。
量子随机行走算法的量子电路如图6所示。
图6 量子随机行走算法电路
使用IBM Qx4量子芯片,在1 024 shots的情况下重复运行3次量子随机行走算法,结果为:|00>态出现的概率分别为0.857、0.834、0.845,平均概率为0.845;|01>态出现的概率分别为0.058、0.065、0.083,平均概率为0.069;|10>态出现的概率分别为0.064、0.074、0.051,平均概率为0.063;|11>态出现的概率分别为0.021、0.026、0.021,平均概率为0.023。
在8 192 shots的情况下重复运行3次量子随机行走算法,结果为:|00>态出现的概率分别为0.830、0.832、0.830,平均概率为0.830;|01>态出现的概率分别为0.070、0.069、0.068,平均概率为0.069;|10>态出现的概率分别为0.076、0.077、0.076,平均概率为0.076 3;|11>态出现的概率分别为0.024、0.021、0.026,平均概率为0.024。上述2种情况的数据结果对比如图7所示。
图7 在IBM Qx4量子芯片上运行量子随机行走算法结果
在IBM Qx4量子芯片和模拟器上分别运行量子随机行走算法,在8 192 shots的情况下进行3次实验,结果为:|00>态出现的概率分别为1、1、1,平均概率为1;|01>态出现的概率分别为0、0、0,平均概率为0;|10>态出现的概率分别为0、0、0,平均概率为0;|11>态出现的概率分别为0、0、0,平均概率为0。IBM Qx4量子芯片与模拟器实验结果对比情况如图8所示。
图8 在IBM Qx4量子芯片和模拟器上运行量子随机行走算法结果对比(8 192 shots)
在IBM的5 bit超导量子芯片运行结果(图3、图7所示)中,测量次数增加(shots增大),测试结果并没有随之优化。这是因为量子比特的状态与测量环境有关,每次的测量状态不完全相同。但是,在测量次数更多时结果的稳定性更好。
量子芯片将量子线路集成在芯片上,在极限低温下构建量子物理系统,同时对量子物理系统进行调控,其间遵守量子动力学规律。量子模拟器基于经典计算机的架构模拟量子系统。在IBM量子芯片与模拟器的对比测试结果(图4、图8所示)中,模拟器计算结果的准确度明显优于量子芯片。在真实芯片测量环境下,单比特门与双比特门的保真度不高。例如,稀释制冷机中没有完全隔绝的热噪声会影响原子跃迁,微波系统测量精确度不足将导致最后的结果偏差,每次测量时量子比特的随机坍缩等都是影响其保真度的因素。
2 量子傅里叶变换算法与Grover搜索算法
2.1 5 bit量子傅里叶变换算法
量子傅里叶变换即作用在空间C2n中的离散傅里叶变换。离散傅里叶变换是有限长序列傅里叶变换的有限点离散采样,而量子傅里叶变换把一组标准正交基{|x>}用另一组标准正交基{|y>}表示:Y=UX。此处的U就是量子傅里叶变换的核心,即作用在Hilbert空间中任意矢量上的变换矩阵UQFT,该矩阵可以拆分成一系列逻辑门。一个量子比特的量子傅里叶变换就是H门操作,在多量子位态空间上的傅里叶变换是上述单量子位H变换的推广。简而言之,量子傅里叶变换就是将任意单量子态制备成叠加量子态,从而进行酉变换并完成指数级加速。
量子傅里叶变换由2个基本门操作实现:一位门操作H门和两位控制U门操作CUa,b。其中,b为控制位,a为目标位。当且仅当第b量子位为|1>态时,才对第a位施加幺正变换Ua,b。在a、b两量子位Hilbert空间的计算机下,有:
其中,相移θa,b=2πxb/2a-b+1。
5量子位的傅里叶变换可以用图9所示的电路实现,该网络对输入态|x>=|x4x3x2x1x0>从左到右依次执行变换[16]:H0U1,0H1(U2,0U2,1)H2(U3,0U3,1U3,2)H3(U4,0U4,1U4,2U4,3)H4。其中,门H的下标指明它作用的量子位。CU1在IBM Q量子云平台中表示沿Z轴旋转一定角度的受控Z门,其是一个双比特门。而在IBM量子云平台中,使用CU1门来实现该操作。其中,Pi/2代表沿Z轴转动π/2的角度,对于U0,1来说,当且仅当q[1]为|1>态时,才对q[0]施加幺正变换U0,1,使之沿Z轴转动π/2,以此类推。
图9 5 bit量子傅里叶变换模拟电路
本次模拟次数为8 192 shots。根据理论推算,其结果应该是5 bit的均匀叠加态,即32个等概率的量子态:从|00000>到|11111>,概率为1/32=0.031 25。模拟器的运行结果(如图10所示)显示了20个结果的状态,其中,横坐标1#～20#代表不同的量子态,分别为|10101>、|10110>、|11010>、|11011>、|01011>、|10111>、|00011>、|11100>、|01000>、|01110>、|10011>、|00101>、|10100>、|10000>、|00010>、|00111>、|01100>、|11001>、|11110>、|00000>。余下12个量子态的概率值以一个总和的结果呈现:0.355/12≈0.029 6。根据上述理论结果推算,模拟器结果的最大概率误差为0.1。
图10 5 bit量子傅里叶变换模拟计算结果
2.2 3 bit Grover搜索算法
3 bit Grover搜索算法模拟电路如图11所示。3 bit Grover搜索算法的目标是从<000|到<111|的状态中寻找|110>量子态,其算法思路如前文所述。在图11中,C、B、A为Toffoli门,在IBM模拟器中,为CCX门。
图11 3 bit Grover搜索算法模拟电路
Toffoli门的矩阵表示为:
采用IBM量子模拟器在8 192 shots情况下进行测量,结果如图12所示。其中,横坐标代表量子态。由图12可以看出,搜索到目标量子|110>的概率为0.944,相比于2 bit的Grover搜索算法模拟结果而言,误差相对较大。造成该现象的原因是量子逻辑门运行时会有一定的噪声,在本次实验中,采用了Toffoli 3 bit的逻辑门,从而造成明显误差。此外,量子比特数增多、量子线路变长也会引起误差增加[17]。
图12 3 bit Grover搜索算法模拟计算结果
采用模拟器对单比特门进行模拟后可知,单比特门的模拟结果也存在误差。对于H门,最优计算结果是均匀叠加态,即|0>和|1>的测量概率相等,均为0.5,但模拟计算结果为0.502和0.498,误差范围在0.01以内。
3 结束语
本文基于IBM Q云计算平台,针对3种典型量子算法——Grover搜索算法、量子随机行走算法、量子傅里叶变换算法,分别采用量子芯片和量子模拟器进行测试。结果表明,增加测试次数并不能提高量子芯片的保真度,而相比量子芯片,模拟器的计算结果准确度较高。此外,本文设计并运行5 bit量子傅里叶变换算法和3 bit Grover搜索算法,分别采用IBM Q模拟器进行8 192 shots情况下的测量。结果表明,量子模拟结果和数学理论推导结果在误差范围内一致。本文最后将经典计算机量子模拟结果与数学分析结果作对比,分别对单比特门和多比特门的误差产生进行分析。下一步将针对更高量子比特的算法,在设计与实现的过程中使运算结果更接近所求解的目标值,以进一步减小误差,提高保真度。
