ソルベイ-キタエフの定理

定理¹

$\mathcal{G}$を特殊ユニタリ群 $\mathrm{SU}(2)$の（逆元について閉じている）有限部分集合だとしよう。

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

すると、$\mathcal{G}$によって生成される自由群 $\braket{\mathcal{G}}$は、$\mathrm{SU}(2)$で稠密^denseである。

特殊化²

アダマールゲート $H$、位相ゲート $R_{\pi/4}$、$\operatorname{CNOT}_{q}$ゲートを組み合わせることによって、任意の量子ゲートを望みどおり近似できる。

説明

古典コンピュータでは、任意のブール関数を表すことができる汎用ゲートが存在する。しかし、量子コンピュータでは、そのような汎用ゲートは存在しない。量子ゲートはユニタリ作用素で、全てのユニタリ作用素の集合は（実数集合と同じサイズの）非可算無限集合である。一方で、有限個の量子ゲートを有限回合成して得られる全ての量子回路の集合のサイズは、高々（自然数集合と同じサイズの）可算無限集合である。したがって、全ての量子ゲートを量子ゲートの合成によって表すことはできない。言い換えれば、有限個の量子ゲートで機能的に完全な集合を作ることはできない。ただし、上記の定理に従えば、十分に近づけることは可能である。