Fewest CNOTs for a flagged parity check

Task

Measure the parity P = Z^⊗w of w data qubits with a small circuit of ancilla preparations, CNOTs and ancilla measurements. One measurement outcome is the syndrome s. Every other outcome is a flag. The circuit must satisfy two conditions:

• With no fault, every flag reads 0 and the circuit performs exactly the projective measurement of P: a data state ρ becomes Π_sρΠ_s with Π_s = (I + (−1)^sP)/2.
• For one fault, and for any two faults at different operations, either at least one flag reads 1, or the data error E left behind has min(wt(E), wt(E·P)) at most the number of faults.

This is the t-flag condition of Chamberland and Beverland (arXiv:1708.02246) with t = 2. Minimize the number of CNOTs.

• Instance z04-t2-a2: weight 4, at most 2 ancilla wires. A debug instance for testing a submission pipeline.
• Instance z06-t2-a3: weight 6, at most 3 ancilla wires. Also a debug instance.
• Instance z08-t2-a4: weight 8, at most 4 ancilla wires.
• Instance z12-t2-a5: weight 12, at most 5 ancilla wires.
• Instance z16-t2-a5: weight 16, at most 5 ancilla wires.

The plain circuit uses one ancilla in |0⟩ and a CNOT from every data qubit onto it, then measures it. It is not fault tolerant: a single Z fault on the ancilla halfway through spreads back through the remaining CNOTs onto about w/2 data qubits (a hook error). Flag qubits, introduced by Chao and Reichardt (arXiv:1705.02329) for one fault, are extra ancillas that detect such spreading. A decoder can then treat a flagged round differently. Chamberland and Beverland extended flags to t faults and gave a general two-fault construction for any weight. The instance names give the weight, the number of faults and the ancilla limit.

Submission file

JSON structure (this is the weight-4 baseline, a complete accepted file for z04-t2-a2):

{"ancillas": 2,
 "ops": [["RZ", 4], ["CX", 0, 4], ["RX", 5], ["CX", 5, 4], ["CX", 1, 4], ["CX", 2, 4],
         ["CX", 5, 4], ["MX", 5], ["CX", 3, 4], ["MZ", 4]],
 "syndrome": 1}

Wire 4 collects the parity and its Z measurement (record bit 1) is the syndrome. Wire 5 is a flag in |+⟩ whose two CNOTs onto wire 4 surround the middle data CNOTs, so a Z fault on wire 4 between them flips the flag.

• The file is a UTF-8 JSON object of at most 20 MiB with exactly the keys ancillas, ops and syndrome. Indices are JSON integers, never floats or booleans. Duplicate keys, NaN and Infinity are rejected.
• ancillas is an integer from 0 to the instance limit. Wires 0 to w − 1 are the data, wires w to w + ancillas − 1 the ancillas. Every declared ancilla wire counts in the score, used or not.
• ops lists at most 256 operations, applied in order, with at most 128 CX and at most 32 measurements: ["RZ", q] and ["RX", q] prepare an inactive ancilla in |0⟩ or |+⟩; ["CX", c, t] is a CNOT with control c and target t, two different live wires (data wires are always live); ["MZ", q] and ["MX", q] measure a live ancilla in the Z or X basis, append one bit to the record (0 means eigenvalue +1, 1 means −1) and make the wire inactive. A measured wire may be prepared again.
• Ancillas start inactive; every ancilla that is prepared must be measured by the end, and declared ancillas that are never used may stay inactive. Data wires can never be prepared or measured. There are no other gates, no operations conditioned on outcomes and no postselection.
• syndrome is the index of the syndrome bit in the record (measurements are numbered from 0 in order). Every other record bit is a flag.

Noise model

Every listed operation is one fault location. A fault applies one of the following:

• CX: one of the 15 non-identity two-qubit Paulis right after the gate.
• RZ: X right after the preparation. RX: Z right after the preparation.
• MZ, MX: the recorded bit is flipped.

Waiting wires have no noise, and any two wires may share a CNOT (all-to-all connectivity). A two-fault event has its faults at two different operations, so two CNOT locations give 15 × 15 = 225 combinations. A result on this board is a count in this model; real hardware adds idle noise and connectivity limits.

