Open Autoresearch Cuts ECDSA Circuit Spacetime Score

Breaking elliptic-curve cryptography with Shor's algorithm depends on much more than asymptotic quantum complexity: reversible arithmetic circuits must fit within realistic logical-qubit and gate-count budgets. Elliptic-curve point addition is a central cost in that arithmetic. ECDSA.Fail turns one such circuit-design problem into a public, machine-checked optimization task, asking participants to minimize peak logical width times average executed Toffoli count rather than arguing over improvements that cannot be independently evaluated.

Core Contribution

The paper's primary contribution is Open Autoresearch: a workflow in which proposed circuit changes are admitted through an evaluator, published on a leaderboard, and accumulated as a public record. Its first instance, ECDSA.Fail, targets reversible secp256k1 point addition with one addend supplied classically. The benchmark score is $S = Q \times T$, where $Q$ is peak logical-qubit width and $T$ is the average number of executed Toffoli gates. That objective exposes a real engineering trade-off: reducing width can increase arithmetic work, while a gate-saving construction can require more workspace.

The distinction from a conventional circuit paper is consequential. The authors do not present a single fixed design as the endpoint; they build an evaluation interface under which many contributors can submit changes and retain only improvements that satisfy the benchmark. The resulting record is evidence about a collaborative search process as well as about one circuit family.

Technical Approach

The challenge evaluates reversible point-addition circuits for the secp256k1 curve. Its principal interface takes advantage of a classical addend, which makes it cheaper than the coherent operation needed inside a complete quantum algorithm. To connect the leaderboard result to Shor-style use, the authors also construct a coherent windowed-addition-compatible variant implementing the required single-call interface.

That second construction is the more relevant sanity check for cryptanalytic interpretation. The paper reports 1,162 qubits and 1,684,161 average executed Toffoli gates for it, then samples 100,000 random inputs to estimate whether the circuit succeeds under the evaluated conditions. The reported empirical probability is $\hat{p}=0.99809$, and the authors use a per-call sensitivity adjustment, $Q \times T / \hat{p}$, rather than presenting it as a full end-to-end Shor success probability. This separation is appropriate: a locally tested arithmetic primitive is not equivalent to a fault-tolerant resource estimate for an entire attack.

Results and Analysis

At the 26 July 2026 cutoff, the best challenge circuit used 1,151 logical qubits and 1,299,453 average executed Toffoli gates, for $Q \times T \approx 1.496$ billion. This improves on the reported 10.75 billion baseline by 86.1%. Figure 1 traces that descent and places the published Google/Babbush operating point of 2.993 billion on the same score axis. The numerical gap is substantial, but the paper correctly treats the external point as context rather than a directly interchangeable benchmark because the interfaces and accounting conventions differ.

The Pareto view matters because the minimum product is not the only usable design. Figure 2 plots challenge submissions by qubits and Toffolis, distinguishing admitted Pareto points from other submissions and showing external Google/Babbush and Schrottenloher reference points. The coherent variant's adjusted score is about 1.961 billion under the stated per-call model. Its reported qubit and Toffoli counts are below the cited published thresholds and operating points, but that is a comparison of resource counts under non-identical methods, not proof that it dominates prior estimates.

The strongest result is therefore narrower than a claim that ECDSA is now practically broken: evaluator-verified circuit search materially improved this particular arithmetic benchmark. The post-cutoff record of 1.259 billion and a separate 813-qubit design suggest that the objective still has room for movement. For circuit engineers, the benchmark offers a reproducible target and a visible qubit–Toffoli trade-off; for cryptanalytic resource estimators, it supplies improved components that still need integration into a full algorithmic and fault-tolerance accounting.