How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

Craig Gidney1 and Martin Ekerå2,3

1Google Inc., Santa Barbara, California 93117, USA
2KTH Royal Institute of Technology, SE-100 44 Stockholm, Sweden
3Swedish NCSA, Swedish Armed Forces, SE-107 85 Stockholm, Sweden

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Ekerå-Håstad 2017, Ekerå 2017, Ekerå 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of $10^{-3}$, a surface code cycle time of 1 microsecond, and a reaction time of 10 microseconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Van Meter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses $3 n + 0.002 n \lg n$ logical qubits, $0.3 n^3 + 0.0005 n^3 \lg n$ Toffolis, and $500 n^2 + n^2 \lg n$ measurement depth to factor $n$-bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.

► BibTeX data

► References

[1] G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, Y.-K. Liu, C. Miller, D. Moody, R. Peralta, R. Perlner, A. Robinson, and D. Smith-Tone. Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process. Technical Report NIST Internal Report (NISTIR) 8240, NIST, January 2019. 10.6028/​NIST.IR.8240.

[2] R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven. Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity. Physical Review X, 8 (4): 041015(1–36), 2018. 10.1103/​PhysRevX.8.041015. arXiv:1805.03662.

[3] R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O'Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and J. M. Martinis. Superconducting quantum circuits at the surface code threshold for fault tolerance. Nature, 508: 500–503, April 2014. 10.1038/​nature13171. arXiv:1402.4848.

[4] E. Barker, L. Chen, A. Roginsky, A. Vassilev, and R. Davis. Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. Technical Report NIST Special Publication (SP) 800-56A, Rev. 3, NIST, April 2018. 10.6028/​NIST.SP.800-56Ar3.

[5] E. Barker, L. Chen, A. Roginsky, A. Vassilev, R. Davis, and S. Simon. Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography. Technical Report NIST Special Publication (SP) 800-56B, Rev. 2, NIST, March 2019. 10.6028/​NIST.SP.800-56Br2.

[6] S. Beauregard. Circuit for Shor's algorithm using $2n+3$ qubits. Quantum Information & Computation, 3 (2): 175–185, 2003. 10.26421/​QIC3.2-8. arXiv:quant-ph/​0205095.

[7] D. Beckman, A. N. Chari, S. Devabhaktuni, and J. Preskill. Efficient networks for quantum factoring. Physical Review A, 54 (2): 1034, 1996. 10.1103/​PhysRevA.54.1034. arXiv:quant-ph/​9602016.

[8] D. W. Berry, C. Gidney, M. Motta, J. R. McClean, and R. Babbush. Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization. Quantum, 3: 208, 2019. 10.22331/​q-2019-12-02-208. arXiv:1902.02134.

[9] BlueKrypt. Cryptographic Key Length Recommendation. https:/​/​, 2019. URL https:/​/​ Accessed: 2019-03-03.

[10] A. Bocharov, M. Roetteler, and K. M. Svore. Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits. Physical Review Letters, 114: 080502, Feb 2015. 10.1103/​PhysRevLett.114.080502. arXiv:1404.5320.

[11] F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, and P. Zimmermann. Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment. In Advances in Cryptology – CRYPTO 2020, volume 12171 of Lecture Notes in Computer Science (LNCS), pages 62–91. Springer, 2020. 10.1007/​978-3-030-56880-1_3.

[12] M. Braithwaite. Experimenting with post-quantum cryptography. https:/​/​​2016/​07/​experimenting-with-post-quantum.html, July 2016. URL https:/​/​​2016/​07/​experimenting-with-post-quantum.html.

[13] S. Bravyi and A. Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71 (2): 022316, 2005. 10.1103/​PhysRevA.71.022316. arXiv:quant-ph/​0403025.

[14] J. P. Buhler, H. W. Lenstra Jr., and C. Pomerance. Factoring integers with the number field sieve. In The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics (LNM), pages 50–94. Springer, 1993. 10.1007/​BFb0091539.

[15] E. Campbell, A. Khurana, and A. Montanaro. Applying quantum algorithms to constraint satisfaction problems. Quantum, 3: 167, 2019. 10.22331/​q-2019-07-18-167. arXiv:1810.05582.

[16] R. Cleve and J. Watrous. Fast parallel circuits for the quantum Fourier transform. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 526–536. IEEE, 2000. 10.1109/​SFCS.2000.892140.

[17] D. Copsey, M. Oskin, F. Impens, T. Metodiev, A. Cross, F. T. Chong, I. L. Chuang, and J. Kubiatowicz. Toward a scalable, silicon-based quantum computing architecture. IEEE Journal of Selected Topics in Quantum Electronics, 9 (6): 1552–1569, 2003. 10.1109/​JSTQE.2003.820922.

[18] S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton. A new quantum ripple-carry addition circuit. arXiv preprint quant-ph/​0410184, 2004. URL https:/​/​​abs/​quant-ph/​0410184.

[19] W. Diffie and M. E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22 (6): 644–654, 1976. 10.1109/​TIT.1976.1055638.

