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

AI summary

Overview

Research area: Quantum algorithms and quantum resource estimation for elliptic-curve cryptography, combined with a study of AI-agent-assisted open research organization (the "open autoresearch" paradigm).

Technical level: Advanced. The paper assumes familiarity with Shor's algorithm, reversible/coherent arithmetic, Toffoli-count resource models, elliptic-curve group law, and quantum error-correction cost accounting.

Scope (one sentence): The paper reports how an open, verifier-gated competition (ECDSA.Fail) involving more than one hundred human and AI-agent contributors drove an 86.1% reduction in a spacetime-inspired Q × T score for a reversible secp256k1 point-addition circuit, and describes the resulting circuits, the optimizations behind them, and the organizational model that produced them.

What This Paper Is About

Shor's algorithm can break elliptic-curve cryptography, but only if a quantum computer can run a reversible circuit for elliptic-curve point addition — and the modular inversion inside point addition is the dominant cost. The authors turned the optimization of one such circuit (a mixed point addition on secp256k1) into a public leaderboard challenge where humans and AI agents submit improvements that a machine-checkable evaluator verifies, scoring entries by the product of peak logical qubit width Q and average executed Toffoli count T. The goal is both to push the circuit frontier and to test whether an open, evaluator-gated research model can work on a hard quantum-computing problem.

Key Contributions

1. The Open Autoresearch paradigm. A verifier-gated organizational model in which anyone can participate without formal entry requirements, and humans and AI agents improve a shared objective through a public evaluator, repository, leaderboard, and experimental record. The authors report more than 100 leaderboard contributors and over 400 promoted submissions at the data cutoff, and derive a framework combining parallel search, human steering, verification, shared memory, and evolving agent skills.

2. Frontier-level point-addition circuits. The best circuit at the data cutoff, submission 8e9c9a2, uses Q = 1,151 and T = 1,299,453, for a score of 1.496 B — an 86.1% reduction from the 10.75 B baseline (Q = 2,715, T = 3,960,753), and more than 50% below the reported Google/Babbush et al. operating point of 2.993 B. The authors describe this comparison as contextual rather than formal dominance because interfaces and accounting conventions differ.

3. A coherent windowed-addition-compatible variant. Because the benchmark supplies one addend classically while windowed Shor selects it coherently, the authors build a single-call variant with Q = 1,162 and T = 1,684,161. On 100,000 random inputs its empirical success probability was p̂ = 0.99809, giving a proxy Q × T/p̂ ≈ 1.961 B under a per-call sensitivity model. Post-cutoff, submission 3616dbf further reduced the raw score to approximately 1.259 B (Q = 1,321, T = 952,707).

4. Source-auditable architectures, optimizations, and reproducible evidence. Circuits build on the record-and-replay Euclidean (dialog-GCD) architecture of Khattar et al. and the TrailMix substrate. Documented optimizations include jump-2 Euclidean steps, compressed transcript codecs, ping-pong dialog-GCD, Karatsuba squaring with pseudo-Mersenne modulo, register-shared extended Euclidean inversion, constant propagation, and dead-code elimination. The authors reconstruct the improvement trajectory and Pareto frontier and classify 400 scored source commits by primary optimization mechanism.

Main Findings

• Baseline to cutoff trajectory: The score fell from 10.75 B (Q = 2,715, T = 3,960,753) to 1.496 B (Q = 1,151, T = 1,299,453) at the data cutoff of 26 July 2026, 09:21:55 UTC — an 86.1% reduction, exceeding 50% below the reported Google operating point of 2.993 B.

• First sub-million-Toffoli result: Submission 3616dbf, introduced after the cutoff, used a comparison-free "ping-pong" GCD technique to reach Q = 1,321 and T = 952,707, a score of approximately 1.259 B and a 15.9% reduction relative to the cutoff incumbent. It was the first result reported with fewer than one million average executed Toffoli gates.

• Low-width regime: The best low-Q submission at the cutoff, b6f2b0a, used 825 qubits. A later submission, b4a51d2, reported 813 qubits, which is 22 qubits below Luo et al.'s 835-qubit result.

