ConceptIntermediateGates

Quantum Gate Universality

A universal gate set can approximate any $n$-qubit unitary to arbitrary accuracy; examples are all single-qubit gates plus CNOT, or the finite set $\{H,T,\mathrm{CNOT}\}$.

Barenco and colleagues (1995) showed that all single-qubit gates together with CNOT are enough to build any unitary matrix on $n$ qubits exactly. This set is infinite because the angles are continuous. Devices and error correction, however, need a finite set; the set $\{H,T,\mathrm{CNOT}\}$ (with $S$) is approximately universal: it approximates any gate to precision $\epsilon$. The Solovay–Kitaev theorem states that the number of gates needed to approximate a single-qubit gate grows polylogarithmically in $1/\epsilon$.

Universality does not mean efficiency: most unitary matrices on $n$ qubits need an exponential number of gates. Useful algorithms are those built with a polynomial number.

The Clifford set $\{H,S,\mathrm{CNOT}\}$ alone is not universal, and Clifford circuits with computational preparation and measurement can be simulated efficiently classically (the Gottesman–Knill theorem), even though they generate entanglement. Adding $T$ is what breaks this. On hardware, Qiskit's transpilation turns the circuit into the device's native gates, such as $\{R_Z,\sqrt{X},\mathrm{CX}\}$ or their equivalent.

Mathematical formula

$$U\approx G_k\cdots G_2G_1,\quad G_i\in\{H,T,\mathrm{CNOT}\},\quad \|U-G_k\cdots G_1\|\le\epsilon$$

Worked example

The Toffoli gate (CCX) is not in the set, but it has an exact standard decomposition into 6 CNOT gates and a number of $H$, $T$ and $T^\dagger$ gates. The $Z$ gate equals $T^4$ and $S=T^2$. $R_Z(0.3)$, however, is not built exactly from $H,T$; it is approximated by a sequence that gets longer as $\epsilon$ gets smaller.

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. A. Barenco; C. H. Bennett; R. Cleve; D. P. DiVincenzo; N. Margolus; P. Shor; T. Sleator; J. A. Smolin; H. Weinfurter (1995). Elementary gates for quantum computation. Phys. Rev. A 52(5):3457–3467 doi:10.1103/PhysRevA.52.3457
  2. Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.