Universal Gate Sets
A universal gate set can approximate any unitary to arbitrary accuracy; a small finite set suffices for all quantum computation.
What universality means
A gate set is universal if any unitary on any number of qubits can be built, or approximated to arbitrary precision, from gates in the set. Universality is what lets a fixed, small hardware repertoire run every possible quantum algorithm.
Two flavours
- Exact universality: continuous sets, e.g. all single-qubit gates plus CNOT, build any unitary exactly
- Approximate universality: discrete sets, e.g. {H, T, CNOT}, approximate any unitary as closely as desired
The standard discrete set
The most cited universal set is {H, T, CNOT}: Hadamard, the 45-degree T phase gate, and controlled-NOT. Single-qubit gates alone cannot entangle, so CNOT is essential; H and T alone generate a dense subset of single-qubit unitaries. Together they suffice for everything.
Solovay-Kitaev theorem
The Solovay-Kitaev theorem guarantees that a discrete universal set approximates any target gate efficiently: reaching accuracy epsilon needs only about log(1/epsilon) raised to a small power gates. So discreteness costs only a modest overhead, and the approximation does not blow up — a crucial fact for practical compilation.
Why discrete sets are preferred
Fault-tolerant error correction works cleanly with a discrete set, because only finitely many gates need to be made fault-tolerant. In many codes H and CNOT are relatively cheap while T is expensive, so counting T gates has become the main measure of an algorithm's fault-tolerant resource cost. Choosing the gate set is therefore both a mathematical and an engineering decision.