Solvay-Kitaev Theorem

Theorem¹

Let’s consider $\mathcal{G}$ as a finite subset of the special unitary group $\mathrm{SU}(2)$ that is closed under taking inverses.

$$ \mathcal{G} \subset \mathrm{SU}(2), \qquad g \in \mathcal{G} \implies g^{-1} \in \mathcal{G} $$

Then, the free group $\braket{\mathcal{G}}$ generated by $\mathcal{G}$ is dense in $\mathrm{SU}(2)$.

Specialization²

By composing the Hadamard gate $H$, phase gate $R_{\pi/4}$, and $\operatorname{CNOT}_{q}$gate, any quantum gate can be approximated as closely as desired.

Description

In classical computers, there exists a universal gate that can represent any Boolean function. However, in quantum computers, there is no universal gate. Quantum gates are unitary operators, and the set of all unitary operators is an (uncountably infinite set) that is the same size as the set of real numbers. In contrast, the size of the set of all quantum circuits that can be obtained by a finite composition of quantum gates is at most (countably infinite), the same size as the set of natural numbers. Therefore, not all quantum gates can be represented by the composition of quantum gates. In other words, it is not possible to make a functionally complete set with a finite number of quantum gates. However, according to the theorem above, it can be approximated closely enough.