PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Craig Gidney, Martin Ekerå

arXiv:1905.09749v3quant-ph

TL;DR

The paper addresses the high cost of implementing Shor’s algorithms for cryptographically relevant factoring and discrete-logarithm problems on noisy quantum hardware. It combines algorithmic and architectural optimizations, then estimates abstract and surface-code costs under plausible superconducting-platform assumptions. The resulting estimates are orders of magnitude lower than earlier works with comparable physical assumptions, including a reduction from a billion to twenty million physical qubits for factoring 2048-bit RSA integers.

  • Problem

    Noisy quantum hardware and the resulting error-correction overhead make cryptographically relevant implementations of Shor’s algorithms impractical despite their polynomial-time complexity.

  • Method

    The paper combines existing and novel optimizations for modular exponentiation and estimates their costs in abstract circuits and surface-code implementations on nearest-neighbor superconducting architectures.

  • Results

    The estimated costs are orders of magnitude lower than previous works with comparable physical assumptions, with the 2048-bit RSA physical-qubit estimate dropping from one billion to twenty million.

  • Takeaways & Limitations

    The construction provides concrete lower cost estimates for factoring integers and computing discrete logarithms over finite fields on large-scale quantum computers.

  • Takeaways & Limitations

    The estimates have large systemic uncertainties and are intended as ballpark figures rather than exact predictions of future quantum computers.

Abstract

from arXiv · show

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.

1 Introduction

Shor’s algorithms have clear cryptographic applications, but noisy quantum hardware and error-correction overhead make cryptographically relevant instances impractical without substantial optimization. This work combines algorithmic and implementation techniques to reduce those costs and estimates them under physical assumptions for large-scale superconducting platforms.

  • 1 Introduction: Quantum noise makes reliable modular exponentiation far more expensive than classical modular exponentiation, despite Shor’s polynomial-time complexity.Error correction is required because quantum hardware is expected to be many orders of magnitude noisier than classical hardware.
  • 1 Introduction: The construction combines optimizations that reduce both the number of modular multiplications and the cost of each multiplication.Windowed arithmetic and Ekerå–Håstad derivatives reduce multiplication counts, while coset representations and oblivious carry runways reduce multiplication costs.
  • 1 Introduction: The authors estimate costs in both an abstract circuit model and an error-corrected implementation using surface-code assumptions and nearest-neighbor connectivity.The physical model uses square distance-d logical-qubit patches operated via lattice surgery.
  • 1 Introduction: The estimates have large systemic uncertainties and are intended as ballpark figures rather than exact predictions of future quantum computers.The paper notes that changing the physical gate error rate by a factor of two changes the required qubit count by more than 10%.
  • 1 Introduction: Compared with previous works, the construction reduces RSA-factoring Toffoli count by over 10x and improves comparable physical cost estimates by over 100x.The latter comparison is restricted to works using the same basic cost model, with remaining cost-model differences accounted for.

2 Our construction

The construction combines modified quantum algorithms and arithmetic optimizations to reduce the quantum work required for factoring and discrete-logarithm computations. Its implementation uses fewer multiplications, lower-cost arithmetic, and compact registers while retaining a reference implementation for comparison.

  • Quantum algorithms: 1.5n + O(1) exponent qubits reduce the total exponent length relative to Shor’s 2n-qubit exponent, lowering the number of quantum multiplications.The two-exponent function is f(e1, e2) = ge1y−e2, with exponent lengths 2m and m, where m = 0.5n + O(1).
  • Quantum algorithms: 99% recovery probability allows the Ekerå–Håstad factoring procedure to generally require one quantum run, because the factors are then recovered deterministically.The classical post-processing extracts d, after which p and q follow deterministically from d and N.
  • Reference implementation: 20nen^2 Toffolis form the reference implementation baseline for controlled modular multiplication.The baseline decomposes exponentiation into controlled modular multiplications, then controlled scaled additions and non-modular additions.
  • Windowed arithmetic: Windowed arithmetic fuses controlled additions through table lookups, reducing the number of multiplications by the window size while adding lookup work.The exponent-window implementation uses semi-classical Fourier-transform phasing and recycles exponent qubits; setting cmul = cexp = 1 yields a leading Toffoli term of 24nen^2/lg2 n.
  • Coset representation: 8nen^2 Toffolis is the reduced leading asymptotic term obtained by switching from modular integers to Zalka’s coset representation.The representation enables controlled non-modular additions in 4n Toffolis instead of the assumed 10n for controlled modular additions, with logarithmic padding overhead.
  • Space and implementation: 3n + O(lg n) logical qubits are used, distributed across accumulation, workspace, lookup-output, and semi-classical Fourier-transform registers.The construction focuses its cost analysis on controlled modular multiplications because they are the implementation bottleneck; the QFT is interleaved and implemented semi-classically.

