Quantum gate

Universal quantum gates

A set of universal quantum gates is any set of gates to which any operation possible on a quantum computer can be reduced, that is, any other unitary operation can be expressed as a finite sequence of gates from the set. Technically, this is impossible with anything less than an uncountable set of gates since the number of possible quantum gates is uncountable, whereas the number of finite sequences from a finite set is countable. To solve this problem, we only require that any quantum operation can be approximated by a sequence of gates from this finite set. Moreover, for unitaries on a constant number of qubits, the Solovay–Kitaev theorem guarantees that this can be done efficiently. Checking if a set of quantum gates is universal can be done using group theory methods and/or relation to (approximate) unitary t-designs. The spectral gap conjecture, if true, would imply that a generically chosen set of quantum gates is efficiently universal.