回路と同じ力を持つ2つの型：測定型と断熱型

相対エントロピーから情報と物理を組み立てる　第6部 第1章 §6.1.5　★★ もつれた資源状態を1量子ビットずつ測るだけの「測定型」と、Hamiltonian をゆっくり変える「断熱型」は、どちらも回路と多項式の手間で互いに真似し合える

測定型：テレポーテーションを繰り返す

測定型量子計算（一方向量子計算）では、ゲートを当てる代わりに、初めに大きなもつれた状態を用意し、あとは1量子ビットずつ測るだけで計算を進める。用意する状態はクラスター状態で、格子の各点に $| + \rangle =(| 0 \rangle +| 1 \rangle )/\sqrt2$ を置き、隣り合う点の対すべてに CZ を当てて作る。CZ は互いに交換するので、当てる順序によらない。

基本の操作は1段の測定である。測る基底を、角 $\theta$ を選んで

$$| \pm_\theta \rangle =\frac{1}{\sqrt2}\bigl(| 0 \rangle \pm\mathrm{e}^{\mathrm{i}\theta}| 1 \rangle \bigr)\tag{6.1.8}$$

とし、$| +_\theta \rangle$ が出たら結果 $m=0$、$| -_\theta \rangle$ が出たら $m=1$ と書く。

証明

$| \psi \rangle =a| 0 \rangle +b| 1 \rangle$ と書く。CZ は1つ目が $| 1 \rangle$ のときだけ2つ目に $Z$ を当て、$Z| + \rangle =| - \rangle$ なので、CZ の後の状態は $a| 0 \rangle | + \rangle +b| 1 \rangle | - \rangle$ である。1つ目を $\langle \pm_\theta |$ に射影すると、$\langle \pm_\theta | 0 \rangle =1/\sqrt2$、$\langle \pm_\theta | 1 \rangle =\pm\mathrm{e}^{-\mathrm{i}\theta}/\sqrt2$ から、2つ目に残るのは$\frac{1}{\sqrt2}\bigl(a| + \rangle \pm\mathrm{e}^{-\mathrm{i}\theta}b| - \rangle \bigr)=\frac{1}{\sqrt2}H\bigl(a| 0 \rangle \pm\mathrm{e}^{-\mathrm{i}\theta}b| 1 \rangle \bigr)=\frac{1}{\sqrt2}HZ^mP(-\theta)| \psi \rangle$である。$HZ=XH$ から $HZ^m=X^mH$ で、ベクトルの長さの2乗 $1/2$ が結果 $m$ の確率になる。

1段の測定は、状態を1つ目の量子ビットから2つ目へ移しながら、ゲート $HP(-\theta)$ を当てる。これはテレポーテーション（第3部第6章）の簡単な形で、$X^m$ は測定結果で決まる「副産物」の Pauli 行列である。結果が確率 $1/2$ ずつで $| \psi \rangle$ によらないことは、測定の結果と入力の状態の相互情報量が $0$ であることを意味する。測定は入力の情報を1ビットも取り出さず、計算に要る情報はすべて、どの角で測るかという選択の側にある。

副産物は、後の測定の角を変えて吸収できる。$XP(\varphi)X=\mathrm{e}^{\mathrm{i}\varphi}P(-\varphi)$ なので、次の段の角を $\theta$ から $(-1)^m\theta$ に変えれば、$X^m$ を測定の後ろへ送り出すことができる。こうして直線に並んだクラスター状態を端から測ると、$HP(-\theta_1)$、$HP(-\theta_2)$、$\dots$ を順に当てたことになり、$HP(-\theta)H\propto R_x(-\theta)$ と $P(-\theta)\propto R_z(-\theta)$ から、3段で ZXZ の Euler 角の回転、すなわち任意の1量子ビットのゲートが作れる（総合問題）。2次元のクラスター状態では、縦の結合が2本の直線の間の CZ の役をし、2量子ビットのゲートも作ることができる。こうして測定型は回路と同じ計算を、多項式の個数の量子ビットと測定で行える¹1R. Raussendorf and H. J. Briegel (2001), Physical Review Letters 86, 5188–5191。詳しい構成は R. Raussendorf, D. E. Browne and H. J. Briegel (2003), Physical Review A 68, 022312。下の脚注へ閉じる。

断熱型：基底状態をゆっくり運ぶ

断熱型量子計算²2E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren and D. Preda (2001), Science 292, 472–475。下の脚注へ閉じるでは、答えを基底状態に持つ Hamiltonian $\hat H_1$ と、基底状態が簡単に用意できる Hamiltonian $\hat H_0$ を選び、