2.6 Oblivious carry runways

Oblivious carry runways reduce addition depth by terminating carry propagation at intermediate points, allowing register pieces to be processed in parallel. The construction combines this optimization with windowed arithmetic and approximate representations while controlling the resulting error.

  • Oblivious carry runways terminate carries at placed runways, allowing large additions to be performed piecewise and in parallel.
  • Runway overhead is linear in the number of pieces but only logarithmic in n, enabling gradual introduction without the large overheads of carry-lookahead adders.
  • A single midpoint runway in a 2048-qubit register increases qubit and Toffoli counts by a couple percent while nearly halving addition depth.
  • The chosen optimizations complement one another, with windowed arithmetic and canonicalized offsets helping combine their benefits.
  • During multiply-add operations, runways are temporarily reduced to single carry qubits so iteration covers the main, padding, and runway qubits more efficiently.
  • The construction is approximate: with cpad = 2 lg n + lg ne + 10, the approximation error is roughly 0.1%.The deviation per addition is bounded using approximate encoded permutations, and deviations compose subadditively.

2.10 Spacetime layout

The implementation arranges lookup additions and their supporting factories, registers, and routing areas into parallel spacetime layouts. Under the stated assumptions, lookup additions dominate runtime, with significant error, repetition, and physical-qubit costs.

  • Lookup-addition layout: Rows of target-register qubits are separated by lookup-output rows and access hallways, enabling lookup additions to feed the subsequent adder.The lookup register is later uncomputed, returning the system to a state ready for another lookup addition.
  • Lookup-addition layout: The addition phase streams data through a shifting operating area to perform Cuccaro’s MAJ and UMA sweeps.Piecewise additions are partitioned horizontally so separate pieces can operate independently, while lookups prepare registers across pieces.
  • Physical layout: 14 CCZ factories determine each piece’s width, producing a 113-logical-qubit piece under the stated code-distance assumptions.Factories are arranged in two rows of seven with gaps for routing data qubits.
  • Runtime: 37 milliseconds approximates one lookup addition, combining a roughly 14-millisecond lookup with a roughly 22-millisecond addition.Because lookup additions dominate the implementation, total runtime is approximately their count multiplied by 37 milliseconds.
  • Runtime: Approximately 7 hours is estimated for one 2048-bit factoring run, before accounting for the reported need for repeated attempts.The estimate notes that larger problem sizes make lookups slower because the minimum code distance increases.
  • Error and resource estimates: Approximately 3 billion CCZ states are distilled for n = 2048, with an estimated 6.4% total distillation error and approximately 27% topological-error probability.The board uses 226 · 63 logical qubits, which at code distance 27 corresponds to approximately 23 million physical qubits.
  • Error and resource estimates: A code distance of 27 requires roughly 1.4 runs on average, while increasing it to 29 raises physical-qubit count by 15% and reduces error by approximately 10×.The choice trades increased space against fewer repetitions.
  • Error and resource estimates: Increasing code distance suppresses logical errors, but proportional reductions in code distance produce approximately cubic reductions in packed spacetime volume.The rule of thumb is considered sufficient for order-of-magnitude estimates between physical error rates of 0.3% and 0.001%, despite stated imperfections.

3 Cryptographic implications of our construction

