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.
Abstract
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.22331/q-2019-12-02-208
arXiv:1902.02134
[9] BlueKrypt. Cryptographic Key Length Recommendation. https://www.keylength.com, 2019. URL https://www.keylength.com. Accessed: 2019-03-03.
https://www.keylength.com
[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.
https://doi.org/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.
https://doi.org/10.1007/978-3-030-56880-1_3
[12] M. Braithwaite. Experimenting with post-quantum cryptography. https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html, July 2016. URL https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html.
https://security.googleblog.com/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/quant-ph/0410184.
arXiv: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.
https://doi.org/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.
https://doi.org/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://eprint.iacr.org/2016/1128.
https://eprint.iacr.org/2016/1128
[22] M. Ekerå. Revisiting Shor’s quantum algorithm for computing general discrete logarithms. arXiv preprint arXiv:1905.09084, 2019. URL https://arxiv.org/abs/1905.09084.
arXiv: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.
https://doi.org/10.1007/s10623-020-00783-2
[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.
https://doi.org/10.1515/jmc-2020-0006
[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.
https://doi.org/10.1007/978-3-319-59879-6_20
[26] A. G. Fowler. Time-optimal quantum computation. arXiv preprint arXiv:1210.4626, 2012. URL https://arxiv.org/abs/1210.4626.
arXiv:1210.4626
[27] A. G. Fowler and C. Gidney. Low overhead quantum computation using lattice surgery. arXiv preprint arXiv:1808.06709, 2018. URL https://arxiv.org/abs/1808.06709.
arXiv: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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/1902.02332.
arXiv:1902.02332
[31] C. Gidney. Factoring with $n+2$ clean qubits and $n-1$ dirty qubits. arXiv preprint arXiv:1706.07884, 2017. URL https://arxiv.org/abs/1706.07884.
arXiv: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.
https://doi.org/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://arxiv.org/abs/1905.08488.
arXiv:1905.08488
[34] C. Gidney. Asymptotically Efficient Quantum Karatsuba Multiplication. arXiv preprint arXiv:1904.07356, 2019b. URL https://arxiv.org/abs/1904.07356.
arXiv:1904.07356
[35] C. Gidney. Windowed quantum arithmetic. arXiv preprint arXiv:1905.07682, 2019c. URL https://arxiv.org/abs/1905.07682.
arXiv: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.
https://doi.org/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://arxiv.org/abs/1905.08916.
arXiv:1905.08916
[38] D. Gillmor. RFC 7919: Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS), August 2016. 10.17487/RFC7919.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://mi.mathnet.ru/eng/dan/v145/i2/p293.
http://mi.mathnet.ru/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/quant-ph/0609001.
arXiv:quant-ph/0609001
[52] A. K. Lenstra. Key Lengths. In The Handbook of Information Security, chapter 6. 2004. URL https://infoscience.epfl.ch/record/164539/files/NPDF-32.pdf.
https://infoscience.epfl.ch/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1109/MSP.2018.3761723
[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.
https://doi.org/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.
https://doi.org/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.nist.gov/csrc/media/projects/cryptographic-module-validation-program/documents/fips140-2/fips1402ig.pdf. Accessed: 2019-05-10, Document Revision: 2019-05-07.
https://csrc.nist.gov/csrc/media/projects/cryptographic-module-validation-program/documents/fips140-2/fips1402ig.pdf
[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.
https://doi.org/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.
https://doi.org/10.1103/PhysRevA.74.052313
arXiv:quant-ph/0606226
[63] OpenSSL Software Foundation. OpenSSL source code: Line 32 of apps/dhparam.c. https://github.com/openssl/openssl/blob/07f434441e7ea385f975e8df8caa03e62222ca61/apps/dhparam.c#L32, 2018. URL https://github.com/openssl/openssl/blob/07f434441e7ea385f975e8df8caa03e62222ca61/apps/dhparam.c#L32. Accessed: 2018-12-11.
https://github.com/openssl/openssl/blob/07f434441e7ea385f975e8df8caa03e62222ca61/apps/dhparam.c#L32
[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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1007/BFb0091538
[72] C. Pomerance. A Tale of Two Sieves. Notices of the AMS, 43 (12): 1473–1485, 1996. URL https://www.ams.org/notices/199612/pomerance.pdf.
https://www.ams.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1109/SFCS.1994.365700
[80] The GnuPG Project. GnuPG Frequently Asked Questions: Why does GnuPG default to 2048 bit RSA-2048? https://www.gnupg.org/faq/gnupg-faq.html#default_rsa2048, 2018. URL https://www.gnupg.org/faq/gnupg-faq.html#default_rsa2048. Accessed: 2018-12-11.
https://www.gnupg.org/faq/gnupg-faq.html#default_rsa2048
[81] The OpenSSH Project. Linux Documentation: Man Page for ssh-keygen(1). https://linux.die.net/man/1/ssh-keygen, 2018. URL https://linux.die.net/man/1/ssh-keygen. Accessed: 2018-12-11.
https://linux.die.net/man/1/ssh-keygen
[82] R. Van Meter. A #QuantumComputerArchitecture Tweetstorm, 2019. 10.5281/zenodo.3496597.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1145/1555754.1555802
[89] Wikipedia. Timeline of quantum computing. https://en.wikipedia.org/wiki/Timeline_of_quantum_computing, 2018. URL https://en.wikipedia.org/wiki/Timeline_of_quantum_computing. Accessed: 2018-12-18.
https://en.wikipedia.org/wiki/Timeline_of_quantum_computing
[90] C. Zalka. Fast versions of Shor’s quantum factoring algorithm. arXiv preprint quant-ph/9806084, 1998. URL https://arxiv.org/abs/quant-ph/9806084.
arXiv:quant-ph/9806084
[91] C. Zalka. Shor’s algorithm with fewer (pure) qubits. arXiv preprint quant-ph/0601097, 2006. URL https://arxiv.org/abs/quant-ph/0601097.
arXiv:quant-ph/0601097
Cited by
[1] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan, “Quantum computational chemistry”, Reviews of Modern Physics 92 1, 015003 (2020).
[2] 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.
[3] 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.
[4] 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.
[5] 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).
[6] Cheng Xue, Zhao-Yun Chen, Yu-Chun Wu, and Guo-Ping Guo, “Effects of Quantum Noise on Quantum Approximate Optimization Algorithm”, arXiv:1909.02196.
[7] Ryan LaRose and Brian Coyle, “Robust data encodings for quantum classifiers”, Physical Review A 102 3, 032420 (2020).
[8] 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”, arXiv:2011.13524.
[9] 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, 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, 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, Fedor Kostritsa, David Landhuis, Pavel Laptev, Erik Lucero, Orion Martin, Jarrod R. McClean, Trevor McCourt, Xiao Mi, Kevin C. Miao, Masoud Mohseni, 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, Adam Zalcman, Hartmut Neven, Sergio Boixo, Vadim Smelyanskiy, Yu Chen, Anthony Megrant, and Julian Kelly, “Exponential suppression of bit or phase flip errors with repetitive error correction”, arXiv:2102.06132.
[10] 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.
[11] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme, “A rigorous and robust quantum speed-up in supervised machine learning”, arXiv:2010.02174.
[12] 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.
[13] 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”, arXiv:2011.03494.
[14] 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).
[15] 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.
[16] Thomas Häner, Torsten Hoefler, and Matthias Troyer, “Assertion-Based Optimization of Quantum Programs”, arXiv:1810.00375.
[17] 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).
[18] J. Pablo Bonilla Ataides, David K. Tuckett, Stephen D. Bartlett, Steven T. Flammia, and Benjamin J. Brown, “The XZZX Surface Code”, arXiv:2009.07851.
[19] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, and Anupam Prakash, “Prospects and challenges of quantum finance”, arXiv:2011.06492.
[20] Tomoki Tanaka, Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tamiya Onodera, and Naoki Yamamoto, “Amplitude estimation via maximum likelihood on noisy quantum computer”, arXiv:2006.16223.
[21] 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”, arXiv:2010.02538.
[22] 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.
[23] Nicolas Delfosse, “Hierarchical decoding to reduce hardware requirements for quantum computing”, arXiv:2001.11427.
[24] Shouvanik Chakrabarti, Rajiv Krishnakumar, Guglielmo Mazzola, Nikitas Stamatopoulos, Stefan Woerner, and William J. Zeng, “A Threshold for Quantum Advantage in Derivative Pricing”, arXiv:2012.03819.
[25] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick, “Simpler Proofs of Quantumness”, arXiv:2005.04826.
[26] Sonika Johri, Shantanu Debnath, Avinash Mocherla, Alexandros Singh, Anupam Prakash, Jungsang Kim, and Iordanis Kerenidis, “Nearest Centroid Classification on a Trapped Ion Quantum Computer”, arXiv:2012.04145.
[27] 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.
[28] Oscar Higgott and Nikolas P. Breuckmann, “Subsystem codes with high thresholds by gauge fixing and reduced qubit overhead”, arXiv:2010.09626.
[29] Jun Yang, James Brown, and James Daniel Whitfield, “A comparison of three ways to measure time-dependent densities with quantum simulators”, arXiv:1909.03078.
[30] 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.
[31] Jaime Sevilla and C. Jess Riedel, “Forecasting timelines of quantum computing”, arXiv:2009.05045.
[32] W. Cai, Y. Ma, W. Wang, C. -L. Zou, and L. Sun, “Bosonic quantum error correction codes in superconducting quantum circuits”, arXiv:2010.08699.
[33] Earl T. Campbell, “Early fault-tolerant simulations of the Hubbard model”, arXiv:2012.09238.
[34] Xavier Bonnetain and Samuel Jaques, “Quantum Period Finding against Symmetric Primitives in Practice”, arXiv:2011.07022.
[35] James R. Cruise, Neil I. Gillespie, and Brendan Reid, “Practical Quantum Computing: The value of local computation”, arXiv:2009.08513.
[36] Lei Zhang, Andriy Miranskyy, and Walid Rjaibi, “Quantum Advantage and Y2K Bug: Comparison”, arXiv:1907.10454.
[37] 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.
[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] Craig Gidney, “Quantum block lookahead adders and the wait for magic states”, arXiv:2012.01624.
[40] 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.
[41] Thomas Häner, Samuel Jaques, Michael Naehrig, Martin Roetteler, and Mathias Soeken, “Improved quantum circuits for elliptic curve discrete logarithms”, arXiv:2001.09580.
[42] Michael Streif, Martin Leib, Filip Wudarski, Eleanor Rieffel, and Zhihui Wang, “Quantum algorithms with local particle number conservation: noise effects and error correction”, arXiv:2011.06873.
[43] Kianna Wan, Soonwon Choi, Isaac H. Kim, Noah Shutty, and Patrick Hayden, “Fault-tolerant qubit from a constant number of components”, arXiv:2011.08213.
[44] Benjamin Harsha and Jeremiah Blocki, “An Economic Model for Quantum Key-Recovery Attacks against Ideal Ciphers”, arXiv:2005.05911.
[45] Dennis Lucarelli, “Quantum Error Source and Channel Coding”, arXiv:2004.09479.
[46] 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).
[47] 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).
[48] Wei Cui, Tong Dou, and Shilu Yan, “Threats and Opportunities: Blockchain Meets Quantum Computation”, arXiv:2011.03460.
[49] 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).
[50] Samuel Jaques and Craig Gidney, “Offloading Quantum Computation by Superposition Masking”, arXiv:2008.04577.
[51] 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.
[52] David Ittah, Thomas Häner, Vadym Kliuchnikov, and Torsten Hoefler, “Enabling Dataflow Optimization for Quantum Programs”, arXiv:2101.11030.
[53] Panjin Kim and Daewan Han, “Measurement-based Uncomputation Applied to Controlled Modular Multiplication”, arXiv:2102.01453.
[54] Michael L. Wall and Giuseppe D’Aguanno, “Tree tensor network classifiers for machine learning: from quantum-inspired to quantum-assisted”, arXiv:2104.02249.
[55] Andriy Miranskyy, Lei Zhang, and Javad Doliskani, “On Testing and Debugging Quantum Software”, arXiv:2103.09172.
[56] 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.
[57] Élie Gouzien and Nicolas Sangouard, “Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory”, arXiv:2103.06159.
[58] Nhung H. Nguyen, Muyuan Li, Alaina M. Green, Cinthia Huerta Alderete, Yingyue Zhu, Daiwei Zhu, Kenneth R. Brown, and Norbert M. Linke, “Demonstration of Shor encoding on a trapped-ion quantum computer”, arXiv:2104.01205.
The above citations are from SAO/NASA ADS (last updated successfully 2021-04-19 18:19:59). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2021-04-19 18:19:57).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
Coinsmart. Beste Bitcoin-Börse in Europa
Source: https://quantum-journal.org/papers/q-2021-04-15-433/
