Computing 256-bit elliptic curve discrete logarithms in 26 days on a fault-tolerant trapped-ion quantum computer with 20,000 qubits

AI summary

Overview

Research area: Quantum computing — fault-tolerant quantum architecture design, quantum resource estimation, and cryptanalysis of elliptic curve cryptography.

Technical level: Advanced. The paper assumes familiarity with Shor's algorithm, elliptic curve arithmetic, quantum error-correcting codes (including quantum LDPC codes), magic-state distillation, and compilation/routing for fault-tolerant hardware.

Scope (one sentence): The paper presents an end-to-end, ECDLP-specialized design of a trapped-ion quantum computer based on the "Walking Cat Architecture," compiling Shor's algorithm for secp256k1 down to architecture-legal measurement schedules and concluding that about 19,397 physical qubits could solve the problem in roughly 25.7 days per attempt.

What This Paper Is About

Shor's algorithm can in principle break elliptic curve cryptography, but the practical question is how many physical qubits and how much time a real, fault-tolerant machine would need. Earlier estimates for trapped-ion hardware put the cost of solving the 256-bit ECDLP on secp256k1 (the curve used by Bitcoin) between 1.2 million and 9.4 million qubits. This paper designs a specialized trapped-ion architecture, an optimized logical circuit, and a full compiler toolchain to show that approximately 20,000 physical qubits and about 26 days per attempt would suffice — roughly a 60-fold to 480-fold reduction in qubit count relative to those earlier trapped-ion estimates.

Key Contributions

1. A complete trapped-ion architecture for the ECDLP. The authors describe a detailed design compatible with the Walking Cat Architecture, including all logical operations, quantum error-correcting codes, error-correction circuits, and a compiler. They state that, to their knowledge, it is the first ECDLP architecture for trapped ions based on quantum LDPC codes.

2. A reduced logical circuit. They lower the Toffoli count of Schrottenloher's circuits from 2^25.78 ≈ 58 million to 39 million Toffoli gates at 1,457 logical qubits, using conditionally-inverted additions in place of controlled additions and a modular squarer for pseudo-Mersenne primes built on a single Karatsuba split and a squarer-specific optimization of Litinski's non-modular multiplier.

3. Rigorous success-probability bounds. They derive bounds on the failure probability of the whole algorithm that account for approximation errors in both phase and computational basis, using random offset masks. The resulting bound on the failure probability of the 28 point additions, p_f ≤ 0.0335, holds with confidence at least 1 − 2^−128, combined with a Monte Carlo bound for the in-place multiplications and exactly computed bounds for the remaining components.

4. Architecture-level speed and qubit reductions. They introduce a fast CCZ magic-state factory and a depth-one CCZ injection, reducing CCZ gate execution time by a factor of 31 (a Toffoli gate time of 29.5 ms); a more efficient loss-correction protocol that removes the need for beacon qubits; recycling of CliNR ancilla qubits requiring only 4 extra Q102 blocks rather than two per memory block; and reusable cat-state resources provisioned to the circuit's peak measurement parallelism.

Main Findings

