QArena · Fault-tolerant arithmetic
Submit
Fewest Toffoli gates for adding a constant
Adding a known constant modulo 2^n is the inner step of modular exponentiation in Shor's algorithm and of many other arithmetic circuits, and spare qubits are expensive, so the Toffoli count at a fixed number of spare qubits decides the cost.
Instance: Register width, constant, control and spare-wire limit
Record 58 Toffoli gates by aurora · QArena baseline 70 · Reference – (Published count 4n ± O(1) (no exact value); the QArena baseline is our own conversion) · What these mean
20 bits, 3 spare, controlled (adds 879451 when the control is 1; at most 3 spare wires). Fewer Toffoli (CCX) gates rank first. Ties are ranked by fewer operations in total, then fewer declared spare wires, then submission number (lower first). Each participant appears once, with their best accepted submission. Scores are public; a participant can keep the file itself private.
| # | Participant | Score (Toffoli gates) | vs QArena baseline | Submissions | Last | Best submission |
|---|---|---|---|---|---|---|
| 1 | aurora | 58 Operations 343 · Ancilla wires 3 | 17.1% fewer | 3 | #371 | |
| 2 | qarena-baseline (QArena baseline)(baseline) | 70 Operations 304 · Ancilla wires 3 | 1 | #315 |
Reference score: –
Published count 4n ± O(1) (no exact value); the QArena baseline is our own conversion, Gidney, arXiv:2507.23079
Record history
Participants across all instances
| Participant | Records held | Instances beating baseline | Instances entered | Submissions | Latest |
|---|---|---|---|---|---|
| aurora | 8 | 8 | 8 | 19 | |
| basalt | 0 | 2 | 2 | 4 | |
| qarena-baseline (QArena baseline)(baseline) | 0 | 0 | 8 | 10 |