[20] T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore. A logarithmic-depth quantum carry-lookahead adder. Quantum Information & Computation, 6 (4–5): 351–369, 2006. 10.26421/​QIC6.4-5-4. arXiv:quant-ph/​0406142.

[21] M. Ekerå. Modifying Shor's algorithm to compute short discrete logarithms. Cryptology ePrint Archive, Report 2016/​1128, 2016. URL https:/​/​​2016/​1128.

[22] M. Ekerå. Revisiting Shor’s quantum algorithm for computing general discrete logarithms. arXiv preprint arXiv:1905.09084, 2019. URL https:/​/​​abs/​1905.09084.

[23] M. Ekerå. On post-processing in the quantum algorithm for computing short discrete logarithms. Designs, Codes and Cryptography, 88 (11): 2313–2335, 2020. 10.1007/​s10623-020-00783-2. iacr:2017/​1122.

[24] M. Ekerå. Quantum algorithms for computing general discrete logarithms and orders with tradeoffs. Journal of Mathematical Cryptology, 15 (1): 359–407, 2021. 10.1515/​jmc-2020-0006. (To appear.) iacr:2018/​797.

[25] M. Ekerå and J. Håstad. Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers. In Post-Quantum Cryptography, volume 10346 of Lecture Notes in Computer Science (LNCS), pages 347–363. Springer, 2017. 10.1007/​978-3-319-59879-6_20.

[26] A. G. Fowler. Time-optimal quantum computation. arXiv preprint arXiv:1210.4626, 2012. URL https:/​/​​abs/​1210.4626.

[27] A. G. Fowler and C. Gidney. Low overhead quantum computation using lattice surgery. arXiv preprint arXiv:1808.06709, 2018. URL https:/​/​​abs/​1808.06709.

[28] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86 (3): 032324, 2012. 10.1103/​PhysRevA.86.032324. arXiv:1208.0928.

[29] A. G. Fowler, S. J. Devitt, and C. Jones. Surface code implementation of block code state distillation. Scientific Reports, 3: 1939, 2013. 10.1038/​srep01939. arXiv:1301.7107.

[30] V. Gheorghiu and M. Mosca. Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes. arXiv preprint arXiv:1902.02332, 2019. URL https:/​/​​abs/​1902.02332.

[31] C. Gidney. Factoring with $n+2$ clean qubits and $n-1$ dirty qubits. arXiv preprint arXiv:1706.07884, 2017. URL https:/​/​​abs/​1706.07884.

[32] C. Gidney. Halving the cost of quantum addition. Quantum, 2: 74, 2018. 10.22331/​q-2018-06-18-74. arXiv:1709.06648.

[33] C. Gidney. Approximate encoded permutations and piecewise quantum adders. arXiv preprint arXiv:1905.08488, 2019a. URL https:/​/​​abs/​1905.08488.

[34] C. Gidney. Asymptotically Efficient Quantum Karatsuba Multiplication. arXiv preprint arXiv:1904.07356, 2019b. URL https:/​/​​abs/​1904.07356.

[35] C. Gidney. Windowed quantum arithmetic. arXiv preprint arXiv:1905.07682, 2019c. URL https:/​/​​abs/​1905.07682.

[36] C. Gidney and A. G. Fowler. Efficient magic state factories with a catalyzed $|\text{CCZ}\rangle$ to $2|\text{T}\rangle$ transformation. Quantum, 3: 135, 2019a. 10.22331/​q-2019-04-30-135. arXiv:1812.01238.

[37] C. Gidney and A. G. Fowler. Flexible layout of surface code computations using AutoCCZ states. arXiv preprint arXiv:1905.08916, 2019b. URL https:/​/​​abs/​1905.08916.

[38] D. Gillmor. RFC 7919: Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS), August 2016. 10.17487/​RFC7919.

[39] D. M. Gordon. Discrete logarithms in GF($p$) using the Number Field Sieve. SIAM Journal on Discrete Mathematics, 6 (1): 124–138, 1993. 10.1137/​0406010.

[40] R. B. Griffiths and C.-S. Niu. Semiclassical Fourier Transform for Quantum Computation. Physical Review Letters, 76 (17): 3228–3231, April 1996. 10.1103/​PhysRevLett.76.3228. arXiv:quant-ph/​9511007.

[41] J. Haah and M. B. Hastings. Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates. Quantum, 2: 71, 2018. 10.22331/​q-2018-06-07-71. arXiv:1709.02832.

[42] T. Häner, M. Roetteler, and K. M. Svore. Factoring using $2n+2$ qubits with Toffoli based modular multiplication. Quantum Information & Computation, 17 (7–8): 673–684, 2017. 10.26421/​QIC17.7-8-7. arXiv:1611.07995.

[43] M. B. Hastings and A. Geller. Reduced Space-Time and Time Costs Using Dislocation Codes and Arbitrary Ancillas. Quantum Information & Computation, 15 (11–12): 962–986, 2015. 10.26421/​QIC15.11-12-6. arXiv:1408.3379.

