量子計算学習ノート - Deutschのアルゴリズム

---

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。

---

量子並列性を用いて、古典計算を凌ぐ働きを量子回路にさせてみよう。今度は次のような初期状態を用意する。

$$
|01\rangle
$$

次に、量子並列性の記事でみたように全ての量子ビットにアダマールゲートを作用させる。

$$
(H \otimes H) |01\rangle = \left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right)\left(\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right)
$$

ここで1ビットの入力から1ビットを出力する関数$${f}$$と、それを用いた量子ゲート$${U_f}$$を再び考える。先の状態にこの量子ゲートを適用してみよう。

$$
\begin{array}{l}
U_f (H \otimes H) |01\rangle\\
= \frac{|0, f(0)\rangle - |0, 1 \oplus f(0)\rangle + |1, f(1)\rangle - |1, 1 \oplus f(1)\rangle}{2}\\
\end{array}
$$

適用後の状態は$${f(0) = f(1)}$$なのか$${f(0) \neq f(1)}$$なのかで場合分けすると、よりすっきり記述することができる。実際$${f(0) = f(1)}$$のときは

$$
\begin{array}{l}
U_f (H \otimes H) |01\rangle\\
= \frac{(|0\rangle + |1\rangle)|f(0)\rangle - (|0\rangle + |1\rangle)|1 \oplus f(0)\rangle}{2}\\
= \frac{(|0\rangle + |1\rangle)(|f(0)\rangle - |1 \oplus f(0)\rangle)}{2}\\
= \left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right)\left(\frac{|f(0)\rangle - |1 \oplus f(0)\rangle}{\sqrt{2}}\right)\\
= (-1)^{f(0)}\left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right)\left(\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right)
\end{array}
$$

となる。同様の計算により、$${f(0) \neq f(1)}$$のときは

$$
\begin{array}{l}
U_f (H \otimes H) |01\rangle\\
= (-1)^{f(0)}\left(\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right)\left(\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right)
\end{array}
$$

であることがわかる。最後にアダマールゲートを第1量子ビットに適用する。$${(H \otimes I)U_f (H \otimes H) |01\rangle}$$は$${f(0) = f(1)}$$のとき

$$
(-1)^{f(0)}|0\rangle\left(\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right)
$$

$${f(0) \neq f(1)}$$のときは

$$
(-1)^{f(0)}|1\rangle\left(\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right)
$$

である。第1量子ビットは実はどちらの場合も$${f(0) \oplus f(1)}$$に等しいことがわかるので、結果的に場合分けは以下のようにまとめられる。

$$
(H \otimes I)U_f (H \otimes H) |01\rangle = (-1)^{f(0)}|f(0) \oplus f(1)\rangle\left(\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right)
$$

この結果は実は驚くべきものだ。この量子回路を使えば第1量子ビットを1回観測するだけで関数$${f}$$の全体の性質である $${f(0) \oplus f(1)}$$を求めることができる！ これは$${f(0) \oplus f(1)}$$の導出に2回、回路の適用と観測が必要な古典計算よりも速い。

これがDeutschのアルゴリズムだ。次の記事では量子並列性の特性がより顕著に表れ、かつDeutschのアルゴリズムの一般系であるDeutsch-Jozsaのアルゴリズムを説明しよう。