Fewest T gates for a multi-controlled Z with measurements

Task

Build a circuit from Clifford gates and T gates, with measurements and gates that depend on the measurement outcomes, that applies the multi-controlled-Z gate to N data qubits: the gate that multiplies the basis state |x₀ x₁ … x_N−1⟩ by (−1)^{x₀x₁···x_N−1}, so that only |11…1⟩ changes sign. For N = 4 this is CCCZ. The circuit may use spare qubits, called workspace wires, that start in |0⟩; every workspace wire still live at the end must be back in |0⟩ (a measured wire may stay unused). Whatever the measurement outcomes are, the data must end up with exactly this gate applied. The score is the largest number of T gates the circuit runs on any outcome that can occur. Fewer is better.

• Instance mcz3-a1: N = 3, at most 1 workspace wire. A debug instance (CCZ).
• Instance mcz4-a1: N = 4, at most 1 workspace wire. A debug instance (CCCZ).
• Instances mcz5-a1 and mcz5-a2: N = 5, at most 1 and at most 2 workspace wires.
• Instances mcz6-a1, mcz6-a2 and mcz6-a3: N = 6, at most 1, 2 and 3 workspace wires.

A T gate costs a distillable magic state, so it is the expensive operation of a fault-tolerant computer. A multi-controlled-Z is the phase half of every multi-controlled NOT, which lookups, comparators, adders and oracles need. Jones (arXiv:1212.5069) and Gidney (arXiv:1709.06648) showed that a measurement can erase a computed AND for free at the cost of an outcome-dependent CZ correction, which gives a CCZ with four T gates. Gidney and Jones (arXiv:2106.11513) build on this for larger gates, and for N ≥ 4 with N − 3 workspace wires the ladder in the baseline table needs 4N − 10 T gates. With fewer workspace wires the best circuits known to QArena are its own constructions, and none of them is proved optimal. A stabilizer-nullity argument only shows that N T gates are necessary.

Submission file

JSON structure (this shows the syntax only):

{"ancillas": 1,
 "ops": [["H", 4], ["T", 4], ["CX", 0, 4], ["MX", 4], ["IF", [0], 1, ["CZ", 0, 1]]]}

The verifier bundle contains a complete accepted file (the mcz6-a3 baseline).

• The file is a UTF-8 JSON object of at most 20 MiB. It has exactly the keys ancillas and ops. Indices and values are JSON integers, never floats or booleans. Duplicate keys, NaN and Infinity are rejected.
• ancillas is an integer from 0 up to the instance limit. Wires 0 to N − 1 are the data wires, with an unknown input state. Wires N to N + ancillas − 1 are workspace wires, all live and in |0⟩ at the start.
• ops lists at most 256 instructions, applied in order, with no macros, loops or subroutines: ["X", q], ["Z", q], ["H", q] (the Hadamard gate, with entries 1/√2 and ±1/√2), ["S", q] and ["SDG", q] (diag(1, i) and its inverse), ["T", q] and ["TDG", q] (diag(1, e^iπ/4) and its inverse), ["CX", c, t] and ["CZ", a, b] with two distinct wires; ["MX", q] and ["MZ", q] measure a live workspace wire in the X or Z basis, destroy it, and append one bit to the record (bit 0 means eigenvalue +1, bit 1 means −1); ["RZ", q] prepares a dead workspace wire (one that was measured) in |0⟩; ["IF", bits, v, gate] runs one gate exactly when the XOR of the listed earlier record bits equals v.
• The gate inside an IF is one of X, Z, H, S, SDG, T, TDG, CX, CZ, never another IF, a measurement or an RZ. The list bits is strictly increasing and names only measurements made earlier in the list. An empty list has XOR 0, so ["IF", [], 0, g] always runs g and ["IF", [], 1, g] never does. v is the integer 0 or 1.
• Measurements and RZ are unconditional, so which wires are live at each point is fixed by the list. Every wire a gate touches must be live, including the wires of an IF whose condition turns out false. Data wires cannot be measured or reset. At most 4 measurements occur. The record bits are numbered 0, 1, … in the order of the measurement instructions.
• At the end each workspace wire is either dead or live in exactly |0⟩. There are no free magic states, no catalysts, no discarded outcomes and no postselection, and CCX is not an instruction: write the Toffoli out in gates.
• ancillas is the declared number of workspace wires, which bounds the peak and is what the score counts, not the number of preparations: a wire that was measured can be revived with RZ and used again. An artifact that is legal for the instance with fewer workspace wires is also legal for every instance with the same N and a higher limit (mcz5-a1 → mcz5-a2, mcz6-a1 → mcz6-a2 → mcz6-a3), so one circuit can lead several instances.

