Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (6A): 649-653.doi: 10.11896/jsjkx.210600149

• Interdiscipline & Application • Previous Articles     Next Articles

Optimization for Shor's Integer Factorization Algorithm Circuit

LIU Jian-mei, WANG Hong, MA Zhi   

  1. 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).

PDF (PC)

725

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.18n3+0.000 465n3log n and the measurement depth is 0.3n3+0.000 465n3log 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

CLC Number: 

  • TP301
[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.
[1] Renata WONG. Application of Early Quantum Algorithms in Quantum Communication,Error Correction and Other Fields [J]. Computer Science, 2022, 49(6A): 645-648.
[2] SONG Hui-chao, LIU Xiao-nan, WANG Hong, YIN Mei-juan, JIANG Duo. Integer Decomposition Based on Grover Search Algorithm [J]. Computer Science, 2021, 48(4): 20-25.
[3] WANG Ya-hui and YAN Song-yuan. New Quantum Algorithm for Breaking RSA [J]. Computer Science, 2016, 43(4): 24-27.
[4] DONG Qing WU Nan （State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210093 ,China）. [J]. Computer Science, 2008, 35(8): 17-20.
[5] . [J]. Computer Science, 2007, 34(5): 79-80.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.