tianrong1945的个人博客分享 http://blog.sciencenet.cn/u/tianrong1945

博文

浅谈量子计算机-4 精选

已有 3608 次阅读 2023-12-20 05:23 |个人分类:系列科普|系统分类:科普集锦

4.2 多伊奇算法

 

上节介绍的Grover搜索算法,并不是第一个量子算法。第一个量子算法是由多伊奇发表的,多伊奇被誉为“量子计算之父”,是一位常人眼中行为奇特的科学家。

 

戴维·多伊奇教授是出生在以色列长在英国的犹太人,表面上,他是英国物理学家,牛津大学教授,量子计算先驱!不过他不教书,实际上是一个没有固定工作的自由学者。他靠着演讲、奖金和出书来赚钱为生,据说是位很少与人来往的牛津隐居者。

 

特别引起公众瞩目的,是多伊奇那两本可以当作科普来读却又与一般科普完全不一样的书:《真实世界的脉络》和《无穷的开始》。书中多伊奇有许多新奇深奥的科学哲学观点,在此我们不详谈,对他的书感兴趣的读者可阅读参考文献78

 

4.7:多伊奇

 

总而言之,多伊奇这位两耳不闻窗外事的古怪科学家,在1985年突然声名大振,因为他发表了一篇里程碑式的论文,文中他展示了Deutsch算法,表明量子计算可以比经典更快。7年后(1992年)发表了对多伊奇算法的推广9。在多伊奇算法启发下的之后两年间,量子算法来到多产期。SimonShor Grover的算法都在这期间相继发表。

 

多伊奇算法没有什么应用,但作为第一个量子算法意义重大,它只适用于一种特殊的情况。因此作一个简要介绍。

 

考虑一个只有一个变量的函数,输入为01,输出也为01。这样的函数共有四个,分别记为f0f1f2f3:函数f0,输入01,输出都是0,即f0(0) =0f0(1) =0。函数f1,输出与输入相等,即f1(0) =0f1(1) =1。函数f2,输出与输入相反,即f2(0) =1f2(1) =0。函数f3,输入01,输出都是1,即f3(0) =1f3(1) =1,见图4.7下图。

 

4.8:多伊奇函数

 

我们将函数f0f3称为常值函数,即对于两个输入,输出都是相同的值的函数。如果一个函数一半的输出是0,另一半的输出是1,那么就称这个函数为平衡函数。例如f1f2就是平衡函数(图4.7上图)。

 

Deutsch提出的问题是:随机给定这四个函数中的一个,我们需要查询多少次,才能确定这个函数是常值函数还是平衡函数?就是说我们不关心给定函数是四个函数中的哪一个,只问它是常值函数还是平衡函数。

 

首先想想经典计算需要多少次?经典计算机一次只能有一个输入,也只能计算并输出一个函数值。但是,为了回答多伊奇问题,我们必须把01都代入函数,所以一定需要做两次经典操作。那么,如果使用量子计算机呢?量子计算机优于经典计算之处,是因为量子比特是叠加态,它可以同时储存10两个数。那么,就有可能操纵量子比特,同时对01进行计算,因此便有可能一次得出答案。实际上也可以做到,这正是多伊奇算法所展示的。

 

具体可用IBM模拟实例慢慢体会,在这儿首先直觉地理解一下,为什么量子计算可以一次做到?

 

从多伊奇4个函数的定义出发,考虑另一个相关的“二进制和”函数Fi = (fi(0) + fi(1))。我们发现:F0 = 0F1 = 1F2 = 1F3 = 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) 有关。

 

多伊奇算法的量子电路图中有t0t4,共5个时间点,初始态|00>,通过X非门,变|01>。然后,|+>|->,再经过Oracle Uf。用相位Oracle的公式,第2个量子比特保持|->不变,测量第1个量子比特,如果结果为0,是常值函数;结果为1,是平衡函数。所以经典计算机要作2次,而用多伊奇算法的量子计算只用1次。

 

4.11:多伊奇-乔萨算法

 

多伊奇-乔萨算法想法是类似的,第一个比特推广到n个量子比特。测量前n 个量子位,如果测得|00 0态的话,说明f (x)是常数函数;如果测得的状态不是|000态时,说明f(x)是对称函数。 

 

相对于经典算法的2n +1次计算,量子算法只需一次黑盒计算,实现了相对的指数加速。

 

4.3 秀尔算法-1(经典,数论部分)

 

最重要的量子算法是秀尔(Short)算法,假如有了可用的量子计算机,我们便可以用它破解RSA加密算法。RSA是保障银行安全常用的加密解密方法,它的基础是因数分解问题。加密过程中将两个互素数pq相乘得到N = p*q。加密是作一次乘法就完成的简单操作,但是反过来的解码过程则非常困难。

 

