4.4 秀尔算法-2（量子部分）

上面介绍的量子秀尔算法的经典部分，解释了它将一个大整数分解为两个素数因子的过程，即就是将其转化成了周期查找问题的过程。周期查找问题对经典而言关键而困难，对此问题经典算法的复杂度是指数级别，而秀尔用量子计算机可将复杂度降到多项式级别。

秀尔算法中只有“周期查找”这一步，是需要在量子计算机上完成的，其他都可在经典计算机上完成。量子计算机运行完“计算周期”的子程序后，就会将结果，即周期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，我们得到序列：

7⁰(mod 15) = 1,  7¹(mod 15) = 7,  7²(mod 15) = 4,  7³(mod 15) = 13,  7⁴(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)=x^a(mod N)生效，生成指数模周期序列。即将量子态|a> |0>映射成|a> |x^a (mod N)>。对上述具体例子，转换门之前和之后的量子态y1和y2的表达式如图4.16所示。 

图4.16：量子黑箱函数的作用

换言之，量子黑箱函数的作用是：为存储在寄存器R1中的每个数计算x^a模N，并将计算结果存储在寄存器R2中。由于量子并行性，x^a模N的计算可以在量子计算机上一步完成。这个步骤完成之后，量子存储寄存器的联合状态为y2。我们将y2按输入输出展开后，再根据输出寄存器重新排列：

图4.17：y2的重新排列

虽然输出寄存器R2有4个量子位，可以表示0-15之间的任何数，但因为例3中的模周期函数7^a(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

*********************************************************