Clifford + π/8量子回路の計算能力

摘要

量子ゲート（ユニタリ行列）の集合Gが万能であるとは，Gの元のみを用いて，任意の量子計算（ユニタリ行列）を任意精度で近似できることである．これまでの研究で，いくつかの有限要素からなる万能集合が見出されているものの，一般に万能集合の元を用いて具体的にユニタリ行列を表現することは難しい．本稿では，BoykinらFOCS '99により万能性が示された基底集合である，Hadamardゲート，7T/8ゲート，制御NOTゲートからなる量子回路に着目し，その表現能九あるいは計算能力を解析する．そして，特に1qubit回路に対しては，この基底で計算可能な行列が全て正規形と名付けた良い性質を持つ回路により与えれることを明らかにする．任意の回路は，正規形回路に容易に変換でき，また，2つの正規形回路C{sub}a，C{sub}bは，これが等しいときかつそのときに限り同じ行列を計算する．本稿ではまた，Hadamardゲート，Phaseゲート，制御NOTおよび，限定された個数のπ/8ゲートからなる量子回路の計算能力についても議論する．