⚛️ quantum physics

ECDSA.Fail: Open Autoresearch for Optimizing Elliptic-Curve Point Addition in Shor's Algorithm

This paper introduces "Open Autoresearch," a human-AI collaborative paradigm that successfully optimized reversible secp256k1 point-addition circuits for Shor's algorithm, achieving an 86.1% reduction in spacetime cost and surpassing Google's published efficiency thresholds for breaking ECDSA.

Original authors: Jieyi Long, Theodore Pender, Zhao Huang, Manuel B. Santos, Samrendra Kumar Singh, Bartosz Naskręcki, Bit Wonka, Joe Doyle, Pierre-Luc Dallaire-Demers, Francesco Giannicola, Ruben M. L. Paschoarelli, O

Published 2026-09-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jieyi Long, Theodore Pender, Zhao Huang, Manuel B. Santos, Samrendra Kumar Singh, Bartosz Naskręcki, Bit Wonka, Joe Doyle, Pierre-Luc Dallaire-Demers, Francesco Giannicola, Ruben M. L. Paschoarelli, Oli Freuler, Jackie Chia-Hsun Lee, Vasily Gnuchev, Gopi Kannappan, John Boyer, Xavier Butler, Akash Balasubramani, Jordan Newman, Bereket Dereje, Alexander Hertlein, Robert Kodra, Lucas Levy, Shaan Patel, JT Rose, Matt Zweil, Okechukwu Wisdom, Tarek El-Eter, Edison Lee, Michael Dong, Alan Li, Anto Joseph, Gajesh Naik, Gautham Anant, Soubhik Deb, Justin Drake

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of modern security, many of our digital locks rely on a mathematical puzzle involving points on a curved line. This puzzle is so difficult for today's computers that it protects everything from bank accounts to the digital currency Bitcoin. However, scientists have long known that a future type of computer, one that uses the strange laws of quantum physics, could solve this puzzle much faster than any machine we have now. To understand how close we are to building such a machine, researchers try to estimate the resources it would need. They calculate how many tiny quantum bits, called qubits, and how many complex logical steps would be required to break these locks. These estimates are crucial because they tell us when we must switch to new, unbreakable security systems before the old ones fail.

A new project called ECDSA.Fail has taken a fresh approach to this problem by turning the search for better quantum designs into an open competition. Instead of a single team working in secret, hundreds of people and artificial intelligence agents collaborated to improve a specific part of the quantum code needed to crack the elliptic curve puzzle. The goal was to make the circuit—the blueprint for the quantum computer's actions—as efficient as possible. The researchers measured efficiency by looking at two things: the number of qubits the circuit needed to run at once, and the total number of complex operations it performed. They multiplied these two numbers together to get a single score, where a lower score meant a better, more efficient design.

The results of this open collaboration were striking. The team started with a baseline design that required over two thousand qubits and nearly four million operations. Through a process of continuous improvement, where participants shared their best ideas and AI agents helped test thousands of variations, the group managed to slash the efficiency score by more than eighty-six percent. By the time the data was collected, the best design required only about one thousand one hundred and fifty qubits and roughly one point three million operations. This new record is significantly better than previous estimates from major research groups, including one from Google, which had kept its specific circuit design hidden. The ECDSA.Fail team achieved this by making the circuit smaller and faster, proving that a community of humans and machines working together can solve complex engineering problems faster than isolated experts.

The project did more than just find a better number; it revealed how different strategies work. One group of participants focused on making the circuit as small as possible, squeezing it down to use just eight hundred and twenty-five qubits. While this version used far fewer quantum bits, it required many more operations to run, showing a clear trade-off between space and time. Another group focused on the overall score, balancing the two factors to find the most efficient path. The researchers also built a version of the best design that could work with a more advanced method of running the quantum algorithm, showing that the improvements were not just theoretical but could be adapted for real-world use.

