Fewest Toffoli gates for adding a constant

Task

Each instance gives a register width n, a constant c and a limit on spare wires. Build a circuit that adds c to the n-qubit register modulo 2ⁿ, for every input at once and without disturbing anything else:

• Plain instances (add...): the data wires 0 to n−1 hold x, with wire 0 the least significant bit, and must end holding (x + c) mod 2ⁿ.
• Controlled instances (cadd...): wire n is a control qubit q. The data wires must end holding (x + q·c) mod 2ⁿ, so c is added only when q = 1, and the control must be unchanged.
• Spare wires (also called workspace or ancillas) follow the data and control wires. They start in |0⟩ and must all be back in |0⟩ at the end. The instance limit says how many a circuit may declare: 1, 3 or 10 at width 20, 3 at widths 6 and 12.

The circuit is built from X, CNOT and Toffoli (CCX, a NOT controlled by two wires) gates, plus X-basis measurements of spare wires and Z gates that fix the signs the measurements leave behind. Instance names give the width, the constant in hexadecimal and the spare-wire limit, for example cadd20-d6b5b-a10: 20 bits, c = 0xd6b5b = 879,451, controlled, at most 10 spare wires. The 6-bit pair is for debugging and is not ranked.

Submission file

JSON structure:

{"ancillas": 1,
 "ops": [["CCX", 0, 1, 6], ["CX", 6, 2], ["MX", 6], ["RZ", 6], ["PZ", 0, [0], 0]]}

This example is written for add06-2b-a3 (data wires 0 to 5, spare wire 6). It shows the format and is not a correct adder. The verifier bundle contains an accepted file for add20-d6b5b-a3.

• ancillas: the number of spare wires, from 0 to the instance limit. Every declared wire counts in the score, used or not.
• ops: at most 20,000 operations, applied in order. Each one has one of these exact forms; 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 (see MX).
  • ["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 and control wires cannot be measured. At most 512 measurements.
  • ["RZ",q] prepares an inactive spare wire q in |0⟩ and makes it live again. A live wire cannot be reset, and data and control wires cannot be prepared.
  • ["PZ",q,bits,value] applies Z to the live wire q (a data, control or spare wire) 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. Records stay usable after their wire is prepared again. Over the whole file at most 8,192 record numbers may appear in bits lists. This rule is the reverse of the "parity equals value" rule of the PX/PZ operations on the circuit boards for emitters and fault-tolerant state preparation: here the Z is applied when the XOR, including value, is 1.
  Nothing else is allowed: no other gates, no measurement in another basis, no postselection and no gate whose operands depend on a measurement outcome except through PZ.
• Every declared spare wire must be live and in |0⟩ at the end. 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 keeps every live wire as a table of its value on all inputs: 2ⁿ of them, or 2ⁿ⁺¹ with the control. Each table is one long bit string, so a gate updates every input in a single big-integer operation. It then checks, over all inputs:

1. The data wires hold (x + c) mod 2ⁿ, or (x + q·c) mod 2ⁿ for the controlled instances.
2. The control is unchanged and every declared spare wire is live and 0.
3. Every measurement branch gives the same operation. Measuring a wire that holds the value f(x), with outcome r, multiplies the branch by (−1)^r·f(x), 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₀(x) + ∑ r_j·p_j+1(x), where each p is a Boolean function of the input that the verifier tracks exactly. The file is accepted only if each p is the same for every input (all 0 or all 1).

When all three hold, every measurement outcome leaves the target operation up to a sign that does not depend on the input, and a sign that does not depend on the input 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. A circuit that measures a carry wire and forgets the Z correction therefore fails even though the computational output is right for every input, because a superposition of inputs would be damaged. The same holds if a measurement destroys information that the rest of the circuit needed: the output check then fails. Any 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) × 2ⁿ⁺¹/64 word operations. On one PC core (limit 300 s, 1,024 MiB) the largest file the caps allow, 20,000 operations on the 20-bit controlled instance with 512 measurements, 8,192 record numbers and up to 494 nonconstant phase coefficients alive at once, verifies in under 2 s of CPU time and 154 MiB; the baselines take under 0.1 s. A second program, written independently, simulates the circuit one input at a time and follows every measurement outcome explicitly on small cases. It agreed with the verifier on all of 200,150 random and adversarial files, accepted and rejected alike, with no disagreement.

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 exact and no operation is free except by not being written. There is no depth or time score. The caps trade against each other: at width 20 the same constant appears with 1, 3 and 10 spare wires.