[44] C. Horsman, A. G. Fowler, S. Devitt, and R. Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14 (12): 123011, 2012. 10.1088/​1367-2630/​14/​12/​123011. arXiv:1111.4022.

[45] L. Jiang, J. M. Taylor, A. S. Sørensen, and M. D. Lukin. Scalable quantum networks based on few-qubit registers. International Journal of Quantum Information, 8 (01n02): 93–104, 2010. 10.1142/​S0219749910006058.

[46] N. C. Jones, R. Van Meter, A. G. Fowler, P. L. McMahon, J. Kim, T. D. Ladd, and Y. Yamamoto. Layered Architecture for Quantum Computing. Physical Review X, 2 (3): 031007, 2012. 10.1103/​PhysRevX.2.031007. arXiv:1010.5022.

[47] A. A. Karatsuba and Y. P. Ofman. Multiplication of many-digital numbers by automatic computers. Doklady Akademii Nauk SSSR, 145 (2): 293–294, 1962. URL http:/​/​​eng/​dan/​v145/​i2/​p293.

[48] Y. Kim, R. Daly, J. Kim, C. Fallin, J. H. Lee, D. Lee, C. Wilkerson, K. Lai, and O. Mutlu. Flipping bits in memory without accessing them: An experimental study of DRAM disturbance errors. In 2014 ACM/​IEEE 41st International Symposium on Computer Architecture (ISCA), pages 361–372. IEEE, 2014. 10.1109/​ISCA.2014.6853210.

[49] T. Kivinen and M. Kojo. RFC 3526: More Modular Exponentiation (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE), May 2003. 10.17487/​RFC3526.

[50] T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé, J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery, D. A. Osvik, t. R. Herman, A. Timofeev, and P. Zimmermann. Factorization of a 768-Bit RSA Modulus. In Advances in Cryptology – CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science (LNCS), pages 333–350. Springer, 2010. 10.1007/​978-3-642-14623-7_18.

[51] S. A. Kutin. Shor's algorithm on a nearest-neighbor machine. arXiv preprint quant-ph/​0609001, 2006. URL https:/​/​​abs/​quant-ph/​0609001.

[52] A. K. Lenstra. Key Lengths. In The Handbook of Information Security, chapter 6. 2004. URL https:/​/​​record/​164539/​files/​NPDF-32.pdf.

[53] A. K. Lenstra and H. W. Lenstra Jr., editors. The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics (LNM). Springer, 1993. 10.1007/​BFb0091534.

[54] A. K. Lenstra and E. R. Verheul. Selecting Cryptographic Key Sizes. Journal of Cryptology, 14: 225–293, 2001. 10.1007/​s00145-001-0009-4.

[55] A. K. Lenstra, H. W. Lenstra Jr., M. S. Manasse, and J. M. Pollard. The number field sieve. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pages 564–572. ACM, 1990. 10.1145/​100216.100295.

[56] D. Litinski. Magic State Distillation: Not as Costly as You Think. Quantum, 3: 205, 2019. 10.22331/​q-2019-12-02-205. arXiv:1905.06903.

[57] M. Mosca. Cybersecurity in an Era with Quantum Computers: Will We Be Ready? IEEE Security & Privacy, 16 (5): 38–41, 2018. 10.1109/​MSP.2018.3761723. iacr:2015/​1075.

[58] M. Mosca and A. Ekert. The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. In Quantum Computing and Quantum Communications, volume 1509 of Lecture Notes in Computer Science (LNCS), pages 174–188. Springer, 1999. 10.1007/​3-540-49208-9_15.

[59] NIST. Digital Signature Standard (DSS). Technical Report Federal Information Processing Standards Publications (FIPS PUBS) 186-4, July 2013. 10.6028/​NIST.FIPS.186-4.

[60] NIST and CCCS. Implementation Guidance for FIPS 140-2 and the Cryptographic Module Validation Program. Technical report, May 2019. URL https:/​/​​csrc/​media/​projects/​cryptographic-module-validation-program/​documents/​fips140-2/​fips1402ig.pdf. Accessed: 2019-05-10, Document Revision: 2019-05-07.

[61] J. O'Gorman and E. T. Campbell. Quantum computation with realistic magic-state factories. Physical Review A, 95 (3): 032338, 2017. 10.1103/​PhysRevA.95.032338. arXiv:1605.07197.

[62] D. K. L. Oi, S. J. Devitt, and L. C. L. Hollenberg. Scalable error correction in distributed ion trap computers. Physical Review A, 74 (5): 052313, 2006. 10.1103/​PhysRevA.74.052313. arXiv:quant-ph/​0606226.

[63] OpenSSL Software Foundation. OpenSSL source code: Line 32 of apps/​dhparam.c. https:/​/​​openssl/​openssl/​blob/​07f434441e7ea385f975e8df8caa03e62222ca61/​apps/​dhparam.c#L32, 2018. URL https:/​/​​openssl/​openssl/​blob/​07f434441e7ea385f975e8df8caa03e62222ca61/​apps/​dhparam.c#L32. Accessed: 2018-12-11.

