有限のゲート集合で近似する：Solovay–Kitaev の定理

相対エントロピーから情報と物理を組み立てる　第6部 第1章 §6.1.3　★★★ 有限個のゲートの積は数えられるだけしかないので、万能性は「任意の精度で近似できる」の意味になる。誤りはゲートごとに足し算で積み上がり、必要なゲートの数は精度の対数の多項式で済む

なぜ近似で満足するのか

2節の万能性は「すべての1量子ビットのユニタリ」という連続無限個のゲートを前提にしていた。実際の装置で用意できるのは有限個の種類のゲートで、とくに誤り訂正の中（第6部第5章）では、誤りに強く作れるゲートが $H,S,T,\mathrm{CNOT}$ のような少数のものに限られる。有限個の種類のゲートを有限個並べた積は、数えられる個数しかない。一方 $n$ 量子ビットのユニタリ全体は、全体の位相を除いて $4^n-1$ 次元の連続な集合である。したがって有限のゲート集合では、ほとんどのユニタリは厳密には作れない。求めるのは近似である。

誤りはゲートごとに足し算で積み上がる

近似を許すなら、各ゲートを少しずつ違うもので置き換えたとき、回路全体でどれだけずれるかを知る必要がある。

証明

$m=2$ のとき、$U_2U_1-V_2V_1=U_2(U_1-V_1)+(U_2-V_2)V_1$ と分け、ユニタリを掛けても作用素ノルムは変わらないことを使えば$\lVert U_2U_1-V_2V_1\rVert \le\lVert U_1-V_1\rVert +\lVert U_2-V_2\rVert$。一般の $m$ は、$m-1$ 個の積を1つのユニタリとみなして同じ分け方を繰り返せばよい。

誤りが掛け算でなく足し算で増えるのは、ユニタリが長さを変えないからである。回路の大きさが $L$ で全体の誤りを $\varepsilon$ 以下にしたければ、各ゲートを $\varepsilon /L$ の精度で近似すれば足りる。

作用素ノルムの差が、測定の結果にどう現れるかも確かめておく。同じ入力 $| \psi \rangle$ に $U$ と $V$ を当てた2つの純粋状態 $| a \rangle =U| \psi \rangle$、$| b \rangle =V| \psi \rangle$ のトレース距離は$T(| a \rangle \langle a |,| b \rangle \langle b |)=\sqrt{1-\lvert \langle a | b \rangle \rvert ^2}$ である。$x=\lvert \langle a | b \rangle \rvert \le1$ と置くと$\lVert | a \rangle -| b \rangle \rVert ^2=2-2\operatorname{Re}\langle a | b \rangle \ge2-2x\ge1-x^2$（最後は $(1-x)^2\ge0$）なので、

$$T(| a \rangle \langle a |,| b \rangle \langle b |)\le\lVert | a \rangle -| b \rangle \rVert \le\lVert U-V\rVert .\tag{6.1.6}$$

第3部第1章（第3部第1章）の Helstrom の結果によれば、2つの状態を1回の測定で見分ける成功確率は最善でも $\tfrac12(1+T)$ である。したがって、全体の誤りが $\lVert U-V\rVert \le\varepsilon$ の回路は、どんな測定をしても、理想の回路と確率 $\tfrac12(1+\varepsilon )$ を超えて見分けられない。測定の結果のどの確率も、理想の値から $\varepsilon$ 以上ずれない。

有限のゲート集合で回転を埋め尽くす

1量子ビットのゲートのうち $H$ と $S$ が生成する群（Clifford 群）は、全体の位相を除いて24個の元しか持たない有限群である。Clifford 群のゲートと CNOT と Pauli 行列の測定だけからなる回路は、古典の計算機で効率よく真似できる（Gottesman–Knill の定理¹1D. Gottesman (1998), arXiv:quant-ph/9807006。下の脚注へ閉じる。スタビライザーの言葉は 第3部第9章）。万能にするには Clifford 群の外のゲートが要り、$T$ がその標準の選び方である。

証明

