猫でもわかる量子情報（２６）

ドイチ＝ジョサのアルゴリズム

　というわけで、量子オラクル V_f を、アダマールで｜0＞と｜1＞を混ぜた状態

　　　　　　｜x＞ = 1/√2 (｜0 ＞+｜1＞)

に作用させてみます。

　　V_f ｜x＞ = 1/√2 { (-1)^f(0)｜0＞+ (-1)^f(1)｜1 ＞ }

この状態を観測して、最初の状態と同じに見つかる確率 P を計算すると

　　　　　　P = | ＜x｜V_f ｜x＞ |² = 1/4 | (-1)^f(0) + (-1)^f(1) |²
つまりは
　　　　P = 1　（ f(0)=f(1)　 ；f(x)が定数関数の時 ）
　　　　P = 0　（ f(0)<>f(1)　；f(0)、f(1)の一方が１他方が０の時 ）

です。具体的には函数 f がAかDだと P = 1になり、BかCだと P = 0になります。古典的な普通の方法だと f(0) と f(1)を計算するのにオラクルを２回用いなければなりませんが、この場合は量子オラクル V_f を１回使っただけです。本来の量子オラクル U_f を２回使ったからズルだといわれればそうですが（本当は１回で V_f と同等なの作る裏技もある）、実は x をn ビットにしても今の手順は全然不変で、V_f を１回（もしくは U_f を２回）用いて

　　　P = 1　（ f(x)が定数関数の時 ）
　　　P = 0　（ x のうちf(x)=1のものと、f(x)=0のもの個数等しい時 ）

という判別ができますが、これを古典的オラクルでやると f(x) を x 全部の値で計算するために 2^n 回どうしても用いざるを得ません。つまり２ビットだと４回、３ビットは１６回、４ビットなら２５６回です。

このようにオラクルを用いて、量子操作で通常の計算より遥かに少ないステップ数で、実際になにか関数の有意義な性質を引き出しうることを、今の例で最初に示したのがドイチという人とお弟子さんのジョサというひとでした。本当をいうと大して有意義な性質、という訳でもないのですが、量子並列演算の原型のような例ですので必ず取り上げられます。ここでも、簡単で教育的だという理由で実際の働き具合を少し詳しく見ていきます。