![](static/image/blog/recommendico.gif)
上面介绍的量子秀尔算法的经典部分,解释了它将一个大整数分解为两个素数因子的过程,即就是将其转化成了周期查找问题的过程。周期查找问题对经典而言关键而困难,对此问题经典算法的复杂度是指数级别,而秀尔用量子计算机可将复杂度降到多项式级别。
秀尔算法中只有“周期查找”这一步,是需要在量子计算机上完成的,其他都可在经典计算机上完成。量子计算机运行完“计算周期”的子程序后,就会将结果,即周期r,返回给经典计算机,让它继续完成计算过程。
实际上,量子计算和经典计算各有利弊。量子比特的特点是叠加态,有可能被利用来实现并行计算而加快算法,但是,在量子计算的过程中一般不进行(或少进行)测量,因为测量伴随着叠加态的塌缩,一旦塌缩到一个本征态,便失去了量子计算的优势,而经典计算有容易掌控的优越性。因此,专家们认为,量子计算机或许永远不会单独存在,而是一直和经典计算机配合执行任务,各展其长。输出输入以及复杂度简单的部分由经典计算完成,特殊问题的困难部分由量子计算完成,就像秀尔算法这样,便是用经典与量子配合起来完成破解RSA密钥的过程。此外,与许多量子算法一样, Shor算法是概率性的。也就是说,它以高概率给出正确答案,并且通过算法的重复来降低失败的概率。
秀尔量子算法的周期查找,由指数模操作和量子傅里叶变换两部分组成,如图4.15a所示Shor算法依赖于模运算和量子并行计算,下面介绍秀尔算法中量子部分(图4.15b),看看秀尔算法是如何找到周期的?
图4.15:秀尔算法-量子
描述周期函数最合适的数学方法,是傅里叶变换Fourier Transform。秀尔周期查找的核心技术,正是被称为量子傅里叶变换的QFT。
首先看一下我们问题中的周期函数长什么样?这是来自于数论得到的一个重要结果:设F(a) 等于x的a次方mod N,那么F(a)是一个周期函数。
用上一节4.3中的例3为例,即N=15、x=7,我们得到序列:
70(mod 15) = 1, 71(mod 15) = 7, 72(mod 15) = 4, 73(mod 15) = 13, 74(mod 15) = 1……等等。
这个例子的周期函数F(a)如图4.15c所示。秀尔算法量子部分的目的是要找到指数模序列F(a)的周期,可归纳为下列过程,我们在介绍一般过程时,也将上述例子结合于对过程的解释中:
首先,选择一个等于2的幂的整数q,定义它的取值范围为N^2≤q≤2N^2。例子中的N=15,我们选取q=256;再选择一个与N互质的随机整数x ,我们选取x等于7。
第二步,创建一个量子寄存器R,将其划分为两个独立的寄存器:R1和R2,R1用作输入寄存器,R2输出。R1必须有足够的个量子位来表示任何q-1以内的整数;R2必须有足够的个量子位,来表示任何N-1以内的整数。对例子中的具体数值,R的12个量子比特分成两部分,n=8和m=4。
如图4.15b所示,用y0、y1、y2、y3分别代表4个不同时间点的量子态。将R1和R2初始化为全0时的状态为y0。然后,对R1的量子位应用哈达玛变换,即应用n个H门到n个基态0,这将使寄存器R1的组合状态成为从0到q-1的(2的n次方个)均匀等权的量子叠加态,而R2不变,总状态记为y1。
再次强调一下:哈达玛德H门很重要,能产生量子叠加态。一个H门作用后产生两个基态的叠加,n个H门则产生2的n次方个基态的叠加。不过,在这儿的秀尔算法中,产生的不仅仅是R1的均匀叠加态,而且必须使得R1和R2互相纠缠,也就是使输入和输出互相纠缠。这样,当我们测量一个使其塌缩时,也影响到另一个状态的塌缩。
从y1到y2的转换,是应用一个特别的量子转换门(黑箱Oracle),使指数模函数f(a)=xa(mod N)生效,生成指数模周期序列。即将量子态|a> |0>映射成|a> |xa (mod N)>。对上述具体例子,转换门之前和之后的量子态y1和y2的表达式如图4.16所示。
图4.16:量子黑箱函数的作用
换言之,量子黑箱函数的作用是:为存储在寄存器R1中的每个数计算xa模N,并将计算结果存储在寄存器R2中。由于量子并行性,xa模N的计算可以在量子计算机上一步完成。这个步骤完成之后,量子存储寄存器的联合状态为y2。我们将y2按输入输出展开后,再根据输出寄存器重新排列:
图4.17:y2的重新排列
虽然输出寄存器R2有4个量子位,可以表示0-15之间的任何数,但因为例3中的模周期函数7a(mod 15) 只有4个数值:1、7、4、13,所以y2中的R2是|1> 、|7>、|4>、|13> 的均匀叠加态。
然后对输出量子位R2进行测量。这时 有趣的事情发生了:测量输出R2使其以相同的概率塌缩成4个态中的一个。例如塌缩成|1> ,因为R2和R1互相纠缠,所以R2的塌缩也造成了R1的部分塌缩。
图4.18:测量R2造成自己塌缩以及R1的部分塌缩
因此,测量后的合成态如图4.18所示:y(2-3)的输出部分只有一项,y(2-3)的输入部分仍然是叠加态,也是一个周期序列,正等待作QFT。
最后,执行量子傅立叶变换求周期。QFT算法很复杂难以详细介绍,但傅里叶变换的概念是通用的。例如 如果输入是正弦或余弦函数,变换后的结果是在 某一频率的德尔塔函数。对一般的周期函数 结果会是周期附近的多个尖峰。
在我们的具体例子中,峰值在0、64、128等。根据多次测量,不难计算出周期,我们例子中的周期r=4 。然后,便遵循上一讲描述的程序,可以成功地分解N而得到N=5x3。
秀尔算法几乎利用了量子计算机的所有优势:一是叠加性,即量子位的多重表示。就是用哈达玛达门制造出均匀叠加,叠加态可以同时进行平行运算,但却不能测量。因为一旦测量,便会塌缩到所有本征态的其中之一。因此,最好的办法是将量子算法部分“包”在经典部分的中间,例如秀尔的量子部分包括QFT在内。从经典部分给量子部分输入少量的参数,量子给经典返回周期的数值。而将大量计算量,利用量子比特的平行运算能力,在量子计算机内部完成。量子计算部分被包住了,不测量就不会塌缩!然而,秀尔也巧妙地利用了量子态之间的纠缠性,引起部分塌缩但仍然保持叠加态。另外,量子傅里叶变换利用了量子相干性,因为物理中干涉衍射,其数学本质就是傅里叶变换。
如何用量子模拟线路实现秀尔算法?请参考IBM模拟软件平台的文件【10】。
(待续)
参考文献:
【1】Keynote talk, 1st conference on Physics and Computation, MIT, 1981。(International Journal of Theoretical Physics, 21: 467–488, 1982)
【2】Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein; 殷建平等译. 第1章 算法在计算机中的作用. 算法导论 原书第3版. 北京: 机械工业出版社. 2013年1月
【3】张天蓉. 世纪幽灵-走近量子纠缠(第二版)[M].合肥:中国科技大学出版社,2020年5月。
【4】Bloch Sphere(wikipedia),https://en.wikipedia.org/wiki/Bloch_sphere
【5】IBM Quantum (2022). estimator primitive (Version x.y.z) [computer software]. https://quantum-computing.ibm.com/
【6】Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
【7】无穷的开始: 世界进步的本源,作者:戴维·多伊奇 (David Deutsch), 王艳红, 张
出版社:人民邮电出版社,出版日期:2014-11-01
【8】真实世界的脉络,作者: [英] 戴维·多伊奇,出版社: 广西师范大学出版社,译者: 梁焰 / 黄雄,出版年: 2002-8
【9】David Deutsch & Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A. 439 (1907): 553–558.
【10】Shor’s algorithm from IBM:
https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm
(待续)
**********************************************************
作者部分YouTube视频:
https://www.youtube.com/watch?v=0I8FdazqAvc&list=PL6YHSDB0mjBKB2LBZDKL9UhcMMx6GtOsx
https://www.youtube.com/watch?v=_d0wquZkOYU&list=PL6YHSDB0mjBJ6qgfin-xKmP3FtTQr4x7i
*********************************************************
转载本文请联系原作者获取授权,同时请注明本文来自张天蓉科学网博客。
链接地址:https://wap.sciencenet.cn/blog-677221-1417043.html?mobile=1
收藏