经典启发式量子计算整数分解问题

Problem of Classical Heuristic Quantum Computing Integer Factorization

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

Large integer factorization is one of the basic ways to crack RSA encryption algorithm,however,it is difficult for classical computers to solve the large integer factorization problem effectively due to the large amount of computation.Shor's algorithm is a quantum algorithm that can efficiently and rapidly factorize large integers.However,Shor's algorithm requires modular exponentiation,which makes circuit design extremely complex and time complexity high.To solve this problem,a new heuristic algorithm was proposed based on the inspiration of classical computing by using the parallelism of quantum computing.The relevant Oracle was designed to calculate the product of two odd superposition states a and b,and then the negative phase of the superposition state product was added to the Fourier basis of the large integer N.When the result was 0,a prime factor p satisfying pq=N was extracted by using multiple control gates.The proposed algorithm only needed 2n qubits at least,and its time complexity reached exponential acceleration.In addition,the algorithm was implemented on the framework of QISKit,which proves the feasibility and generality of the algorithm.