Simple Algorithm
Quantum Computing · Rydberg State · 30 min

The Pauli & Clifford Groups

The group structure behind stabilizers and error correction.

Conjugate a Pauli by HH and you get another Pauli. The unitaries with this property form the Clifford group: finite modulo phases, with exactly 24 single-qubit elements and 11,520 two-qubit ones, and secretly the symplectic group over F2\mathbb{F}_2. It is the backbone of stabilizer codes, randomized benchmarking and the Gottesman–Knill theorem.

What you’ll learn

  • Define the nn-qubit Pauli group, compute its order and center, and encode it in F22n\mathbb{F}_2^{2n} with the symplectic form.
  • Define the Clifford group as the normalizer of the Pauli group and prove Cn/(U(1)⋅Pn)≅Sp(2n,F2)\mathcal{C}_n/\big(U(1)\cdot\mathcal{P}_n\big)\cong Sp(2n,\mathbb{F}_2).
  • Derive ∣Cn/U(1)∣=2n2+2n∏j=1n(4j−1)\abs{\mathcal{C}_n/U(1)}=2^{n^2+2n}\prod_{j=1}^n(4^j-1), giving 24 and 11,520.
  • Identify the single-qubit Clifford group with the rotation group of the octahedron, and place TT in the Clifford hierarchy.

The Pauli group and its binary picture

Up to phase, a Pauli string is a pair of bit strings. Write P(a∣b)=Xa1Zb1⊗⋯⊗XanZbnP(\mathbf a|\mathbf b)=X^{a_1}Z^{b_1}\otimes\cdots\otimes X^{a_n}Z^{b_n} for (a∣b)∈F22n(\mathbf a|\mathbf b)\in\mathbb{F}_2^{2n}. Multiplication becomes addition, P(v)P(w)∝P(v+w)P(v)P(w)\propto P(v+w), so Pn/⟨iI⟩≅F22n\mathcal{P}_n/\langle i\id\rangle\cong\mathbb{F}_2^{2n}. All of the non-commutativity is captured by a single bilinear form.