Validation

Let r range over all 2^M complete lists of measurement outcomes, including those with probability zero, where M is the number of measurement instructions. Let K_r be the map from a data input state to the final data and live workspace state, without normalization, when the record is r. The verifier requires, for every r,

K_r = c_r (U_N ⊗ |0...0⟩_live)

for one complex number c_r that does not depend on the data input, and the squared magnitudes of the c_r must add up to exactly 1. The number c_r may be 0 and may differ between outcomes, including by a phase. This is exactly the statement that the circuit applies U_N to an arbitrary data state, with the workspace returned clean, whatever the outcomes. Dephasing, a workspace left dirty or entangled, an outcome probability that depends on the data, and a circuit that is right on one outcome only all fail it. How the verifier decides this, exactly:

• Amplitudes are exact: four integers (a₀, a₁, a₂, a₃) standing for (a₀ + a₁ζ + a₂ζ² + a₃ζ³) / (√2)^h with ζ = e^iπ/4, and no floating-point number enters any decision. The exponent h depends only on the outcomes, because H and measurements in the X basis are run or skipped by the record alone.
• Each of the 2^N basis inputs is followed through every measurement outcome (a depth-first search over the at most 16 records). Input 0 fixes c_r. Every other input must end exactly in c_r (−1)^{x₀···x_N−1}|x, 0…0⟩, compared as four integers at equal h. A branch whose scalar is zero on input 0 is still compared on every other input. Comparing labels or probabilities alone would miss a wrong phase.
• By linearity the basis inputs fix each K_r, so the check holds for every data state, including states entangled with other qubits. The sum of |c_r|² is checked as an invariant in the ring, scaled to the largest h.
• When a check fails, the report names the record, the input and the kind of failure: workspace not |0⟩, data basis state changed, a residual phase, or an outcome probability that depends on the input.
• Limits: 300 CPU seconds and 1 GiB of memory. If the verifier runs out of either, the result is an error with no score. The dense worst case within the caps (N = 6, 3 workspace wires, 4 measurements, 256 instructions, states of 512 amplitudes) takes about 10 s on one PC core, and the baselines take well under a second.

Scoring

After the circuit is accepted, the score is the triple (t, gates, ancillas), lowest first in that order:

• t is the largest number of T and TDG gates that run on one outcome record with c_r ≠ 0. A conditional T counts only on the records that run it, T counts of mutually exclusive outcomes are never added, and an outcome with probability zero does not count.
• gates is the number of instructions in ops. An IF counts as one, whether or not it runs.
• ancillas is the declared number of workspace wires.

Ties on all three are ranked by submission number (lower first). Each instance has its own ranking.

Baseline and reference scores

None of the baselines is proved optimal, and the one- and two-workspace cells are open. A borrowed-wire fallback that needs no clean workspace (70 T gates for N = 5 and 112 for N = 6, one declared wire) also verifies, but it is only a correctness check, and every baseline above beats it. The three conditionally clean circuits are QArena's own constructions. They borrow a data wire that is zero whenever the sign matters (conditionally clean), and they were checked on all inputs and all outcomes. Khattar and Gidney (arXiv:2407.17966) describe conditionally clean ancillas, but their counts are not converted into this instruction set, so those cells have no published reference. The AND, its inverse and CCZ in these circuits are the four-T AND of Gidney and the 15-instruction, seven-T Toffoli written out in gates (H, CX, T, TDG, S, SDG).

Application

Compilers for arithmetic, table lookup (SELECT) and oracles need multi-controlled gates with few T gates and few spare qubits. A circuit accepted here is a complete instruction list whose action has been checked on every measurement outcome, with an exact worst-case T count.

Current records

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