CSS circuits: useful quantum circuits that can be simulated with O(1) cost per gate

The paper in detail

A CSS state is a stabilizer state generated by positive-sign products of \(Z\)s and positive-sign products of \(X\)s. CNOT maps \(Z\)-type operators to \(Z\)-type and \(X\)-type to \(X\)-type, so it preserves this property. A \(Z\)-basis measurement either has a deterministic outcome, which must be \(+1\) because positive \(Z\) products are closed under multiplication, or a random one, in which case the \(+1\) branch is again a CSS state. Hence a circuit of CNOTs and \(X\)/\(Z\) measurements starting from \(\ket0^{\otimes n}\) can always produce the all-zero record.

Gidney's earlier simulation method (Stim) samples a stabilizer circuit by fixing one reference sample and propagating a Pauli frame: a measurement result is the reference result flipped if the frame anticommutes with the measured operator, and every measurement or reset multiplies the measured operator into the frame with probability one half. Its only expensive step is finding the reference sample. For CSS circuits the all-zero record works, even when gates are adaptive, and intended Pauli gates can be folded into the frame like noise.

The resulting simulator stores \(x_q\) (bit flipped) and \(z_q\) (phase flipped) for each qubit. CNOT xors \(x_c\) into \(x_t\) and \(z_t\) into \(z_c\); \(M_Z\) reports \(x_q\) and randomises \(z_q\); \(M_X\) reports \(z_q\) and randomises \(x_q\). Every gate touches \(O(1)\) bits. Because removing gates from a CSS circuit leaves a CSS circuit, skipped gates from atom loss stay inside the class (an editorial gloss on the authors' suggestion).

The paper ends with open questions: how to recognise circuits that are secretly CSS after compilation, and whether non-CSS-ness behaves as a resource that can be stored in states, as magic is.

Transferable methods

1. A free reference sample from CSS trajectories

   Frame simulation needs one valid noiseless sample. Proving that the all-zero record is always valid for Pauli-free CSS circuits removes the expensive bootstrapping step, so every gate costs constant time even under adaptivity.

   CNOT flows: \(Z_c\to Z_c\), \(Z_t\to Z_cZ_t\), \(X_c\to X_cX_t\), \(X_t\to X_t\). For a measurement of \(Z_m\) on a state with CSS generators: if \(Z_m\) is in the stabilizer group, it is a product of \(Z\)-type generators, all with sign \(+\), so the result is 0. Otherwise some \(X\)-type generator anticommutes with \(Z_m\); multiply it into the other anticommuting generators (keeping them \(X\)-type), replace it by \(+Z_m\), and the result-0 branch is a CSS state. Induction over the circuit gives the all-zero trajectory.

   With reference record \(r\equiv0\), the result of measuring \(M\) is simply \([P\text{ anticommutes with }M]\), where \(P\) is the tracked frame. For a single qubit this is \(x_q\) for \(M_Z\) and \(z_q\) for \(M_X\), and stabilizer randomisation after the measurement multiplies the measured operator into the frame with probability one half.

   Editorial check: six random 3-qubit circuits of ten gates each (mixtures of \(X\), \(Z\), CNOT, \(M_X\), \(M_Z\)) were sampled 4000 times with this simulator and with exact statevector collapse. The total-variation distances between the outcome histograms were 0.00 to 0.05, consistent with sampling noise over up to 32 outcomes.

   How to reuse it

   Any class of circuits with a guaranteed trajectory, such as all-zero outcomes, gets constant-cost frame simulation for free. Look for gate sets whose generators preserve a sign-positive stabilizer structure.

2. Bell inequalities as a no-go for extending a simulator

   Adding Hadamard looks easy (swap the two bits), but it is wrong, and the reason is structural: the simulator assigns every qubit predetermined answers to both measurements and updates them locally, so it is a local hidden-variable model and cannot reproduce a Bell violation.

   In the GHZ game three players receive bits \(x,y,z\) with \(x+y+z\) even and must output \(A\oplus B\oplus C=(x+y+z)/2\bmod2\). Editorial derivation of the classical bound: a deterministic strategy assigns \(a_x,b_y,c_z\), and the four questions require \[a_0+b_0+c_0=0,\quad a_0+b_1+c_1=1,\quad a_1+b_0+c_1=1,\quad a_1+b_1+c_0=1\pmod 2.\] Each variable appears exactly twice, so the left sides sum to 0 while the right sides sum to 1: at most three of four can hold, and uniform questions give success at most 75%.

   The paper gives circuits in CSS plus \(S\), CSS plus \(H\) and CSS plus CZ that win with probability 1, so none of these gate sets admits a local two-bit simulator. The naive swap rule already fails on a small example: \((H_a\,\mathrm{CNOT}_{a\to b})^4=X_b\), which the swap rule treats as the identity (checked editorially by matrix multiplication).

   How to reuse it

   Before extending a fast classical simulator to a new gate, ask whether the simulator is local and realistic in the Bell sense. If the extended gate set can win a nonlocal game with certainty, no local update rule will do, and the extension must give up locality or speed.

Source: Section 2.2 (Lemmas 2.1–2.3, Theorem 2.4); Section 2.3 and Figure 1; Section 2.4. Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. Teleportation, CSS-code error correction and entanglement purification are all CSS circuits, so they can be sampled at flip-simulation speed without bootstrapping. The authors suggest the class is well suited to benchmarking error correction under atom loss.

Limitations. A short note with no benchmarks and no implementation of a loss model. The Bell argument rules out extensions that keep the local two-bit representation, not every constant-cost simulator of CSS plus Hadamard. Many compiled error-correction circuits use CZ and Hadamard and are only CSS in disguise; detecting such circuits is left open. The authors state that no AI tools were used.

Description based on the full arXiv HTML of v1, read 2026-11-13: the whole paper (Sections 1–3, the simulator code and the AI statement). The simulator was compared with statevector sampling on random small CSS circuits, the identity \((H_a\,\mathrm{CNOT}_{a\to b})^4=X_b\) was checked, and the GHZ bound was rederived.