首页
社区
课程
招聘
[原创]量子算法分析: 深入算法内核掌握量子计算的精髓
发表于: 2023-6-7 15:16 22409

[原创]量子算法分析: 深入算法内核掌握量子计算的精髓

gjden 活跃值
14
2023-6-7 15:16
22409


好长时间没有来看雪发文了,近期也没什么可写的,把以前不务正业写的文章重新整理下(换个题目并调整了部分内容)发到这里冒个泡。废话几句,量子计算往往容易被媒体吹嘘得神乎其神,写这篇目的也是为了能够让更多的人了解量子计算的精髓和灵魂,也是我自己理解量子计算的一个过程,分享出来希望能够给想要试图理解量子计算的小伙伴一点启示。对于量子计算我也好些年没搞了,目前的水平也只能如此了,如有错误,望各位海涵。不知道该发哪个版块,段老大说发软件逆向板块吧,因此扔到这里来共同学习探讨。由于论坛不支持公式编辑,因此文字中的公司只能用类似字母代替,推导的公式也只能截图,如果阅读时对应不上,可以留言。



很多人对于量子计算或多或少都有所了解,但目前量子计算圈和安全圈存在着巨大的鸿沟,关于量子计算报道大多喜欢夸大其词,让人感觉量子计算像玄学一样,徒增神秘感,并不利于量子计算思想的普及。很多人虽然对量子计算做了很深入了解,但大多事后仍旧疑惑不解:为什么量子叠加态还能参与计算?量子计算机又是怎样实现并行运算的?量子计算机又是如何解决特定问题的?


本文就从量子计算最为重要的算法—Shor算法开始做详细探讨,看他是如何破解RSA的? 为了更通俗易懂,本文涉及的公式推导都尽量详细,力求高中水平的数学基础能看懂。你既不需要懂密码学,也不需要懂量子力学也能明白算法的精髓。


本文将详细分析Shor算法的实现过程,整数周期数及非整数周期数下Shor算法分析,Shor算法概率评估,实例分析。不得不说,量子计算以及量子计算机是一个很庞大的知识体系,个人水平有限,此处我们仅仅就单纯地围绕Shor算法本身进行探讨分析,不考虑退相干对算法的影响,也不考虑物理实现。


废话不多说,先回答几个让人疑惑的问题。



一个量子可以同时处于两种状态的叠加(比如自旋向上和自旋向下),这种叠加态测量的瞬间就会随机变为一个确定的态(测量得到自旋向上),这个过程叫波函数的坍塌。我们如果将这两个态表示为0,1,而每种态观测后出现的概率幅(注意不是概率,概率幅的平方为概率为1)为α,β,那么这个量子可以表示为






这里右尖括号为狄拉克符号,表示量子态, 0,1为基态,+表示叠加,两种态的概率幅平方和为1,即 α^2+β^2=1 。而我们通常说的量子计算就是通过量子逻辑门来操作处于叠加态的量子。比如Hadamard门,简称H门(在量子计算中非常重要),他的一个主要功能就是通过计算基态产生等概率的叠加态。通过H门变换后的单量子叠加态为:


 


两种基态的坍塌概率都为1/2 ,两个量子的H门得到的结果如下:



每个态坍塌的概率 1/4 ,对于n个量子的H门变换后:



其他量子门这里就不做介绍了,本文暂时不会涉及,想更深入了解可以到维基上看。


https://en.wikipedia.org/wiki/Quantum_logic_gate


量子门及其对应的门矩阵如下图:

量子门及门矩阵,图片来自wikipedia


还有一个比较重要的复合门是受控U(a,x)门,想深入了解的看这篇文章:一只冰牙喵:4.2 受控操作不过这里看不懂也没关系,我们只需要知道受控U门可以用于计算以a为基底的幂,其一般用于生成指数函数值。


