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

作     者：张兴兰 张丰 陈菲 郭艳琨 ZHANG Xinglan;ZHANG Feng;CHEN Fei;GUO Yankun

作者机构：北京工业大学信息学部北京100124 可信计算北京市重点实验室北京100124 

基　　金：北京市自然科学基金资助项目(4212015) 

出 版 物：《北京工业大学学报》 (Journal of Beijing University of Technology)

年 卷 期：2023年第49卷第6期

页      码：675-683页

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

主 题 词：整数分解 量子计算 Shor算法 启发式算法 傅里叶基 QISKit 

学科分类：08[工学] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.11936/bjutxb2022100007

馆 藏 号：203122261...