$\cos\theta=2\cos^2(\theta/2)-1=2\cos^4(\pi/8)-1$ に $\cos^2(\pi/8)=(2+\sqrt2)/4$ を入れると $\cos\theta=(2\sqrt2-1)/4$。$x=2\cos\theta=(2\sqrt2-1)/2$ は $4x^2+4x-7=0$ を満たし、この2次式は有理数の範囲で因数分解できない（判別式 $128$ は平方数でない）。したがって $x$ の最小多項式は $x^2+x-7/4$ で、係数が整数でないから $x$ は代数的整数でない。もし $\theta/\pi$ が有理数なら $\mathrm{e}^{\mathrm{i}\theta}$ は1の冪根で、1の冪根は代数的整数なので、その和 $x=\mathrm{e}^{\mathrm{i}\theta}+\mathrm{e}^{-\mathrm{i}\theta}$ も代数的整数になるはずである。矛盾。

角が $\pi$ の無理数倍なら、$U,U^2,U^3,\dots$ の回転角 $k\theta$ を $2\pi$ で割った余りは $[0,2\pi)$ の中に稠密に並ぶ（鳩の巣原理：$N$ 個の角のうち2つは $2\pi/N$ 以内に入り、その差の倍数で円を細かく刻める）。したがって、軸 $\bm{n}$ のまわりの任意の角の回転を、$U$ の冪で任意の精度に近似することができる。$H$ で挟んだ $HUH$ は軸を $(\cos\frac\pi8,-\sin\frac\pi8,\cos\frac\pi8)$ の向きに移した回転で、$\bm{n}$ と平行でない。平行でない2本の軸のまわりの任意の角の回転を有限個掛ければ、任意の回転を作ることができる。こうして $\{H,T\}$ は1量子ビットで万能になり、CNOT を足した $\{H,T,\mathrm{CNOT}\}$ は2節の結果と合わせて万能になる。

Solovay–Kitaev の定理

万能であることは分かったが、上の「冪で角を合わせる」やり方では、精度 $\varepsilon$ を得るのに $1/\varepsilon$ に比例する長さの積が要る。これをはるかに短くできることを保証するのが次の定理である。

定理は Solovay と Kitaev が独立に得たもので、Kitaev の論文²2A. Yu. Kitaev (1997), Russian Mathematical Surveys 52, 1191–1249。下の脚注へ閉じるに証明がある。Dawson と Nielsen³3C. M. Dawson and M. A. Nielsen (2006), Quantum Information and Computation 6, 81–95。下の脚注へ閉じるは積を実際に組み立てる手順を与え、その長さを $\mathcal{O}(\ln^{3.97}(1/\varepsilon ))$ と見積もった。証明の考え方は、粗い近似を作ってから、残った小さなずれを「群の交換子 $VWV^\dagger W^\dagger$」で打ち消す操作を再帰的に繰り返すことにある。小さい回転 $V,W$ の交換子はさらに小さい回転になり、ずれの大きさが1段ごとにおよそ $3/2$ 乗で小さくなる一方、積の長さは5倍にしかならない。この比から指数 $c=\ln5/\ln(3/2)\approx3.97$ が出る。

定理の内容を言い換えると、近似の精度を上げる手間は精度の桁数の多項式で済む。2節の回路が厳密なゲートで $L$ 個のとき、各ゲートを $\varepsilon /L$ の精度で $\mathcal G$ の積に置き換えれば（補題 6.1.8）、全体の大きさは $\mathcal{O}(L\ln^c(L/\varepsilon ))$ で、もとの $L$ に対数の多項式が掛かるだけである。したがって、どの万能なゲート集合を選んでも、効率よく解ける問題の範囲は変わらない。

図 6.1.2 は、$\{H,T\}$ の語をすべて数え上げて、回転 $R_z(1)$ への最小距離を調べたものである。$T^8=\mathbf 1$ や Clifford 群の関係で同じ元が何度も現れるので、位相を除いて異なる元の数は $2^L$ よりずっと少なく、1文字ごとに約 $1.30$ 倍にしか増えない。それでも最小距離は、異なる元の数を $N_L$ として $N_L^{-1/3}$ の線に沿って下がる。指数 $-1/3$ の理由は4節の数え上げで説明する。

1　D. Gottesman (1998), arXiv:quant-ph/9807006。

2　A. Yu. Kitaev (1997), Russian Mathematical Surveys 52, 1191–1249。

3　C. M. Dawson and M. A. Nielsen (2006), Quantum Information and Computation 6, 81–95。

4　N. J. Ross and P. Selinger (2016), Quantum Information and Computation 16, 901–953。