Shor整数分解算法的线路优化

作     者：刘建美 王洪 马智 LIU Jian-mei;WANG Hong;MA Zhi

作者机构：数学工程与先进计算国家重点实验室郑州450001 河南省网络密码技术重点实验室郑州450001 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2022年第49卷第S01期

页      面：649-653页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金(61972413,61701539,61901525) 国家密码发展基金(mmjj20180107,mmjj20180212)。 

主　　题：整数分解 量子算法 量子线路 

摘      要：借助加窗技术和模整数的陪集表示技术,在加法的近似编码表示基础上给出Shor算法量子线路的整体优化和资源估计,并对设计的量子线路进行了仿真实验。借助加窗技术和模整数的陪集表示技术可以有效减少Toffoli门的数目以及降低整个量子线路的深度,其中Toffoli门数目为0.18n^(3)+0.000465n^(3)log n,线路深度为0.3n^(3)+0.000465n^(3)log n。由于采用加窗的半经典傅里叶变换,使得空间资源代价为3n+O(log n)个量子比特。在增加少量近似误差(误差可以随着填充数目的增加呈指数减小)的前提下,实现了时间空间资源代价的折衷。