Cheapest fault-tolerant preparation of an encoded |0⟩

Task

Write a circuit that prepares the logical |0⟩ state of a small CSS code fault-tolerantly. If s ≤ t faults occur, the run is either rejected by its own checks or it ends with a data error whose X part and Z part each have weight at most s, up to stabilizers (the exact rule is under Validation). Minimize a certified upper bound on the expected number of CNOTs per accepted run (the score is defined under Scoring).

• Instance steane7-t1: Steane [[7,1,3]] code, t = 1. A debug instance for testing a submission pipeline.
• Instance color17-t2: [[17,1,5]] 4.8.8 color code, t = 2.
• Instance color19-t2: [[19,1,5]] 6.6.6 color code, t = 2.
• Instance bh49-t2: Bravyi-Haah [[49,1,5]] code, t = 2. No fault-tolerant circuit for it has been published.

Each instance file gives the check matrices HX and HZ as lists of qubit indices. Logical X and logical Z are the all-ones operators. The target state is the one stabilized by +X(a) for every a in the row space of HX and by +Z(b) for every b in the row space of HZ together with logical Z. The color-code layouts are those of Chamberland and Beverland (arXiv:1708.02246, Appendix H). The BH49 matrices follow Bravyi and Haah (arXiv:1209.2426, Appendix B).

Steane-type error correction and many logical gadgets consume one encoded |0⟩ per use. The usual preparation runs a non-fault-tolerant encoder, measures some stabilizers with extra ancillas (sometimes with flag qubits), and discards the run when a check fires. Goto (Sci. Rep. 6, 19578) built such a circuit for the Steane code, and Peham et al. (arXiv:2408.11894) synthesize them automatically for distance 3 and 5 codes.

Submission file

JSON structure:

{"qubits": 8,
 "ops": [["RZ", 0], ["RX", 3], ..., ["CX", 3, 1], ..., ["CX", 0, 7], ["MZ", 7]],
 "accept": [{"bits": [0], "value": 0}]}

This shows the file structure. The verifier bundle contains a complete accepted file (the color17-t2 baseline).

• The file is a UTF-8 JSON object without a byte-order mark. It has exactly the keys qubits, ops and accept, and every accept entry has exactly the keys bits and value. Indices and values are JSON integers, never floats or booleans. Duplicate keys, NaN and Infinity are rejected.
• qubits is an integer from n to 2n + 32. Wires 0 to n − 1 carry the data; the other wires are ancillas.
• ops lists at most 1500 operations, applied in order: ["RZ", q] and ["RX", q] prepare |0⟩ and |+⟩; ["X", q], ["Z", q]; ["CX", c, t] with c ≠ t; ["MZ", q] and ["MX", q] measure destructively and append one bit to the record (bit 0 means eigenvalue +1); ["PX", q, bits, v] and ["PZ", q, bits, v] apply X or Z exactly when the XOR of the listed earlier record bits equals v.
• Every wire starts unprepared. A wire can be prepared only if it is unused or has been measured. All other operations need a prepared wire that has not been measured since. Record indices count the measurements from 0. Every bits list is strictly increasing: in PX and PZ it may name only measurements made before that operation, and in accept any measurement of the run.
• accept is a list of at most 1500 parity equations {"bits": [...], "value": v} on the final record. A run is accepted when all of them hold. An empty list accepts every run.
• All data wires must be prepared and unmeasured at the end. Ancillas may stay prepared at the end, but the data must not be entangled with them.

Noise model

Every listed operation is one fault location that fails with probability p = 1/1000. A failure applies one of the following, each equally likely:

• RZ: X after the preparation. RX: Z after the preparation.
• X, Z, PX, PZ: X, Y or Z after the operation. This applies whether or not the conditional Pauli fires.
• CX: one of the 15 non-identity two-qubit Paulis after the gate.
• MZ, MX: the reported bit is flipped.

Waiting wires have no noise. A fault event of size s has faults at s distinct operations, so two CNOT locations give 15 × 15 = 225 combinations.

Validation

