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

By Craig Gidney, Martin Ekerå. Quantum, 2019

924 citations recorded by the source corpus.

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 3n+0.002nlg⁡n logical qubits, 0.3n3+0.0005n3lg⁡n Toffolis, and 500n2+n2lg⁡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.

Subfields: Artificial Intelligence, Information Systems

View Paper: https://www.semanticscholar.org/paper/ee1044cb1b4fa931e86a3a1c3cd1534c52c8cb70

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Robust data encodings for quantum classifiers (2020, background): “While the gap be-tween NISQ capabilities and required resources for, e.g., factoring 2048-bit integers is large [5], recent hardware advancements have led to the ﬁrst quantum computation which classical computers cannot emulate [6].”
Zero Trust Architecture (ZTA): A Comprehensive Survey (2022, background): “In [182] it was demonstrated that 2048-bit RSA can be easily cracked in around eight hours by a quantum computer consisting of 20 million qbits.”
Magic state cultivation: growing T states as cheap as CNOT gates (2024, methodology): “For example, consider an algorithm implementation that used ripple carry adders to minimize T count (such as [GE21]).”
Quantum error correction below the surface code threshold (2024, neutral): “3b-c, observing good agreement with O ( p ( d +1) / 2 ) error suppression.”
Logical quantum processor based on reconfigurable atom arrays (2023, background): “Similar techniques can be used to move logical degrees of freedom to implement nonlocal logical gates 23 .”
A rigorous and robust quantum speed-up in supervised machine learning (2020, methodology): “Then, construct a quantum circuit U y using the quantum algorithm for discrete log [42, 50, 53] which uses ˜ O ( n 3 ) gates (we use ˜ O ( · ) to hide polylog factors), The overall procedure for preparing | C y,k (cid:105) is as follows, up to adding/discarding auxiliary qubits: Deﬁnition 10.”
Quantum technology for military applications (2021, background): “public-key cryptography schemes breaking) • Timeline expectation: mid- to long-term • Qubits requirement: ∼ 6200 for 2048 bit RSA factorisation [35], ∼ 2900 for 256 bit ECDLP-based3 encryption [36] • Main challenges: number of logical qubits One of the most well-known quantum computer applications i”
Qulacs: a fast and versatile quantum circuit simulator for research purpose (2020, methodology): “To construct a quantum computer large enough for Shor’s algorithm [48, 49], a quantum simulation for quantum manybody systems [36, 50], or algorithms for linear systems [51], quantum error correction [52] is necessary to reduce logical error rates to an arbitrarily small value.”