Fewest Toffoli gates for elliptic-curve point addition

Task

Each instance fixes the elliptic curve y² = x³ + 7 over the prime field F_p, with p = 11, 251 or 4,093 (the ranked prime), and asks for a circuit that adds a point Q to a point P held in qubits, for every promised input at once. The result must replace P:

λ = (y_Q − y_P) / (x_Q − x_P),   x_R = λ² − x_P − x_Q,   y_R = λ(x_P − x_R) − y_P,   all mod p,   and P becomes R = P + Q.

Coordinates are stored in b bits each (b = 4, 8, 12 for p = 11, 251, 4,093), wire 0 of a coordinate the least significant bit. There are three kinds of instance:

• ec4093-offset: Q = (5, 65) is a fixed classical point (it is not on any wire). The inputs are the finite points P of the curve with x_P ≠ x_Q and x_R ≠ x_Q: 4,167 of the curve's 4,170 finite points. Wires 0 to 11 hold x_P, wires 12 to 23 hold y_P.
• ec4093-quantum: Q is a second quantum point on wires 24 to 35 (x_Q) and 36 to 47 (y_Q). It is read-only: its wires may control gates but are never changed. The inputs are all ordered pairs (P, Q) of finite curve points with x_P ≠ x_Q and x_R ≠ x_Q: 17,376,390 pairs.
• ec4093-offset-plane: Q = (5, 65) is classical, and the inputs are all pairs (x, y) of field elements, on the curve or not, with x ≠ 5 and x_R ≠ 5: 16,744,463 inputs. The formula above never uses the curve's constant, so it is a well-defined map of the plane, and it is one-to-one on these inputs.

The prime 11 and 251 instances (ec11-..., ec251-...) have the same three kinds with Q = (2, 2) and (0, 42), and are for debugging. Behaviour on any other input is free. Spare wires follow the data wires; they start in |0⟩ and must end live and in |0⟩.

The promise leaves out the inputs with x_R = x_Q (on the curve, P = −2Q). An arithmetic circuit that computes λ must also erase it, and the usual way recomputes it from the output as λ = (y_R + y_Q) / (x_Q − x_R), which is undefined there.

Lookup tables. The curve over F₄₀₉₃ has only 4,170 finite points (4,171 with the point at infinity, a cyclic group), and a point is fixed by its x-coordinate and the parity of y. So on the two curve instances, tables of the group (P → P + Q, or discrete logarithms) are legal and, at this size, can beat field arithmetic; the QArena baseline for ec4093-offset is such a table. The plane instance has 16.7 million inputs, so a table would need about 2²⁴ entries: the curve-point table no longer works there, although other structured shortcuts are not ruled out. Every circuit that passes it also passes ec4093-offset.

Submission file

JSON structure:

{"ancillas": 2,
 "ops": [["CCX", 0, 12, 24], ["CX", 24, 25], ["MX", 24], ["RZ", 24], ["PZ", 12, [0], 0]]}

This example is written for ec4093-offset (data wires 0 to 23, spare wires 24 and 25). It shows the format and is not a correct circuit. The verifier bundle contains an accepted example for ec4093-offset-plane; the baselines of every instance are listed on its leaderboard.

• ancillas: the number of spare wires. Data and spare wires together may number at most 512 (on the ranked instances at most 488 spare wires with a classical Q and 464 with a quantum Q). Every declared wire counts in the score, used or not.
• ops: at most 1,048,576 operations, applied in order, in the gate set of the constant-add board. All operands are JSON integers (not true or 1.0) naming a wire, and the operands of one gate must be different wires:
  • ["X",t], ["CX",c,t], ["CCX",c1,c2,t]: NOT on t, controlled by one wire, controlled by two wires. Every wire they touch must be live. The target t may not be a wire of Q.
  • ["MX",q] measures a live spare wire q in the X basis. Each measurement appends one record bit (0 for the outcome +1, 1 for −1), numbered 0, 1, 2, … in order, and the wire becomes inactive. Data wires (P or Q) cannot be measured. At most 4,096 measurements.
  • ["RZ",q] prepares an inactive spare wire q in |0⟩ and makes it live again. A live wire cannot be reset, and data wires cannot be prepared.
  • ["PZ",q,bits,value] applies Z to the live wire q (any wire, Q included) exactly when value XOR the XOR of the listed records equals 1. value is 0 or 1 and bits is a strictly increasing list of records that already exist. ["PZ",q,[],1] is an unconditional Z and ["PZ",q,[],0] does nothing but still counts as an operation. Over the whole file at most 65,536 record numbers may appear in bits lists. As on the constant-add board, the Z is applied when the XOR, including value, is 1.
  Nothing else is allowed: no other gates (in particular no measurement-based AND with a free correction), no blocks or repetitions, no postselection and no gate that depends on a measurement outcome except through PZ.