$$\hat H(s)=(1-s)\hat H_0+s\hat H_1,\qquad s=s(t),\quad s(0)=0,\ s(t_{\mathrm f})=1\tag{6.1.10}$$

に沿って時間 $t_{\mathrm f}$ をかけてゆっくり変える。量子力学の断熱定理によれば、$\hat H(s)$ の最低の固有値が次の固有値から幅 $g(s)>0$ で離れている限り、十分ゆっくり変えれば状態は基底状態にとどまる³3T. Kato (1950), Journal of the Physical Society of Japan 5, 435–439。誤りの明示的な上界は S. Jansen, M.-B. Ruskai and R. Seiler (2007), Journal of Mathematical Physics 48, 102111。下の脚注へ閉じる。どれだけゆっくりかの目安は

$$t_{\mathrm f}\gg\frac{\hbar\,\max_s\lVert \partial_s\hat H\rVert }{g_{\min}^2},\qquad g_{\min}=\min_sg(s)\tag{6.1.11}$$

である。終わりに測れば $\hat H_1$ の基底状態、すなわち答えが得られる。

この型の手間は時間 $t_{\mathrm f}$ で測り、それはエネルギーの間隔の最小値 $g_{\min}$ で決まる。回路の大きさに当たるのが $t_{\mathrm f}$ である。Aharonov らは、大きさ $L$ の回路を、$L$ の多項式の時間で動く断熱型の計算で真似できることを示した⁴4D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd and O. Regev (2007), SIAM Journal on Computing 37, 166–194。下の脚注へ閉じる。回路の各段の状態を「時計」の量子ビットと組にした状態の重ね合わせを基底状態に持つ局所的な Hamiltonian を作り、その間隔が $1/L$ の多項式より速くは閉じないことを示す。逆向き（断熱型を回路で真似する）は、時間発展を細かく区切ってゲートの積で書けばよい。こうして断熱型も回路と同じ力を持つ。

例として、$N$ 個の候補 $| 1 \rangle ,\dots,| N \rangle$ から印のついた1つ $| w \rangle$ を探す問題を考える。$| \phi \rangle =\sum_x| x \rangle /\sqrt N$ を一様な重ね合わせとし、エネルギーの単位を $E_0$ として

$$\hat H(s)=E_0\bigl[(1-s)(\mathbf 1-| \phi \rangle \langle \phi |)+s(\mathbf 1-| w \rangle \langle w |)\bigr]\tag{6.1.12}$$

と置く。$\hat H(s)$ は $| w \rangle$ と $| \phi \rangle$ が張る2次元の部分空間を保ち、その中の2つの固有値の差（エネルギーの間隔）を計算すると

$$g(s)=E_0\sqrt{1-4\Bigl(1-\frac1N\Bigr)s(1-s)},\qquad g_{\min}=g(1/2)=\frac{E_0}{\sqrt N}\tag{6.1.13}$$

となる（図 6.1.4）。$s$ を一定の速さで変えると、式 (6.1.11) から $t_{\mathrm f}\gg N\hbar/E_0$ が要り、全部の候補を1つずつ調べるのと同じ手間になる。Roland と Cerf⁵5J. Roland and N. J. Cerf (2002), Physical Review A 65, 042308。下の脚注へ閉じるは、間隔が広い所では速く、狭い所では遅く進む速さ $\mathrm{d} s/\mathrm{d} t=\kappa\,g(s)^2/(\hbar E_0)$（$\kappa\ll1$）を選んだ。このときかかる時間は

$$t_{\mathrm f}=\frac{\hbar}{\kappa E_0}\int_0^1\frac{E_0^2\,\mathrm{d} s}{g(s)^2}=\frac{\hbar}{\kappa E_0}\,\frac{N}{\sqrt{N-1}}\arctan\sqrt{N-1}\ \approx\ \frac{\pi}{2\kappa}\sqrt N\,\frac{\hbar}{E_0}\tag{6.1.14}$$

で、$\sqrt N$ に比例する。これは回路で探す Grover のアルゴリズム（第6部第4章）と同じ速さである。

1　R. Raussendorf and H. J. Briegel (2001), Physical Review Letters 86, 5188–5191。詳しい構成は R. Raussendorf, D. E. Browne and H. J. Briegel (2003), Physical Review A 68, 022312。

2　E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren and D. Preda (2001), Science 292, 472–475。

3　T. Kato (1950), Journal of the Physical Society of Japan 5, 435–439。誤りの明示的な上界は S. Jansen, M.-B. Ruskai and R. Seiler (2007), Journal of Mathematical Physics 48, 102111。

4　D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd and O. Regev (2007), SIAM Journal on Computing 37, 166–194。

5　J. Roland and N. J. Cerf (2002), Physical Review A 65, 042308。