Stabilizer formalism

Stabilizer formalism is a mathematical framework for representing and efficiently simulating certain quantum states (stabilizer states) using only Pauli operations. A stabilizer state is uniquely defined as the eigenstate with eigenvalue $+1$ of a set of commuting Pauli operators (stabilizers). This restriction enables polynomial-time simulation of Clifford circuits and provides the foundation for quantum error correction.

A stabilizer state $|\psi\rangle$ is a state fixed by a group of commuting Pauli operators:

$$S_i |\psi\rangle = |\psi\rangle$$

for each stabilizer $S_i$ in a set $\{S_1, S_2, \ldots, S_n\}$. The stabilizer group $\mathcal{S}$ is the group generated by these stabilizers. For an $n$-qubit state, a minimal stabilizer set has $n$ independent generators.

Example: The Bell state $|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ is stabilized by $XX$ and $ZZ$:

$$XX |\Phi^+\rangle = |\Phi^+\rangle, \quad ZZ |\Phi^+\rangle = |\Phi^+\rangle$$

Clifford gates (H, S, CNOT, etc.) map Pauli operators to Pauli operators via conjugation: $C P C^\dagger$ is Pauli for any Clifford $C$ and Pauli $P$. This property means Clifford gates preserve the stabilizer structure—applying a Clifford to a stabilizer state yields another stabilizer state with transformed stabilizers.

A stabilizer circuit (Clifford-only circuit) can be simulated in polynomial time using tableau representation, making it efficient for circuits with hundreds or thousands of qubits.

Stabilizer states are represented efficiently using a binary matrix (tableau) encoding the Pauli generators. Each stabilizer is a Pauli on $n$ qubits, representable as $2n$ bits:

$$S_i = \pm i^{a_i} X^{x_{i,1}} Z^{z_{i,1}} X^{x_{i,2}} Z^{z_{i,2}} \cdots$$

where $x_{i,j}, z_{i,j} \in \{0, 1\}$ indicate whether Pauli X or Z acts on qubit $j$. The tableau is a $(n+1) \times (2n+1)$ matrix with one extra row for tracking the overall phase.

Operations on stabilizer states become linear algebra operations on the tableau:

• H: swaps X and Z columns for the target qubit
• S: adds Z to X for the target qubit (in the tableau)
• CNOT: adds rows (controlled-qubit X acts on target Z, target X acts on control Z)

Measuring a qubit in the computational basis:

1. Find a stabilizer involving that qubit
2. The measurement outcome is the eigenvalue ($+1$ or $-1$) when applied to the current state
3. Remove that stabilizer from the tableau (measurement projects the state)

This requires no exponential state vector. Pauli basis measurements work similarly with basis rotation.

• Clifford-only circuits: $O(n^3)$ per gate using Gaussian elimination on the tableau
• Adding one non-Clifford gate (e.g., T gate): exponential resources required; the state exits the stabilizer code
• Practical range: ~1000-qubit Clifford circuits are simulatable; mixing in T gates reduces this dramatically

This is the basis of the Gottesman-Knill theorem: Clifford circuits can be simulated classically in polynomial time.

Quantum error-correcting codes (surface codes, toric codes, CSS codes) use stabilizer codes to detect and correct errors:

• Stabilizer generators: operators that commute with the code's logical operators
• Syndrome measurements: measure stabilizer eigenvalues to detect errors without measuring the state
• Error correction: use syndrome data (classical) to identify and correct Pauli errors

This allows quantum computations to remain in the code space throughout the circuit.

Stabilizer formalism works because:

• Any error is a Pauli operator (by assumption in error models)
• Pauli anticommutation structure encodes error information
• Measuring stabilizers (which commute with logical operators) reveals error type without collapsing logical state

• Non-Clifford gates: States with T gates or other non-Clifford gates escape stabilizer formalism
• Non-stabilizer states: Superpositions outside the stabilizer code require exponential representation
• Entanglement structure: Limited to graph states and their local-Clifford variants

• Quantum simulation: Efficient simulation of Clifford circuits in classical simulators (e.g., Qiskit Aer with stabilizer backend)
• Error correction: Designing and analyzing quantum error-correcting codes
• Circuit verification: Proving equivalence of Clifford-only circuit implementations
• Classical verification: Verifying quantum computations on small qubit counts with classical overhead

• Clifford gates: gates that preserve stabilizer structure
• Pauli gates: generators of stabilizer operators and errors
• Stabilizer states: states representable in this formalism
• Error correction: surface codes, toric codes, CSS codes
• Gottesman-Knill theorem: Clifford circuits simulate classically in polynomial time