[64] M. Oskin, F. T. Chong, and I. L. Chuang. A practical architecture for reliable quantum computers. Computer, 35 (1): 79–87, 2002. 10.1109/​2.976922.

[65] A. Parent, M. Roetteler, and M. Mosca. Improved reversible and quantum circuits for Karatsuba-based integer multiplication. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), volume 73 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. 10.4230/​LIPIcs.TQC.2017.7. arXiv:1706.03419.

[66] S. Parker and M. B. Plenio. Efficient Factorization with a Single Pure Qubit and $\log N$ Mixed Qubits. Physical Review Letters, 85 (14): 3049, October 2000. 10.1103/​PhysRevLett.85.3049. arXiv:quant-ph/​0001066.

[67] A. Pavlidis and D. Gizopoulos. Fast quantum modular exponentiation architecture for Shor's factorization algorithm. Quantum Information & Computation, 14 (7–8): 649–682, 2014. 10.26421/​QIC14.7-8-8. arXiv:1207.0511.

[68] S. C. Pohlig and M. E. Hellman. An Improved Algorithm for Computing Logarithms over GF($p$) and Its Cryptographic Significance. IEEE Transactions on Information Theory, IT-24 (1): 106–110, 1978. 10.1109/​TIT.1978.1055817.

[69] J. M. Pollard. Monte Carlo Methods for Index Computation (mod $p$). Mathematics of Computation, 32 (143): 918–924, 1978. 10.1090/​s0025-5718-1978-0491431-9.

[70] J. M. Pollard. Factoring with cubic integers. In The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics (LNM), pages 4–10. Springer, 1993a. 10.1007/​BFb0091536.

[71] J. M. Pollard. The lattice sieve. In The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics (LNM), pages 43–49. Springer, 1993b. 10.1007/​BFb0091538.

[72] C. Pomerance. A Tale of Two Sieves. Notices of the AMS, 43 (12): 1473–1485, 1996. URL https:/​/​​notices/​199612/​pomerance.pdf.

[73] R. L. Rivest, A. Shamir, and L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21 (2): 120–126, 1978. 10.1145/​359340.359342.

[74] M. Roetteler, M. Naehrig, K. M. Svore, and K. Lauter. Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms. In Advances in Cryptology – ASIACRYPT 2017, volume 10625 of Lecture Notes in Computer Science (LNCS), pages 241–270. Springer, 2017. 10.1007/​978-3-319-70697-9_9.

[75] O. Schirokauer. On pro-finite groups and on discrete logarithms. PhD thesis, University of California, Berkeley, May 1992.

[76] O. Schirokauer. Discrete Logarithms and Local Units. Philosophical Transactions of the Royal Society of London A, 345 (1676): 409–423, 1993. 10.1098/​rsta.1993.0139.

[77] A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7 (3–4): 281–292, 1971. 10.1007/​BF02242355.

[78] B. Schroeder, E. Pinheiro, and W.-D. Weber. DRAM Errors in the Wild: A Large-Scale Field Study. SIGMETRICS Performance Evaluation Review, 37 (1): 193–204, 2009. 10.1145/​1555349.1555372.

[79] P. W. Shor. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134. IEEE, 1994. 10.1109/​SFCS.1994.365700.

[80] The GnuPG Project. GnuPG Frequently Asked Questions: Why does GnuPG default to 2048 bit RSA-2048? https:/​/​​faq/​gnupg-faq.html#default_rsa2048, 2018. URL https:/​/​​faq/​gnupg-faq.html#default_rsa2048. Accessed: 2018-12-11.

[81] The OpenSSH Project. Linux Documentation: Man Page for ssh-keygen(1). https:/​/​​man/​1/​ssh-keygen, 2018. URL https:/​/​​man/​1/​ssh-keygen. Accessed: 2018-12-11.

[82] R. Van Meter. A #QuantumComputerArchitecture Tweetstorm, 2019. 10.5281/​zenodo.3496597.

[83] R. Van Meter and K. M. Itoh. Fast quantum modular exponentiation. Physical Review A, 71 (5): 052320, 2005. 10.1103/​PhysRevA.71.052320. arXiv:quant-ph/​0408006.

[84] R. Van Meter, W. J. Munro, K. Nemoto, and K. M. Itoh. Arithmetic on a distributed-memory quantum multicomputer. ACM Journal on Emerging Technologies in Computing Systems (JETC), 3 (4): 1–23, 2008. 10.1145/​1324177.1324179.

[85] R. Van Meter, T. D. Ladd, A. G. Fowler, and Y. Yamamoto. Distributed quantum computation architecture using semiconductor nanophotonics. International Journal of Quantum Information, 8 (01n02): 295–323, 2010. 10.1142/​S0219749910006435. arXiv:0906.2686.

[86] P. C. van Oorschot and M. J. Wiener. On Diffie-Hellman Key Agreement with Short Exponents. In Advances in Cryptology – EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science (LNCS), pages 332–343. Springer, 1996. 10.1007/​3-540-68339-9_29.

