ソルベイ-キタエフの定理
定理1
を特殊ユニタリ群 の(逆元について閉じている)有限部分集合だとしよう。
すると、によって生成される自由群 は、で稠密denseである。
特殊化2
アダマールゲート 、位相ゲート 、ゲートを組み合わせることによって、任意の量子ゲートを望みどおり近似できる。
説明
古典コンピュータでは、任意のブール関数を表すことができる汎用ゲートが存在する。しかし、量子コンピュータでは、そのような汎用ゲートは存在しない。量子ゲートはユニタリ作用素で、全てのユニタリ作用素の集合は(実数集合と同じサイズの)非可算無限集合である。一方で、有限個の量子ゲートを有限回合成して得られる全ての量子回路の集合のサイズは、高々(自然数集合と同じサイズの)可算無限集合である。したがって、全ての量子ゲートを量子ゲートの合成によって表すことはできない。言い換えれば、有限個の量子ゲートで機能的に完全な集合を作ることはできない。ただし、上記の定理に従えば、十分に近づけることは可能である。
https://en.wikipedia.org/wiki/Solovay%E2%80%93Kitaev_theorem ↩︎
김영훈·허재성, 양자 정보 이론 (2020), p99 ↩︎