受控U门(来自https://zhuanlan.zhihu.com/p/422428222




量子并行运算(Quantum Parallelism)是基于量子叠加态(Quantum Superposition)和幺正变换实现的。量子计算正是有了数据的可叠加性和幺正变换,从而决定了一次操作即可改变全部数据。比如有量子寄存器,存了10个处于叠加态的量子,在通过运算时只需要一次性操作这10个量子,但是由于可叠加性,这10个量子叠加态可以表示2^10个基矢,一次操作10个量子,相当于一次对2^10个基矢进行了操作,这就大大提高了运算的速度。


在经典计算中,并行性的核心思想是将一个计算任务分配给多个处理器同时运行,要快于使用一个处理器来运行。在理想的情况下,将工作分配给K 个处理器就应该使计算时间缩短为原来的1/K。但是现实肯定不是这样的,真实的任务往往具有串联性,只有部分具有并联性的子任务才能够做并行运算。由于量子计算的特点是数据的可叠加性质和操作的幺正变换本质,从而就决定了量子计算的语义特征是完全意义上的通过一次操作即可改变全部数据的并行计算。将一个N 位量子寄存器中的 2^N 个数据同时通过一次幺正变换(即进行一次运算)所需的时间定义为 Tq ,而经典计算中对一个数据进行运算的时间为 Tc ,因为一次量子计算就对所有的数据做了并行处理,所以量子计算加速能力可以表示为



如果 Tc=Tq ,那么加速能力 S=2^N,也就是说对量子计算机做一次运算,相当于对经典计算机做 2^N 次运算。


此外,一台量子计算机并不一定在所有计算任务上都比一台经典计算机做得好,比如乘法运算在一台量子计算机上执行就不如传统计算机上快。为了突出量子计算机的优越性,就需要开发量子并行效应能力的算法。



量子计算机是严重依赖于优秀的量子算法的实现,虽然通用量子计算机能做经典计算机的所有事情,但是只有在处理特定问题上量子计算才具有决定性的优势,目前已经有很多优秀的量子算法,其中对大数因子分解,离散对数问题以及更一般的隐含子群问题的解决有着开创性和重大影响的量子算法便是本文要详细分析的Shor算法。


本文将非常详细的分析Shor算法来让各位明白量子计算在解决特定问题上的巨大优势。



在费曼提出量子计算机概念不到15年的时间,shor通过研究出的量子算法给世人了一剂强心针,自从shor算法出来后,人类开始加速了量子计算机的研制,各大头部企业也纷纷加入了量子计算机的量子竞赛行列。


shor算法最令人振奋的是直接将质因子分解以及离散对数问题以指数级速度提升,这给人们的启示是可以利用同样算法思想来解决更为广泛的隐含子群问题。


我们知道RSA是基于经典计算机大数质因式分解的指数复杂度的困难而设计的一种非对称加密算法,目前最优的因子分解算法为指数复杂度

  

而通过shor量子算法可以以多项式复杂度完成大数因式分解,从而可以快速破解RSA算法。那么Shor算法是如何发挥如此威力的,简单来说,Shor算法的核心依赖于三个变换即H变换,U变换,QFT(量子傅立叶),接下来我们一步一步的分析。


Shor算法量子实现线路简图:

Shor算法量子实现线路图




我们设RSA的公钥为 (e,N) ,私钥为 (d,N) ,那么生成公私钥的过程如下:


生成两个足够大的素数p,q,得到合数N=p*q,然后计算得到p-1和q-1的最小公倍数L。

生成e,使得e和L互质,且满足1<e<L

生成d,使得d*e%L=1且1<d<L

那么加密解密操作如下



我们知道RSA是基于大数N的因子分解的困难而设计的非对称加密算法,因此我们只要能够实现大数N的因子分解,就可以破解RSA,这里不做证明了,网上有很多资料。这里你只需要知道,我们可以通过公私钥的N,然后通过Shor算法求得N的因子p,q就可以了。



首先我们需要将大数因子分解问题转化为以求待分解的合数N为模的函数 f(x)=a^x ( mod N) 的周期问题。


设周期函数f(x)=a^x(mod N) 的周期为r(这里a为小于N,且与N互质的整数),则有:f(x)=f(x+r) , 那么:



设整数 

 

则 



那么 x-1, x+1 都能被 kN 整除,那么一定存在 gcd(x+1,N)>1 或者 gcd(x-1,N)>1 (gcd是一个用辗转相除法求公因子的函数),也就说与N存在一个大于1的公约数,这个公约数就是N的分解因子。


例如:设 N=15,a=7 ,则:



由此,我们只要求出f(x)的周期,就能轻而易举的分解合数了。而shor算法的精髓就是利用量子特性来快速求解得到周期r.



设量子比特长度为 L, 则总共可以表示的 q=2^L 个基态, 设N为要分解的合数,为了确保 2^L 长度内有足够的周期数,我们需要满足



然后,我们利用Hadamard门来构造等概率的量子叠加态 |x>存入寄存器reg1,然后利用U门来构造 |f(x)> 的叠加态存入寄存器reg2,且使这两个寄存器处于纠缠态。



两个寄存器展开形式如下:



由于 f(x) 为周期函数,设周期为r,A为总长2^L中存在的周期数,则



设l为小于一个周期内的x的值, x=l+Ar, 则整个系统的态实际为



因此,x可以表示为



然后对reg2进行计算基上的测量,设测量结果设为 Z ,测量Z在reg1中的投影变化为



例如 N=15,a=7 ,测量后的整个系统的态为:



经过投影后



这里,当测量得到一个γ 值后,由于寄存器reg1和寄存器reg2是处于纠缠态,所以Z值测量后寄存器reg1会塌陷为相同Z值的|x>叠加态,如果reg2测量的值为1,那么reg1则处于 (|0>}+|4>}+|8>+...) 的叠加态,那么周期 r 的信息就包含在reg1中,因此对reg1进行量子傅里叶变化:



