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

We significantly reduce the cost of factoring integers and computing discretelogarithms in finite fields on a quantum computer by combining techniques fromShor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Ekerå-Håstad2017, Ekerå 2017, Ekerå 2018, Gidney-Fowler 2019, Gidney 2019. Weestimate the approximate cost of our construction using plausible physicalassumptions for large-scale superconducting qubit platforms: a planar grid ofqubits with nearest-neighbor connectivity, a characteristic physical gate errorrate of 10^-3, a surface code cycle time of 1 microsecond, and a reactiontime of 10 microseconds. We account for factors that are normally ignored suchas noise, the need to make repeated attempts, and the spacetime layout of thecomputation. When factoring 2048 bit RSA integers, our construction’s spacetimevolume is a hundredfold less than comparable estimates from earlier works (VanMeter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al.2019). In the abstract circuit model (which ignores overheads fromdistillation, routing, and error correction) our construction uses 3 n + 0.002n n logical qubits, 0.3 n^3 + 0.0005 n^3 n Toffolis, and 500 n^2 +n^2 n measurement depth to factor n-bit RSA integers. We quantify thecryptographic implications of our work, both for RSA and for schemes based onthe DLP in finite fields.

Further reading#

• Access Paper in arXiv.org