Validation

Besides the format and the caps, the verifier checks the following exactly, with no sampling:

• For the ideal measurement, the verifier runs the circuit once on w Bell pairs, each made of a data qubit D_i and a reference qubit R_i that the circuit never touches. It uses a stabilizer simulation in which every sign and every record bit is a parity (over GF(2), possibly plus a constant) of the random measurement outcomes, so one run covers all outcomes. Every flag bit must be 0 on every run. The syndrome bit must depend on a random outcome, so it is 0 or 1 with probability 1/2 each. The final state of the data and reference qubits must be stabilized by +Z(D_i)Z(R_i) for every i, by +X(D₀)X(R₀)X(D_i)X(R_i) for every i ≥ 1, and by (−1)^sZ(D₀)…Z(D_w−1). These 2w operators fix the state, so on every run the circuit applies Π_s up to a phase. Since the syndrome is unbiased on the Bell pairs, this is exactly the measurement ρ ↦ Π_sρΠ_s.
• For the faults, each one is pushed to the end of the circuit as a Pauli frame. A CX copies the X part of the frame from control to target and the Z part from target to control. A measurement reads the X part (MZ) or the Z part (MX) of its wire and drops that wire's frame, and a preparation starts a clean one. This gives the flipped flag bits and the data error E = X(x)Z(z). The flips and the error of an event are the XOR of those of its faults. For every single fault and every pair of faults at different operations that flips no flag, min(wt(E), wt(E·P)) must be at most the number of faults, where wt counts the data qubits on which E acts as X, Y or Z. The syndrome bit is not a flag: a fault that only flips the syndrome passes.
• When a check fails, the report names the operations, the faults and the data error.
• Limits: 120 CPU seconds and 512 MiB of memory. If the verifier runs out, the result is an error, even when every event checked so far passed. Circuits within the caps take a few hundredths of a second.

Scoring

The score is the number of CX gates, and lower ranks first. Ties are ranked by fewer declared ancilla wires, then fewer measurements, then the earlier submission. In the baselines every flag costs two CNOTs on top of the w data CNOTs.

The board certifies the hook condition for one measurement of one check. A full error-correction round also needs repeated syndromes and a decoder that uses the flags.

Baseline and reference scores

All baselines use the interval family of the specification: the syndrome ancilla s = w is prepared in |0⟩, the data CNOTs CX(i, s) come in increasing order, and a flag interval (a, b) is a flag in |+⟩ with one CNOT onto s after a data CNOTs and one after b data CNOTs, measured in the X basis. Released flag wires are reused.

The reference is the general two-fault construction of Chamberland and Beverland (Quantum 2, 53 (2018), Section 3.3): w/2 − 1 flag pairs, one spanning the first to the second-last data CNOT, one spanning the second to the last, and the others starting after every two data CNOTs, for 2w − 2 CNOTs. The paper reports no score in this board's model, so QArena built each reference circuit from that rule and checked it here: all five pass, with the counts in the table. QArena also searched the interval family exhaustively: all sets of distinct intervals (a, b) with 0 ≤ a < b ≤ w, each tried in every listed order. No gadget with fewer flags than the baseline passes at any of the five weights (for example none with 4 flags at weight 16), and none with the same number of flags needs fewer ancillas, so every baseline is optimal within this family. At weight 12, 1,730 of the 1,426,425 sets of 4 flags pass in increasing order, 602 of them with 4 ancillas. At weight 16, 27,658 of the 359,933,112 sets of 5 flags pass, 2,180 of them with 4 ancillas. Each new baseline is the first of these in lexicographic order. The searches do not cover other shapes, such as flags on flags, several collecting ancillas or flags measured in the Z basis.

Application

Measuring the checks of a code with flags needs only a few ancillas per check, against w for a Shor-style cat state. Cheaper flagged circuits for checks of weight 6 to 16 reduce the cost of syndrome extraction for color codes and quantum LDPC codes, many of which have checks in that range.

Current records

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