RSA算法的解码过程需要将一个整数N 作“质因数分解” ,得到质数pq使得N = p*q。对经典计算机,时间复杂度是指数级别。例如,要分解d个十进制数字的整数N,蛮力算法需要遍历所有素数p直到sqrt(N),检查是否p能整除N。分解 d=230N需要1025次运算。2021年最快的计算机每秒钟1200万亿次(1.2x1015 /s,也得运算2000年左右。

 

4.12:秀尔算法和经典算法

 

然而,秀尔量子算法展示了:在量子计算机上,因数分解问题可以在N的多项式时间内被有效解决,即足够大的量子计算机可以破解RSA,见图4.12IBM2001年成功展示秀尔算法实例,使用7个量子比特的量子计算机,将15分解成3×5,之后又分解21=3x7。这两个数字都很小,但却表明了秀尔算法具体实现的可能性。

 

秀尔的整个算法,分为经典算法和量子算法两部分。经典部分完成可以在多项式时间内能用经典算法完成的计算,而将最困难的“傅里叶变换估算周期”,留给量子算法解决。如果用经典算法来“估算周期”,最好的情况也仍然是以指数增长。最有效的经典因式分解算法,称为通用数域筛选法,可实现d1/3N=10d)运行时间指数。

 

概括秀尔量子算法:1,经典,因式分解化为周期查找问题;2,量子,傅里叶变换估算周期。首先介绍经典部分:将分解因子化为周期查找问题?这个“周期”是怎么回事呢?

 

20 世纪 70 年代,数学家们就知道,如果可以找到一个模指数函数的周期,那么因式分解大数N就会变得容易。模函数k(mod N)表示的是kN ,即k/N,的余数。例如,如下恒等式a b(mod N) 的意思是说,整数abN除的余数相同。

 

我们用如下几个实例来加深对模函数以及“模指数函数的周期”的理解。

 

1:假设N=15k=11(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的不止116,还有很多:116314661……。也就是说,模函数k(mod 15),对整数k一直写下去的话,一定的周期后(15),数值会循环,写出的序列是一个周期为15的周期函数:123,……,0123,……。

 

不过这不是我们感兴趣的周期函数,我们感兴趣的是另外一种,叫做“指数” 模周期函数。

 

2:仍然以N=15为例,但这次不用正整数序列,而用某一个整数的“指数”序列来模N,比如,用2的“幂指数”形成的序列:1248163264128256

也就是序列:202122232425262728        1

2的“幂指数” 序列(1)模15之后,得到另一个序列:

124812481                     2

 

可以看出,这个序列 (2) 的周期是4,我们将其称为 “指数a=2 的模周期,用r表示。在这个例子中,N=15a=2时,模周期r=4。除了2的“幂指数“序列外,也可以用其它整数a的幂指数序列,如以下例3所示。

 

3:例如给定a=7 然后,给定幂指数序列:1772737475 …,用这个序列模 15之后,得到的序列是:

1741317……

这个序列的周期r正好也为4

 

4:对2的“幂指数”序列模 21后得到:12481611124 …,周期r6

 

数论学家们发现这种“指数” 模周期r,对整数N的素因子分解大有用处!一旦得到了周期r,并且r是个偶数的话,N就可以被分解成两个素数的乘积,为什么呢?

 

周期r被定义为满足a1(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可以分解为两个素数因子p1p2的乘积,即N=p1p2。上一段分析而得到的结论只在下面条件下才能成立:,p1 p2分别是ar/2-1 ar/2+1的素因子。 因此,我们可以通过计算最大公约数: gcd(N, ar/2-1) gcd(N, ar/2+1),来找到p1p2 ,也就是将N分解。

 

可以用上面的例4进行具体计算来说明这个过程。例4中,N=21a=2r=6,周期r是满足a1(mod N)的最小正整数,即21(mod 21)。因为r=6=3x2,是偶数。

可写成81(mod 21),此外我们又有:11(mod 21);两式相减得:(82-12)  0 (mod 21)

或者:(8+1) x (8-1)  0 (mod 21)。然后我们计算最大公约数:

GCD(21, 9)=3GCD(21, 7)=7,所以,N=21)可因式分解为:21=3x7

 

这个例子可以推广到一般情况,因此,只要找到了指数模周期r,便能将N分解成质因数p1p2的乘积。然而如何寻找指数模周期r呢?这就要借助于量子算法来加速计算。

 

4.14:秀尔算法总体流程图

 

4.4 秀尔算法-2(量子部分)

 (待续)

参考文献:

 

1Keynote talk, 1st conference on Physics and Computation, MIT, 1981(International Journal of Theoretical Physics, 21: 467488, 1982)

2Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein; 殷建平等译. 1 算法在计算机中的作用. 算法导论 原书第3. 北京: 机械工业出版社. 20131

3】张天蓉. 世纪幽灵-走近量子纠缠(第二版)[M].合肥:中国科技大学出版社,20205月。

4Bloch Spherewikipedia),https://en.wikipedia.org/wiki/Bloch_sphere

5IBM Quantum (2022). estimator primitive (Version x.y.z) [computer software]. https://quantum-computing.ibm.com/

6Grover 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

9David Deutsch & Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A. 439 (1907): 553–558.

10Shor’s algorithm from IBM

https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm

相关视频:

        封面  28.jpg

(待续)

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://m.sciencenet.cn/blog-677221-1414555.html

上一篇:浅谈量子计算机-3
下一篇:浅谈量子计算机-5

5 郑永军 张林 鲍海飞 康建 王成玉

该博文允许注册用户评论 请点击登录 评论 (10 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-4-17 00:38

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部