Past exam of the laser science and quantum information processing course of the University of Oxford / 2018 / 4 / a

A universal quantum gate set can approximate any unitary operation on any finite register, to arbitrary requested accuracy, using a finite sequence of its gates on the register. Unobservable overall global phase is ignored. Approximation matters: a fixed finite alphabet has only countably many finite circuits, whereas there are uncountably many exact unitary matrices.

The Hadamard gate $H$ and T gate generate a dense set of single-qubit operations, but cannot themselves entangle different qubits. Adding the controlled-NOT gate gives a universal multi-qubit set. More generally, an available two-qubit gate must be genuinely entangling: it must take at least one product input to an entangled output. A product of local unitaries, or a SWAP gate composed with local unitaries, cannot provide this resource. Together with arbitrary single-qubit control, an entangling two-qubit gate on a connected interaction network supplies universal register control.