上式可以变换为:



这里为什么要这么变换,因为当测量Reg2时,Reg2坍塌为了r个值中的一个值,所以每一个值对应reg1中的A个叠加态。这里设:



这里,我们需要考虑两种情况,一种是 2^L 能够整除 r 的情况,也就是在 2^L 内刚好有整数个周期,一种是不能整除的情况。如果能够整除,那说明每个波峰刚好位于 ϒ=k2^L/r ,不能整除时,波峰位于非常接近波峰的两侧,因为波峰处的 ϒ 本应该为非整数,而我们测量得到 ϒ只能是整数,所以这时候我们需要加入微调的参数。接下来我们分别对这两种情况进行分析。


A.整数周期


在(2)式的[ ]中,在 ϒ 是 2^L/r 的整数倍情况下变成,出现相长干涉,求和后为 A=2^L/r ,如果不为整数,则为相消干涉,其值趋于0. 所以



当 γ≠ k2^L/r 时,我们通过等比数列转化得到:



带入(0)式得:


 


由于

 

,也就是说,当γ k2^L/r ,也即不为整数时,为相消干涉,其值为0。


通过量子傅里叶变换后得到如下叠加态:


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

最后于 2023-7-24 17:20 被gjden编辑 ,原因: 图片挂掉
收藏
免费 29
支持
分享
打赏 + 5.00雪花
打赏次数 1 雪花 + 5.00
 
赞赏  orz1ruo   +5.00 2023/06/09 感谢分享~
最新回复 (31)
雪    币: 2536
活跃值: (4368)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
2
学废了
2023-6-7 15:23
0
雪    币: 47147
活跃值: (20310)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
3
太高深了!
2023-6-7 15:24
1
雪    币: 6790
活跃值: (4441)
能力值: (RANK:600 )
在线值:
发帖
回帖
粉丝
4
kanxue [em_63]太高深了!
高手可以略过了,拙文旨在帮助大家更深的理解量子计算和量子算法。
2023-6-7 15:35
0
雪    币: 3244
活跃值: (10891)
能力值: ( LV9,RANK:240 )
在线值:
发帖
回帖
粉丝
5
小学数学我都做了2个小时:边长12cm的正方形,四个角都裁掉边长2cm的正方形,剩余的形状上面,能裁出的最大正方形,面积为多少?
2023-6-7 15:40
0
雪    币: 916
活跃值: (3434)
能力值: ( LV8,RANK:120 )
在线值:
发帖
回帖
粉丝
6
这个太猛了,顶一下
2023-6-7 15:40
0
雪    币: 465
活跃值: (667)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
7
太残暴了,生活的打击比比皆是,都挺过来了,却不曾想,“物理学不存在了”。
如果能再讲解量子计算机的应用场景和未来趋势等进行科普,那就更好了。
2023-6-7 16:01
0
雪    币: 16
活跃值: (5204)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
wsc
8
ssarg 太残暴了,生活的打击比比皆是,都挺过来了,却不曾想,“物理学不存在了”。 如果能再讲解量子计算机的应用场景和未来趋势等进行科普,那就更好了。
三体
2023-6-7 16:47
0
雪    币: 4341
活跃值: (5517)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
看不明白,但我大受震撼。
2023-6-7 17:01
0
雪    币: 2959
活跃值: (4866)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
10
段总推存,来膜拜一下
2023-6-7 17:04
0
雪    币: 2082
活跃值: (2024)
能力值: ( LV2,RANK:15 )
在线值:
发帖
回帖
粉丝
11
努努力,学费了
2023-6-7 17:22
0
雪    币: 11705
活跃值: (975)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
12
很精彩,努力学习中。 

IBM 发布的量子芯片,要放在一个几立方米的冷却箱里面运行(温度接近绝对零度附近, 25 mK ),一次运行能维持450微秒。 