• Parsing is strict: exact keys, no duplicate keys, no NaN, and integers must be JSON integers. The file may be at most 20 MiB.

Validation

The verifier checks every promised input; nothing is sampled. It takes the inputs in a fixed order (the order of the curve's point list; for the plane by x, then y; for the quantum instances by Q, then P) in chunks of at most 262,144. Within a chunk every live wire is one long bit string with one bit per input, so a gate updates all inputs of the chunk in one big-integer operation. For every chunk it checks:

1. The P wires hold x_R and y_R, and the Q wires still hold Q.
2. Every declared spare wire is live and 0.
3. Every measurement branch gives the same operation. Measuring a wire that holds the value f(u) on input u, with outcome r, multiplies the branch by (−1)^r·f(u), up to a factor 1/√2, and a PZ adds the current value of its wire to the exponent of the records it lists. So the sign of a branch is (−1) to the power p₀(u) + ∑ r_j·p_j+1(u), where every p is a Boolean function of the input that the verifier tracks exactly. Each p must be the same on every promised input: all 0 or all 1. The first chunk fixes each constant and every later chunk must give the same one, so a sign that depends only on Q, or that changes between chunks, is rejected.

When all three hold, every measurement outcome applies the target map up to a sign that does not depend on the input, which is a global phase. The test is also necessary: if some p_j+1 depends on the input, the outcome with only r_j = 1 applies a wrong operation to superpositions. A circuit that measures a wire and forgets the Z correction therefore fails even when every basis output is right. The target map is one-to-one on the promised inputs, so a circuit that loses information about the input fails the output check. A file that breaks a format rule is rejected before simulation, and the report names the rule or the first failing input.

The work is about (operations + measurements + record numbers) × (number of inputs) / 64 word operations. On one core of an AMD Ryzen 9 9950X (limit 900 s, 2,048 MiB) a file that uses every cap at once on ec4093-quantum (1,048,576 operations of which 941,398 are Toffoli gates on dense wires, 4,096 measurements whose signs stay unresolved until the end, 65,536 record numbers, 512 wires) verifies in 148 to 170 s of CPU time (six runs) and 428 MiB; on the plane instance in 137 to 158 s and 425 MiB. The ranked baselines take 0.3 to 30 s. A second program, written independently from the specification, simulates one input at a time and follows every measurement branch explicitly on small cases, and uses numpy bit arrays on the large instances. On 29,813 test files (random circuits, mutations of every baseline, measured signs with right and wrong corrections, malformed files, chunks of 1 to 5 inputs), 7,156 of them accepted, it gave the same verdict and the same exact score as the verifier every time.

Scoring

Each instance is ranked by its number of Toffoli (CCX) gates. Fewer Toffoli gates rank first; equal counts are ranked by fewer operations in total (X, CX, CCX, MX, RZ and PZ each count 1), then by fewer declared spare wires, then by submission number (lower first). The score is read from the file: it does not depend on inputs or measurement outcomes, and no operation is free except by not being written. There is no depth or time score.

Baseline and reference scores

No instance has a published exact count, so none shows a reference score. The QArena baselines are ours. On each instance the generator builds every construction below that applies, the verifier checks all of them on the full domain, and the cheapest is shipped.

The lookups follow the select-swap tables of Low, Kliuchnikov and Schaeffer (arXiv:1812.00954) and Berry et al. (arXiv:1902.02134): a unary iteration over the high address bits writes 2^k table rows into clean registers. When the row has to stay available as an operand (the inverses and the table of λ), a network of controlled swaps on the k low address bits moves the addressed row to the first register, and everything is undone after use. When the lookup only XORs its row into a target (the offset tables and the discrete logarithms), there is no swap network: the registers hold row 0 and the differences row l ⊕ row 0, a one-hot decoder of the k low bits is built in place, and one Toffoli gate per register bit adds the addressed difference to the target. That costs (2^k − 1) Toffoli gates per output bit instead of twice that.

A unary iteration computes each node of its address tree with one Toffoli gate. In this gate set the usual measurement-based uncomputation of such an AND has no free correction (it would need a CZ conditioned on the outcome), so the baselines rely on the pass that undoes the lookup: the first pass removes each node by an X measurement, the second pass recomputes the same node anyway, and a single PZ on it, listing that record, cancels the sign. A node then costs 3 Toffoli gates instead of 4. The same rule removes the partial products that a product clears early to save wires (an X measurement now, the recompute and its PZ in the reverse pass: one extra Toffoli gate per cleared wire instead of two), and it keeps the value A of the quantum construction below in a register. The verifier's sign check certifies these corrections: a baseline with any one of these PZ operations removed fails.

• Two table lookups (offset instances on the curve): (x_R, parity of y_R), 13 bits, is looked up from (x_P, parity of y_P) into 13 clean wires; a second lookup addressed by those wires XORs P ⊕ R into the P wires, and the 13 wires are cleared from the new P wires by CX gates. The first table has 13-bit rows, so it can use 32 registers within the 512 wires (k = 5); the second has 24-bit rows and uses 16.
• Field arithmetic with a quantum Q (ec4093-quantum), after the in-place structure of Roetteler, Naehrig, Svore and Lauter (arXiv:1706.06752): d = x_Q − x and e = y_Q − y are formed in place on the P wires, and λ = e/d uses 1/d from a 12-bit table lookup instead of the extended Euclidean algorithm. With A = 3x_Q − λ², y_R + y_Q = λA − e and x_Q − x_R = A − d, so one product λA and two in-place modular subtractions turn (d, e) into (x_Q − x_R, y_R + y_Q). λ is cleared by a second division, with the inverse of x_Q − x_R, and the differences are undone in place: three products and two inverses. A sits in a 12-wire register while it is used: its circuit is computed once, as many of its wires as the 512-wire cap allows stay alive (88 of 272), the others are removed by X measurements, and when A is cleared only the measured wires are computed again, each with its PZ correction. The subtraction that uses λA reads the product's output wires in place, and the last subtraction, y_R + y_Q − y_Q, is the modular adder run backwards. Products and the square are Boolean circuits (schoolbook rows with ripple-carry additions for products, column compression for the square, reduction by 2¹² ≡ 3 mod 4,093) that are computed, copied and uncomputed; when a product goes into a register, its last layer (the selection that subtracts p or not) is written straight into that register, so that layer needs no spare wires and is not undone. While an inverse is in use its lookup registers stay alive, and the product clears the partial products of its first rows as soon as they are added, so the whole circuit fits in 512 wires.
• Field arithmetic with a classical Q (the plane instances): after λ = (y_Q − y)/(x_Q − x) is computed as above, the register y_Q − y equals λ(x_Q − x), so y_R + y_Q = (3x_Qλ − λ³) − (y_Q − y) and x_R = (λ² − x_Q) − x. Both corrections depend on λ alone, so one table lookup addressed by λ returns 3x_Qλ − λ³ and λ² − x_Q, and two in-place modular subtractions apply them. λ is then cleared with the second inverse. That needs two products instead of four.
• In-place modular additions and subtractions (all arithmetic constructions) are ripple-carry adders (Cuccaro, Draper, Kutin and Moulton, arXiv:quant-ph/0410184) with a carry or comparison flag, a correction by p controlled by the flag, and a comparison of the result that clears the flag: 62 to 96 Toffoli gates at 12 bits.
• Discrete logarithms (quantum debug instances): k = log P by lookup, P erased by the table of multiples, k ← k + log Q mod the group order, P rewritten from k, and k erased by log P. On ec4093-quantum it takes 6,516 Toffoli gates, more than the arithmetic. The plane constructions also pass ec4093-offset, with 5,410 Toffoli gates.

The deterministic fallback of the board specification is kept as a known answer for the verifier's tests: four or six full prefix-tree lookups (every prefix on its own clean wire, 32,760 Toffoli gates and 74,017 or 99,277 operations per 13-bit table, exactly the specification's component counts) and a ripple-adder modular addition. Its exact scores are 131,186 Toffoli gates and 347,467 operations on ec4093-offset, and 376, 616, 6,174 and 10,256 Toffoli gates on the four curve instances at p = 11 and 251. The ECDSA.fail challenge uses a different curve size and an average-shot Toffoli–qubit product, so its numbers are context only.

No lower bound is proved here. The constructions above are a starting point: windowed arithmetic, cheaper inversions, dirty-qubit lookups and better use of the 512 wires all leave room.

Application

Shor's algorithm for elliptic-curve discrete logarithms spends almost all of its Toffoli gates on point additions: adding a classical multiple of a point to a quantum point register (the offset kind) or, in some variants, adding two quantum points. Compiler authors compare constructions by their Toffoli count at a fixed number of qubits, and this board ranks exactly checked kernels on a curve small enough to check every input. It certifies these finite 12-bit kernels only: it makes no claim about secp256k1 or other cryptographic curves and does not bound the success probability of a full Shor run. The score does not model circuit depth, the cost of measurements and corrections, or error rates.

Current records

Reference scores come from cited papers or derived constructions. Only accepted submissions can hold a QArena record.