Shor's Algorithm for ECDLP — Q-Day Prize Submission

Quantum solver for the Elliptic Curve Discrete Logarithm Problem (ECDLP), built for the Q-Day Prize Challenge by Project Eleven. The goal: recover ECC private keys on real quantum hardware using Shor's algorithm.

• Author: Giancarlo Lelli
• Contact: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• Background: Technology leader with 10+ years in enterprise software, full-stack architecture, and cloud-native development. Background in computer science with hands-on experience across .NET, Python, Rust, and Cloud ecosystems. Currently working as Cloud GTM Specialist focused on solution architecture and sales engineering.

Approach

All challenge curves use y^2 = x^3 + 7 over F_p (a = 0, b = 7), matching the secp256k1 family. The solver implements the two-register variant of Shor's algorithm for ECDLP:

1. Prepare counting registers |j>, |k> in uniform superposition (Hadamard)
2. Compute |j>|k>|jG + kQ> via 2t controlled point additions (t = num_counting qubits)
3. Measure the point register, collapsing it to some group element R
4. Apply inverse QFT to the counting registers
5. Measure j, k and extract d from the relation j + kd = r (mod n)

The private key d is recovered by collecting multiple (j, k) samples that satisfy the same linear relation modulo the group order n. The solver supports six oracle strategies for the controlled point additions, selected automatically based on curve size or manually via --oracle.

Oracle Strategies

Strategy 1: Dense Unitary (default for n_bits <= 6)

Used for curves with group order up to ~6 bits. Implemented in projecteleven.py.

Each controlled point addition "add S" is represented as a 2^(n+1) x 2^(n+1) permutation matrix applied via qc.unitary(). The matrix encodes the full group action: the upper-left block is identity (control=0), the lower-right block permutes basis states according to the map P -> P+S (control=1).

• Encoding: Group index (0..n-1)
• Memory: O(2^{2n}) per matrix
• Qubits: 2t + n (two counting registers + point register)
• Limitation: Qiskit's unitary decomposition is O(4^n), making this infeasible beyond ~6-bit

Strategy 2: Efficient Permutation Decomposition (default for n_bits > 6)

Used for larger curves. Implemented in quantum_arithmetic.py.

Instead of building dense matrices, each "add S" permutation is cycle-decomposed into transpositions. Each transposition (swap of two basis states |a> <-> |b>) is implemented with:

1. CNOT reduction -- CNOTs from a pivot bit to all other differing bits, reducing the multi-bit difference to a single-bit difference
2. Multi-controlled X -- An MCX gate on the pivot bit, conditioned on all other bits matching the target pattern
3. Undo CNOTs -- Reverse step 1 to restore the non-pivot bits

The MCX uses V-chain decomposition with (n-2) dedicated ancilla qubits, giving O(n) Toffoli gates per MCX instead of O(n^2) without ancillas. Each controlled addition is built as an isolated sub-circuit and appended as a single opaque gate, avoiding quadratic DAG growth in Qiskit.

• Encoding: Group index (0..n-1)
• Memory: O(N) per addition (N = group order)
• Qubits: 2t + n + (n-2) ancillas
• Gates per addition: O(N * n)

Strategy 3: Coordinate-Based Quantum Oracle (--oracle coordinate)

Available for curves up to ~6-bit. Implemented in quantum_oracle.py.

Instead of encoding points as group indices, the quantum register holds actual (x, y) field-element coordinates in binary plus an identity flag. The point register layout is:

• x_reg: f_bits qubits (f_bits = ceil(log2(p)))
• y_reg: f_bits qubits
• id_flag: 1 qubit (1 = point at infinity)

Each controlled "add S" is computed from the EC addition formula over all valid coordinate encodings, producing a permutation on the coordinate register. This permutation is cycle-decomposed into transpositions using the same CNOT-reduction + MCX infrastructure as Strategy 2.

• Encoding: (x, y, id_flag) coordinates
• Qubits: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) ancillas
• Gates per addition: O(N * f_bits)

Strategy 4: Arithmetic Oracle (--oracle arithmetic)

Framework for polynomial-scaling point addition. Implemented in quantum_oracle.py and quantum_arithmetic.py.

Uses coordinate encoding (same as Strategy 3) with QFT-based modular arithmetic primitives as building blocks toward fully arithmetic point addition. The codebase includes tested implementations of:

• Beauregard modular adder -- QFT-based (target + constant) mod p with proper ancilla uncompute
• Quantum-quantum modular multiply -- |a>|b>|0> -> |a>|b>|a*b mod p> via shift-and-add with explicit modular doubling, O(n^3) gates
• Modular inverse permutation -- |x> -> |x^{-1} mod p> via lookup table transpositions
• Controlled quantum-quantum modular add -- Controlled |a> -> |a + b mod p> with Beauregard reduction

The arithmetic primitives achieve O(n^3) scaling per point addition vs O(N*n) for the permutation approach. However, the QFT-based operations carry a ~150x larger constant factor, making the arithmetic approach more efficient only for curves above ~20-bit group order. For current challenge sizes (up to 12-bit), the permutation-based adder remains faster and is used by default.

Strategy 5: Google Semiclassical Phase Estimation (--oracle google)

Implemented in google_semiclassical.py. Inspired by the qubit-recycled phase estimation technique from Griffiths & Niu (1996), applied at scale in Babbush et al. (2026) for secp256k1 ECDLP resource estimates. The Babbush et al. paper was published on March 30, 2026.

Replaces the two multi-qubit counting registers (j, k) and bulk inverse QFT with two single recycled qubits and classically-conditioned phase corrections. Each counting register bit is processed sequentially: prepare in |+>, apply controlled point addition, correct phase based on all previously measured bits, then measure. The reset + if_test dynamic circuit primitives in Qiskit enable this on IBM Quantum hardware.

The oracle for controlled point additions is delegated to the existing infrastructure (dense unitary for <= 6-bit, efficient permutation for > 6-bit), so the qubit savings come entirely from eliminating the counting registers.

Curve size	Standard qubits	Semiclassical qubits	Savings	Hardware verified
4-bit (n=7)	11	5	55%	Yes
6-bit (n=31)	17	7	59%	Yes
7-bit (n=79)	26 + anc	14	46%	Yes
8-bit (n=139)	25 + anc	10 + anc	60%	No (QPU sync overhead)
10-bit (n=547)	31 + anc	12 + anc	61%	No (QPU sync overhead)

• Encoding: Same as underlying strategy (group index)
• Qubits: 2 + n_bits + ancillas (vs 2t + n_bits + ancillas)
• Trade-off: Requires dynamic circuits (mid-circuit measurement, reset, classically-conditioned gates). Works on IBM Heron r2 up to 7-bit; at 8-bit+ the classical feedback synchronization overhead exceeds the QPU time budget

Strategy 6: Ripple-Carry Modular Addition (--oracle ripple)

Implemented in ripple_carry_shor.py. Uses CDKM ripple-carry adders (Cuccaro et al. 2004) for the controlled point additions, replacing both dense unitary matrices and cycle-decomposed transposition circuits.

In group-index encoding, point P = kG is represented by its index k in the cyclic group. Adding S = sG becomes modular addition of the classical constant s (mod n). The key insight: each controlled point addition reduces to a single controlled modular addition of a known constant, implemented via Qiskit's CDKMRippleCarryAdder and IntegerComparator.