For every fault event with s ≤ t faults, including s = 0, and for every measurement outcome, an accepted run must leave the data in E|0_L⟩ with E = X(x)Z(z) such that

• μ_X(x) = min over a in rowspan(HX) of wt(x + a) is at most s, and
• μ_Z(z) = min over b in rowspan(HZ, logical Z) of wt(z + b) is at most s.

The X and Z parts are weighed separately: an X on one qubit together with a Z on another counts as weight 1 for each part. A logical Z error does no harm to |0_L⟩; a logical X error is a failure. Rejected runs are unrestricted. The verifier decides this exactly, with no sampling:

• It simulates the noiseless circuit once, keeping every stabilizer sign as a GF(2) affine function of the random measurement outcomes, so every branch is covered at once. Every acceptance equation must hold on every branch, and every row of HX, every row of HZ and logical Z must stabilize the output with sign +1 on every branch. A circuit that rejects some noiseless run cannot reach the acceptance floor below.
• It propagates each fault as a Pauli frame to the end of the circuit. Flipped record bits also flip the conditional Paulis that read them. An event is accepted exactly when it flips none of the acceptance equations. For an accepted event, the X and Z syndromes of the data error are compared with the syndromes of all errors of weight at most s. Every single fault is checked and, for t = 2, every pair of faults at distinct operations.
• When a check fails, the report names the event (operation indices and Pauli alternatives) and gives μ_X and μ_Z (exact up to 4; a larger value is reported as > 4).
• The acceptance probability bound P defined under Scoring must be at least 1/2.
• Limits: 1800 CPU seconds and 2 GB 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 well under a minute.

Scoring

Let N be the number of operations and C the number of CX gates. A1, A3 and A15 count the accepted single-fault alternatives at locations with 1 alternative (RZ, RX, MZ, MX), 3 alternatives (X, Z, PX, PZ) and 15 alternatives (CX). Every noiseless run is accepted, so the probability of acceptance with at most one fault is

P = (1 − p)^N + p (1 − p)^(N−1) (A1 + A3/3 + A15/15)
  = 999^(N−1) (14985 + 15 A1 + 5 A3 + A15) / (15 · 1000^N),

which is an exact lower bound on the acceptance probability. The score is cost = C / P, an exact fraction, and lower ranks first. Ties are ranked by fewer ancilla wires (qubits − n, unused wires included), then fewer CX gates, then the earlier submission. The verifier reports cost and P as reduced hexadecimal fractions, with decimals for display only.

The cost is an upper bound on the expected number of CNOTs per accepted run when failed runs are repeated independently. It is not a logical error rate: the board makes no claim about events with more than t faults, and the model has no idle noise.

Baseline and reference scores

The circuits come from the MQT QECC repository (scripts/ft_stateprep/eval/circuits, MIT license). QArena converted them by parsing the text, without running any MQT code: H on a fresh qubit becomes RX, H just before a measurement becomes MX, and MR becomes MZ. The data qubits were relabelled by a permutation that maps each circuit's code onto the instance matrices, and every measurement must read 0. For the baselines, each measurement was then moved up to the last operation on its wire, so the next ancilla can reuse the wire. Without idle noise this changes only the number of wires, which is the first tie-break. The paper reports no score in this board's cost model, so QArena computed these values. Table 3 of the paper (arXiv v3) lists 71 and 120 CNOTs and 4 ancillas with reuse for these two circuits, as in the conversions here. Earlier versions list fewer CNOTs (v1: 65 and 101; v2: 65 and 114). The repository history keeps the August 2024 circuits with 65 and 101 CNOTs (commit 7cab7bf), and this verifier rejects both. In each, the failing event includes a Z fault on a Z-check ancilla that spreads back to several data qubits through the check's remaining CNOTs and is never detected: one such fault is enough for the 65-CNOT circuit, and two faults break the 101-CNOT circuit. The authors replaced these circuits in October 2024 (commit 4e06578, "Adjustments to handling of hook errors").

Application

A cheaper fault-tolerant |0⟩ reduces the cost of Steane-type error correction, which uses one encoded ancilla per round, and of preparing logical qubits for transversal gates.

Current records

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