Universal Gate Sets

Universal Gate Sets

A gate set is universal if any unitary operation on n qubits can be approximated to arbitrary precision using only gates from that set. This is the quantum equivalent of AND+NOT being universal for classical computation.

What does "approximated" mean here? Unitary operations form a continuum, but a finite gate set can only ever build countably many distinct circuits, so a finite set can never hit every unitary exactly. Universality instead means the buildable circuits are dense: for any target unitary U and any tolerance ε, some circuit lands within ε of U. Continuously parameterized sets (arbitrary rotation angles) can be exactly universal; finite sets are approximately universal, and the Solovay-Kitaev theorem at the end of this lesson explains why that is just as good in practice.

Classical Analogy

Classical: NAND gate alone can build any boolean circuit. Quantum: A small set of gates can build any quantum circuit.

The quantum version is a stronger claim than it first appears. A NAND circuit only needs to reproduce a finite truth table. A quantum circuit must reproduce a continuous rotation of a $2^n$-dimensional complex vector. That a four-gate alphabet suffices for this is one of the foundational results of the field.

The Clifford Group

The Clifford group is generated by: {H, S, CNOT}

Clifford circuits are efficiently simulatable on classical computers (Gottesman-Knill theorem). They can prepare Bell states, GHZ states, and perform error correction syndromes: but they cannot achieve universal quantum computation on their own.

This is worth pausing on. Clifford circuits create entanglement, run teleportation, and build every state in the error-correction toolbox, yet a classical computer can track them in polynomial time, by following the small stabilizer group that describes the state instead of its $2^n$ amplitudes. A single qubit has only six stabilizer states (|0⟩, |1⟩, |+⟩, |−⟩, |+i⟩, |−i⟩), and Clifford gates merely permute such states.