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

• URL: http://arxiv.org/abs/2609.05625v1
• Date: Fri, 04 Sep 2026 18:04:05 GMT
• Title: Computing 256-bit elliptic curve discrete logarithms in 26 days on a fault-tolerant trapped-ion quantum computer with 20,000 qubits
• Abstract summary: We present a proof-of-concept for solving the $256$-bit elliptic curve discrete problem logarithm (ECDLP) on $mathttsecp256k1$.<n>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 $40cdot 106$ Toffoli gates.<n>We conclude that a trapped-ion quantum computer based on our architecture can solve the ECDLP on $mathttsecp256k1$
• Score: 4.46968797829255
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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\%$.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Quantum LDPC codes with design rate 1/5 and good performance below 1000 physical qubits [0.0]
  Constant-rate quantum low-density parity-check (LDPC) codes promise fault-tolerant quantum computation with constant spatial overhead in the limit.<n>We introduce a new family of quantum LDPC codes with design rate $1/5$ and check weight $9$ that approaches the teraquop memory regime per qubit-round with several hundred physical qubits.
  arXiv  Detail & Related papers  (2026-07-30T03:55:43Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Resource analysis of Shor's elliptic curve algorithm with an improved quantum adder on a two-dimensional lattice [7.999752490202695]
  Quantum computers have the potential to break classical cryptographic systems.<n>We propose a carry-lookahead quantum adder that achieves Toffoli depth $log n + loglog n + O(1)$ with only $O(n)$ ancillas.<n>We perform a comprehensive resource analysis of Shor's elliptic curve algorithm on two-dimensional lattices.
  arXiv  Detail & Related papers  (2025-10-27T11:02:10Z)
• Batched high-rate logical operations for quantum LDPC codes [2.722479714583866]
  High-rate quantum LDPC codes reduce memory overhead by densely packing many logical qubits into a single block of physical qubits.<n>We extend this concept to high-rate computation by constructing emphbatched fault-tolerant operations that apply the same logical gate across many code blocks in parallel.
  arXiv  Detail & Related papers  (2025-10-07T17:26:10Z)
• Extractors: QLDPC Architectures for Efficient Pauli-Based Computation [39.98920557126034]
  We propose a new primitive that can augment any QLDPC memory into a computational block well-suited for Pauli-based computation.<n>In particular, any logical Pauli operator supported on the memory can be fault-tolerantly measured in one logical cycle.<n>Our architecture can implement universal quantum circuits via parallel logical measurements.
  arXiv  Detail & Related papers  (2025-03-13T14:07:40Z)
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
  We introduce a multiple-circuit algorithm for a quantum lattice Boltzmann method (QLBM) solve of the incompressible Navier--Stokes equations.<n>The presented method is validated and demonstrated for 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• Performance Analysis of a Repetition Cat Code Architecture: Computing 256-bit Elliptic Curve Logarithm in 9 Hours with 126133 Cat Qubits [0.0]
  Cat qubits provide appealing building blocks for quantum computing. We quantify the cost of a repetition code and provide valuable guidance for the choice of a large scale architecture using cat qubits.
  arXiv  Detail & Related papers  (2023-02-13T19:01:05Z)
• Quantum circuit compilation and hybrid computation using Pauli-based computation [0.0]
  Pauli-based computation (PBC) is driven by a sequence of adaptively chosen, non-destructive measurements of Pauli observables. We propose practical ways of implementing PBC as adaptive quantum circuits and provide code to do the required classical side-processing.
  arXiv  Detail & Related papers  (2022-03-03T16:01:55Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Building a fault-tolerant quantum computer using concatenated cat codes [44.03171880260564]
  We present a proposed fault-tolerant quantum computer based on cat codes with outer quantum error-correcting codes. We numerically simulate quantum error correction when the outer code is either a repetition code or a thin rectangular surface code. We find that with around 1,000 superconducting circuit components, one could construct a fault-tolerant quantum computer.
  arXiv  Detail & Related papers  (2020-12-07T23:22:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.