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

doi:10.11896/jsjkx.210600149

计算机科学 ›› 2022, Vol. 49 ›› Issue (6A): 649-653.doi: 10.11896/jsjkx.210600149

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

刘建美, 王洪, 马智

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

出版日期:2022-06-10 发布日期:2022-06-08
通讯作者: 王洪(redwang@meac-skl.cn)
作者简介:(modumingdi@foxmail.com)
基金资助:
国家自然科学基金(61972413,61701539,61901525);国家密码发展基金(mmjj20180107,mmjj20180212)

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

Online:2022-06-10 Published:2022-06-08
About author:LIU Jian-mei,born in 1988,doctoral candidate.His main research interests include quantum computation and quantum information.
WANG Hong,born in 1985,Ph.D,professor,is a member of China Computer Federation.His main research interests include quantum computation and quantum information.
Supported by:
National Natural Science Foundation of China(61972413,61701539,61901525) and National Cryptography Development Fund(mmjj20180107,mmjj20180212).

摘要/Abstract

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

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

Abstract: 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³+0.000 465n³log n and the measurement depth is 0.3n³+0.000 465n³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.

Key words: Integer factorization, Quantum algorithm, Quantum circuits

中图分类号:

TP301

刘建美, 王洪, 马智. Shor整数分解算法的线路优化[J]. 计算机科学, 2022, 49(6A): 649-653. https://doi.org/10.11896/jsjkx.210600149

LIU Jian-mei, WANG Hong, MA Zhi. Optimization for Shor's Integer Factorization Algorithm Circuit[J]. Computer Science, 2022, 49(6A): 649-653. https://doi.org/10.11896/jsjkx.210600149

参考文献

[1] SHOR P.Algorithms for quantum computation:discrete loga-rithms and factoring[C]//Proceeding from the 35th Annual Symposium on Foundations of Computer Science.Santa Fe,NM,IEEE Computer Society Press,1994:124-134.
[2] BARENCO A,BENNETT C H,CLEVE R,et al.Elementary gates for quantum computation[J].Physical Review A,1995,52(5):3457.
[3] GRIFFITHS R B,NIU C S.Semiclassical Fourier transform for quantum computation[J].Physical Review Letters,1996,76(17):3228.
[4] FU X Q,BAO W S.Research on the quantum algorithm withhigh probability[D].Zhengzhou:PLA Information Engineering University,2011.
[5] ZALKA C.Shor's algorithm with fewer(pure) qubits[J].ar-Xiv:quantph/0601097,2006.
[6] BEAUREGARD S.Circuit for Shor's algorithm using 2n+3 qubits[J].Quantum Information & Computation,2003(2):175-185.
[7] HÄNER T,ROETTELER M,SVORE K M.Factoring using2n＋2 qubits with Toffoli based modular multiplication[J].ar-Xiv:1611.07995,2016.
[8] EKERÅ M,HÅSTAD J.Quantum algorithms for computingshort discrete logarithms and factoring RSA integers[C]//Post Quantum Cryptography(PQCrypto 2017).LNCS,Cham:Sprin-ger,2017:347-363.
[9] GIDNEY C.Halving the cost of quantum addition[J].arXiv:1709.06648,2018.
[10] CUCCARO S A,DRAPER T G,KUTIN S A,et al.A newquantum ripple-carry addition circuit[J].arXiv:ph/0410184,2004.
[11] BABBUSH R,GIDNEY C,BERRY D W,et al.Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity[J].arXiv:1805.03662,2018.
[12] GIDNEY C.Approximate encoded permutations and piecewise quantum adders[J].arXiv:1905.08488,2019.
[13] GIDNEY C.Windowed quantum arithmetic[J].arXiv:1905.07682,2019.
[14] KENJI K,YUKIO T.Speeding up elliptic crypto-systems using a signed binary window method[C]//Proceeding of the 12th Annual International Cryptology Conference on Advances in Cryptology.Berlin:Springer-Verlag,1993:345-357.
[15] GIDNEY C,EKERÅ M.How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits[J].arXiv:ph/1905.09749,2019.
[16] GIDNEY C.Asymptotically efficient quantum karatsuba multiplication[J].arXiv:1904.07356,2019.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

Optimization for Shor's Integer Factorization Algorithm Circuit

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

Metrics

本文评价

推荐阅读 0

[1]	Renata WONG. 早期量子算法在量子通信、量子纠错等领域的应用 Application of Early Quantum Algorithms in Quantum Communication,Error Correction and Other Fields 计算机科学, 2022, 49(6A): 645-648. https://doi.org/10.11896/jsjkx.210400214
[2]	宋慧超, 刘晓楠, 王洪, 尹美娟, 江舵. 基于Grover搜索算法的整数分解 Integer Decomposition Based on Grover Search Algorithm 计算机科学, 2021, 48(4): 20-25. https://doi.org/10.11896/jsjkx.200800117
[3]	王亚辉,颜松远. 一种新的攻击RSA的量子算法 New Quantum Algorithm for Breaking RSA 计算机科学, 2016, 43(4): 24-27. https://doi.org/10.11896/j.issn.1002-137X.2016.04.004
[4]	董青吴楠. 整数质因子分解算法新进展与传统密码学面临的挑战计算机科学, 2008, 35(8): 17-20.
[5]	. 应用n—adic展开的快速Harn体制计算机科学, 2007, 34(5): 79-80.
[6]	. 一种新的基于大整数分解困难问题的叛逆者追踪方案计算机科学, 2006, 33(7): 131-133.
[7]	吕欣冯登国. 密码体制的量子算法分析计算机科学, 2005, 32(2): 166-168.
[8]	宋辉戴葵王志英. 量子算法模拟系统研究现状计算机科学, 2000, 27(9): 1-3.