The paper evaluates how its optimized Shor-based construction affects RSA and finite-field discrete-logarithm security. It minimizes expected spacetime volume while considering parameter choices, error probabilities, and several cryptographic group configurations.

  • Scope and objective: The section studies RSA and finite-field discrete-logarithm security using the optimized construction described earlier.The estimates target cryptographically relevant modulus lengths and parameterizations.
  • Scope and objective: Expected spacetime volume includes both per-run quantum cost and the expected number of runs required for success.This objective incorporates repetition overhead rather than evaluating only a single idealized run.
  • Optimization and error analysis: The optimization searches over code distances, window sizes, runway spacings, padding offsets, and two magic-state-distillation strategies.The selected objective is skewed expected spacetime volume, s^1.2 · t/(1 − ε), slightly favoring lower space usage.
  • Optimization and error analysis: The error analysis separately estimates topological, approximation, distillation, and classical-post-processing failure probabilities.These components are combined to derive an upper bound on the overall error probability.
  • Finite-field discrete logarithms: For finite-field discrete logarithms, prime-order subgroups support security choices using Schnorr groups or safe-prime groups with short or full-length exponents.All three parameterization options are stated to provide z bits of classical security when their exponent lengths meet the stated bounds.
  • Finite-field discrete logarithms: Short exponents are often preferred because they provide considerable performance improvements, although Schnorr and safe-prime groups have different operational trade-offs.Schnorr groups require subgroup-membership testing for untrusted elements, while safe-prime groups are more flexible.
  • Algorithmic implications: A single correct run of the modified discrete-logarithm algorithm can achieve at least 99% success probability under the stated padding and classical post-processing assumptions.For the RSA short-discrete-logarithm approach, the post-processing recovers the factors deterministically from the recovered logarithm.
  • Algorithmic implications: Confidentiality lasting 25 years requires migrating away from RSA and Diffie–Hellman at least 25 years before quantum-capable adversaries can break them.The paper distinguishes this timeline from authentication schemes, for which migration can occur closer to practical susceptibility.

4 Future work

Future work targets multiplication, distillation, qubit storage, and distributed computation to reduce practical costs, while several proposals remain unvalidated. The authors emphasize unresolved trade-offs involving constant factors, workspace, error behavior, and communication.

  • 4.1 Investigate asymptotically efficient multiplication: Asymptotically faster multipliers may not help at n = 2048 because reversible implementations and constant factors remain problematic.Karatsuba and Schönhage–Strassen have better asymptotic Toffoli counts, but their reversible forms and workspace demands complicate practical use.
  • 4.2 Optimize distillation: The current CCZ factory could be improved through block-code distillation, heralded-error handling, and detection-based rejection of risky runs.These techniques could reduce code distances or expected volume per magic state, but concrete factory layouts with understood error behavior remain unfinished.
  • 4.3 Optimize qubit storage: Resting logical qubits may use denser storage than computationally active qubits, including compact packing or block-code encodings.Candidate approaches must balance encoding and decoding costs against the benefits of reduced code distance and space.
  • 4.3 Optimize qubit storage: Dislocation-based storage could pack qubits more densely, but its longer stabilizer runs may create additional error opportunities.The paper leaves comparisons with lattice-surgery qubits and block-code layering to simulations that establish equivalent logical error rates.
  • 4.4 Distribute the computation: Eight machines with roughly 4 million qubits each might replace one 20-million-qubit machine if quantum channels provide 150qb/s bandwidth.The authors caution that this distribution proposal is based on surface analysis and has not been carefully explored.

5 Conclusion

The paper combines multiple techniques into a construction for factoring and finite-field discrete logarithms, estimating costs in both abstract and physically motivated models. Its estimates are substantially lower than comparable prior estimates, while future hardware and error-correction advances remain difficult to predict.

  • 5 Conclusion: The construction combines techniques and optimizations for factoring integers and computing discrete logarithms over finite fields.Costs are estimated both in the abstract circuit model and under plausible superconducting-qubit assumptions.
  • 5 Conclusion: The estimated costs are orders of magnitude lower than previous works with comparable physical assumptions.The comparison covers several cryptographically relevant problems evaluated under the paper’s physical model.
  • 5 Conclusion: The upper end of estimates for factoring RSA-2048 has plausibly fallen since 2015, while the lower end remains sensitive to future advances.Predicting advances in quantum error correction, physical qubits, and circuit construction is outside the paper’s scope.
  • 5 Conclusion: The authors hope the paper informs how quickly post-quantum cryptosystems should proceed toward large-scale deployment.Post-quantum standardization and small-scale deployment experiments are underway, but substantial work remains.

Contributions

The contributions span construction design, RSA cost estimation, comparison assembly, and cryptographic-impact analysis beyond RSA factoring.

  • Contributions: Craig Gidney designed the modular-exponentiation construction, produced initial RSA cost estimates, and assembled comparisons from other papers.Martin Ekerå extended the work to problems beyond RSA factoring and algorithms beyond Shor’s factoring algorithm.
  • Contributions: Martin Ekerå conducted the cryptographic-impact analysis and extended cost estimates to finite-field problems beyond RSA factoring.His extensions also covered algorithms beyond Shor’s factoring algorithm.

A.1 Columns

