ECDSA.Fail: Open Autoresearch for Optimizing Elliptic-Curve Point Addition in Shor's Algorithm
quant-ph, cs.CR
Submitted: 2026-09-09
Updated: 2026-09-19
Comments: 62 pages, 10 figures. Project website and latest results: https://ecdsa.fail and source code: https://github.com/Layr-Labs/ecdsafail-challenge
Code: https://github.com/Layr-Labs/ecdsafail-challenge
Project page: https://ecdsa.fail
License: http://creativecommons.org/licenses/by/4.0/
The gist: We propose Open Autoresearch, a paradigm in which humans and AI agents publish evaluator-verified improvements to a public leaderboard.
Terminology
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 about1.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 =0.99809, giving Q times T/ about1.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.
Sources
- A Simple Proof that Toffoli and Hadamard are Quantum Universal
- Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations
- Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits
- Quantum Meets the Minimum Circuit Size Problem
- A new quantum ripple-carry addition circuit
- Brace for impact: ECDLP challenges for quantum cryptanalysis
- DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
- Quantum circuit optimization with deep reinforcement learning
- Quantum resource estimates for computing binary elliptic curve discrete logarithms
- Windowed quantum arithmetic
- Performance Analysis of a Repetition Cat Code Architecture: Computing 256-bit Elliptic Curve Logarithm in 9 Hours with 126133 Cat Qubits
- Flip Graphs for Matrix Multiplication
- Optimized quantum implementation of elliptic curve arithmetic over binary fields
- Rise of conditionally clean ancillae for efficient quantum circuit constructions
- Verifiable Quantum Advantage via Optimized DQI Circuits
- Exact Quantum Circuit Optimization is co-NQP-hard
- Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
- How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates
- Large Language Model Guided Tree-of-Thought
- The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
- Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity