Simple Algorithm
Quantum Computing · Rydberg State · 30 min

The Stabilizer Formalism

Describing states and codes by the Paulis that fix them.

An nn-qubit stabilizer state has 2n2^n amplitudes, yet nn Pauli operators pin it down exactly. Encode each Pauli as a string of 2n2n bits and the theory of stabilizer codes becomes linear algebra over F2\mathbb{F}_2: counting logical qubits, finding logical operators, and simulating Clifford circuits in polynomial time.

What you’ll learn

  • Represent Paulis as vectors in F22n\mathbb{F}_2^{2n} and express commutation through the symplectic form.
  • Prove dim⁡C(S)=2n−r\dim\mathcal{C}(\mathcal{S})=2^{n-r} and N(S)/S≅\mathcal{N}(\mathcal{S})/\mathcal{S}\cong logical Paulis on k=n−rk=n-r qubits by symplectic linear algebra.
  • Use check matrices to read off [[n,k,d]][[n,k,d]] and construct logical operators.
  • State and prove the Gottesman–Knill theorem with the stabilizer tableau, and explain what it says about quantum speedups.

Paulis as bit strings

Every element of the nn-qubit Pauli group can be written as

P=ic XxZz,Xx=Xx1⊗⋯⊗Xxn,Zz=Zz1⊗⋯⊗Zzn,P = i^{c}\,X^{\mathbf{x}}Z^{\mathbf{z}},\qquad X^{\mathbf{x}}=X^{x_1}\otimes\cdots\otimes X^{x_n},\quad Z^{\mathbf{z}}=Z^{z_1}\otimes\cdots\otimes Z^{z_n},

with x,z∈F2n\mathbf{x},\mathbf{z}\in\mathbb{F}_2^n and c∈{0,1,2,3}c\in\{0,1,2,3\}. For example Y=iXZY=iXZ corresponds to (x∣z)=(1∣1)(x|z)=(1|1). Forgetting the phase gives a group isomorphism Pn/⟨iI⟩≅F22n\mathcal{P}_n/\langle iI\rangle\cong\mathbb{F}_2^{2n}: multiplying Paulis adds their bit vectors mod 2.

DerivationCommutation is a symplectic form
  1. ZzXx′=(−1)z⋅x′ Xx′ZzZ^{\mathbf{z}}X^{\mathbf{x}'} = (-1)^{\mathbf{z}\cdot\mathbf{x}'}\,X^{\mathbf{x}'}Z^{\mathbf{z}}

    On each qubit ZX=−XZZX=-XZ, so a sign appears wherever both zj=1z_j=1 and xj′=1x'_j=1.

  2. (XxZz)(Xx′Zz′)=(−1)z⋅x′ Xx+x′Zz+z′\big(X^{\mathbf{x}}Z^{\mathbf{z}}\big)\big(X^{\mathbf{x}'}Z^{\mathbf{z}'}\big) = (-1)^{\mathbf{z}\cdot\mathbf{x}'}\,X^{\mathbf{x}+\mathbf{x}'}Z^{\mathbf{z}+\mathbf{z}'}

    Move ZzZ^{\mathbf{z}} past Xx′X^{\mathbf{x}'}.

  3. PP′=(−1)ω(v,v′) P′P,ω((x∣z),(x′∣z′))=x⋅z′+z⋅x′ mod 2PP' = (-1)^{\omega(v,v')}\,P'P,\qquad \omega\big((\mathbf{x}|\mathbf{z}),(\mathbf{x}'|\mathbf{z}')\big) = \mathbf{x}\cdot\mathbf{z}' + \mathbf{z}\cdot\mathbf{x}' \bmod 2

    The opposite order carries (−1)z′⋅x(-1)^{\mathbf{z}'\cdot\mathbf{x}}; divide. The form ω\omega is bilinear, alternating (ω(v,v)=0\omega(v,v)=0) and non-degenerate: a symplectic form, ω(v,v′)=v Λ v′T\omega(v,v')=v\,\Lambda\,v'^{T} with Λ=(0II0)\Lambda=\begin{pmatrix}0&I\\I&0\end{pmatrix}.

H[[5,1,3]]=(1001001100010010011010100000110101010001)H_{[[5,1,3]]} = \left(\begin{array}{ccccc|ccccc} 1&0&0&1&0 & 0&1&1&0&0\\ 0&1&0&0&1 & 0&0&1&1&0\\ 1&0&1&0&0 & 0&0&0&1&1\\ 0&1&0&1&0 & 1&0&0&0&1 \end{array}\right)
The five-qubit code: rows XZZXIXZZXI, IXZZXIXZZX, XIXZZXIXZZ, ZXIXZZXIXZ. Rows 1 and 2 give x1⋅z2+z1⋅x2=1+1=0\mathbf{x}_1\cdot\mathbf{z}_2+\mathbf{z}_1\cdot\mathbf{x}_2=1+1=0: they commute (and so do all other pairs).
Check your understanding

Use ω\omega to decide whether X⊗Y⊗ZX\otimes Y\otimes Z and Z⊗Z⊗XZ\otimes Z\otimes X commute.

  1. They commute: ω=0\omega=0
  2. They anticommute: ω=1\omega=1
  3. They commute, because they have the same weight
  4. It cannot be decided without the phases
Show the answer

B. They anticommute: ω=1\omega=1

XYZ↦(110 ∣ 011)XYZ\mapsto(110\,|\,011) and ZZX↦(001 ∣ 110)ZZX\mapsto(001\,|\,110). Then x⋅z′+z⋅x′=(110)⋅(110)+(011)⋅(001)=0+1=1\mathbf{x}\cdot\mathbf{z}'+\mathbf{z}\cdot\mathbf{x}'=(110)\cdot(110)+(011)\cdot(001)=0+1=1: they anticommute. Directly: they clash on all three qubits, an odd number.

Codespaces, normalizers and logical operators

Let V=rowspace⁡(H)⊂F22nV=\operatorname{rowspace}(H)\subset\mathbb{F}_2^{2n} be the image of S\mathcal{S}, so dim⁡V=r\dim V=r. Commutativity of S\mathcal{S} says V⊆V⊥V\subseteq V^{\perp}, where V⊥={w:ω(v,w)=0 ∀v∈V}V^\perp=\{w:\omega(v,w)=0\ \forall v\in V\} is the symplectic complement: VV is isotropic. A Pauli normalizes S\mathcal{S} if and only if it commutes with every generator, so the normalizer N(S)\mathcal{N}(\mathcal{S}) is exactly V⊥V^\perp (with phases).

The same linear algebra gives a canonical form: Witt's theorem provides a Clifford unitary UU with UgiU†=ZiUg_iU^\dagger=Z_i for i=1,…,ri=1,\dots,r (signs fixed by Paulis). Every stabilizer code is therefore U(∣0⟩⊗r⊗C2k)U\big(\ket{0}^{\otimes r}\otimes\C^{2^k}\big), a trivial code in disguise. All the protection lies in how UU spreads the information across qubits.

Think first How many cosets does N(S)/S\mathcal{N}(\mathcal{S})/\mathcal{S} have, ignoring phases, for an [[n,k,d]][[n,k,d]] code?

∣V⊥/V∣=2(n+k)−(n−k)=4k\abs{V^\perp/V}=2^{(n+k)-(n-k)}=4^k: exactly the size of the kk-qubit Pauli group modulo phases, {I,X,Y,Z}⊗k\{I,X,Y,Z\}^{\otimes k}.

Clifford circuits and the Gottesman–Knill theorem

The Clifford group Cn\mathcal{C}_n consists of the unitaries that map Paulis to Paulis under conjugation; up to phases it is generated by HH, SS and CNOT. Conjugation acts linearly on bit vectors and preserves ω\omega, and modulo Paulis and phases Cn\mathcal{C}_n is the symplectic group Sp(2n,F2)Sp(2n,\mathbb{F}_2), of order 2n2∏j=1n(4j−1)2^{n^2}\prod_{j=1}^n(4^j-1). For n=1n=1 that is 6, times 4 Paulis: the 24 single-qubit Cliffords up to phase.

GateAction on XXAction on ZZ
HHX↦ZX\mapsto ZZ↦XZ\mapsto X (so Y↦−YY\mapsto-Y)
SSX↦YX\mapsto YZ↦ZZ\mapsto Z
CNOT (control 1)X1↦X1X2X_1\mapsto X_1X_2, X2↦X2X_2\mapsto X_2Z1↦Z1Z_1\mapsto Z_1, Z2↦Z1Z2Z_2\mapsto Z_1Z_2
Update rules P↦UPU†P\mapsto UPU^\dagger. Each gate touches O(1)\order{1} columns of the tableau.
DerivationProof: track the stabilizer, not the state
  1. Invariant. The state is always a stabilizer state, stored as nn generators: an n×2nn\times2n binary matrix plus nn sign bits. Initially the generators are Z1,…,ZnZ_1,\dots,Z_n.

  2. U∣ψ⟩=Ug∣ψ⟩=(UgU†) U∣ψ⟩U\ket{\psi} = U g\ket{\psi} = (UgU^\dagger)\,U\ket{\psi}

    Gates. If gg stabilizes ∣ψ⟩\ket{\psi}, then UgU†UgU^\dagger stabilizes U∣ψ⟩U\ket{\psi}. Conjugate each generator using the table: constant work per generator, O(n)\order{n} per gate.

  3. Random outcomes. To measure a Pauli MM: if some generator gpg_p anticommutes with MM, the outcome is ±1\pm1 with probability 12\tfrac12 each. (Conjugation by gpg_p swaps the projectors 12(I±M)\tfrac12(I\pm M) while fixing ∣ψ⟩\ket{\psi}, so both projections have equal norm.) Replace gpg_p by ±M\pm M and multiply every other anticommuting generator by the old gpg_p, so that all generators commute again.

  4. Deterministic outcomes. If MM commutes with every generator, then ±M∈S\pm M\in\mathcal{S}, because with r=nr=n the normalizer equals S\mathcal{S} up to phases (40=14^0=1 coset). The outcome is the sign, found by writing ±M\pm M as a product of generators: O(n3)\order{n^3} by Gaussian elimination, or O(n2)\order{n^2} if destabilizers are stored too. Every step is polynomial. □\square

Clifford circuits produce GHZ states, cluster states and the codewords of every stabilizer code: massive entanglement, all classically simulable. So entanglement alone does not explain quantum speedups. The missing ingredient is non-stabilizerness, or magic, supplied by gates such as TT (see Fault Tolerance). Below, think in stabilizers rather than amplitudes.

Stabilizer states, graph states and the frontier

With r=nr=n the codespace is one-dimensional: a stabilizer state. There are exactly 2n∏j=1n(2j+1)2^n\prod_{j=1}^{n}(2^j+1) of them on nn qubits: 6 for one qubit (the six poles of the Bloch axes), 60 for two. Every stabilizer state is equivalent under local Cliffords to a graph state ∣G⟩=∏(a,b)∈ECZab∣+⟩⊗n\ket{G}=\prod_{(a,b)\in E}CZ_{ab}\ket{+}^{\otimes n}, stabilized by Ka=Xa∏b∼aZbK_a=X_a\prod_{b\sim a}Z_b. The cluster state you built is the graph state of a path.

Beyond Clifford circuits the simulation cost grows with the non-Clifford content. Writing a state as a sum of χ\chi stabilizer states (its stabilizer rank) lets you simulate Clifford circuits on it at a cost that scales with χ\chi; this yields algorithms for circuits with tt TT gates whose cost is exponential in tt but only polynomial in nn (Bravyi, Gosset and collaborators, 2016).

Key takeaways

  • Paulis modulo phases form F22n\mathbb{F}_2^{2n}, and commutation is the symplectic form ω(v,v′)=x⋅z′+z⋅x′\omega(v,v')=\mathbf{x}\cdot\mathbf{z}'+\mathbf{z}\cdot\mathbf{x}'.
  • A stabilizer code is an isotropic subspace VV of dimension rr; logical operators live in V⊥/V≅F22kV^\perp/V\cong\mathbb{F}_2^{2k} with k=n−rk=n-r, and d=min⁡wt⁡(V⊥∖V)d=\min\operatorname{wt}(V^\perp\setminus V).
  • Every stabilizer code is a Clifford-rotated trivial code, U(∣0⟩⊗r⊗C2k)U(\ket0^{\otimes r}\otimes\C^{2^k}); the Clifford group modulo Paulis is Sp(2n,F2)Sp(2n,\mathbb{F}_2).
  • Gottesman–Knill: Clifford circuits with Pauli measurements are simulable in polynomial time by updating an n×2nn\times2n tableau, so entanglement alone does not give speedups.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

With P↦(x∣z)P\mapsto(\mathbf{x}|\mathbf{z}) and P′↦(x′∣z′)P'\mapsto(\mathbf{x}'|\mathbf{z}'), the Paulis PP and P′P' commute if and only if…

  1. x⋅x′+z⋅z′=0(mod2)\mathbf{x}\cdot\mathbf{x}'+\mathbf{z}\cdot\mathbf{z}'=0 \pmod 2
  2. x=x′\mathbf{x}=\mathbf{x}' and z=z′\mathbf{z}=\mathbf{z}'
  3. x⋅z′+z⋅x′=0(mod2)\mathbf{x}\cdot\mathbf{z}'+\mathbf{z}\cdot\mathbf{x}'=0 \pmod 2
  4. x⋅z=x′⋅z′(mod2)\mathbf{x}\cdot\mathbf{z}=\mathbf{x}'\cdot\mathbf{z}' \pmod 2
Show the answer

C. x⋅z′+z⋅x′=0(mod2)\mathbf{x}\cdot\mathbf{z}'+\mathbf{z}\cdot\mathbf{x}'=0 \pmod 2

A sign arises each time a ZZ of one operator meets an XX of the other, which counts z⋅x′\mathbf{z}\cdot\mathbf{x}' and x⋅z′\mathbf{x}\cdot\mathbf{z}'. Their parity is the symplectic form ω\omega.

Question 2

For an [[n,k,d]][[n,k,d]] stabilizer code, how many cosets does N(S)/S\mathcal{N}(\mathcal{S})/\mathcal{S} have, ignoring phases?

  1. 4k4^k
  2. 2k2^k
  3. 2n−k2^{n-k}
  4. 4n4^n
Show the answer

A. 4k4^k

dim⁡V⊥−dim⁡V=(n+k)−(n−k)=2k\dim V^\perp-\dim V=(n+k)-(n-k)=2k, so there are 22k=4k2^{2k}=4^k cosets: one for each logical Pauli in {I,X,Y,Z}⊗k\{I,X,Y,Z\}^{\otimes k}.

Question 3

Which addition to a Clifford circuit (stabilizer inputs, Pauli measurements) takes it beyond the Gottesman–Knill simulation, as far as anyone knows?

  1. Mid-circuit Pauli measurements with classical feed-forward
  2. Preparing a 1000-qubit GHZ state
  3. Starting some qubits in ∣+⟩\ket{+} instead of ∣0⟩\ket{0}
  4. Many TT gates (or other non-Clifford gates)
Show the answer

D. Many TT gates (or other non-Clifford gates)

Feed-forward, huge entanglement and other stabilizer inputs are all covered by the tableau method. Non-Clifford gates leave the stabilizer world; known simulation costs then grow exponentially with their number.

Question 4

A check matrix on n=6n=6 qubits has rank 4 and satisfies HΛHT=0H\Lambda H^T=0. You find a weight-2 Pauli with zero syndrome that is not in S\mathcal{S}. What can you conclude?

  1. k=4k=4 and d=2d=2
  2. k=2k=2 and d≤2d\le2
  3. k=2k=2 and d≥3d\ge3
  4. The matrix does not define a valid code
Show the answer

B. k=2k=2 and d≤2d\le2

k=n−rank⁡H=6−4=2k=n-\operatorname{rank}H=6-4=2. A weight-2 element of N(S)∖S\mathcal{N}(\mathcal{S})\setminus\mathcal{S} is a logical operator, so the minimum weight dd is at most 2 (it would be 1 if a weight-1 logical also existed).

Further reading

  • D. Gottesman, Stabilizer Codes and Quantum Error Correction, PhD thesis, Caltech (1997), arXiv:quant-ph/9705052.
  • A. R. Calderbank, E. M. Rains, P. W. Shor & N. J. A. Sloane, "Quantum error correction via codes over GF(4)", IEEE Trans. Inf. Theory 44 (1998).
  • D. Gottesman, "The Heisenberg representation of quantum computers" (1998), arXiv:quant-ph/9807006.
  • S. Aaronson & D. Gottesman, "Improved simulation of stabilizer circuits", Phys. Rev. A 70, 052328 (2004).
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §10.5 (Cambridge, 10th anniv. ed., 2010).