ドイチ・ジョザアルゴリズム (Deutsch-Jozsa algorithm)

この記事に関して

ここでは量子アルゴリズムの一つである、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$ 個で以下の条件のどちらかが成り立つものとします。

1. 全ての入力で $f(x)$ が同じ
   → 全ての $x$ で $f(x)=0$ または 全ての $x$ で $f(x)=1$

2. 入力の半分で $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) 『量子コンピュータ入門[第２版]』 日本評論社