Baseline and reference scores

No instance has a published exact count, so none shows a reference score. The QArena baselines come from three constructions.

Three or more spare wires use the adder of Gidney (arXiv:2507.23079). The paper states 4n ± O(1) Toffoli gates with 3 clean spare wires, and the control costs no extra Toffoli gates. It gives the circuits as figures, so QArena rebuilt the adder gate by gate in this gate set. The files are our conversion, not the author's code, and the counts below are exact scores of verified files, not 4n. The adder has three parts:

• Streaming ripple-carry. Bit by bit, the carry into the next bit is computed on a spare wire (one Toffoli per bit) and the carry that was just used is measured in the X basis (the paper calls this venting), then its wire is reset and reused. Two spare wires carry the whole addition. Each measurement leaves a sign (−1)^{outcome·carry} that must be repaired later.
• Repair from the finished sum. The carries of the addition equal the carries of adding c to the bitwise complement of the finished sum, so they can be recomputed from the result. A carry-xor circuit (Häner, Roetteler and Svore, arXiv:1611.07995) xors all these carries into a register with about two Toffoli gates per carry, and Z gates placed between two such passes turn the xor into a sign on the carries.
• Borrowing back and forth. The register is split into two halves. Each half uses the other half as the register that receives the xor; the register may hold any state (a dirty workspace) and is restored. A third spare wire holds the carry from the lower half to the upper half until the end.

With ten spare wires the baseline uses a variant of our own: when about n/2 clean spare wires are free, the lower half's signs are repaired by computing its carries into clean wires, applying Z, and undoing the computation. That costs 2 Toffoli gates per carry instead of 4, and gives 3n − 9 Toffoli gates at n = 20 without the control.

With one spare wire the baseline is a construction of our own that uses no measurements. Bits are changed from the top down, so every bit below the one being changed still holds its original value, and the carry into bit j can be computed from those bits. A carry-xor circuit writes the carry onto a dirty wire borrowed from the other half of the register; it is copied to the target, the carry-xor runs again, and a second copy cancels the dirty value, so the target receives the carry exactly. The top half takes its carries from a chain that starts at the carry out of the bottom half, which the spare wire holds, and the bottom half then takes its carries into the spare wire one bit at a time. The cost grows with the square of the width: 522 Toffoli gates at width 20 (562 with the control), about sixteen times fewer than the borrowed-bit construction below and about eight times the count with three spare wires. Häner, Roetteler and Svore (arXiv:1611.07995) describe a constant adder that needs only one borrowed wire; we have not built it, so its exact count on these instances is not known and they leave room.

The borrowed-bit construction of the board specification is kept as a known answer for the verifier's tests. It adds the constant one set bit at a time: adding 2^b flips bit j when bits b to j−1 are all 1, which is a NOT with many controls, applied from the top bit downwards. Each many-control NOT uses the one spare wire, in any state, as a borrowed bit and is split into two halves, repeated twice (Barenco et al., arXiv:quant-ph/9503016). It needs 8,255 Toffoli gates at width 20 (10,070 controlled).

The borrowed-bit construction has these exact scores at widths 6, 12, 16 and 20, controlled and not, as (Toffoli, operations) = (47, 54), (95, 99), (1,111, 1,126), (1,565, 1,573), (2,875, 2,894), (3,685, 3,695), (8,255, 8,280) and (10,070, 10,083), each with one spare wire.

No lower bound is proved here. Gidney's paper also gives an adder with 3n ± O(1) Toffoli gates that borrows n−2 dirty qubits. This board has no dirty spare qubits: every spare wire starts clean and counts in the score.

Application

Adding a known constant modulo 2ⁿ, with or without a control, is the inner step of modular exponentiation in Shor's algorithm and of many other arithmetic circuits, for example modular multiplication by repeated controlled additions. In a fault-tolerant computer a Toffoli gate costs far more than a CNOT, and a spare qubit has its own cost, so the number of Toffoli gates at a fixed workspace limit decides the price of these subroutines. 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.