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

Optimization for Shor’s Integer Factorization Algorithm Circuit

作　　者：刘建美 王洪 马智 LIU Jian-mei;WANG Hong;MA Zhi(State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450001,China;Henan Key Laboratory of Network Cryptography Technology,Zhengzhou 450001,China)

机构地区：[1]数学工程与先进计算国家重点实验室,郑州450001 [2]河南省网络密码技术重点实验室,郑州450001

出　　处：《计算机科学》2022年第S01期649-653,共5页Computer Science

基　　金：国家自然科学基金(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)个量子比特。在增加少量近似误差(误差可以随着填充数目的增加呈指数减小)的前提下,实现了时间空间资源代价的折衷。With the help of techniques such as windowed arithmetic and the coset representation of modular integers,the overall optimization and resource estimation for the quantum circuit of Shor’s algorithm has been shown.What’s more,the simulation experiment of the designed quantum circuit has been carried out.The Toffoli gate and the depth of the overall circuit can be reduced by techniques such as windowed arithmetic and the coset representation of modular integers.The Toffoli count is 0.18n^(3)+0.000465n^(3)log n and the measurement depth is 0.3n^(3)+0.000465n^(3)log n.Due to the windowed semiclassical Fourier transform,the space usage includes 3n+O(log n)logical qubits.A tradeoff for resources consume between the time and the space has been made at the cost of adding some approximation errors.

关 键 词：整数分解 量子算法 量子线路 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]