• Correctness of the windowed variant: The coherent windowed-addition-compatible variant achieved p̂ = 0.99809 over 100,000 random inputs, yielding the retry-adjusted proxy Q × T/p̂ ≈ 1.961 B. On a separate longitudinal sample of 50,000 pseudorandom inputs, the retry-adjusted score closely tracked the raw score because p̂ stayed near one.

• Comparison caveats: The circuits' reported Q and T both lie below the Google and Schrottenloher operating points, but differing interfaces and accounting conventions preclude formal dominance. The benchmark supplies one addend classically; windowed Shor selects it coherently.

• Score limitations: The score omits Toffoli depth and parallelism, so circuits with identical Q and T score equally even when their schedules differ. It is a width–work proxy, not a physical-resource estimate, and omits routing, memory access, error-correction overhead, and architecture-specific costs.

• Window schedule arithmetic: For n = 256 and window size w = 16, windowing reduces the conceptual schedule from 512 bitwise additions to 32 windowed additions; direct initialization and classical postprocessing reduce the implemented estimate to 28 point-addition calls, each using tables with 2^16 entries, with an added QROM cost of 3 · 2^w Toffolis per retained windowed addition.

• Agents complemented human judgment: The public record shows AI agents contributing alongside human participants, which the authors present as evidence for open autoresearch on efficiently evaluable, machine-checkable objectives.

Methodology in Plain English

The authors defined a single, precisely measurable target: a reversible circuit that adds a classically known point to a quantum accumulator on secp256k1, scored as Q × T (peak logical qubits times average executed Toffolis). A public evaluator checks every submission automatically. Crucially, the circuits belong to a restricted "kickmix" class — built only from reversible permutation gates (X, CNOT, Toffoli), diagonal phase gates (Z, CZ, CCZ), and mid-circuit X-basis measurement with classically conditioned phase corrections. Because no operation in this class spreads a basis state into dense entanglement, the evaluator can verify value correctness, ancilla cleanliness, and phase cleanliness on every test input rather than sampling or trusting the submitter. Cleanliness matters because a circuit inside a larger coherent algorithm must return every ancilla to |0⟩ and leave no residual phase.

On the algorithmic side, the team worked within the standard reversible point-addition blueprint, where the modular inverse — implemented as an unrolled, input-oblivious GCD iteration that must later be uncomputed — dominates cost. Reductions came from restructuring that GCD (jump-2 steps, dialog-GCD record-and-replay, and eventually a comparison-free ping-pong variant), compressing the transcripts exchanged between phases, sharing registers during inversion, and replacing expensive squaring with Karatsuba plus pseudo-Mersenne reduction. The windowed-compatible variant additionally uses the standard lookup → use → unlookup pattern (QROM) so the addend is materialized from a quantum window index and then uncomputed.

Organizationally, the project ran as an open competition with no formal entry requirements. Independent teams using heterogeneous models and workflows submitted improvements to a common leaderboard, and verified improvements became the foundation for further work while documented failures remained reusable evidence. The authors then reconstructed the full trajectory, Pareto frontier, and low-width branches, and classified 400 scored source commits by what optimization they primarily introduced, distinguishing invention from rediscovery. They also release circuit sources, submission histories, frozen leaderboard data, operating-point manifests, and reconstruction procedures.

Why This Matters

The work bears on how soon a cryptographically relevant quantum computer might threaten deployed public-key cryptography, since that timing depends partly on the logical resources Shor's ECDLP circuit requires. secp256k1 is the curve behind Bitcoin and Ethereum transaction authorization, so concrete resource estimates for this specific curve carry direct economic weight: a machine able to solve ECDLP could recover private signing keys from exposed public keys and forge signatures. Policy timelines already assume migration is urgent — the initial public draft of NIST IR 8547 proposes deprecating classical public-key algorithms at the 112-bit security level after 2030 and disallowing them after 2035, and U.S. federal guidance calls for migrating digital signatures in sensitive federal systems by 2031.

Beyond cryptography, the paper is a test of a research-organization model: can a public, verifier-gated leaderboard with human and AI-agent participants push a frontier problem faster than a small expert team? The authors argue the combination of openness and observability — a public sequence of verified, attributable steps — may generalize to other problems with efficiently verifiable objectives.

