Efficient Record-and-Replay Arithmetic for Quantum Elliptic-Curve Point Addition

AI summary

Overview

Research area: Quantum algorithms and reversible circuit design for elliptic-curve cryptography — specifically, resource-efficient arithmetic for Shor's algorithm against the secp256k1 curve's discrete logarithm problem.

Technical level: Advanced. The paper assumes familiarity with reversible/coherent quantum arithmetic, the extended Euclidean algorithm, base-5 encoding, windowed scalar multiplication, and Toffoli-count-based resource models. The prose is readable but the subject matter is specialist.

Scope (one sentence): The paper presents and empirically evaluates two record-and-replay GCD architectures (Jump-2 and ping-pong) for reversible modular inversion inside quantum secp256k1 point addition, together with their adaptation to quantum-addressed windowed lookup, a targeted repair, and cautious comparison against prior resource estimates.

What This Paper Is About

Shor's algorithm for the elliptic-curve discrete logarithm problem repeatedly adds elliptic-curve points, and the most expensive part of each addition is a modular inversion: computing λ = (y_R − y_A)(x_R − x_A)^(−1) mod p. Doing that inversion reversibly, without keeping full-width Bézout coefficients alive, is what makes the circuit large.

The "record-and-replay" trick records the decisions of a binary GCD run into a small quantum transcript, then replays those decisions to update field-valued registers. This paper asks how to make that record-and-replay step cheaper in both qubits and Toffoli gates, and it reports results from circuits developed through the public ECDSA.Fail challenge.

Key Contributions

1. Compressed record-and-replay GCD (Jump-2). Consecutive binary-GCD operations are grouped into larger reversible steps, and their control decisions are compressed using a base-5 transcript encoding. The 261-step Jump-2 schedule needs 609 transcript qubits, computed as 2 + 86 × 7 + 5, since three symbols (each one of five reachable values) pack into 7 qubits because z < 125 < 2^7. With in-place register reuse and secp256k1-specialized arithmetic, this yields the historical mixed-addition operating point of 1,151 logical qubits and 1,299,453 mean executed Toffolis.

2. A comparison-free ping-pong GCD. Instead of comparing full-width operands and performing data-dependent swaps, the circuit alternates which register is updated on a fixed schedule and records one bit per round indicating whether to add or subtract. The paper proves (Lemma 1) that each round is reversible, preserves odd operands, and preserves the GCD. At matched correction width, an isolated inverse-replay cell uses 393 rather than 446 static Toffolis, with one additional workspace qubit. In a controlled backend comparison that fixes the Karatsuba square and disables post-emission optimization passes, ping-pong saves 340,442 static Toffolis while increasing width from 1,150 to 1,321 qubits.

3. Fused replay and windowed adaptation. Doubling and signed addition are combined into a single modular correction during replay. Both constructions are adapted to an interface where a quantum address selects a point from a classically precomputed table, with measurement-based uncomputation clearing temporary lookup data. This cleanup reduces mean executed Toffolis by 9.56% for Jump-2 and 12.50% for ping-pong without increasing peak width.

4. Validation, targeted repair, and stated scope. A three-circuit frozen study tests 100,000 fresh inputs across nine lookup-table configurations. A separate targeted repair removes the tested zero-payload and zero-slope failures at 1,419 qubits and 1.356 million mean executed Toffolis, with no detected failures on another frozen 100,000-input study. The paper also gives conditional coherent-error analysis and reversible safegcd reference comparisons, while explicitly stating that the results concern individual window-selected additions, not complete Shor computations.

Main Findings

• Transcript compression has a concrete cost model. Jump-2's 261-step schedule occupies 609 transcript qubits via 86 seven-qubit blocks plus one five-qubit block and a two-qubit special initial step; the encoding uses workspace released as the Euclidean operands shrink and decodes one block at a time during reverse replay.
• Ping-pong trades transcript length for cheaper updates. It uses 704 rounds and stores one transcript qubit per round — longer than the 609-qubit Jump-2 transcript — but avoids multi-bit symbol decoding and eliminates full-width comparisons and data-dependent swaps.
• The savings come from simpler value updates and replay arithmetic, according to the source-level resource accounting, rather than from a single dominant trick.
• Lookup cleanup is measurably beneficial. Measurement-based uncomputation of quantum-addressed table data cuts mean executed Toffolis by 9.56% (Jump-2) and 12.50% (ping-pong) with no peak-width increase.
• The repaired circuit passes finite-sample testing only. No failures were detected on 100,000 fresh inputs, but the paper states that explicit supported inputs still violate the round and width schedules, and that passing cls/anc/pha checks is finite-sample evidence rather than an all-input proof.
• Comparison against prior work is contextual, not a dominance claim. Under the leading-order window allowance used in external studies, the repaired circuit's qubit width and counted work fall below Schrottenloher's low-gate construction and Google's published low-gate caps, but differing interfaces, correctness evidence, and resource-accounting conventions preclude formal dominance.
• The official evaluator uses 9,024 pseudorandom inputs derived from a SHAKE256 hash of the serialized circuit, checking correct affine output, clean ancillas, and absence of unwanted relative phase.
• The score is S = Q × T (peak logical width times mean executed Toffolis), which the paper notes omits routing, parallelism, error correction, and architecture-dependent costs.
• The challenge record is observational. Over the first eight weeks, more than one hundred participants and four hundred promoted submissions were involved, but the paper states this record does not isolate the causal contribution of AI agents.

