本源国内首次完整开发Shor算法自主知识产权应用程序
点击上方蓝色字体，关注我们
本文共2111字 | 预计阅读时长6分钟
大数据时代的到来，使网络信息加密成为人们关注的焦点。目前，互联网上大部分的信息加密，都由RSA算法来完成。只要RSA钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。
随着量子计算理论的发展，研究者们找到了一种有能力把“质因数分解”的时间复杂度降低到多项式级别，使大数分解问题的解决变为可能的理论，这就是Shor算法。它的提出意味着RSA密钥的安全性受到了挑战。
近期，本源量子研究团队利用自主研发的量子软件开发包pyQPanda完整实现了Shor算法，实现了中国量子计算在此领域“零的突破”！
目前，绝大多数宣布实现Shor算法的机构使用的是简化后的量子线路图，其实现不能普适任意的质因数分解。而本源通过pyQPanda完整实现了Shor算法的底层清晰描述，具体的实现过程将会在本源量子教育平台（https://learn-quantum.com/EDU/index.html）新推出的《从零学量子计算破解RSA密码》教程中完整呈现。
Shor算法
Shor算法，以数学家 Peter Shor命名，是一个在1994年发现的，针对整数分解这题目的量子算法。它解决问题如下：给定一个整数N，找出他的质因数。
Shor算法实施过程
Shor算法首先将质因数分解问题转化成了一个子问题（下图量子计算部分）。假设我们待分解的数为N，我们将通过以下步骤来得到N的2个质因数。
使用量子算法帮助寻找周期
Shor算法中最重要的一部分就是计算模指函数的周期，这一步我们需要使用量子计算机来完成。其核心电路设计如下图所示。
该线路首先经过QFT傅里叶变换，然后经过模指电路，再通过一次逆傅里叶变换，来提取该模指函数的周期。
其中，QFT线路可以通过一系列受控R门实现。
模指电路模块，可以分解为常数模乘，常数模乘又可以用常数模加来表示，常数模加又可以用量子加法器来构造。
其电路模型图在整个Shor算法线路上表示如下。
用pyqpanda软件开发包实现Shor算法
我们可以使用本源量子提供的pyqpanda软件开发包，来实现上述的线路设计。下面的代码构造了QFT线路。
逆傅里叶的变换线路，我们可以使用qft(qlist).dagger()来进行构造。常数模指的线路构造如下：
常数模指用到的主要组件是常数模乘，常数模乘的构造线路如下：
常数模乘用到的主要组件为常数模加，常数模加的构造线路如下：
鉴于篇幅有限，我们这里没有列举出所有的子模块，本源量子教育平台新推出的《从零学量子计算破解RSA密码》教程里会对各个模块进行详细地讲解。
案例演示
比如对于分解N=15这个数，我们选择基底为base=7，可以构建如下的主程序来获取15的周期。
在pyQPanda框架下，程序首先对本源量子虚拟机进行初始化（init_quantum_machine），按需申请量子比特（qAlloc）。之后，创建一个量子程序（QProg）并对其依次插入算法所指定的操作（X，H，constModExp和qft），最后运行（directly_run）即可得到算法的结果。
我们对结果进行绘图，可以看到它的周期为4。
根据shor 算法的实施过程，f(4/2)=7^2mod15=4。然后分别计算3和5对于15的最大公因数gcd(3,15)=3,gcd(5,15)=5。检验知3和5都是15的质因数，于是我们得到了问题的答案。
Shor算法总结
Shor算法首先把问题分解为了“经典计算机部分”和“量子计算机部分”。然后利用了量子态的叠加原理，快速取得了函数在一个很大范围内的取值（对于n个工作比特而言，取值范围为0~2^n-1）。
由于函数本身是周期的，所以自变量和函数值自动地纠缠了起来，因此对于某一个函数值来说，工作比特上的态就是一组周期数态的叠加态。在取得“周期数叠加态”之后，我们自然可以通过傅里叶变换得到这组周期数的周期，从而快速解决了这个问题。
本源量子最新上线的《从零学量子计算破解RSA密码》系列教程，将会对以上提到的线路设计进行详细讲解，并带领你用本源量子提供的pyQPanda软件开发包，一步一步实现Shor算法。
目前，《从零学量子计算破解RSA密码》系列教程已登录本源教育云、网易云课堂、腾讯课堂、哔哩哔哩，扫描下方二维码，获取最新视频教程！
下面是本源量子教育系列培训课程具体目录截图
[获取视频资源方式一]
本源量子官网
[获取视频资源方式二]
本源量子网易云课堂
[获取视频资源方式三]
本源量子腾讯视频
[获取视频资源方式四]
本源量子哔哩哔哩视频
欢迎爱学习的朋友加入公号粉丝群
在本源量子公众号主页面回复“加群”
即可获取二维码
据说全球懂得量子计算的人不超过1000人
你还在等什么……
扫码关注本源量子！