The Stabilizer Formalism
Describing states and codes by the Paulis that fix them.
An -qubit stabilizer state has amplitudes, yet Pauli operators pin it down exactly. Encode each Pauli as a string of bits and the theory of stabilizer codes becomes linear algebra over : counting logical qubits, finding logical operators, and simulating Clifford circuits in polynomial time.
What you’ll learn
- Represent Paulis as vectors in and express commutation through the symplectic form.
- Prove and logical Paulis on qubits by symplectic linear algebra.
- Use check matrices to read off 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 -qubit Pauli group can be written as
with and . For example corresponds to . Forgetting the phase gives a group isomorphism : multiplying Paulis adds their bit vectors mod 2.
On each qubit , so a sign appears wherever both and .
Move past .
The opposite order carries ; divide. The form is bilinear, alternating () and non-degenerate: a symplectic form, with .
Use to decide whether and commute.
- They commute:
- They anticommute:
- They commute, because they have the same weight
- It cannot be decided without the phases
Show the answer
B. They anticommute:
and . Then : they anticommute. Directly: they clash on all three qubits, an odd number.
Codespaces, normalizers and logical operators
Let be the image of , so . Commutativity of says , where is the symplectic complement: is isotropic. A Pauli normalizes if and only if it commutes with every generator, so the normalizer is exactly (with phases).
The same linear algebra gives a canonical form: Witt's theorem provides a Clifford unitary with for (signs fixed by Paulis). Every stabilizer code is therefore , a trivial code in disguise. All the protection lies in how spreads the information across qubits.
Think first How many cosets does have, ignoring phases, for an code?
: exactly the size of the -qubit Pauli group modulo phases, .
Clifford circuits and the Gottesman–Knill theorem
The Clifford group consists of the unitaries that map Paulis to Paulis under conjugation; up to phases it is generated by , and CNOT. Conjugation acts linearly on bit vectors and preserves , and modulo Paulis and phases is the symplectic group , of order . For that is 6, times 4 Paulis: the 24 single-qubit Cliffords up to phase.
| Gate | Action on | Action on |
|---|---|---|
| (so ) | ||
| CNOT (control 1) | , | , |
Invariant. The state is always a stabilizer state, stored as generators: an binary matrix plus sign bits. Initially the generators are .
Gates. If stabilizes , then stabilizes . Conjugate each generator using the table: constant work per generator, per gate.
Random outcomes. To measure a Pauli : if some generator anticommutes with , the outcome is with probability each. (Conjugation by swaps the projectors while fixing , so both projections have equal norm.) Replace by and multiply every other anticommuting generator by the old , so that all generators commute again.
Deterministic outcomes. If commutes with every generator, then , because with the normalizer equals up to phases ( coset). The outcome is the sign, found by writing as a product of generators: by Gaussian elimination, or if destabilizers are stored too. Every step is polynomial.
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 (see Fault Tolerance). Below, think in stabilizers rather than amplitudes.
Stabilizer states, graph states and the frontier
With the codespace is one-dimensional: a stabilizer state. There are exactly of them on 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 , stabilized by . 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 stabilizer states (its stabilizer rank) lets you simulate Clifford circuits on it at a cost that scales with ; this yields algorithms for circuits with gates whose cost is exponential in but only polynomial in (Bravyi, Gosset and collaborators, 2016).
Key takeaways
- Paulis modulo phases form , and commutation is the symplectic form .
- A stabilizer code is an isotropic subspace of dimension ; logical operators live in with , and .
- Every stabilizer code is a Clifford-rotated trivial code, ; the Clifford group modulo Paulis is .
- Gottesman–Knill: Clifford circuits with Pauli measurements are simulable in polynomial time by updating an 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.
With and , the Paulis and commute if and only if…
- and
Show the answer
C.
A sign arises each time a of one operator meets an of the other, which counts and . Their parity is the symplectic form .
For an stabilizer code, how many cosets does have, ignoring phases?
Show the answer
A.
, so there are cosets: one for each logical Pauli in .
Which addition to a Clifford circuit (stabilizer inputs, Pauli measurements) takes it beyond the Gottesman–Knill simulation, as far as anyone knows?
- Mid-circuit Pauli measurements with classical feed-forward
- Preparing a 1000-qubit GHZ state
- Starting some qubits in instead of
- Many gates (or other non-Clifford gates)
Show the answer
D. Many 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.
A check matrix on qubits has rank 4 and satisfies . You find a weight-2 Pauli with zero syndrome that is not in . What can you conclude?
- and
- and
- and
- The matrix does not define a valid code
Show the answer
B. and
. A weight-2 element of is a logical operator, so the minimum weight 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).