betaFeedback

WorksPhysics and Astronomy

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

Abstract

"CSS circuits" are quantum circuits generated by XX, ZZ, MXM_X, MZM_Z, and CNOT gates. Although CSS circuits are extremely restrictive, they can implement important quantum protocols like teleportation, error correction, and entanglement purification. We present a simple CSS circuit simulator that uses O(1)O(1) work per gate. The simulator corresponds to a local hidden variable model, so we use Bell inequalities to prove the simulator can't also support Hadamard gates, CZ gates, or S gates. We note that CSS circuits appear ideal for benchmarking quantum error correction in the presence of atom loss errors.

Introduction

In 1998, Daniel Gottesman showed that quantum stabilizer circuits can be efficiently simulated by classical computers [8]. This is remarkable, because many important quantum protocols can be performed by stabilizer circuits. For example: stabilizer circuits can perform quantum teleportation, can violate Bell inequalities, and can perform quantum error correction. In fact, because stabilizer circuits are so efficient to analyze, most quantum error correction protocols created to date are based on stabilizer circuits [2].

Stabilizer circuits do have some downsides. Of particular interest in this paper is the fact that existing stabilizer simulation methods take Ω(n2)\Omega(n^2) time per gate [3, 1], where nn is the number of qubits in the circuit. An error correction circuit can easily contain hundreds of thousands of gates, span thousands of qubits, and be sampled billions of times. The only reason that kind of analysis is tractable is because it can be determined in O(1)O(1) time per gate whether or not a measurement will be flipped [7]. Flip information is usually sufficient for correcting errors, and so most error correction circuit simulations use “flip simulation” rather than full simulation.

There are contexts where flip simulation doesn’t work. In particular, on neutral atom machines, an important kind of noise is atom loss. When an atom is lost, the gates targeting that atom do not occur. The missed gates can include Clifford operations. Flip simulations understand Pauli errors, but not Clifford errors. Consequently, the presence of atom loss noise forces the use of a full stabilizer simulation rather than a flip simulation and this increases simulation costs from O(1)O(1) per gate to Ω(n2)\Omega(n^2) per gate.

In this paper we’ll show that, for a subset of stabilizer circuits that we call “CSS circuits”, it’s still possible to do fast simulation in the presence of loss. We call this subset CSS Circuits because the states produced by such circuits always have stabilizer generators that are pure XX products and pure ZZ products (similar to the stabilizer generators used by CSS codes).

The paper is organized as follows. § 2 describes CSS circuits, shows how to simulate them, and notes limitations on extending the simulation method to other gates. § 3 then makes some closing remarks.

Body

CSS Circuits

A “CSS circuit” is a circuit built from the following five gates: XX, ZZ, MXM_X, MZM_Z, and CNOT. The gates may be performed probabilistically and adaptively. The gates are defined as follows:

