ドイチュ・ジョザアルゴリズム

ドイチュ・ジョザアルゴリズムは、 1992年にデイビッド・ドイチュとリチャード・ジョザによって提案され、1998年にリチャード・クリーブ、アルトゥール・エケルト、キアラ・マキアヴェッロ、ミシェル・モスカによって改良された決定論的 量子アルゴリズムです^{。[1] [2]実用性はほとんどありませんが、あらゆる決定論的古典アルゴリズムよりも指数}関数的に高速な量子アルゴリズムの最初の例の1つです。^[3]

ドイチュ・ジョザ問題は、量子アルゴリズムにとっては容易で、決定論的古典アルゴリズムにとっては困難となるように特別に設計されている。これはブラックボックス問題であり、量子コンピュータによってエラーなしで効率的に解くことができるが、決定論的古典コンピュータでは、問題を解決するためにブラックボックスへの指数関数的な数のクエリが必要になる。より正式には、これは、量子コンピュータで多項式時間で正確に解くことができる問題のクラスであるEQPとPが異なるというオラクルを生成する。^[4]

この問題は確率的古典コンピュータで簡単に解けるため、確率的古典コンピュータで多項式時間内に制限された誤差で解くことができる問題のクラスであるBPPとのオラクル分離は生じません。サイモンの問題は、 BQPとBPPの間でオラクル分離が生じる問題の例です。

Deutsch-Jozsa 問題では、何らかの関数を実装するオラクルと呼ばれるブラックボックスの量子コンピュータが与えられます。

${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$

この関数は、n ビットのバイナリ値を入力として受け取り、各値に対して 0 または 1 を出力します。関数は定数(すべての入力に対して 0 または 1) またはバランスの取れた値(入力ドメインのちょうど半分に対して 1 、残りの半分に対して 0)のいずれかであることが保証されています。 ^[1]次に、オラクルを使用して、関数が定数かバランスが取れているかを判断する必要があります。 ${\displaystyle f}$

従来の決定論的アルゴリズム（はビット数）の場合、最悪の場合、の評価が必要になります。が定数であることを証明するには、入力セットの半分強を評価し、その出力が同一であることを確認する必要があります（関数はバランスが取れているか定数であることが保証されており、その中間ではないため）。 関数がバランスが取れていて、最初の 2 つの出力値が異なる場合が最良のケースです。 従来のランダム化アルゴリズムの場合、関数を一定回数評価するだけで、高い確率で正しい答えが得られます（の場合は確率で失敗します）。 ただし、エラーの可能性がない答えが必要な場合は、 評価が依然として必要です。 Deutsch-Jozsa 量子アルゴリズムは、 を 1 回評価するだけで常に正しい答えを生成します。 ${\displaystyle n}$${\displaystyle 2^{n-1}+1}$${\displaystyle f}$${\displaystyle f}$${\displaystyle k}$${\displaystyle \epsilon \leq 1/2^{k}}$${\displaystyle k\geq 1}$${\displaystyle k=2^{n-1}+1}$${\displaystyle f}$

Deutsch–Jozsaアルゴリズムは、David Deutschによる以前の研究（1985年）を一般化したもので、 という単純なケースの解を提供した。 具体的には、入力が1ビットのブール関数が与えられた場合、それは定数であるか？^[5]${\displaystyle n=1}$
${\displaystyle f:\{0,1\}\rightarrow \{0,1\}}$

ドイチュが最初に提案したアルゴリズムは決定論的ではありませんでした。アルゴリズムが成功する確率は半分でした。1992 年にドイチュとジョザは、入力にビットを受け取る関数に一般化された決定論的アルゴリズムを作成しました。ドイチュのアルゴリズムとは異なり、このアルゴリズムでは 1 回ではなく 2 回の関数評価が必要でした。 ${\displaystyle n}$

Deutsch-JozsaアルゴリズムはCleveらによってさらに改良され、^[2]決定論的でありながら単一のクエリのみを必要とするアルゴリズムが生まれました。このアルゴリズムは、彼らが採用した画期的な技術に敬意を表して、今でもDeutsch-Jozsaアルゴリズムと呼ばれています。^[2]${\displaystyle f}$

Deutsch-Jozsa アルゴリズムが機能するには、 を計算するオラクルがデコヒーレントな量子オラクルでなければなりません。また、 のコピーを作成してはなりません。これは、複製禁止定理に違反するためです。 ${\displaystyle f(x)}$${\displaystyle x}$ ${\displaystyle x}$${\displaystyle x}$

アルゴリズムはビット状態から始まります。つまり、最初の n ビットはそれぞれ状態 にあり、最後のビットは です。各ビットにアダマールゲートを適用して状態 を取得します。 ${\displaystyle n+1}$${\displaystyle |0\rangle ^{\otimes n}|1\rangle }$${\displaystyle |0\rangle }$${\displaystyle |1\rangle }$

${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle) -|1\rangle )}$、

