Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 39 ยท Gates and Circuits

Universal Gate Sets and Circuit Identities

Learn what a universal gate set is, why Clifford+T works, how the Clifford group conjugates Paulis, how sequences of H and T approximate any rotation, and key circuit identities.

Hardware can only implement a few native operations. How do we know that a small collection of gates is enough to run any quantum algorithm? The answer is the idea of a universal gate set. This lesson explains what universality means in the quantum setting (it is subtler than in classical logic), introduces the Clifford group and the famous Clifford+T set, shows how sequences of two gates approximate any rotation, and collects the circuit identities that compilers use every day.

What universality means

Classical NAND gates can build any Boolean function exactly. The quantum situation differs because there are infinitely many unitary operations (angles are continuous), but any finite gate set generates only countably many circuits. So no finite set can produce every unitary exactly.

Instead, a gate set is universal if it can approximate any unitary on any number of qubits to any desired accuracy. Several choices work:

  • Single-qubit rotations plus CNOT. All single-qubit unitaries (via the ZYZ decomposition from Rotation Gates and Phase) together with CNOT can build every multi-qubit unitary exactly. This is the "exactly universal" set used for analysis.
  • Clifford + T. The discrete set {H, S, CNOT, T} is universal in the approximate sense and is the standard set for fault-tolerant machines.
  • H, Toffoli (with a restriction to real amplitudes) is also universal, a result that surprises many people.

The Clifford group

The Clifford gates are H, S and CNOT (and everything they generate, including the Pauli gates). Their defining property: conjugating a Pauli operator by a Clifford gate gives another Pauli operator. For example H X H = Z, S X Sโ€  = Y, and CNOT maps X (x) I to X (x) X. That structure is why Clifford circuits are so special.

The Gottesman-Knill theorem states that a circuit built only from Clifford gates, with computational-basis inputs and measurements, can be simulated efficiently on a classical computer. So the Clifford set alone is not universal, and the quantum advantage must come from gates outside it. Adding the T gate (a 45-degree phase) gives the missing power. It is also the costly gate in error-corrected hardware, so the number of T gates, the T-count, is a standard measure of an algorithm's cost.

Python Clifford gates map Paulis to Paulis

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output shows that H and S always map X and Z to Paulis, while T X Tโ€  is not a Pauli: it is (X + Y)/sqrt(2), a mix. That is exactly what makes T non-Clifford.

Approximating rotations with H and T

How can two gates, H and T, approximate an arbitrary rotation? Products of H and T generate a dense set of rotations: sequences of longer and longer length come arbitrarily close to any single-qubit unitary. The Solovay-Kitaev theorem says approximating to accuracy epsilon needs only a number of gates that grows polylogarithmically in 1/epsilon, which is encouraging: precision is cheap.

We can watch this happen with brute force. The metric below compares two unitaries up to global phase using |trace(Uโ€  V)| / 2, which equals 1 for identical gates.

Python Brute-force approximation of a rotation with H and T

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The best score creeps toward 1 as longer sequences are allowed. Real compilers use much smarter algorithms (exact synthesis and number-theoretic methods) that find near-optimal sequences directly.

Circuit identities

Compilers use identities to shorten circuits and rewrite them for hardware gates. Here are the ones worth knowing:

  • Inverses cancel: H H = X X = Z Z = CNOT CNOT = I (the same CNOT twice).
  • Axis swap: H X H = Z and H Z H = X.
  • CNOT from CZ: (I x H) CZ (I x H) = CNOT.
  • Reversal of CNOT: (H x H) CNOT(a, b) (H x H) = CNOT(b, a). Surrounding a CNOT by Hadamards on both qubits reverses control and target.
  • SWAP from three CNOTs.
  • Rotation merging: Rz(a) Rz(b) = Rz(a + b), and likewise for the other axes.
  • Controlled-Z is symmetric.
Python Verifying the CNOT-reversal identity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compiling in practice

A real toolchain performs three jobs, which the later chapter on tools revisits:

  1. Decompose every gate into the device's native gate set (often a rotation family plus one two-qubit gate).
  2. Route qubits so two-qubit gates only occur between connected neighbors, inserting SWAPs.
  3. Optimize by canceling inverses, merging rotations and applying identities.

Universality is about approximability, not efficiency. A gate set can be universal and still need extremely long circuits for some unitaries. Choosing a basis that keeps circuits short is a hardware design question.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can no finite gate set produce every unitary exactly?

    Universality is therefore defined as approximation to any accuracy.
  2. 2. Which set is the standard universal set for fault-tolerant quantum computing?

    Clifford gates (H, S, CNOT) plus the T gate are approximately universal.
  3. 3. What does the Gottesman-Knill theorem say?

    Circuits of only Clifford gates with computational-basis input and measurement are classically easy, so quantum advantage requires non-Clifford gates.
  4. 4. What does surrounding a CNOT with Hadamards on both qubits do?

    (H x H) CNOT(a, b) (H x H) = CNOT(b, a).

Summary

  • A gate set is universal if it approximates any unitary to arbitrary accuracy.
  • Single-qubit rotations plus CNOT are exactly universal; Clifford+T is the standard discrete set.
  • Clifford gates map Paulis to Paulis and are classically simulable; T is the non-Clifford resource.
  • Sequences of H and T approximate any rotation, with cost growing only polylogarithmically in precision.
  • Identities (reversal, swap, rotation merging) are the compiler's toolbox.

Next: Bell States and Entanglement