What makes this achievement particularly notable is the method used to reach it. The researchers created a system where anyone could submit a design, and a computer program would immediately check if it worked correctly and calculate its score. This allowed artificial intelligence agents to act as tireless researchers, proposing changes, testing them, and learning from failures without needing constant human supervision. Humans stepped in to guide the overall direction, choosing which ideas to pursue and interpreting the results. The project showed that when a problem can be checked quickly and accurately by a machine, a diverse group of humans and AI can outperform traditional research teams.

The paper also clarifies what these results mean for the future. While the new designs are much more efficient, they are not yet a complete blueprint for a machine that can break current encryption. The circuits tested are just one piece of a much larger puzzle, and the full system would still require massive amounts of error correction and physical hardware that does not exist yet. Furthermore, the designs were tested on a specific set of inputs to ensure they worked, but they are not guaranteed to work perfectly in every single possible scenario. The researchers are careful to state that these are improvements to the theoretical understanding of the problem, not a warning that the locks are about to break tomorrow.

Ultimately, the ECDSA.Fail project serves as a powerful demonstration of how science can evolve when it is open and collaborative. By making the problem public and the results verifiable, the team created a living record of progress that anyone could study. They showed that the path to solving hard problems is no longer just about individual genius, but about building systems where human insight and machine speed can reinforce each other. As the world moves toward a future with quantum computers, this kind of open, transparent research will be essential for understanding the risks and preparing the defenses needed to protect our digital world.

Technical Summary: ECDSA.Fail: Open Autoresearch for Optimizing Elliptic-Curve Point Addition in Shor's Algorithm

1. Problem Statement

The paper addresses the optimization of reversible quantum circuits for elliptic-curve point addition, a critical bottleneck in Shor's algorithm for solving the Elliptic-Curve Discrete Logarithm Problem (ECDLP). Specifically, the challenge focuses on the secp256k1 curve, which underpins Bitcoin and Ethereum.

The primary objective is to minimize a spacetime-inspired cost metric, $S = Q \times T$ , where:

$Q$ : The peak logical qubit width (space).
$T$ : The average executed Toffoli gate count (non-Clifford work).

The benchmark task is to implement a reversible mixed point-addition circuit ( $R \leftarrow R + A$ ) where the accumulator $R$ is quantum data and the addend $A$ is classically specified. The circuit must be "clean" (ancilla qubits return to $|0\rangle$ ) and "phase-clean" (no residual phases) to function correctly within a larger coherent algorithm like Shor's.

2. Methodology: Open Autoresearch

The paper introduces and instantiates a new research paradigm called Open Autoresearch. Unlike traditional research driven by individual specialists or small teams, this approach involves a heterogeneous community of humans and AI agents competing and collaborating via a public leaderboard.

Mechanism: Participants propose circuit modifications to a shared repository. These are evaluated by a machine-checkable evaluator that verifies classical correctness, ancilla cleanliness, and phase cleanliness on a deterministic, submission-dependent test set (derived via Fiat-Shamir hashing).
Process: Verified improvements become public "bases" for further optimization. The process is open, observable, and cumulative, allowing independent human-agent teams to build upon each other's work without prior coordination.
Tools: Participants utilized Large Language Model (LLM) agents (e.g., Claude Code, Codex) for hypothesis generation, code implementation, and debugging, guided by human steering for high-level strategy and domain constraints.

3. Key Contributions

A. The Open Autoresearch Paradigm

The paper formalizes a framework where:

Verifiable Objectives: Problems are defined by efficiently computable, machine-checkable metrics.
Cumulative Search: Independent agents contribute to a shared public record of successes and failures.
Human-Agent Synergy: Humans provide architectural direction and interpret results, while agents handle implementation, repetitive experimentation, and local optimization.
The paper argues this model is effective for frontier optimization problems where evaluation is cheap and reliable.

B. Frontier-Level Circuit Optimizations

The challenge produced significant reductions in resource estimates for secp256k1 point addition. Key architectural innovations include:

