Computing 256-bit elliptic curve discrete logarithms in 26 days on a fault-tolerant trapped-ion quantum computer with 20,000 qubits
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 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· 106 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 secp256k1 in approximately 25.7 days using 19,397 physical qubits with an estimated success probability of 63%.
Related
- Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition
- Towards fault-tolerant quantum computing with optically controlled superconducting qubits
- Below-threshold execution of fault-tolerant ripple-carry addition on a trapped-ion quantum computer
- SynDebug: A Framework to Debug Logic Bugs in Fault-Tolerant Quantum Computing Programs
- Finite-temperature transition-window weights on a fault-tolerant quantum computer: duplex filtering on a thermal purification
BibTeX
@misc{haner2026computing,
title = {{Computing 256-bit elliptic curve discrete logarithms in 26 days on a fault-tolerant trapped-ion quantum computer with 20,000 qubits}},
author = {Thomas Häner and Felix Tripier and Jacob Young and Michael Naehrig and Andrii Maksymov and Safwan Alam and Dmitri Maslov and Matthew Parrott and Yvette de Sereville and Jordan Sullivan and Mark Webster and Nicolas Delfosse and John Gamble and Martin Roetteler},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05625},
eprint = {2609.05625},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05625},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Computing 256-bit elliptic curve discrete logarithms in 26 days on a fault-tolerant trapped-ion quantum computer with 20,000 qubits
AU - Thomas Häner
AU - Felix Tripier
AU - Jacob Young
AU - Michael Naehrig
AU - Andrii Maksymov
AU - Safwan Alam
AU - Dmitri Maslov
AU - Matthew Parrott
AU - Yvette de Sereville
AU - Jordan Sullivan
AU - Mark Webster
AU - Nicolas Delfosse
AU - John Gamble
AU - Martin Roetteler
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05625
UR - https://arxiv.org/abs/2609.05625
AB - 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 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· 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 secp256k1 in approximately 25.7 days using 19,397 physical qubits with an estimated success probability of 63%.
ER -