本源量子

本源国内首次完整开发Shor算法自主知识产权应用程序

发布时间:2019-06-10 09:08:52

大数据时代的到来,使网络信息加密成为人们关注的焦点。目前,互联网上大部分的信息加密,都由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密码》系列教程已登录本源教育云、网易云课堂、腾讯课堂、哔哩哔哩,扫描下方二维码,获取最新视频教程!