摘要
大整数分解是破解RSA加密算法的基本途径之一,由于计算量过大,经典计算机难以有效解决大整数分解问题.量子叠加和纠缠的特性,使得量子计算可以对经典问题求解起到并行加速的作用. Shor算法是一个能够高效快速对大整数分解的量子算法.然而,Shor算法需要进行模幂运算,使得电路设计极其复杂,时间复杂度也高.为了解决该问题,基于经典计算的启发,提出一种启发式算法:利用量子计算的并行性,设计相关Oracle去计算2个奇数叠加态a和b的乘积,再将叠加态乘积的负相位加在大整数N的傅里叶基上,当结果为0时,利用多控制门便能够将满足pq=N的一个质因子p给提取出来.该文提出的算法最低仅需要2n个量子比特,时间复杂度也达到指数级加速.另外,该文在QISKit框架上实现了该算法,证明了算法的可行性和通用性.
- 单位