[87] V. Vedral, A. Barenco, and A. Ekert. Quantum networks for elementary arithmetic operations. Physical Review A, 54 (1): 147–153, 1996. 10.1103/​PhysRevA.54.147. arXiv:quant-ph/​9511018.

[88] M. G. Whitney, N. Isailovic, Y. Patel, and J. Kubiatowicz. A fault tolerant, area efficient architecture for Shor's factoring algorithm. In Proceedings of the 36th Annual International Symposium on Computer Architecture, pages 383–394. ACM, 2009. 10.1145/​1555754.1555802.

[89] Wikipedia. Timeline of quantum computing. https:/​/​​wiki/​Timeline_of_quantum_computing, 2018. URL https:/​/​​wiki/​Timeline_of_quantum_computing. Accessed: 2018-12-18.

[90] C. Zalka. Fast versions of Shor's quantum factoring algorithm. arXiv preprint quant-ph/​9806084, 1998. URL https:/​/​​abs/​quant-ph/​9806084.

[91] C. Zalka. Shor's algorithm with fewer (pure) qubits. arXiv preprint quant-ph/​0601097, 2006. URL https:/​/​​abs/​quant-ph/​0601097.

Cited by

[1] Yasunari Suzuki, Yoshiaki Kawase, Yuya Masumura, Yuria Hiraga, Masahiro Nakadai, Jiabao Chen, Ken M. Nakanishi, Kosuke Mitarai, Ryosuke Imai, Shiro Tamiya, Takahiro Yamamoto, Tennin Yan, Toru Kawakubo, Yuya O. Nakagawa, Yohei Ibe, Youyuan Zhang, Hirotsugu Yamashita, Hikaru Yoshimura, Akihiro Hayashi, and Keisuke Fujii, "Qulacs: a fast and versatile quantum circuit simulator for research purpose", Quantum 5, 559 (2021).

[2] Josu Etxezarreta Martinez, Patricio Fuentes, Pedro Crespo, and Javier Garcia-Frias, "Time-varying quantum channel models for superconducting qubits", npj Quantum Information 7 1, 115 (2021).

[3] Robin M. Berger and Marcel Tiepelt, Lecture Notes in Computer Science 12912, 44 (2021) ISBN:978-3-030-88237-2.

[4] Michael Kreshchuk, Shaoyang Jia, William M. Kirby, Gary Goldstein, James P. Vary, and Peter J. Love, "Simulating hadronic physics on noisy intermediate-scale quantum devices using basis light-front quantization", Physical Review A 103 6, 062601 (2021).

[5] Michel Barbeau, Erwan Beurier, Joaquin Garcia-Alfaro, Randy Kuang, Marc-Oliver Pahl, and Dominique Pastor, "1. Quantum Applications - Fachbeitrag: The Quantum What? Advantage, Utopia or Threat?", Digitale Welt 5 4, 34 (2021).

[6] Daniel Carney, Hartmut Häffner, David C. Moore, and Jacob M. Taylor, "Trapped Electrons and Ions as Particle Detectors", Physical Review Letters 127 6, 061804 (2021).

[7] Oscar Higgott and Nikolas P. Breuckmann, "Subsystem Codes with High Thresholds by Gauge Fixing and Reduced Qubit Overhead", Physical Review X 11 3, 031039 (2021).

[8] Shouvanik Chakrabarti, Rajiv Krishnakumar, Guglielmo Mazzola, Nikitas Stamatopoulos, Stefan Woerner, and William J. Zeng, "A Threshold for Quantum Advantage in Derivative Pricing", Quantum 5, 463 (2021).

[9] Waqas Aman, Muhammad Mahboob Ur Rahman, Hasan T. Abbas, Muhammad Arslan Khalid, Muhammad A. Imran, Akram Alomainy, and Qammer H. Abbasi, "Securing the Insecure: A First-Line-of-Defense for Body-Centric Nanoscale Communication Systems Operating in THz Band", Sensors 21 10, 3534 (2021).