DerivationCommutation is symplectic
  1. XaZb Xa′Zb′=(−1)ba′ Xa+a′Zb+b′X^aZ^b\,X^{a'}Z^{b'}=(-1)^{ba'}\,X^{a+a'}Z^{b+b'}

    Move ZbZ^b past Xa′X^{a'} using ZX=−XZZX=-XZ.

  2. XaZb Xa′Zb′=(−1)ab′+ba′  Xa′Zb′ XaZbX^aZ^b\,X^{a'}Z^{b'}=(-1)^{ab'+ba'}\;X^{a'}Z^{b'}\,X^aZ^b

    The product in the other order carries (−1)b′a(-1)^{b'a}; take the ratio.

  3. P(v)P(w)=(−1)ω(v,w)P(w)P(v),ω((a∣b),(a′∣b′))=a⋅b′+b⋅a′(mod2)P(v)P(w)=(-1)^{\omega(v,w)}P(w)P(v),\qquad\omega\big((\mathbf a|\mathbf b),(\mathbf a'|\mathbf b')\big)=\mathbf a\cdot\mathbf b'+\mathbf b\cdot\mathbf a'\pmod 2

    Tensor factors multiply their signs, so the exponents add. ω\omega is the standard symplectic form: bilinear, alternating (ω(v,v)=0\omega(v,v)=0) and non-degenerate.

Check your understanding

Do X⊗X⊗IX\otimes X\otimes\id and Z⊗Y⊗ZZ\otimes Y\otimes Z commute?

  1. No: XX and ZZ anticommute on the first qubit
  2. Yes: they anticommute on exactly two sites, and (−1)2=1(-1)^2=1
  3. No: Pauli strings that differ on every site never commute
  4. Only up to a factor of ii
Show the answer

B. Yes: they anticommute on exactly two sites, and (−1)2=1(-1)^2=1

Site by site: XX and ZZ anticommute, XX and YY anticommute, I\id and ZZ commute. Two sign flips cancel, so ω=0\omega=0 and the strings commute. The same count shows why the Bell-pair stabilizers XXXX and ZZZZ commute.

The Clifford group is symplectic

GateXX-type generatorsZZ-type generators
HHX↦ZX\mapsto ZZ↦XZ\mapsto X
SSX↦YX\mapsto YZ↦ZZ\mapsto Z
CNOT12\mathrm{CNOT}_{12}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
A Clifford is fixed, up to phase, by the images of the 2n2n generators Xj,ZjX_j,Z_j; for example Y=iXZY=iXZ goes to i (UXU†)(UZU†)i\,(UXU^\dagger)(UZU^\dagger).
DerivationCounting the group
  1. ∣Sp(2n,F2)∣=∏j=1n(4j−1) 22j−1=2n2∏j=1n(4j−1)\abs{Sp(2n,\mathbb{F}_2)}=\prod_{j=1}^{n}(4^j-1)\,2^{2j-1}=2^{n^2}\prod_{j=1}^{n}(4^j-1)

    Count symplectic bases: choose e1≠0e_1\neq0 (4n−14^n-1 ways), then f1f_1 with ω(e1,f1)=1\omega(e_1,f_1)=1 (an affine hyperplane, 22n−12^{2n-1} ways), then recurse on their (2n−2)(2n-2)-dimensional symplectic complement. Note ∑j(2j−1)=n2\sum_j(2j-1)=n^2.

  2. ∣Cn/U(1)∣=4n⋅2n2∏j=1n(4j−1)=2n2+2n∏j=1n(4j−1)\abs{\mathcal{C}_n/U(1)}=4^n\cdot2^{n^2}\prod_{j=1}^{n}(4^j-1)=2^{n^2+2n}\prod_{j=1}^{n}(4^j-1)

    Multiply by the kernel, ∣Pn/⟨iI⟩∣=4n\abs{\mathcal{P}_n/\langle i\id\rangle}=4^n.

  3. n=1: 24,n=2: 11 520,n=3: 92 897 280n=1:\ 24,\qquad n=2:\ 11\,520,\qquad n=3:\ 92\,897\,280

    The order grows like 22n2+O(n)2^{2n^2+\order{n}}: finite, but hopeless to enumerate beyond a few qubits.

One qubit: the symmetries of the octahedron

Modulo phase, a single-qubit Clifford is a rotation of the Bloch sphere that permutes the six Pauli eigenstates ±x^,±y^,±z^\pm\hat x,\pm\hat y,\pm\hat z: a rotational symmetry of the octahedron. To count them, choose where ZZ goes (six signed axes), then where XX goes (four signed axes perpendicular to it). The image of Y=iXZY=iXZ is then forced, which rules out reflections.

Predict before you look

How many single-qubit Cliffords are there, modulo global phase?

Show the answer

24

6×4=246\times4=24, matching 21+2(4−1)=242^{1+2}(4-1)=24. By rotation type: the identity (1), half-turns about x,y,zx,y,z (3), quarter-turns about x,y,zx,y,z (6), third-turns about the 4 body diagonals (8), and half-turns about the 6 edge axes such as HH's axis (x^+z^)/2(\hat x+\hat z)/\sqrt2 (6). The group is isomorphic to S4S_4.

Think first Why must a Clifford map Pauli eigenstates to Pauli eigenstates?

If UPU†=P′UPU^\dagger=P' and P∣ψ⟩=∣ψ⟩P\ket\psi=\ket\psi, then P′ U∣ψ⟩=UPU†U∣ψ⟩=U∣ψ⟩P'\,U\ket\psi=UPU^\dagger U\ket\psi=U\ket\psi: UU carries the +1+1 eigenstate of PP to the +1+1 eigenstate of P′P'. On nn qubits the same argument shows that Cliffords map stabilizer states to stabilizer states, of which there are 2n∏k=1n(2k+1)2^n\prod_{k=1}^n(2^k+1) (6 for one qubit, 60 for two).

Stabilizers, the hierarchy, and why it matters

On nn qubits, a stabilizer state is the unique joint +1+1 eigenstate of nn independent, commuting Pauli strings, its stabilizers. A Clifford circuit acts on such a state by conjugating its stabilizers, a bookkeeping task that is classically efficient. Try reasoning in stabilizers instead of amplitudes: before you build, work out what ZZZZ must be.

Why this matters. Gates in C(3)\mathcal{C}^{(3)} can be applied by gate teleportation, consuming a resource state and correcting with Cliffords (Gottesman & Chuang 1999). That is the seed of magic-state computing: in a surface-code machine, Cliffords are cheap and every TT costs a distilled magic state. Clifford circuits on stabilizer inputs, meanwhile, can be simulated in polynomial time (Gottesman–Knill, made fast with the tableaux of Aaronson & Gottesman 2004). And uniformly random multiqubit Cliffords reproduce Haar averages up to third moments (the group is a unitary 3-design, though not a 4-design), which is what randomized benchmarking relies on.

Check your understanding

Which gate is in the third level of the Clifford hierarchy but not in the second?

  1. HH
  2. X\sqrt X
  3. TT
  4. Rz(π/8)R_z(\pi/8)
Show the answer

C. TT

TXT†=e−iπ/4SXTXT^\dagger=e^{-i\pi/4}SX is a Clifford but not a Pauli, and TZT†=ZTZT^\dagger=Z; so T∈C(3)∖C(2)T\in\mathcal{C}^{(3)}\setminus\mathcal{C}^{(2)}.

Key takeaways

  • Pn\mathcal{P}_n has 4n+14^{n+1} elements; modulo phases it is F22n\mathbb{F}_2^{2n}, and commutation is the symplectic form ω(v,w)=a⋅b′+b⋅a′\omega(v,w)=\mathbf a\cdot\mathbf b'+\mathbf b\cdot\mathbf a'.
  • The Clifford group normalizes Pn\mathcal{P}_n, is generated by HH, SS and CNOT, and satisfies Cn/(U(1)⋅Pn)≅Sp(2n,F2)\mathcal{C}_n/\big(U(1)\cdot\mathcal{P}_n\big)\cong Sp(2n,\mathbb{F}_2).
  • ∣Cn/U(1)∣=2n2+2n∏j(4j−1)\abs{\mathcal{C}_n/U(1)}=2^{n^2+2n}\prod_j(4^j-1): 24 for one qubit (the octahedral rotation group) and 11,520 for two.
  • TT lies in the third level of the Clifford hierarchy; such gates can be teleported using magic states, which is how fault-tolerant machines reach universality.

Check yourself

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

Question 1

How many elements does the two-qubit Pauli group P2\mathcal{P}_2 have, phases included?

  1. 16
  2. 32
  3. 64
  4. 256
Show the answer

C. 64

Four phases times 424^2 strings: 64=4n+164=4^{n+1} with n=2n=2.

Question 2

A single-qubit Clifford maps X↦−YX\mapsto-Y. Which image of ZZ is allowed?

  1. Z↦YZ\mapsto Y
  2. Z↦XZ\mapsto X
  3. Z↦iZZ\mapsto iZ
  4. Z↦−YZ\mapsto-Y
Show the answer

B. Z↦XZ\mapsto X

The images must be Hermitian Paulis that anticommute, as XX and ZZ do. −Y-Y and XX anticommute, so (X,Z)↦(−Y,X)(X,Z)\mapsto(-Y,X) works, and then Y=iXZ↦i(−Y)X=−ZY=iXZ\mapsto i(-Y)X=-Z.

Question 3

What is ∣C2/U(1)∣\abs{\mathcal{C}_2/U(1)}, the number of two-qubit Cliffords modulo phase?

  1. 576576
  2. 2424
  3. 92 897 28092\,897\,280
  4. 11 52011\,520
Show the answer

D. 11 52011\,520

24+4(4−1)(16−1)=256⋅45=11 5202^{4+4}(4-1)(16-1)=256\cdot45=11\,520. Only 242=57624^2=576 of them are products of single-qubit Cliffords; the rest entangle.

Question 4

Why is the Clifford group not a universal gate set?

  1. Modulo phases it is a finite group, so it cannot approximate arbitrary unitaries
  2. It contains no entangling gates
  3. Clifford gates are not unitary
  4. HH and SS commute, so together they generate only a few rotations
Show the answer

A. Modulo phases it is a finite group, so it cannot approximate arbitrary unitaries

A finite set of unitaries (mod phase) cannot be dense in SU(2n)SU(2^n). Separately, Gottesman–Knill shows that Clifford circuits on stabilizer inputs are classically simulable. Adding a non-Clifford gate such as TT makes the set universal.

Further reading

  • D. Gottesman, Stabilizer Codes and Quantum Error Correction, PhD thesis, Caltech (1997), arXiv:quant-ph/9705052.
  • D. Gottesman, "The Heisenberg representation of quantum computers" (1998), arXiv:quant-ph/9807006.
  • 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, 1369 (1998).
  • D. Gottesman & I. L. Chuang, "Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations", Nature 402, 390 (1999).
  • S. Aaronson & D. Gottesman, "Improved simulation of stabilizer circuits", Phys. Rev. A 70, 052328 (2004).