Real-world applications and relevance:

• Blockchain and custody security: Informing key-rotation, address-migration, and post-quantum upgrade planning for secp256k1-based systems such as Bitcoin and Ethereum.
• Standards and regulatory planning: Providing circuit-level inputs to bodies setting deprecation deadlines for classical public-key algorithms.
• Hardware and architecture roadmaps: Grounding physical-qubit estimates — for example, Cain et al.'s figure of as few as 10,000 physical qubits for a P-256 discrete logarithm in a neutral-atom architecture with qLDPC codes, or roughly 26,000 for a days-scale attack, and Dallaire-Demers et al.'s 2027–2033 window for a full 256-bit instance under explicit hardware and error-correction assumptions.
• AI-assisted research tooling: A documented case study for deploying off-the-shelf coding agents against machine-checkable objectives, with provenance auditing.

Industry relevance spans cryptography vendors, blockchain foundations and infrastructure teams, quantum-hardware companies producing resource estimates, and organizations building automated research pipelines.

Future Directions

• Completing the full windowed Shor instantiation. The paper states that instantiating the complete 28-call window schedule, all shifted tables, the Fourier transforms, and the classical postprocessing remains future work; only the point-addition kernel and one coherent single-call variant are implemented and evaluated here.

• Richer cost metrics than Q × T. Because the score ignores Toffoli depth and parallelism, circuits with equal Q and T can have very different schedules. Finer-grained alternatives named in the paper include Toffoli depth, active-volume models, and architecture-specific gate schedules.

• Reconciling comparisons across interfaces. The authors flag that differing interfaces and accounting conventions — classical versus coherent addend supply, and different accounting rules — prevent formal dominance claims against the Google and Schrottenloher operating points, leaving a clear open problem in standardized benchmarking.

• Testing whether open autoresearch generalizes. The paradigm is proposed for other problems with efficiently verifiable objectives; whether it transfers beyond circuit optimization, and how much of the progress is attributable to agents versus human steering, remain open questions the public record is intended to let others analyze.

Target Audience

Quantum-computing researchers working on Shor's algorithm, reversible arithmetic, and resource estimation; cryptographers and security engineers tracking post-quantum migration for secp256k1 and ECDSA-based systems; blockchain infrastructure and protocol teams planning key and address migration; quantum-hardware architects converting logical resource counts into physical machine sizes; and researchers studying AI-agent-driven and open/crowdsourced models of scientific research who want a documented, machine-checkable case study with a public commit-level record.

Authors’ abstract

We propose Open Autoresearch, a paradigm in which humans and AI agents publish evaluator-verified improvements to a public leaderboard. We instantiate it in ECDSA.Fail, optimizing reversible secp256k1 point-addition circuits, a bottleneck in Shor's algorithm for elliptic-curve cryptography. The benchmark minimizes the spacetime-inspired score $S=Q\times T$, where $Q$ is peak logical qubit width and $T$ is average executed Toffoli count. Participants reduced $S$ by 86.1%. At the data cutoff (26 July 2026), the best-scoring circuit uses 1,151 qubits and 1,299,453 average executed Toffoli gates, giving $Q\times T\approx1.496$ billion. This is more than 50% below Google's published point-addition score thresholds (arXiv:2603.28846), under different accounting conventions. Because the benchmark supplies one addend classically, we construct a coherent windowed-addition-compatible variant implementing the single-call interface required by windowed Shor. It uses 1,162 qubits and 1,684,161 average executed Toffoli gates. On 100,000 random inputs, its empirical success probability is $\hat{p}=0.99809$, giving $Q\times T/\hat{p}\approx1.961$ billion under an independently rerunnable per-call sensitivity model, not a full-Shor success estimate. Its qubit and Toffoli counts lie below Google's published thresholds and Schrottenloher's reported operating points (arXiv:2606.02235), although differing interfaces, accounting conventions, and validation scope preclude formal dominance. After the cutoff, the score was further reduced to 1.259 billion, while a separate low-width circuit reached 813 qubits. The public record shows AI agents complementing human judgment, providing evidence for open autoresearch on efficiently evaluable, machine-checkable objectives.