[10] Zijun Chen, Kevin J. Satzinger, Juan Atalaya, Alexander N. Korotkov, Andrew Dunsworth, Daniel Sank, Chris Quintana, Matt McEwen, Rami Barends, Paul V. Klimov, Sabrina Hong, Cody Jones, Andre Petukhov, Dvir Kafri, Sean Demura, Brian Burkett, Craig Gidney, Austin G. Fowler, Alexandru Paler, Harald Putterman, Igor Aleiner, Frank Arute, Kunal Arya, Ryan Babbush, Joseph C. Bardin, Andreas Bengtsson, Alexandre Bourassa, Michael Broughton, Bob B. Buckley, David A. Buell, Nicholas Bushnell, Benjamin Chiaro, Roberto Collins, William Courtney, Alan R. Derk, Daniel Eppens, Catherine Erickson, Edward Farhi, Brooks Foxen, Marissa Giustina, Ami Greene, Jonathan A. Gross, Matthew P. Harrigan, Sean D. Harrington, Jeremy Hilton, Alan Ho, Trent Huang, William J. Huggins, L. B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Kostyantyn Kechedzhi, Seon Kim, Alexei Kitaev, Fedor Kostritsa, David Landhuis, Pavel Laptev, Erik Lucero, Orion Martin, Jarrod R. McClean, Trevor McCourt, Xiao Mi, Kevin C. Miao, Masoud Mohseni, Shirin Montazeri, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Michael Newman, Murphy Yuezhen Niu, Thomas E. O’Brien, Alex Opremcak, Eric Ostby, Bálint Pató, Nicholas Redd, Pedram Roushan, Nicholas C. Rubin, Vladimir Shvarts, Doug Strain, Marco Szalay, Matthew D. Trevithick, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Juhwan Yoo, Adam Zalcman, Hartmut Neven, Sergio Boixo, Vadim Smelyanskiy, Yu Chen, Anthony Megrant, and Julian Kelly, "Exponential suppression of bit or phase errors with cyclic error correction", arXiv:2102.06132, Nature 595 7867, 383 (2021).

[11] Élie Gouzien and Nicolas Sangouard, "Factoring 2048-bit RSA Integers in 177 Days with 13 436 Qubits and a Multimode Memory", Physical Review Letters 127 14, 140503 (2021).

[12] Michael L. Wall and Giuseppe D'Aguanno, "Tree-tensor-network classifiers for machine learning: From quantum inspired to quantum assisted", arXiv:2104.02249, Physical Review A 104 4, 042408 (2021).

[13] Alexia Auffèves, "Optimiser la consommation énergétique des calculateurs quantiques : un défi interdisciplinaire", Reflets de la physique 69, 16 (2021).

[14] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan, "Quantum computational chemistry", arXiv:1808.10402, Reviews of Modern Physics 92 1, 015003 (2020).

[15] Yuri Alexeev, Dave Bacon, Kenneth R. Brown, Robert Calderbank, Lincoln D. Carr, Frederic T. Chong, Brian DeMarco, Dirk Englund, Edward Farhi, Bill Fefferman, Alexey V. Gorshkov, Andrew Houck, Jungsang Kim, Shelby Kimmel, Michael Lange, Seth Lloyd, Mikhail D. Lukin, Dmitri Maslov, Peter Maunz, Christopher Monroe, John Preskill, Martin Roetteler, Martin Savage, and Jeff Thompson, "Quantum Computer Systems for Scientific Discovery", arXiv:1912.07577.

[16] Laird Egan, Dripto M. Debroy, Crystal Noel, Andrew Risinger, Daiwei Zhu, Debopriyo Biswas, Michael Newman, Muyuan Li, Kenneth R. Brown, Marko Cetina, and Christopher Monroe, "Fault-Tolerant Operation of a Quantum Error-Correction Code", arXiv:2009.11482.

[17] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush, "Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction", PRX Quantum 2 3, 030305 (2021).

[18] Christopher Chamberland, Kyungjoo Noh, Patricio Arrangoiz-Arriola, Earl T. Campbell, Connor T. Hann, Joseph Iverson, Harald Putterman, Thomas C. Bohdanowicz, Steven T. Flammia, Andrew Keller, Gil Refael, John Preskill, Liang Jiang, Amir H. Safavi-Naeini, Oskar Painter, and Fernando G. S. L. Brandão, "Building a fault-tolerant quantum computer using concatenated cat codes", arXiv:2012.04108.

[19] Ryan LaRose and Brian Coyle, "Robust data encodings for quantum classifiers", Physical Review A 102 3, 032420 (2020).

[20] J. Pablo Bonilla Ataides, David K. Tuckett, Stephen D. Bartlett, Steven T. Flammia, and Benjamin J. Brown, "The XZZX surface code", Nature Communications 12, 2172 (2021).

[21] J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J. Eisert, and J. Bermejo-Vega, "Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics", Physical Review Letters 125 25, 250501 (2020).

[22] Cheng Xue, Zhao-Yun Chen, Yu-Chun Wu, and Guo-Ping Guo, "Effects of Quantum Noise on Quantum Approximate Optimization Algorithm", arXiv:1909.02196, Chinese Physics Letters 38 3, 030302 (2019).

[23] A. D. Corcoles, A. Kandala, A. Javadi-Abhari, D. T. McClure, A. W. Cross, K. Temme, P. D. Nation, M. Steffen, and J. M. Gambetta, "Challenges and Opportunities of Near-Term Quantum Computing Systems", arXiv:1910.02894.

[24] Christopher Chamberland and Kyungjoo Noh, "Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits", npj Quantum Information 6, 91 (2020).