UnitaryMatrix⁡(X)=(0110)UnitaryMatrix⁡(Z)=(100−1)UnitaryMatrix⁡(CNOT⁡)=(1000010000010010)Projectors⁡(MZ)={(1000),(0001)}Projectors⁡(MX)={(0.50.50.50.5),(0.5−0.5−0.50.5)}\begin{aligned} \operatorname{UnitaryMatrix}(X) &= \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \\ \operatorname{UnitaryMatrix}(Z) &= \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \\ \operatorname{UnitaryMatrix}(\operatorname{CNOT}) &= \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} \\ \operatorname{Projectors}(M_Z) &= \left\{ \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \right\} \\ \operatorname{Projectors}(M_X) &= \left\{ \begin{pmatrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{pmatrix}, \begin{pmatrix} 0.5 & -0.5 \\ -0.5 & 0.5 \end{pmatrix} \right\} \end{aligned}

A CSS circuit can of course also perform any effect achievable by composition of these gates. For example, a CSS circuit can prepare a qubit into the ∣0⟩\lvert0\rangle state by performing a ZZ-basis measurement (MZM_Z) and then adaptively applying a bit flip (XX) if the measurement result was 1 instead of 0. CSS circuits can similarly prepare ∣+⟩\lvert+\rangle, ∣−⟩\lvert-\rangle, and ∣1⟩\lvert1\rangle. They can also perform swap gates (by decomposing into three CNOTs), CXSWAP gates (two CNOTs), multi-qubit XX basis parity measurement (like MXXXM_{XXX}), and multi-qubit ZZ basis parity measurements. CSS circuits cannot perform Hadamard gates (HH), CZ gates, S gates, Toffoli gates (CCX), Fredkin gates (CSWAP), T gates, Y basis measurements (MYM_Y), or mixed basis parity measurements (like MXZM_{XZ}).

CSS Trajectories through Degenerate CSS Circuits

A “CSS stabilizer” is a stabilizer with positive sign equal to a product of ZZ operators or else to a product of XX operators. For example, Z2Z9Z_2Z_9 is a CSS stabilizer and X1X2X3X_1X_2X_3 is a CSS stabilizer and so is Z0Z_0, but X2Z3X_2Z_3 isn’t and neither is Y1Y_1 nor −X0-X_0.

A “CSS state” is a stabilizer state generated by CSS stabilizers. For example, the state ∣0⟩⊗n\lvert0\rangle^{\otimes n} is a CSS state because it is generated by the CSS stabilizers Z0Z_0, Z1Z_1, …\ldots, Zn−1Z_{n-1}.

A gate has a “CSS trajectory” if it can produce an output state that is a CSS state when given an input that is a CSS state. Furthermore, if the gate is a measurement, the measurement result must be 0 for the trajectory to count as a CSS trajectory.

A “degenerate stabilizer circuit” is a stabilizer circuit where it is possible for all measurement results to return 0 when the input state is the state ∣0⟩⊗n\lvert0\rangle^{\otimes n}.

A “degenerate CSS circuit” is a CSS circuit that contains no Pauli gates.

The efficient simulability of CSS circuits will come from the fact that degenerate CSS circuits are degenerate stabilizer circuits. We prove this by proving each gate in a degenerate CSS circuit has a CSS trajectory.

Lemma 2.1. CNOT gates have a CSS trajectory.

CNOTc→t_{c\to t} has the stabilizer flow generators Zc→ZcZ_c \to Z_c, Zt→ZcZtZ_t \to Z_cZ_t, Xc→XcXtX_c \to X_cX_t, and Xt→XtX_t \to X_t. These flows turn ZZ terms into ZZ terms, and XX terms into XX terms, so they preserve CSS-ness. Thus, conjugating a CSS stabilizer with a CNOT gate produces a CSS stabilizer. Therefore CNOT gates have CSS trajectories.

Lemma 2.2. MZM_Z gates have a CSS trajectory.

There are two cases to consider: the case where the MZM_Z measurement operation produces a deterministic result and the case where the result is random.

If the measurement is deterministic, then measurement operator ZmZ_m must be equal to a product of some subset of the ZZ basis CSS stabilizer generators of the input state. Because all the generators have positive sign, and positive ZZ-basis generators are closed under multiplication, the product of the CSS generators must produce +Zm+Z_m rather than −Zm-Z_m. Therefore, if the measurement is deterministic, the measurement result is 0. Also, because the measurement is determined, the state does not change and so since the input is a CSS state the output is equivalently a CSS state.

In the random case there must be at least one XX basis generator that anticommutes with the measurement (among the nn CSS stabilizer generators of the nn-qubit input state). Choose any one of these anticommuting generators to be the “victim”. Multiply the victim into the other generators that anticommute with the measurement, causing those generators to now commute with the measurement. This preserves the fact the stabilizer generators are CSS stabilizers, because XX-basis CSS stabilizers are closed under multiplication. Now only the victim anticommutes with measurement operator. The generators of the output state are the non-victim generators and also the measurement operator ±Zm\pm Z_m. The sign of the new generator is determined by the random result of the measurement. The CSS trajectory is the one where the measurement result is 0.

In both the deterministic and random case, the output state can be a CSS state. Therefore MZM_Z has a CSS trajectory.

Lemma 2.3. MXM_X gates have a CSS trajectory.

The proof that X-basis measurements have CSS trajectories is identical to the proof for Z-basis measurements, but with X and Z exchanged.

Theorem 2.4. Degenerate CSS circuits are degenerate stabilizer circuits.

A degenerate CSS circuit is built from CNOT gates, MXM_X gates, and MZM_Z gates. These gates have CSS trajectories, and the initial state ∣0⟩⊗n\lvert0\rangle^{\otimes n} is a CSS state, therefore the circuit as a whole has a CSS trajectory. CSS trajectories only produce measurement results equal to 0, therefore the all-zeroes sample is possible. Therefore a degenerate CSS circuit is a degenerate stabilizer circuit.

CSS Simulation

In [7] it is shown that the difficult part of sampling from a stabilizer circuit is getting the first sample (the “reference sample”). If the circuit has no probabilistic or adaptive gates, further samples can be produced by diffing against the reference sample with a flip simulation. Concretely, the simulation strategy is:

  1. Bootstrapping. Acquire one reference sample of the circuit (with noise removed) via some other stabilizer simulation method. This sample can be reused each time another shot is needed. The reference sample is a catalyst, not a consumable.

  1. Tracking. Store a “Pauli frame” PP tracking whether each qubit is bit and/or phase flipped.

  1. Unitary Conjugation. To apply a unitary gate GG, conjugate PP by GG.

  1. Measurement Perturbation. The result of a measurement operation that measures MM is the result of the measurement recorded in the reference sample, except it’s inverted if PP anticommutes with MM.

  1. Stabilizer Randomization. When measuring or preparing an operator MM, multiply MM into PP with 50% probability. (For example, to reset a qubit to ∣0⟩\lvert0\rangle, clear its tracked Pauli operator but then randomly multiply a ZZ back into its tracked Pauli.)

  1. Noise. When a Pauli product noise operator NN is sampled, multiply NN into PP.

The key insight is to notice that, if you are told that the circuit you will need to simulate is a degenerate stabilizer circuit, then you know that the all-zero sample is a valid reference sample. In effect, the bootstrapping step can be skipped and measurement results are purely whether the tracked Pauli frame PP anticommutes with the measured operator MM. Because all degenerate CSS circuits are degenerate stabilizer circuits, degenerate CSS circuits can be simulated in this simplified way. This works even if gates are adaptive or probabilistic, because the reference sample is always all-zero. Intended Pauli gates can then be accounted for by treating them as noise, yielding a straightforward simulation strategy for all CSS circuits.

In Figure 1 we present simple Python code that implements CSS circuit simulation. It’s trivial to see that the simulation strategy performs O(1)O(1) work per gate. Each qubit qq is represented as two bits: one bit xqx_q indicating if the qubit is bit flipped and one bit zqz_q indicating if the qubit is phase flipped. Qubits are initialized into the ∣0⟩\lvert0\rangle state by setting xqx_q to false and randomizing zqz_q. The Pauli X gate flips xqx_q. The Pauli Z gate flips zqz_q. The MXM_X gate reports zqz_q while randomizing xqx_q. The MZM_Z gate reports xqx_q while randomizing zqz_q. The CNOT gate controlled by cc and targeting tt xors xcx_c into xtx_t and also xors ztz_t into zcz_c. All of these implementations apply O(1)O(1) operations to O(1)O(1) bits, and so the simulator performs O(1)O(1) work per gate.

A CSS circuit simulator in twenty lines of Python

Figure 1. A CSS circuit simulator in twenty lines of Python.

import collections
import random

class CssCircuitSimulator:
    def __init__(self):
        # Qubits default to |0>, requiring stabilizer randomization of Z.
        self.zs = collections.defaultdict(lambda: random.random() < 0.5)
        self.xs = collections.defaultdict(bool)

    def x(self, target):
        self.xs[target] ^= True

    def z(self, target):
        self.zs[target] ^= True

    def cx(self, control, target):
        self.xs[target] ^= self.xs[control]  # bit flips propagate from control to target
        self.zs[control] ^= self.zs[target]  # phase kickback

    def mx(self, target) -> bool:
        self.xs[target] ^= random.random() < 0.5  # Stabilizer randomization.
        return self.zs[target]

    def mz(self, target) -> bool:
        self.zs[target] ^= random.random() < 0.5  # Stabilizer randomization.
        return self.xs[target]

CSS + Hadamard Violates Bell Inequalities

Looking at the form of the code in Figure 1, it seems easy to add support for Hadamard gates. Hadamard exchanges the X and Z axes of a qubit, and so one might expect the Hadamard can be simulated by simply swapping the X and Z bits associated with a qubit. However, this is wrong. For example, the resulting simulation code acts as if (Ha⋅CNOT⁡a→b)4(H_a \cdot\operatorname{CNOT}_{a\to b})^4 has no effect when actually that gate sequence is equivalent to XbX_b. In fact, there is a fundamental obstacle to adding support for the Hadamard gate to this simulator.

Note that the simulator in Figure 1 corresponds to a local hidden variable model. Each qubit is represented by two bits, and those bits directly specify the results of possible measurements of the qubit. Bell inequalities cannot be violated by local hidden variable models [4]. Therefore, if CSS+H circuits can violate Bell inequalities, the simulator cannot possibly support Hadamard gates without some sort of major change.

The GHZ test [6] has a Bell inequality. In this test, three spacelike separated players are given respective bits x,y,zx,y,z. The bits are promised to satisfy (x+y+z) mod 2=0(x+y+z)\bmod2=0. The players produce respective bits A,B,CA,B,C. They pass the test if (A+B+C) mod 2=(x+y+z)/2(A+B+C) \bmod2=(x+y+z)/2. When x,y,zx,y,z are chosen uniformly randomly, classical players fail the test at least 25% of the time [6]. Quantum players can pass 100% of the time by consuming entanglement [6].

The traditional quantum circuit for passing the GHZ test is a CSS + S circuit (see Figure 2). We were also able to construct GHZ-passing CSS + H and CSS + CZ circuits (see Figure 3 and Figure 4). Therefore no local hidden variable model (such as Figure 1) can simulate CSS + H, CSS + S, or CSS + CZ circuits. This doesn’t prove there is no CSS + H simulator achieving O(1)O(1) work per gate, but it presents a clear locality obstacle that would need to be overcome.

CSS + S circuit that passes the GHZ test

Figure 2. A CSS + S circuit that passes the GHZ test. Left half is the preparation of the entangled state before the test. Right half is the spacelike separated portion used during the test. Click here to open in Quirk.

CSS + H circuit that passes the GHZ test

Figure 3. A CSS + H circuit that passes the GHZ test. Left half is the preparation of the entangled state before the test. Right half is the spacelike separated portion used during the test. Click here to open in Quirk.

CSS + CZ circuit that passes the GHZ test

Figure 4. A CSS + CZ circuit that passes the GHZ test. Left half is the preparation of the entangled state before the test. Right half is the spacelike separated portion used during the test. Click here to open in Quirk.

Conclusion

In this paper, we showed that circuits built from Pauli gates, Controlled-Not gates, X basis measurement, and Z basis measurement can be simulated in constant time per gate. We called these circuits “CSS circuits”. Despite their simplicity, CSS circuits can implement a variety of quantum protocols: teleportation, superdense coding, error correction, and even entanglement purification. However, they cannot violate Bell inequalities (unless H or S or CZ or some other gate is added to the available gates). They can simulate some uses of entanglement, but not all uses.

An interesting practical question that we didn’t explore in this paper is whether compiled CSS circuits can be efficiently reverse engineered. For example, consider a circuit produced by individually compiling the CNOT gates of a CSS circuit into CZ+Hadamard gates. This circuit is not strictly CSS, but it is “secretly CSS”. We leave the question of how to detect if a circuit is “secretly CSS”, and how to safely and efficiently simulate such circuits, as future work.

An interesting theoretical question that we didn’t explore in this paper is non-CSS-ness as a resource. For example, note that Figure 3 uses non-CSS gates to create the entangled state distributed to the players but doesn’t need non-CSS gates when consuming the state. This is an example of non-CSS-ness being encoded into a state, similar to how non-stabilizer-ness can be encoded into states like ∣0⟩+i∣1⟩|0\rangle+ \sqrt{i}|1\rangle [5].

CSS circuits are such a simple concept that we cannot help but suspect we have merely rediscovered them. For example, phase-free ZX diagrams [9] are clearly analogous. Regardless, we hope that readers leave this paper with fresh awareness of a useful concept.

Contributions

Cody Jones discovered CSS circuits and showed they are efficiently simulable. Craig Gidney noticed the Bell inequality obstacle preventing the simulator from supporting other gates. Craig Gidney wrote the paper. No AI tools were used in the conception or writing of this paper.

Acknowledgements

We thank Hartmut Neven, and the entire Google Quantum AI team, for creating an environment where this work was possible.

References

  1. [1]Simon Anders and Hans J. Briegel. “Fast simulation of stabilizer circuits using a graph-state representation”. In: Physical Review A 73.2 (Feb. 2006). ISSN: 1094-1622. DOI: 10.1103/physreva.73.022334. URL: http://dx.doi.org/10.1103/PhysRevA.73.022334 (Cited on page 1).
  2. [2]Victor V. Albert and Philippe Faist, eds. The Error Correction Zoo. 2026. DOI: 10.48550/arXiv.2606.11484. eprint: 2606.11484. URL: https://errorcorrectionzoo.org/ (Cited on page 1).
  3. [3]Scott Aaronson and Daniel Gottesman. “Improved simulation of stabilizer circuits”. In: Physical Review A 70.5 (2004), p. 052328. DOI: 10.1103/PhysRevA.70.052328 (Cited on page 1).DOI
  4. [4]J. S. Bell. “On the Einstein Podolsky Rosen paradox”. In: Physics Physique Fizika 1.3 (Nov. 1964), pp. 195–200. ISSN: 0554-128X. DOI: 10.1103/physicsphysiquefizika.1.195. URL: http://dx.doi.org/10.1103/PhysicsPhysiqueFizika.1.195 (Cited on page 4).
  5. [5]Sergey Bravyi and Alexei Kitaev. “Universal quantum computation with ideal Clifford gates and noisy ancillas”. In: Physical Review A 71.2 (2005), p. 022316 (Cited on page 6).DOI
  6. [6]Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. “Going Beyond Bell’s Theorem”. In: Bell’s Theorem, Quantum Theory and Conceptions of the Universe. Springer Netherlands, 1989, pp. 69–72. ISBN: 9789401708494. DOI: 10.1007/978-94-017-0849-4_10. URL: http://dx.doi.org/10.1007/978-94-017-0849-4_10 (Cited on page 4).
  7. [7]Craig Gidney. “Stim: a fast stabilizer circuit simulator”. In: Quantum 5 (July 2021), p. 497. ISSN: 2521-327X. DOI: 10.22331/q-2021-07-06-497 (Cited on pages 1, 3).DOI
  8. [8]Daniel Gottesman. “The Heisenberg Representation of Quantum Computers”. In: (1998). DOI: 10.48550/ARXIV.QUANT-PH/9807006. URL: https://arxiv.org/abs/quant-ph/9807006 (Cited on page 1).
  9. [9]Aleks Kissinger. Phase-free ZX diagrams are CSS codes (...or how to graphically grok the surface code). 2022. DOI: 10.48550/ARXIV.2204.14038. URL: https://arxiv.org/abs/2204.14038 (Cited on page 6).

Paper details

vlnc:W_7z98f7zx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents