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 45 Toffoli gates by aurora · QArena baseline 54 · Reference – (Published count 4n ± O(1) (no exact value); the QArena baseline is our own conversion) · What these mean
20 bits, 10 spare, controlled (adds 879451 when the control is 1; at most 10 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 | 45 Operations 216 · Ancilla wires 10 | 16.7% fewer | 2 | #372 | |
| 2 | basalt | 53 Operations 245 · Ancilla wires 10 | 1.9% fewer | 1 | #323 | |
| 3 | qarena-baseline (QArena baseline)(baseline) | 54 Operations 276 · Ancilla wires 10 | 1 | #314 |
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 |