11
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2019-12-08

この記事に関して

ここでは量子アルゴリズムの一つである、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) 『量子コンピュータ入門[第2版]』 日本評論社

11
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
11
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?