Methodology in Plain English

The researchers start from the standard in-place point-addition pipeline: form the two coordinate differences, invert the x-difference to get the slope, square and multiply to produce the new coordinates, and uncompute temporaries. The inversion is done with an extended Euclidean algorithm, but instead of carrying Bézout coefficients through the whole computation, the circuit first runs a binary GCD on the pair (p, x) and records the decisions it made into a small register, then replays those decisions on field elements to obtain the inverse (or, run backwards, a product). Because the input can be in superposition, every branch must be coherent and later undone.

Jump-2 attacks the record size: it merges two halvings into one recorded step, notes that only five combinations of the three decision bits are reachable, and packs three such symbols into 7 qubits using base-5 arithmetic. Ping-pong attacks the update cost: it only looks at the second-least-significant bit of each operand, adds when the residues mod 4 agree and subtracts otherwise, then halves — the result is always odd, so the walk stays valid without comparisons or swaps, at the price of one transcript bit per round.

Both are then adapted so a quantum address can select an elliptic-curve point from a classical table, with measurement-based uncomputation clearing the lookup data. Evaluation separates source-level static changes from sampled execution: a three-circuit frozen study on 100,000 fresh inputs across nine lookup-table configurations, a targeted repair, an independently seeded 100,000-input validation, and controlled backend ablations that hold other components fixed.

Why This Matters

Impact on research. The paper provides an unusually candid accounting of an empirical, leaderboard-driven circuit-optimization effort: it separates static gate counts from sampled execution means, warns that nonce search can change the circuit hash and thus the validation set, and refuses to claim formal dominance over prior constructions. It also documents a concrete alternative to comparison-based Euclidean control flow in reversible arithmetic.

Real-world applications:

• Cryptanalytic resource estimation for ECDSA-secured blockchains and wallets, where secp256k1 is the dominant curve.
• Setting realistic qubit and gate budgets for post-quantum migration planning and cryptographic risk assessment.
• Benchmark design for open, reproducible quantum-circuit optimization challenges with shared evaluators and leaderboards.
• Methodology for quantum resource accounting, particularly the separation of correctness evidence from gate-count claims.

Industry relevance. The author list spans Ethereum Foundation, Starknet Foundation, StarkWare, Eigen Labs, Brevis, Sei Labs, Theta Labs and others — a sign that blockchain teams treat quantum resource estimates for secp256k1 as operationally relevant. The ECDSA.Fail challenge model (shared evaluator, public leaderboard, human–agent teams) is also a template for industrial research collaboration.

Future Directions

• Extending from single additions to full Shor computations. The paper explicitly limits its claims to individual window-selected additions; end-to-end resource estimates including error correction, routing, and parallelism remain open.
• Stronger correctness guarantees. The conditional coherent-error composition bound and the finite-sample validation leave open a proof covering all supported inputs, including the stated round- and width-schedule violations and the unfiltered R = −2A case.
• Fair, unified comparison with safegcd and prior low-gate constructions. The full-width references use shared payload primitives but do not establish a resource advantage over optimized reversible safegcd, and safegcd's termination bound does not apply to ping-pong — so a matching termination analysis is needed.
• Attribution and reproducibility in human–AI research. The paper notes that the observational challenge record cannot isolate an agent advantage; controlled experiments separating human and agent contributions would address this.

Target Audience

Quantum-algorithm researchers working on reversible arithmetic and cryptanalytic resource estimation; cryptographic engineers and protocol designers assessing quantum risk to secp256k1-based systems; and practitioners of open, benchmark-driven quantum circuit optimization who want a careful example of how to report empirical results without overclaiming.

Authors’ abstract

We study reversible secp256k1 point-addition circuits developed through ECDSA.Fail for Shor's elliptic-curve discrete-logarithm algorithm. Two complementary constructions improve record-and-replay GCD arithmetic: Jump-2 groups binary-GCD steps and compresses their decisions using base-5 encoding, while ping-pong uses fixed register alternation and one-bit decisions to avoid full-width comparisons and data-dependent swaps. Fused replay combines doubling and signed addition into one modular correction. Both constructions support quantum-addressed window selection with measurement-based lookup cleanup. We compare three circuits on 100,000 fresh inputs across nine lookup-table configurations. A separately tested repair uses 1,419 qubits and 1.356 million mean executed Toffolis, with no detected failures on another 100,000 inputs. Structured supported-input counterexamples remain, so these tests do not establish all-input correctness. We also provide conditional coherent-error analysis and reversible safegcd comparisons. Under the stated window allowance, repaired-circuit resources lie below Google's low-gate caps and Schrottenloher's low-gate estimates, but differing accounting and correctness evidence preclude formal dominance. The results concern individual window-selected additions, not complete Shor computations.