この記事に関して
ここでは量子アルゴリズムの一つである、Deutsch-Jozsa algorithm(ドイチ・ジョザ アルゴリズム)について、説明します。
Oracle
まずはこのアルゴリズムに出てくるオラクルから説明します。
簡単にいうと、ある入力に対し 0 あるいは 1 を返す関数です。
例として、物を買う状況を考えましょう。お肉屋さんで買える物を 1、 買えない物を 0 とします。
すると以下の状況になります。
f(x) = \left\{ \begin{array}{cc} 1 & (x\ \text{がお肉屋さんで買える。}) \\
0 & (x\ \text{がお肉屋さんで買えない。}) \end{array} \right.
これを用いるとパソコンはお肉屋さんで買えなく、牛肉は買えるので、
f\ ({\text{パソコン}})=0, \ \ \ \ \ f\ ({\text{牛肉}})=1
となります。
このように 0 と 1 に分ける関数をオラクルと言います。
量子コンピュータでは x に状態を入れて、特定の状態のみを取り出すのに使います。
つまりある状態のみを取り出すゲートのことを言います。
Deutsch algorithm
まずは Deutsch さんが考えたアルゴリズムについて説明していきます。
Deutsch algorithm とは、$\left|0\right>$ か $\left|1\right>$ である1ビットの入力のOracleを判別するというものです。
つまりはこういう状況のことを言います。
$x = \left|0\right>$ または $\left|1\right>$ のとき考えられるオラクルは以下の4通りになる。
f(x) = \left\{ \begin{array}{cc}0 & (x = \left|0\right>)\\0 & (x = \left|1\right>) \end{array}\right.or
\left\{ \begin{array}{cc}0 & (x = \left|0\right>)\\1 & (x = \left|1\right>) \end{array}\right.or
\left\{ \begin{array}{cc}1 & (x = \left|0\right>)\\0 & (x = \left|1\right>) \end{array}\right.or
\left\{ \begin{array}{cc}1 & (x = \left|0\right>)\\1 & (x = \left|1\right>) \end{array}\right.
Deutsch algorithm はこの $f$ が $\left|0\right>$ と $\left|1\right>$ で値が同じものなのか、それとも違うものなのかを判定してくれます。
具体的な回路を考えます。
\begin{array}{cccccccccccc}\left|0\right>&-&H&-&|&x&&x&|&-&H&-\\
&&&&|&&\large{U_f}&&|\\
\left|1\right>&-&H&-&|&y&&y\oplus f(x)&|&-&-&-\\
&&&↑&&&&&&↑&&↑\\
&&&\left|\psi_1\right>&&&&&&\left|\psi_2\right>&&\left|\psi_3\right> \end{array}
この $U_f$ が Oracle です。
ただし 0番目は入ってきた値をそのまま返し、1番目の $\oplus$ は入ってきた値と $f(x)$ との和のmod2をとるものとします。(mod2 → 2で割った余り)
ではそれぞれの状態を確認します。
$\left|\psi_1\right> = H\left|0\right>\otimes H\left|1\right> =
\frac{1}{\sqrt2}(\left|0\right>+\left|1\right>) \otimes \frac{1}{\sqrt2}(\left|0\right>-\left|1\right>)$
ここで上の式を $\frac{1}{2}\left|0\right>\otimes(\left|0\right>-\left|1\right>)+\frac{1}{2}\left|1\right>\otimes(\left|0\right>-\left|1\right>)$ と変形させます。
1番目のビットを見ると、$\left|0\right>$ と $\left|1\right>$ を入れ替えると符号が変わることがわかります。
この状態で上の4通りから $\left|\psi_2\right>$ を考えてみます。
$f(x)$ は 1番目のビットにかかるので
f(x) = 0 → \mbox{1番目のビットは入れ替わらない。}\\
f(x) = 1 → \mbox{1番目のビットが入れ替わる。}
よって、変形した2つの項で作られた式を見ると
f(0) = f(1) → \text{各項の符号は同じ。}\\
f(0) \neq f(1) → \text{各項の符号が異なる。}
このことから
\begin{align*}\left|\psi_2\right> = \left\{\begin{array}{cc}\pm\frac{1}{2}\left|0\right>\otimes(\left|0\right>-\left|1\right>)\pm\frac{1}{2}\left|1\right>\otimes(\left|0\right>-\left|1\right>) & (\ f(0) = f(1)\ )\\
\pm\frac{1}{2}\left|0\right>\otimes(\left|0\right>-\left|1\right>)\mp\frac{1}{2}\left|1\right>\otimes(\left|0\right>-\left|1\right>) & (\ f(0) \neq f(1)\ )\end{array}\right.\\
= \left\{\begin{array}{cc}\pm H\left|0\right>\otimes H\left|1\right> & (\ f(0) = f(1)\ )\\
\pm H\left|1\right>\otimes H\left|1\right> & (\ f(0) \neq f(1)\ )\end{array}\right.\end{align*}
となる。
よって $\left|\psi_3\right>$ は
\left|\psi_3\right> = \left\{ \begin{array}{cc} \pm\left|0\right>\otimes H\left|1\right> & (\ f(0) = f(1)\ )\\
\pm\left|1\right>\otimes H\left|1\right> & (\ f(0) \neq f(1)\ )\end{array} \right.
測定には $\pm$ は関係ないので、0番目のビットを測定するとOracleを判別することがわかる。
以上で Deutsch algorithm が説明できた。
Deutsch-Jozsa algorithm
では次に Deutsch algorithm の一般化である Deutsch-Jozsa algorithm を説明します。
Deutsch-Jozsa algorithm はこの $f$ の入力が $\left|00\cdots000\right>$ から $\left|11\cdots111\right>$ の $2^n$ 個で以下の条件のどちらかが成り立つものとします。
-
全ての入力で $f(x)$ が同じ
→ 全ての $x$ で $f(x)=0$ または 全ての $x$ で $f(x)=1$ -
入力の半分で $f(x)$ が異なる
→ $2^{n-1}$ 個の $x$ で $f(x)=0$ 、残りの $x$ で $f(x)=1$
このアルゴリズムでは Oracle が上の1. か 2. かを判別します。
具体的な回路を考えます。
\begin{array}{cccccccc}\left|0\right>&-&H&-&|&&&&|&-&H&-\\
\left|0\right>&-&H&-&|&x&&x&|&-&H&-\\
\vdots&&\vdots&&\vdots&&&&\vdots&&\\
\left|0\right>&-&H&-&|&&\huge{U_f}&&|&-&H&-\\
\left|0\right>&-&H&-&|&&&&|&-&H&-\\
\\
\left|1\right>&-&H&-&|&y&&y\oplus f(x)&|&-&H&-\\
&&&↑&&&&&&↑&&↑\\
&&&\left|\psi_1\right>&&&&&&\left|\psi_2\right>&&\left|\psi_3\right>\\
\end{array}
$\left|0\right>$ は n個並んでいるものとします。
ではそれぞれの状態を確認します。
\left|\psi_1\right> = \left(\bigotimes_{}^{n} H\left|0\right>\right)\otimes H\left|1\right> =
\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}^{2^n} \{\left|x\right> \otimes (\left|0\right>-\left|1\right>)\}\\
=\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}^{2^n} \left|x\right> \otimes \left|0\right>-\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}^{2^n} \left|x\right> \otimes \left|1\right>
n 番目のビットを見ると、$\left|0\right>$ と $\left|1\right>$ を入れ替えると全体の符号が変わることがわかります。
次に $\left|\psi_2\right>$ を考えてみます。
$f(x)$ は n 番目のビットにかかるので
f(x) = 0 → \mbox{n番目のビットは入れ替わらない。}\\
f(x) = 1 → \mbox{n番目のビットが入れ替わる。}
となリます。
各項について $f(x) = 0, 1$ でシグマを分けると
\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}^{2^n} \left|x\right> \otimes \left|0\right> \xrightarrow{U_f}
\frac{1}{\sqrt{2^{n+1}}}\sum_{f(x)=0}^{} \left|x\right> \otimes \left|0\right>+\frac{1}{\sqrt{2^{n+1}}}\sum_{f(x)=1}^{} \left|x\right> \otimes \left|1\right>\\
\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}^{2^n} \left|x\right> \otimes \left|1\right> \xrightarrow{U_f}
\frac{1}{\sqrt{2^{n+1}}}\sum_{f(x)=0}^{} \left|x\right> \otimes \left|1\right>+\frac{1}{\sqrt{2^{n+1}}}\sum_{f(x)=1}^{} \left|x\right> \otimes \left|0\right>
$f(x)=1$ のときビットが変わっていることがわかります。
まとめると、
\left|\psi_2\right> =
\frac{1}{\sqrt{2^{n}}}\left(\sum_{f(x)=0}^{} \left|x\right> -\sum_{f(x)=1}^{}\left|x\right> \right) \otimes \frac{1}{\sqrt2}(\left|0\right>-\left|1\right>) \\
よって、1 のときは $f=0,1$ のどちらかのシグマが消えるので
\left|\psi_2\right> = \pm\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}^{2^n} \left|x\right> \otimes \frac{1}{\sqrt2}(\left|0\right>-\left|1\right>)\\
= \pm\left(\bigotimes_{}^{2^n} H\left|0\right>\right)\otimes H\left|1\right>
また、2 のときは両方ともシグマは残るのでこれ以上計算できません。
以上から $\left|\psi_3\right>$ は
\left|\psi_3\right> = \left\{ \begin{array}{cc} \pm\left|00\cdots00\right>\otimes H\left|1\right> & (\ f → 1. \ )\\
\pm\left|x\right>\otimes H\left|1\right> & (x \neq 00\cdots00),(\ f → 2.\ )\ \end{array} \right.
$\left|\psi_2\right>$ の上から n個のビットが $H\left|0\right> \otimes \cdots \otimes H\left|0\right>$ でない限り $\left|\psi_3\right>$ の上から n個のビットは$\left|00\cdots00\right>$ になり得ないので、$\left|\psi_3\right>$ は上のようにかけることがわかる。
測定には $\pm$ は関係ないので、n-1番目までのビットを測定すると全て 0 かそれ以外かで Oracleを判別することがわかる。
以上で Deutsch-Jozsa algorithm が説明できた。
まとめ
今回は Deutsch-Jozsa algorithm について説明しました。
次回は Grover's algorithm について説明しようと思います。
参考文献
宮野 健次郎・古澤 明 (2016) 『量子コンピュータ入門[第２版]』 日本評論社