Binary-Tableau Stabilizer Simulation

Stabilizer simulation represents a quantum state by commuting Pauli constraints instead of amplitudes. For Clifford gates and Pauli measurements this representation supports polynomial classical algorithms, even for highly entangled states. It does not provide a generic efficient simulator for arbitrary non-Clifford circuits.

Helpful background. Stabilizer formalism supplies the state definition; statevector simulation provides a small-register reference.

Binary symplectic representation

Represent a Pauli string by binary vectors $x,z\in\mathbb F_2^n$ and a phase. A convenient algebraic convention is

$$P=i^p X^{x_0}Z^{z_0}\otimes\cdots\otimes X^{x_{n-1}}Z^{z_{n-1}}, \qquad p\in\mathbb Z_4.$$

Then multiplication gives

$$(x,z,p)(x',z',p') =(x+x',z+z',p+p'+2z\cdot x'),$$

with binary vector sums and phase modulo four. The cross term comes from moving $Z$ through $X$. Two strings commute exactly when $x\cdot z'+z\cdot x'=0$ modulo two.

For Hermitian stabilizer generators one can instead store a sign bit and a Hermitian Pauli convention, but the update rules must match it. Dropping phase information changes the state even if all commutators remain correct.

Gate updates by conjugation

Hadamard exchanges $X$ and $Z$ and sends $Y$ to $-Y$. The phase gate $S=\operatorname{diag}(1,i)$ sends $X$ to $Y$, $Y$ to $-X$, and fixes $Z$. Controlled-$X$ maps

$$X_c\mapsto X_cX_t,\quad Z_t\mapsto Z_cZ_t,\quad Z_c\mapsto Z_c,\quad X_t\mapsto X_t.$$

Update each generator using these conjugation rules and the chosen phase convention. Deriving a table from actual one- and two-qubit matrices is safer than mixing binary formulas from different conventions.

For the explicit $i^pX^xZ^z$ convention above, these give executable updates using the old bits:

$$\begin{aligned} H_j:&\quad p\leftarrow p+2x_jz_j,\quad (x_j,z_j)\leftarrow(z_j,x_j),\\ S_j:&\quad p\leftarrow p+x_j,\quad z_j\leftarrow z_j\oplus x_j,\\ \operatorname{CNOT}_{c,t}:&\quad x_t\leftarrow x_t\oplus x_c,\quad z_c\leftarrow z_c\oplus z_t. \end{aligned}$$

All unspecified components remain unchanged; $p$ is reduced modulo four. In this convention CNOT leaves $p$ unchanged. The familiar additional sign update in a Hermitian-Pauli tableau belongs to a different encoding and must not be added here. For example $Y=iXZ$ has $(x,z,p)=(1,1,1)$: Hadamard changes $p$ to three, giving $-Y$, while $S$ gives $(1,0,2)$, namely $-X$. Exhaustively compare all 16 two-qubit Pauli strings under CNOT with dense conjugation before testing larger circuits.

An $n$-qubit pure stabilizer state has $n$ independent commuting generators and cannot contain $-I$. Store $O(n^2)$ bits plus phases. Destabilizer rows can accelerate measurements, as in the Aaronson–Gottesman tableau.

Pauli measurements

If measured Pauli $M$ anticommutes with at least one stabilizer generator, the outcomes $\pm1$ are equiprobable. Choose one anticommuting generator as pivot, multiply it into the other anticommuting rows to make them commute with $M$, and replace the pivot by the sampled signed $M$.

If $M$ commutes with all generators of a pure stabilizer state, its outcome is deterministic. Determine whether $M$ or $-M$ belongs to the generated group, including phases. Commutation alone does not determine the sign.

The qualification “pure” is essential: fewer than $n$ independent generators describe a code subspace or a mixed stabilizer state. A Pauli commuting with those generators may be a logical observable with an undetermined outcome. For instance, the sole two-qubit generator $Z_0Z_1$ permits both Bell phases; it does not determine $X_0X_1$. Supply the encoded state or an explicit mixed-state representation before sampling it.

These rules preserve a valid generating set and give both outcomes and postmeasurement states without amplitudes.

Bell-state benchmark

Start from stabilizers $Z_0,Z_1$ of $|00\rangle$. Hadamard on 0 gives $X_0,Z_1$; controlled-$X$ gives $X_0X_1,Z_0Z_1$. Measuring $Z_0$ is random, and measuring $Z_1$ afterward gives the same outcome. Measuring $Z_0Z_1$ directly is deterministically $+1$.

The state $(|00\rangle-|11\rangle)/\sqrt2$ instead has generator $-X_0X_1$. This phase-sensitive pair tests errors invisible to computational-basis histograms.

Limits and tests

Compare random small Clifford circuits and measurements with statevectors, including conditional branches. Check generator independence, pairwise commutation, and absence of $-I$ after every update.

Pauli noise can be sampled within stabilizer simulation; arbitrary amplitude damping or a $T$ gate generally leaves the stabilizer class. Approximate decompositions introduce additional computational cost and error. High entanglement alone is not a criterion for classical hardness: Bell pairs and many graph states have compact stabilizer descriptions.

Exercise

Why does a $T$ gate on $|+\rangle$ defeat a single stabilizer tableau?

Solution

$T=\operatorname{diag}(1,e^{i\pi/4})$ rotates $X$ into $(X+Y)/\sqrt2$, which is not a Pauli string. The resulting state is not the unique $+1$ eigenstate of a nontrivial single-qubit Pauli, so the Pauli-generator representation is no longer closed.

References

• Aaronson, S., and Gottesman, D., “Improved simulation of stabilizer circuits,” Physical Review A 70, 052328 (2004), arXiv:quant-ph/0406196.
• Gottesman, D., “The Heisenberg representation of quantum computers,” in Group22, 32–43 (1999), arXiv:quant-ph/9807006.