Jump-2 Euclidean Algorithm: A retiming of the dialog-GCD (record-and-replay) algorithm that groups consecutive Euclidean steps into macro-steps, reducing the number of comparisons and swaps.
Base-5 Transcript Codec: A compression technique that encodes three Jump-2 symbols (which have only 5 valid states out of 8) into a 7-qubit register instead of 9, significantly reducing the transcript storage required for the reversible replay.
Comparison-Free Ping-Pong Dialog-GCD: A post-cutoff architecture that eliminates full-width magnitude comparisons by using low-bit parity checks and alternating update directions, trading qubit width for reduced Toffoli count.
Register-Shared Extended Euclidean Algorithm (EEA): An aggressive register-sharing strategy (derived from Luo et al. and TrailMix) that packs shrinking remainders and growing Bézout coefficients into shared physical banks, enabling extreme width reduction.
Specialized Arithmetic: Implementation of Karatsuba squaring with pseudo-Mersenne modulo reduction and constant propagation to eliminate redundant operations based on classical inputs.

C. Comprehensive Public Record

The project released a complete, source-auditable history of over 400 promoted submissions, including:

The full trajectory of resource improvements.
A classification of 400 accepted commits by optimization mechanism (e.g., dead-code elimination, register allocation, algorithmic substitution).
Reproducible artifacts allowing independent verification of all reported operating points.

4. Results

Performance Metrics

At the data cutoff (July 26, 2026), the challenge achieved the following:

Baseline: $Q = 2,715$ , $T = 3,960,753$ , $S \approx 10.75$ billion.
Best $Q \times T$ Circuit (8e9c9a2): Reduced to $Q = 1,151$ and $T = 1,299,453$ , yielding $S \approx 1.496$ billion.
- This represents an 86.1% reduction in the score.
- The score is more than 50% lower than the previously reported Google/Babbush et al. operating point (approx. 2.993B).
Best Low-Qubit Circuit (b6f2b0a): Achieved $Q = 825$ (subsequently improved to 813 in a post-cutoff submission) with $T \approx 489$ million.
Post-Cutoff Improvement: A "ping-pong" variant (3616dbf) further reduced the score to $S \approx 1.259$ billion ( $Q=1,321, T=952,707$ ).

Comparison with Prior Work

The best $Q \times T$ circuit lies below the reported operating points of Google/Babbush and Schrottenloher on both the $Q$ and $T$ axes. The paper notes that while the numerical score is superior, formal dominance is precluded by differences in interfaces (the benchmark uses a classical addend, whereas windowed Shor requires a coherent addend) and accounting conventions.

Windowed Compatibility

The authors constructed a windowed-addition-compatible variant of the best-scoring circuit. This variant accepts the addend coherently via QROM, adding 11 qubits and ~29.6% Toffoli overhead. It maintains an empirical success probability of $\hat{p} \approx 0.998$ , resulting in a retry-adjusted proxy score of $\approx 1.961$ billion, still below the Google/Schrottenloher points.

5. Significance and Claims

The paper claims significance in two distinct areas:

Cryptographic Resource Estimation: The results provide the lowest reported numerical $Q \times T$ scores for secp256k1 point addition as of the cutoff. These figures refine the understanding of the logical resources required for a cryptographically relevant quantum computer (CRQC) to break elliptic-curve cryptography, though the paper explicitly states these are not complete fault-tolerant resource estimates (omitting physical error correction, routing, and full Shor integration).
Methodological Validation: The paper presents ECDSA.Fail as the first large-scale demonstration of Open Autoresearch. It provides evidence that:
- A community of humans and AI agents can collectively solve hard optimization problems faster than isolated teams.
- The combination of open sharing, machine-checkable verification, and agent-scale experimentation creates a cumulative research process.
- Human judgment remains essential for steering, interpreting results, and bridging conceptual gaps, while agents excel at implementation and iterative refinement.

The authors maintain a modest stance, emphasizing that the results are operating points on a specific benchmark with finite validation support. They do not claim to have broken secp256k1 or established a definitive "Q-day" timeline, but rather to have provided a transparent, reproducible, and significantly improved baseline for future resource estimation and post-quantum migration planning.