The appendix defines columns describing abstract logical-qubit usage, measurement depth, magic-state requirements, and minimum expected spacetime volume.

  • A.1 Columns: Abstract Qubits counts logical qubits in the abstract circuit model while excluding distillation and routing qubits.This column measures the circuit-level qubit requirement rather than the full physical implementation.
  • A.1 Columns: Measurement Depth is the longest chain of dependent measurements and determines reaction-limited runtime.These values are not adjusted for the chance of retrying.
  • A.1 Columns: Toffoli+T/2 counts required magic states, with the division by two approximating the lower distillation volume of T states.These values are not adjusted for the chance of retrying.
  • A.1 Columns: Min volume is the minimum expected spacetime cost among serial, parallel, and intermediate realizations, including retries.The estimates use asymptotic formulas and assume negligible retry chances for papers other than this one.

A.2 Entries

The table combines directly reported, hand-inferred, and ancillary-file-derived entries for earlier constructions and the 2019 construction. Its entries record resource metrics including Toffoli counts, abstract qubits, and measurement depth, with some methodological corrections and assumptions.

  • Entry provenance: Table entries come from papers, hand inference, or the ancillary file “fill-in-table.py”.The stated provenance varies by entry.
  • Prior constructions: Zalka 1998 (log add) reports 52n^3 Toffoli+T/2 count, 5n abstract qubits, and 600n^2 measurement depth.These values are attributed to specified sections of the paper.
  • Prior constructions: The comparison includes Zalka, Vedral, Beauregard, Fowler, Häner, Roetteler, and other prior constructions with entries drawn from papers or derived from figures and tables.Some estimates add lg n factors for approximating arbitrary phase rotations using T states.
  • Prior constructions: Fowler et al. 2012’s abstract-qubit entry is corrected from 2n to 3n + O(1) because its table omitted a necessary workspace register.The correction addresses an identified workspace omission.
  • 2019 construction: The 2019 construction’s asymptotic bounds come from Section 2, while specific-size values come from “estimate costs.py”.Its Toffoli count excludes retrying, but its volume is the expected total volume to factor and includes retries.

B.1 Columns

The columns define physical assumptions, execution characteristics, resource counts, and expected completion measures for comparing quantum factoring constructions. Several definitions distinguish hardware constraints from runtime and volume metrics.

  • Physical assumptions: Physical gate error rate is the probability that a physical gate introduces Pauli errors onto targeted qubits.It is a hardware noise parameter.
  • Physical assumptions: Cycle time is the time required to measure all surface-code stabilizers once, while reaction time covers classical control and measurement-basis decisions.Reaction time includes triggering a logical measurement, collecting and correcting its result, and selecting the next basis.
  • Physical assumptions: Physical connectivity specifies which qubits can interact: planar connectivity permits adjacent interactions on a grid, whereas arbitrary connectivity does not impose that restriction.The passage associates planar connectivity with superconducting qubits and arbitrary connectivity with ion traps.
  • Execution and distillation: Distillation strategy records the dominant magic states and the number or type of factories used to distill them.Execution strategy records low-level computation progress, especially addition strategies and their bottlenecks.
  • Resource measures: Physical qubits count hardware usage, expected runtime averages completion time, and expected volume averages physical qubit-rounds until successful completion.The runtime and volume definitions use the original historical assumptions.

B.2 Entries

The entries document how prior and current physical estimates were obtained, including differences in reaction-time treatment, distillation accounting, and execution architecture. The 2019 entries distinguish parallel, single-threaded, and serial implementations.

  • Prior estimates: Van Meter et al. 2009 and Jones et al. 2009 estimates exclude reaction time because their computations are not reaction limited.Their numbers are derived from cited tables and figures.
  • Prior estimates: Fowler et al. 2012’s expected volume is directly comparable to the 2019 estimate because distillation dominates its volume.Under that condition, changing the reaction-time assumption does not affect distillation volume.
  • Accounting adjustments: O’Gorman et al. 2017’s physical-qubit count is increased by approximately 0.13 · 10^8 to include three n-logical-qubit data registers.The original table count of 2.18 · 10^8 included distillation only.
  • Accounting adjustments: Gheorghiu et al. 2019’s reaction time is stated as 0.1 microseconds because 0.2 microseconds would be insufficient for the inferred T-factory rate.The inference concerns chains of dependent Toffolis.
  • 2019 implementations: The 2019 entries use a common basic architecture, with the parallel implementation adding piecewise additions and double-speed lookups and using more factories.Single-threaded and serial distillation variants use fewer factories and omit those additions and lookups.
Loading 1905.09749v3…