![](static/image/blog/recommendico.gif)
4.2 多伊奇算法
上节介绍的Grover搜索算法,并不是第一个量子算法。第一个量子算法是由多伊奇发表的,多伊奇被誉为“量子计算之父”,是一位常人眼中行为奇特的科学家。
戴维·多伊奇教授是出生在以色列长在英国的犹太人,表面上,他是英国物理学家,牛津大学教授,量子计算先驱!不过他不教书,实际上是一个没有固定工作的自由学者。他靠着演讲、奖金和出书来赚钱为生,据说是位很少与人来往的牛津隐居者。
特别引起公众瞩目的,是多伊奇那两本可以当作科普来读却又与一般科普完全不一样的书:《真实世界的脉络》和《无穷的开始》。书中多伊奇有许多新奇深奥的科学哲学观点,在此我们不详谈,对他的书感兴趣的读者可阅读参考文献【7,8】。
图4.7:多伊奇
总而言之,多伊奇这位两耳不闻窗外事的古怪科学家,在1985年突然声名大振,因为他发表了一篇里程碑式的论文,文中他展示了Deutsch算法,表明量子计算可以比经典更快。7年后(1992年)发表了对多伊奇算法的推广【9】。在多伊奇算法启发下的之后两年间,量子算法来到多产期。Simon、Shor和 Grover的算法都在这期间相继发表。
多伊奇算法没有什么应用,但作为第一个量子算法意义重大,它只适用于一种特殊的情况。因此作一个简要介绍。
考虑一个只有一个变量的函数,输入为0或1,输出也为0或1。这样的函数共有四个,分别记为f0、f1、f2和f3:函数f0,输入0和1,输出都是0,即f0(0) =0和f0(1) =0。函数f1,输出与输入相等,即f1(0) =0和f1(1) =1。函数f2,输出与输入相反,即f2(0) =1和f2(1) =0。函数f3,输入0和1,输出都是1,即f3(0) =1和f3(1) =1,见图4.7下图。
图4.8:多伊奇函数
我们将函数f0和f3称为常值函数,即对于两个输入,输出都是相同的值的函数。如果一个函数一半的输出是0,另一半的输出是1,那么就称这个函数为平衡函数。例如f1和f2就是平衡函数(图4.7上图)。
Deutsch提出的问题是:随机给定这四个函数中的一个,我们需要查询多少次,才能确定这个函数是常值函数还是平衡函数?就是说我们不关心给定函数是四个函数中的哪一个,只问它是常值函数还是平衡函数。
首先想想经典计算需要多少次?经典计算机一次只能有一个输入,也只能计算并输出一个函数值。但是,为了回答多伊奇问题,我们必须把0和1都代入函数,所以一定需要做两次经典操作。那么,如果使用量子计算机呢?量子计算机优于经典计算之处,是因为量子比特是叠加态,它可以同时储存1和0两个数。那么,就有可能操纵量子比特,同时对0和1进行计算,因此便有可能一次得出答案。实际上也可以做到,这正是多伊奇算法所展示的。
具体可用IBM模拟实例慢慢体会,在这儿首先直觉地理解一下,为什么量子计算可以一次做到?
从多伊奇4个函数的定义出发,考虑另一个相关的“二进制和”函数Fi = (fi(0) + fi(1))。我们发现:F0 = 0、F1 = 1、F2 = 1、F3 = 0。也就是说,二进制和函数Fi有这样的规律:对常值函数为0,对平衡函数,和值为1。
多伊奇的问题只是判定函数类型,是常值函数还是平衡函数?这是一种更为整体的性质,并不需要知道是fi中的哪一个。因此我们可以利用量子比特的叠加性,检查二进制和Fi = (fi(0) + fi(1)) 是0还是1?这样就能够1次作出判定,Fi是常值函数还是平衡函数。
图4.9:多伊奇算法
图4.10:实现多伊奇算法的量子电路
图4.9是多伊奇算法的解释,图4.10是实现多伊奇算法的具体量子电路。
实现多伊奇算法的电路,看起来简单,输入输出皆为2。包括一个Oracle函数门、X非门、H门、最后测量。只测量第一个Qubit,第二个不需要测量。
测量后便能1次判定fi的性质(如结果1,是平衡函数;结果0,是常值函数)。
再解释一下Oracle U(Fi)的作用。如果两个量子比特写成|x>|y>, Oracle U(Fi) 设计成这样:第一个Qubit |x>不变,第二个Qubit |y>变成|y+f(x)>。f(x)就是多伊奇定义的那4个函数。所以Oracle门的输出与f(x) 有关。
多伊奇算法的量子电路图中有t0到t4,共5个时间点,初始态|00>,通过X非门,变|01>。然后,|+>|->,再经过Oracle Uf。用相位Oracle的公式,第2个量子比特保持|->不变,测量第1个量子比特,如果结果为0,是常值函数;结果为1,是平衡函数。所以经典计算机要作2次,而用多伊奇算法的量子计算只用1次。
图4.11:多伊奇-乔萨算法
多伊奇-乔萨算法想法是类似的,第一个比特推广到n个量子比特。测量前n 个量子位,如果测得|00 … 0态的话,说明f (x)是常数函数;如果测得的状态不是|00…0态时,说明f(x)是对称函数。
相对于经典算法的2n +1次计算,量子算法只需一次黑盒计算,实现了相对的指数加速。
4.3 秀尔算法-1(经典,数论部分)
最重要的量子算法是秀尔(Short)算法,假如有了可用的量子计算机,我们便可以用它破解RSA加密算法。RSA是保障银行安全常用的加密解密方法,它的基础是因数分解问题。加密过程中将两个互素数p和q相乘得到N = p*q。加密是作一次乘法就完成的简单操作,但是反过来的解码过程则非常困难。
RSA算法的解码过程需要将一个整数N 作“质因数分解” ,得到质数p和q使得N = p*q。对经典计算机,时间复杂度是指数级别。例如,要分解d个十进制数字的整数N,蛮力算法需要遍历所有素数p直到sqrt(N),检查是否p能整除N。分解 d=230的N需要1025次运算。2021年最快的计算机每秒钟1200万亿次(1.2x1015 /s,也得运算2000年左右。
图4.12:秀尔算法和经典算法
然而,秀尔量子算法展示了:在量子计算机上,因数分解问题可以在N的多项式时间内被有效解决,即足够大的量子计算机可以破解RSA,见图4.12。IBM于2001年成功展示秀尔算法实例,使用7个量子比特的量子计算机,将15分解成3×5,之后又分解21=3x7。这两个数字都很小,但却表明了秀尔算法具体实现的可能性。
秀尔的整个算法,分为经典算法和量子算法两部分。经典部分完成可以在多项式时间内能用经典算法完成的计算,而将最困难的“傅里叶变换估算周期”,留给量子算法解决。如果用经典算法来“估算周期”,最好的情况也仍然是以指数增长。最有效的经典因式分解算法,称为通用数域筛选法,可实现d1/3(N=10d)运行时间指数。
概括秀尔量子算法:1,经典,因式分解化为周期查找问题;2,量子,傅里叶变换估算周期。首先介绍经典部分:将分解因子化为周期查找问题?这个“周期”是怎么回事呢?
20 世纪 70 年代,数学家们就知道,如果可以找到一个模指数函数的周期,那么因式分解大数N就会变得容易。模函数k(mod N)表示的是k除N ,即k/N,的余数。例如,如下恒等式a ≡b(mod N) 的意思是说,整数a和b被N除的余数相同。
我们用如下几个实例来加深对模函数以及“模指数函数的周期”的理解。
例1:假设N=15和k=1,1(mod 15)=1,因为1/15余数是1。进一步,将k代入其它正整数:2(mod 15)=2、 3(mod 15)=3、……。当k=15的时候,15(mod 15)=0;而当k=16的时候,16(mod 15)=1,再回到了模函数值为1的情况。显而易见,除15余数为1的不止1和16,还有很多:1、16、31、46、61……。也就是说,模函数k(mod 15),对整数k一直写下去的话,一定的周期后(15),数值会循环,写出的序列是一个周期为15的周期函数:1,2,3,……,0,1,2,3,……。
不过这不是我们感兴趣的周期函数,我们感兴趣的是另外一种,叫做“指数” 模周期函数。
例2:仍然以N=15为例,但这次不用正整数序列,而用某一个整数的“指数”序列来模N,比如,用2的“幂指数”形成的序列:1,2,4,8,16,32,64,128,256 …
也就是序列:20,21,22,23,24,25,26,27,28 … (1)
用2的“幂指数” 序列(1)模15之后,得到另一个序列:
1,2,4,8,1,2,4,8,1 … (2)
可以看出,这个序列 (2) 的周期是4,我们将其称为 “指数a=2” 的模周期,用r表示。在这个例子中,N=15,a=2时,模周期r=4。除了2的“幂指数“序列外,也可以用其它整数a的幂指数序列,如以下例3所示。
例3:例如给定a=7, 然后,给定幂指数序列:1,7,72,73,74,75 …,用这个序列模 15之后,得到的序列是:
1,7,4,13,1,7……
这个序列的周期r正好也为4。
例4:对2的“幂指数”序列模 21后得到:1,2,4,8,16,11,1,2,4 …,周期r是6。
数论学家们发现这种“指数” 模周期r,对整数N的素因子分解大有用处!一旦得到了周期r,并且r是个偶数的话,N就可以被分解成两个素数的乘积,为什么呢?
周期r被定义为满足ar ≡ 1(mod N)的最小正整数,另外我们又有1 ≡ 1(mod N)。将上面两个式子相减可得:
(ar -1) ≡ 0(mod N)。 (3)
此外,如果r是偶数,(ar -1) 可以因式分解为两个因子的乘积:
(ar -1) = (ar/2 +1) (ar/2 -1)。 (4)
图4.13:秀尔算法中经典部分
图4.13总结了秀尔算法中经典部分的算法。根据公式(3),(ar -1) 是N的倍数,然而,因为周期r是满足条件(3)的最小正整数,再与 (4)结合起来看,说明ar/2-1和 ar/2+1不是N的倍数,但它们的乘积(ar -1)却是N的倍数。
假设N可以分解为两个素数因子p1、p2的乘积,即N=p1p2。上一段分析而得到的结论只在下面条件下才能成立:,p1 、p2分别是ar/2-1、 ar/2+1的素因子。 因此,我们可以通过计算最大公约数: gcd(N, ar/2-1) 及gcd(N, ar/2+1),来找到p1和p2 ,也就是将N分解。
可以用上面的例4进行具体计算来说明这个过程。例4中,N=21,a=2,r=6,周期r是满足ar ≡ 1(mod N)的最小正整数,即26 ≡ 1(mod 21)。因为r=6=3x2,是偶数。
可写成82 ≡ 1(mod 21),此外我们又有:12 ≡ 1(mod 21);两式相减得:(82-12) ≡ 0 (mod 21)
或者:(8+1) x (8-1) ≡ 0 (mod 21)。然后我们计算最大公约数:
GCD(21, 9)=3,GCD(21, 7)=7,所以,N(=21)可因式分解为:21=3x7。
这个例子可以推广到一般情况,因此,只要找到了指数模周期r,便能将N分解成质因数p1、p2的乘积。然而如何寻找指数模周期r呢?这就要借助于量子算法来加速计算。
图4.14:秀尔算法总体流程图
4.4 秀尔算法-2(量子部分)
(待续)
参考文献:
【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
相关视频:
(待续)
Contents
**** 1. 前言 ****
**** 2. 历史 ****
**** 3. 基础 ****
3.1 叠加态
3.2 量子比特
3.3 量子门
3.4 量子电路
**** 4. 算法 ****
4.1 Grover 量子搜索算法
4.2 多伊奇算法
4.3 秀尔算法-1(经典,数论部分)
4.4 秀尔算法-2(量子部分)
**** 5. 实现 ****
**********************************************************
作者部分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-1414555.html?mobile=1
收藏