This lecture develops the theory of universal quantum computation, establishing that a generic entangling two-qubit gate suffices to approximate any unitary transformation on n qubits to arbitrary accuracy, since exact universality already holds for two-qubit gates. Universality is shown to be a generic property of the unitary group by exploiting the Lie-algebra structure of unitaries — the reachable generators are closed under real scaling, linear combination, and commutation — so that non-commuting generic gates generate a dense subgroup of SU(N). The lecture then presents the Solovay–Kitaev theorem, which shows that once a gate set forms an epsilon-net closed under inverses, one can recursively construct circuits whose approximation error shrinks doubly-exponentially while circuit size grows only polylogarithmically in 1/epsilon. This material sits within quantum information theory and quantum complexity theory, connecting quantum circuit models to fault-tolerant gate sets and the BQP-versus-BPP question.
This lecture develops the theory of universal quantum computation, establishing that a generic entangling two-qubit gate suffices to approximate any unitary transformation on n qubits to arbitrary ac…