• Headline resource estimate: A trapped-ion quantum computer based on this architecture would solve the ECDLP on secp256k1 in approximately 25.7 days using 19,397 physical qubits, with an estimated success probability of 63% (63.3% using Ekerå's heuristic estimate).
• Runtime accounting: The total expected runtime is 616.555 hours (25.690 days) over 75,251,329 measurement layers at 0.02950 s per measurement layer. The largest single contributor is in-place multiplication at 376.691 hours, followed by unary lookup at 179.686 hours.
• Success probability, two ways: Starting from Mosca's rigorous lower bound (p_S ≈ 0.657) gives a lower bound on single-run success of 0.553 absent logical errors, or 40.7% including the 26.45% logical-error probability. Starting from Ekerå's heuristic p_S = 0.99 gives an estimate of 0.861 absent logical errors, or 63.3% end-to-end.
• Parallel repetition: Assuming independent failures and the 63.3% single-shot estimate, running on five identical devices in parallel raises the probability that at least one succeeds to 1 − (1 − 0.633)^5 = 99.3% without increasing wall-clock runtime.
• Why naive T-state magic factories fail: The circuit consumes 273 million T states (assuming the seven-T exact Toffoli implementation rather than four-T relative-phase constructions). The baseline factory's best logical error rate of 7·10^−8 is insufficient; the new two-level factory produces magic states with logical error rate below 10^−9.
• Naive timing is far too slow: With sequential T injection, a CNOT averages about 90 ms and a Toffoli at least 910 ms, implying 411 days total. The optimized design achieves 29.5 ms per Toffoli — faster by a factor of 31.
• Magic-state supply keeps pace: Four Toffoli factories consuming 1,276 = 4·319 qubits produce Toffoli states with an average production time under 28 ms, providing continuous flow.
• Code choice drives qubit count: A distance-9 surface code would need 243,000 qubits to store the logical qubits (excluding operations and factories); code Q70 would need 55,000 qubits in 250 memory blocks; code Q102 encodes 22 logical qubits into 102 data qubits and brings storage to about 20,000 qubits. Naively making CliNR available per Q102 block would need two extra blocks per memory block — 40,000 extra qubits — whereas pipelining reduces this to 4 extra blocks, a reduction of 39,200 qubits.
• Removing beacon qubits: The improved loss and leakage model plus a new correction unit eliminate beacon qubits, removing about one third of the qubits in each memory block.
• Routing overhead: Integrated routing — merging cross-block routing between components into those components — reduces routing overhead to 5% of total runtime.
• Conservative choices: The 69 memory blocks are all assumed active throughout, and every logical measurement is charged as long as a Toffoli injection, making the reported runtime a conservative upper bound.

Methodology in Plain English

The researchers start from an existing general-purpose trapped-ion design (the Walking Cat Architecture), in which ions are shuttled around a 2D grid to create long-range connections — this is what makes dense quantum LDPC codes usable instead of surface codes. They assume two-qubit gate noise of 10^−4 and single-qubit noise of 10^−5, both demonstrated or within reach experimentally.

On the algorithmic side, they take Schrottenloher's circuits for double-scalar multiplication and change two things: they rewrite controlled modular additions as conditionally-inverted additions (roughly half the non-Clifford cost), and they build a modular squarer tailored to secp256k1's pseudo-Mersenne prime using one Karatsuba split.

To handle the fact that these circuits are approximate and occasionally produce wrong outputs or −1 phases, they add randomly sampled offset masks to the accumulator's starting point and to the lookup tables. Because a fresh mask is sampled each run, they can bound the failure probability for any fixed input pair and translate it into a success-probability bound for the whole algorithm.

On the architecture side, they replace T-state factories with a two-level factory that produces CCZ states directly in a quantum LDPC code, plus a depth-one CCZ injection circuit (CCZ and Toffoli are locally Clifford-equivalent, so this implements Toffoli gates). They use parallel non-overlapping cat-based measurements to raise logical-measurement parallelism, use the logical CliNR protocol to speed up Clifford operations, and pipeline CliNR so that only 4 extra Q102 blocks are needed.

Finally, they implement a compiler that lowers each arithmetic component to an executable, architecture-legal measurement schedule with routing included and exact depth counts, rather than counting gates in the abstract. They also account for effects often ignored in atomic-qubit estimates: qubit transport, leakage, loss, and qubit reloading, and derive logical operation times from an explicit syndrome extraction circuit structure rather than assuming a fixed 1 ms.

Why This Matters

Impact on research. Resource estimates are the field's standard yardstick for progress. The paper reports that physical qubit counts for factoring 2048-bit numbers have fallen three to four orders of magnitude since 2012, and it positions its own result within a similar trajectory for the ECDLP, from 6·10^9 gates in 2003 to 200·10^6 Toffolis in 2023 to 84·10^6 Toffolis in 2026. Its distinctive move is to go beyond gate counting: it compiles every charged component, includes measurement and routing costs, and models transport and loss, which changes the picture substantially compared with Toffoli-only accounting.

Real-world applications (as motivated by the paper's focus):

• Assessing the quantum security of Bitcoin and other blockchain systems that rely on secp256k1.
• Informing migration timelines for organizations that must transition away from elliptic curve cryptography.
• Providing a template for architecture-application co-design, in which a hardware design is specialized and optimized for one dominant workload.
• Setting benchmarks that other hardware modalities (neutral atoms, superconducting circuits) can be compared against on the same problem.

Industry relevance. All authors are affiliated with IonQ Inc., so the paper is simultaneously a scientific resource estimate and a hardware roadmap argument: it identifies concrete engineering targets (10^−4 two-qubit noise, 10^−5 single-qubit noise, shuttling-based connectivity, dense LDPC codes) at which a specific, commercially relevant cryptanalytic task becomes feasible on a trapped-ion machine.

Future Directions

• Exploiting more classical postprocessing. The authors note that removing additional phase-estimation windows, or running more instances (possibly in parallel), could shrink the per-instance quantum circuit; they deliberately forgo this to ease comparison with prior work.
• Heterogeneous adder selection. The compiler currently uses a single adder family throughout; switching between width-optimized and depth-optimized adders according to available scratch space and runtime could reduce cost.
• Dynamic device reconfiguration. The configuration is fixed for the whole computation; dynamically reallocating qubits between memory and gate resources is left open.
• Tighter bounds and less conservative accounting. The runtime is an upper bound because every logical measurement is charged as long as a Toffoli injection, and the success-probability lower bound assumes all 69 memory blocks stay active throughout. Relaxing these assumptions is a route to improved estimates.

Target Audience

This paper is written for quantum-computing researchers and engineers working on fault-tolerant architectures, quantum error correction, and compilation, as well as for cryptographers and security analysts who need concrete quantum resource estimates for elliptic curve cryptography. It is most useful to readers already comfortable with Shor's algorithm and stabilizer codes; readers seeking a plain introduction to quantum cryptanalysis will find the density of architectural detail demanding, though the headline numbers and the discussion of why the naive approach falls short are accessible to a broader technical audience.

Authors’ abstract

One of the strengths of our recently proposed Walking Cat Architecture for a trapped-ion quantum computer is that it is straightforward to extend and optimize for a specific application. As a proof-of-concept, here we present such optimizations for solving the $256$-bit elliptic curve discrete logarithm problem (ECDLP) on $\mathtt{secp256k1}$, which is the elliptic curve used by blockchain technologies such as Bitcoin, using Shor's algorithm. We optimize the circuits from Schrottenloher's recent work and arrive at a logical quantum circuit for solving the ECDLP using about $1450$ qubits and $40\cdot 10^6$ Toffoli gates, with a rigorous lower bound on the logical-level success probability that holds with confidence at least $1-2^{-128}$. Using our compilation toolchain with manual optimization of the logical layout and integrated routing, we produce estimates for the logical measurement depth and the required number of physical qubits by compiling all components to measurement schedules that obey the architectural constraints. A key ingredient is a fast CCZ magic-state factory and a depth-one CCZ state injection, reducing the execution time of CCZ gates by a factor of $31$. We increase the logical-measurement parallelism using non-overlapping cat-based measurements in parallel, and we leverage the recently proposed logical CliNR protocol to speed up Clifford operations. To reduce the qubit overhead, we introduce a more efficient loss correction protocol, design a layout that allows us to recycle the CliNR ancilla qubits, and provision reusable cat-state resources according to the circuit's peak measurement parallelism. All results and optimizations combined, we conclude that a trapped-ion quantum computer based on our architecture can solve the ECDLP on $\mathtt{secp256k1}$ in approximately 25.7 days using 19,397 physical qubits with an estimated success probability of $63\%$.