ここで、 はすべての - ビット文字列に対して実行されます。関数は量子オラクルとして実装されています。オラクルは入力状態を にマッピングします。ここで、 は2 を法とする加算を表します。量子オラクルを適用すると、次のようになります。 ${\displaystyle x}$${\displaystyle n}$${\displaystyle f}$${\displaystyle |x\rangle |y\rangle }$${\displaystyle |x\rangle |y\oplus f(x)\rangle }$${\displaystyle \oplus}$

${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle )}$。

それぞれは0か1です。この2つの可能性をテストすると、上記の状態は次のようになります。 ${\displaystyle x,f(x)}$

${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x )}|x\rangle (|0\rangle -|1\rangle )}$。

この時点で最後の量子ビットは無視され、次のものが残ります。 ${\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}$

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle }$。

次に、量子ビットをアダマールゲートに通します 。

${\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }$

（はビット積の合計、ここでは2を法とする加算）を最初のレジスタに渡して ${\displaystyle j\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}}$${\displaystyle \oplus }$

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle }$

このことから、測定される 状態の確率は${\displaystyle k}$

${\displaystyle \left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot k}\right|^{2}}$

に対応するを測定する確率は、 ${\displaystyle k=0}$${\displaystyle |0\rangle ^{\otimes n}}$

${\displaystyle {\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}}$

これは、が定数（建設的干渉）の場合は 1 に評価され、がバランス（破壊的干渉）の場合は 0 に評価されます。言い換えると、が定数の場合のみ、最終的な測定値は（すべてゼロ）になり、がバランスしている場合は別の状態になります。 ${\displaystyle f(x)}$${\displaystyle f(x)}$${\displaystyle |0\rangle ^{\otimes n}}$${\displaystyle f(x)}$${\displaystyle f(x)}$

Deutsch アルゴリズムは、 において n = 1 となる一般的な Deutsch–Jozsa アルゴリズムの特殊なケースです。条件 を確認する必要があります。これは、(ここで は2 を法とする加算であり、制御 NOT ゲートとして実装された量子XOR ゲートとみなすこともできます) を確認することと同等です。ゼロの場合は が定数であり、それ以外の場合はが定数ではありません。 ${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$${\displaystyle f(0)=f(1)}$${\displaystyle f(0)\oplus f(1)}$${\displaystyle \oplus }$${\displaystyle f}$${\displaystyle f}$

まず2量子ビットの状態から始め、各量子ビットにアダマールゲートを適用します。これにより、 ${\displaystyle |0\rangle |1\rangle }$

${\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}$

にマッピングされる関数の量子実装が与えられます。この関数を現在の状態に適用すると、次のようになります。 ${\displaystyle f}$${\displaystyle |x\rangle |y\rangle }$${\displaystyle |x\rangle |f(x)\oplus y\rangle }$

${\displaystyle {\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))}$

${\displaystyle ={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))}$

${\displaystyle =(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).}$

最後のビットとグローバル位相を無視すると、状態は次のようになります。

${\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).}$

この状態にアダマールゲートを適用すると、

${\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )}$

${\displaystyle ={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).}$

${\displaystyle f(0)\oplus f(1)=0}$を測定した場合に限り、を測定した場合に限ります。したがって、 が一定であるかバランスが取れているかどうかは確実にわかります。 ${\displaystyle |0\rangle }$${\displaystyle f(0)\oplus f(1)=1}$${\displaystyle |1\rangle }$${\displaystyle f(x)}$

• バーンスタイン・ヴァジラニアルゴリズム

• ドイチュ-ジョザアルゴリズムに関するドイチュの講義