[25] Matt McEwen, Lara Faoro, Kunal Arya, Andrew Dunsworth, Trent Huang, Seon Kim, Brian Burkett, Austin Fowler, Frank Arute, Joseph C. Bardin, Andreas Bengtsson, Alexander Bilmes, Bob B. Buckley, Nicholas Bushnell, Zijun Chen, Roberto Collins, Sean Demura, Alan R. Derk, Catherine Erickson, Marissa Giustina, Sean D. Harrington, Sabrina Hong, Evan Jeffrey, Julian Kelly, Paul V. Klimov, Fedor Kostritsa, Pavel Laptev, Aditya Locharla, Xiao Mi, Kevin C. Miao, Shirin Montazeri, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Alex Opremcak, Chris Quintana, Nicholas Redd, Pedram Roushan, Daniel Sank, Kevin J. Satzinger, Vladimir Shvarts, Theodore White, Z. Jamie Yao, Ping Yeh, Juhwan Yoo, Yu Chen, Vadim Smelyanskiy, John M. Martinis, Hartmut Neven, Anthony Megrant, Lev Ioffe, and Rami Barends, "Resolving catastrophic error bursts from cosmic rays in large arrays of superconducting qubits", arXiv:2104.05219.

[26] S. Paesani, M. Borghi, S. Signorini, A. Maïnos, L. Pavesi, and A. Laing, "Near-ideal spontaneous photon sources in silicon quantum photonics", Nature Communications 11, 2505 (2020).

[27] Poulami Das, Christopher A. Pattison, Srilatha Manne, Douglas Carmean, Krysta Svore, Moinuddin Qureshi, and Nicolas Delfosse, "A Scalable Decoder Micro-architecture for Fault-Tolerant Quantum Computing", arXiv:2001.06598.

[28] Thomas E. O'Brien, Stefano Polla, Nicholas C. Rubin, William J. Huggins, Sam McArdle, Sergio Boixo, Jarrod R. McClean, and Ryan Babbush, "Error Mitigation via Verified Phase Estimation", PRX Quantum 2 2, 020317 (2021).

[29] Hyeongrak Choi, Mihir Pant, Saikat Guha, and Dirk Englund, "Percolation-based architecture for cluster state creation using photon-mediated entanglement between atomic memories", arXiv:1704.07292, npj Quantum Information 5, 104 (2019).

[30] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, and Anupam Prakash, "Prospects and challenges of quantum finance", arXiv:2011.06492.

[31] Earl T. Campbell, "Early fault-tolerant simulations of the Hubbard model", arXiv:2012.09238.

[32] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick, "Simpler Proofs of Quantumness", arXiv:2005.04826.

[33] Ryan Babbush, Jarrod McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven, "Focus beyond quadratic speedups for error-corrected quantum advantage", arXiv:2011.04149.

[34] Kianna Wan, Soonwon Choi, Isaac H. Kim, Noah Shutty, and Patrick Hayden, "Fault-tolerant qubit from a constant number of components", arXiv:2011.08213.

[35] Nicolas Delfosse, "Hierarchical decoding to reduce hardware requirements for quantum computing", arXiv:2001.11427.

[36] Michael Streif, Martin Leib, Filip Wudarski, Eleanor Rieffel, and Zhihui Wang, "Quantum algorithms with local particle-number conservation: Noise effects and error correction", Physical Review A 103 4, 042412 (2021).

[37] Xavier Bonnetain and Samuel Jaques, "Quantum Period Finding against Symmetric Primitives in Practice", arXiv:2011.07022.

[38] F. Lecocq, F. Quinlan, K. Cicak, J. Aumentado, S. A. Diddams, and J. D. Teufel, "Control and readout of a superconducting qubit using a photonic link", Nature 591 7851, 575 (2021).

[39] Kento Oonishi, Tomoki Tanaka, Shumpei Uno, Takahiko Satoh, Rodney Van Meter, and Noboru Kunihiro, "Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates", arXiv:2010.00255.

[40] Michał Oszmaniec, Ninnat Dangniam, Mauro E. S. Morales, and Zoltán Zimborás, "Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states", arXiv:2012.15825.

[41] Jaime Sevilla and C. Jess Riedel, "Forecasting timelines of quantum computing", arXiv:2009.05045.

[42] Isaac H. Kim, Eunseok Lee, Ye-Hua Liu, Sam Pallister, William Pol, and Sam Roberts, "Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules", arXiv:2104.10653.

[43] Michael L. Wall, Matthew R. Abernathy, and Gregory Quiroz, "Generative machine learning with tensor networks: Benchmarks on near-term quantum computers", Physical Review Research 3 2, 023010 (2021).

[44] Riccardo Mengoni, Daniele Ottaviani, and Paolino Iorio, "Breaking RSA Security With A Low Noise D-Wave 2000Q Quantum Annealer: Computational Times, Limitations And Prospects", arXiv:2005.02268.

[45] James R. Cruise, Neil I. Gillespie, and Brendan Reid, "Practical Quantum Computing: The value of local computation", arXiv:2009.08513.

[46] Nhung H. Nguyen, Muyuan Li, Alaina M. Green, C. Huerta Alderete, Yingyue Zhu, Daiwei Zhu, Kenneth R. Brown, and Norbert M. Linke, "Demonstration of Shor Encoding on a Trapped-Ion Quantum Computer", Physical Review Applied 16 2, 024057 (2021).

