ドイッチュ・ジョサのアルゴリズム

ドイッチュ・ジョサのアルゴリズムは、量子アルゴリズムであり、1992年にデイビッド・ドイッチュとリチャード・ジョサによって提案され、 Richard Cleve, Artur Ekert, Chiara Macchiavello, そして Michele Mosca によって 1998 年に改良された。実用性は限られるが、既存のどの決定論的古典アルゴリズムよりも指数関数的に早い量子アルゴリズムのうち最も早期に発見されたものの一つである。また、これは決定的アルゴリズムであり、常に解を得ることができ、またその解は常に正しい。

問題設定

ドイッチュ・ジョサの問題では、オラクルと呼ばれるある関数 $f:\{0,1\}^{n}\rightarrow \{0,1\}$ が実装されたブラックボックス量子コンピュータが与えられている。 わかりやすく言えば、オラクルはn桁の2進数値を入力として受け取り、0または1を出力する。

ここで、関数$f$は定値 (すべての量子ビットが0 またはすべての量子ビットが1)であるか、均等 (量子ビットの丁度半数が1で、残りの半数が0)であることが保証されている。

問題は、オラクルを用いて関数が定値か均等かを決定することである。

動機

ドイッチュ・ジョサの問題は、量子アルゴリズムで解きやすく、かつ、決定的古典アルゴリズムでは解くのが難しいよう明示的に意図された問題である。 この問題の動機付けは、決定的古典コンピューターでは問題を解くのに大量のクエリを必要とするブラックボックス問題を、量子コンピューターが誤りなく効率的に解くことが可能であることを示すことにある。