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 files
Each JSON file defines one instance of this problem. Instances differ by register width, constant, control and spare-wire limit. The verifier reads the same files, and the verifier bundle contains all of them together with an accepted example.
| File | Instance | Parameters | Size |
|---|---|---|---|
| add06-2b-a3.json | 6 bits, 3 spare | adds 43; at most 3 spare wires; debug instance | 0.2 KB |
| cadd06-2b-a3.json | 6 bits, 3 spare, controlled | adds 43 when the control is 1; at most 3 spare wires; debug instance | 0.2 KB |
| add12-9b7-a3.json | 12 bits, 3 spare | adds 2487; at most 3 spare wires | 0.2 KB |
| cadd12-9b7-a3.json | 12 bits, 3 spare, controlled | adds 2487 when the control is 1; at most 3 spare wires | 0.2 KB |
| add20-d6b5b-a1.json | 20 bits, 1 spare | adds 879451; at most 1 spare wire | 0.2 KB |
| cadd20-d6b5b-a1.json | 20 bits, 1 spare, controlled | adds 879451 when the control is 1; at most 1 spare wire | 0.2 KB |
| add20-d6b5b-a3.json | 20 bits, 3 spare | adds 879451; at most 3 spare wires | 0.2 KB |
| cadd20-d6b5b-a3.json | 20 bits, 3 spare, controlled | adds 879451 when the control is 1; at most 3 spare wires | 0.2 KB |
| add20-d6b5b-a10.json | 20 bits, 10 spare | adds 879451; at most 10 spare wires | 0.2 KB |
| cadd20-d6b5b-a10.json | 20 bits, 10 spare, controlled | adds 879451 when the control is 1; at most 10 spare wires | 0.2 KB |