Osprey这样的量子芯片必须部署在冷却到接近绝对零温度的专用腔室中。IBM此次推出了IBM Quantum System 2新版量子芯片腔室,预计将于2023年底上市。
2023-6-7 17:33
2
雪    币: 25107
活跃值: (4627)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
13
如读天书
2023-6-7 17:47
0
雪    币: 429
活跃值: (393)
能力值: ( LV6,RANK:81 )
在线值:
发帖
回帖
粉丝
14
太顶了,像看阿拉伯文,只剩余膜拜
2023-6-7 18:03
0
雪    币: 335
活跃值: (786)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
15
看雪的档次都已经去到量子层面了吗?
2023-6-8 09:15
0
雪    币: 2458
活跃值: (4551)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
16
版主,能请教下你数学的学习路线或者参考书籍之类的么?
2023-6-8 09:17
0
雪    币: 2787
活跃值: (30801)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
17
这是讨论下个时代了吗
2023-6-8 09:24
1
雪    币: 369
活跃值: (2598)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
18
版主太牛了,感谢分享
2023-6-8 12:18
0
雪    币: 6790
活跃值: (4441)
能力值: (RANK:600 )
在线值:
发帖
回帖
粉丝
19
@ssarg
太残暴了,生活的打击比比皆是,都挺过来了,却不曾想,“物理学不存在了”。 如果能再讲解量子计算机的应用场景和未来趋势等进行科普,那就更好了。

物理学还存在,先把智子的纠缠态破坏掉,断了与三体人的联系,就没法干扰物理学研究了。

最后于 2023-6-8 15:01 被gjden编辑 ,原因:
2023-6-8 14:33
0
雪    币: 6790
活跃值: (4441)
能力值: (RANK:600 )
在线值:
发帖
回帖
粉丝
20
小白养的菜鸡 版主,能请教下你数学的学习路线或者参考书籍之类的么?

知乎一位答主的回答比较中肯,摘过来希望对你有帮助:


作为一名数学博士,有一些个人观点赠给您,收好不谢。

我不太知道您的基础是怎样的,以下假定您是高中毕业。

首先我认为您应该先学习一些基础知识,数学分好几个大块,学完基础知识您才能知道自己的兴趣在哪里,进而进入更细致更专业的科研。

以下是我能想到的比较效率的数学自学具体步骤:

  1. 学习高等代数(A),数学分析(B),解析几何(C)。发现对哪一门感兴趣可进入下一环节。

  2. (1)兴趣在A:试着学习抽象代数,进而同调代数,表示论,数论。

    (2)兴趣在B:试着学习常微分方程,数学物理方程,实变函数,泛函分析。

    (3)兴趣在C:试着学习微分几何及流形。

    (4)兴趣在AB:试着学习数值分析,并需要学习计算机语言(如C语言和matlab),学会编程。

    (5)兴趣在AC:试着学习代数几何。

    (6)兴趣在BC及ABC:我不太清楚。

    (7)都不感兴趣:试着学习概率论与数理统计,图论。

上面均属一般本科课程。学完这些再决定继续从事科研还是工作。


如果是自学的话,以我的阅历,大多会选择学习代数方向(也就是A,需要的基础不多,高等代数和抽象代数),脑子好使的话可以学数论,还有图论方向(这个方向几乎不需要任何基础)。


如果你是想学完找个好工作的话可以试着学习计算数学(4)和概率论和统计方向。


更精细化的学习建议报一个导师。希望能帮助到您。


出处 https://www.zhihu.com/question/263812517/answer/274879394

最后于 2023-6-8 15:04 被gjden编辑 ,原因:
2023-6-8 15:00
3
雪    币: 2458
活跃值: (4551)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
21

1

最后于 2023-6-8 16:20 被小白养的菜鸡编辑 ,原因:
2023-6-8 16:19
0
雪    币: 2458
活跃值: (4551)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
22
gjden 小白养的菜鸡 版主,能请教下你数学的学习路线或者参考书籍之类的么? 知乎一位答主的回答比较中肯,摘过来希望对你有帮助:作为一名数学博士,有一些个 ...
收到,非常感谢
2023-6-8 16:19
0
雪    币: 2489
活跃值: (2989)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
23
niubility
2023-6-9 10:55
0
雪    币: 1300
活跃值: (94)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
24
小白养的菜鸡 收到,非常感谢[em_63]
学啥数学啊,太难了。
2023-6-9 12:58
0
雪    币: 1300
活跃值: (94)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
25
gjden @ssarg 太残暴了,生活的打击比比皆是,都挺过来了,却不曾想,“物理学不存在了”。 如果能再讲解量子计算机的应用场景和未来趋势等进行科普,那就更好了。 物理学还存在 ...
版主打智子的主意,小心眼前出倒计时,哈哈
2023-6-9 13:02
0
游客
登录 | 注册 方可回帖
返回
//