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