[47] Andriy Miranskyy, Lei Zhang, and Javad Doliskani, "On Testing and Debugging Quantum Software", arXiv:2103.09172.

[48] Craig Gidney, "Quantum block lookahead adders and the wait for magic states", arXiv:2012.01624.

[49] Motohiko Ezawa, "Dirac Formulation for Universal Quantum Gates and Shor's Integer Factorization in High-frequency Electric Circuits", Journal of the Physical Society of Japan 89 12, 124712 (2020).

[50] Jun Yang, James Brown, and James Daniel Whitfield, "A comparison of three ways to measure time-dependent densities with quantum simulators", arXiv:1909.03078.

[51] W. Cai, Y. Ma, W. Wang, C. -L. Zou, and L. Sun, "Bosonic quantum error correction codes in superconducting quantum circuits", arXiv:2010.08699.

[52] Thomas Häner, Torsten Hoefler, and Matthias Troyer, "Assertion-Based Optimization of Quantum Programs", arXiv:1810.00375.

[53] Casey Duckering, Jonathan M. Baker, David I. Schuster, and Frederic T. Chong, "Virtualized Logical Qubits: A 2.5D Architecture for Error-Corrected Quantum Computing", arXiv:2009.01982.

[54] Thomas Häner, Samuel Jaques, Michael Naehrig, Martin Roetteler, and Mathias Soeken, "Improved quantum circuits for elliptic curve discrete logarithms", arXiv:2001.09580.

[55] Katsuhiro Endo, Taichi Nakamura, Keisuke Fujii, and Naoki Yamamoto, "Quantum self-learning Monte Carlo and quantum-inspired Fourier transform sampler", Physical Review Research 2 4, 043442 (2020).

[56] Thomas Häner, Damian S. Steiger, Torsten Hoefler, and Matthias Troyer, "Distributed Quantum Computing with QMPI", arXiv:2105.01109.

[57] David Ittah, Thomas Häner, Vadym Kliuchnikov, and Torsten Hoefler, "Enabling Dataflow Optimization for Quantum Programs", arXiv:2101.11030.

[58] Lei Zhang, Andriy Miranskyy, and Walid Rjaibi, "Quantum Advantage and Y2K Bug: Comparison", arXiv:1907.10454.

[59] Kai Li and Qing-yu Cai, "Practical Security of RSA Against NTC-Architecture Quantum Computing Attacks", International Journal of Theoretical Physics 60 8, 2733 (2021).

[60] Panjin Kim and Daewan Han, "Measurement-based Uncomputation Applied to Controlled Modular Multiplication", arXiv:2102.01453.

[61] Samuel Jaques and Thomas Häner, "Leveraging state sparsity for more efficient quantum simulations", arXiv:2105.01533.

[62] Dennis Lucarelli, "Quantum Error Source and Channel Coding", arXiv:2004.09479.

[63] S. E. Yunakovsky, M. Kot, N. O. Pozhar, D. Nabokov, M. A. Kudinov, A. Guglya, E. O. Kiktenko, E. Kolycheva, A. Borisov, and A. K. Fedorov, "Towards security recommendations for public-key infrastructures for production environments in the post-quantum era", arXiv:2105.01324.

[64] Wei Cui, Tong Dou, and Shilu Yan, "Threats and Opportunities: Blockchain Meets Quantum Computation", arXiv:2011.03460.

[65] Benjamin Harsha and Jeremiah Blocki, "An Economic Model for Quantum Key-Recovery Attacks against Ideal Ciphers", arXiv:2005.05911.

[66] L. Le Guevel, G. Billiot, S. De Franceschi, A. Morel, X. Jehl, A. G. M. Jansen, and G. Pillonnet, "Compact gate-based read-out of multiplexed quantum devices with a cryogenic CMOS active inductor", arXiv:2102.04364.

[67] Samuel Jaques and Craig Gidney, "Offloading Quantum Computation by Superposition Masking", arXiv:2008.04577.

[68] Laird Egan, Dripto M. Debroy, Crystal Noel, Andrew Risinger, Daiwei Zhu, Debopriyo Biswas, Michael Newman, Muyuan Li, Kenneth R. Brown, Marko Cetina, and Christopher Monroe, "Fault-tolerant control of an error-corrected qubit", Nature 598 7880, 281 (2021).

[69] Leandro Stefanazzi, Ken Treptow, Neal Wilcer, Chris Stoughton, Salvatore Montella, Collin Bradford, Gustavo Cancelo, Shefali Saxena, Horacio Arnaldi, Sara Sussman, Andrew Houck, Ankur Agrawal, Helin Zhang, Chunyang Ding, and David I Schuster, "The QICK (Quantum Instrumentation Control Kit): Readout and control for qubits and detectors", arXiv:2110.00557.

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-22 17:01:08) and SAO/NASA ADS (last updated successfully 2021-10-22 17:01:10). The list may be incomplete as not all publishers provide suitable and complete citation data.