Universal Gate Sets and the Clifford Group

qc/gates qc/math

A gate set is universal if any $n$-qubit unitary can be approximated arbitrarily well by some finite sequence of gates drawn from it. One standard universal set: $\{H,T,CX\}$ — every quantum algorithm in principle compiles down to just these three gate types.

The Clifford group — an important non-universal subgroup

Generated by $\{H,S,CX\}$ (see H Gate, S and T Gates, CX Gate and Entanglement). Clifford gates are exactly the gates that map Paulis to Paulis under conjugation — $UP{U}^{†}$ is always another Pauli for Clifford $U$, the same Clifford conjugation rule the Error Mitigation section builds an entire toolchain around.

The Gottesman-Knill theorem

Key insight: any circuit built purely from Clifford gates (plus computational-basis measurements) can be efficiently simulated on a classical computer — however many qubits, however deep. A Clifford-only circuit is never “quantum-hard,” no matter how large. This is exactly why Error Correction (EC) singles out T as the gate that needs special handling (magic state distillation): stabilizer codes protect Clifford operations essentially for free, but a computation made of only protected Clifford gates would be classically simulable and therefore pointless to run on a quantum computer at all. Non-Clifford gates are what make a circuit actually worth running on quantum hardware.

Related

• S and T Gates
• Dressed Gates and Pauli Propagation — the same Clifford-conjugation rule, applied to noise mitigation
• Error Correction (EC) — magic state distillation exists specifically to implement T fault-tolerantly
• H Gate, CX Gate and Entanglement

Self-Check

• Could you name a universal gate set and explain what “universal” actually guarantees?
• Why does the Gottesman-Knill theorem mean a Clifford-only circuit is never worth running on a quantum computer?
• Why does adding just one gate (T) to the Clifford group make the difference between classically-simulable and not?