量子力学と量子コンピューターについての学習メモ #2
前回の続き。
ドイチュ-ジョサのブラックボックス
ジョサのアルゴリズムとは、ブラックボックスが蓄えているビット列が均一か等分かどちらなのかを判定するアルゴリズムである。よって、このアルゴリズムが有効であるのは、ブラックボックスが蓄えているビット列は、均一か等分かのどちらかに限定されている場合である(そうでない場合、その結果としてある程度の切り捨てが発生する)。
まず従来の方法では、一つ一つ順次検査していく。例えば としてブラックボックスが 個のビット列を持っていた場合、これを与えると最大で 回の検査が必要となるが、ドイチュ-ジョサの考案した量子コンピュータによるアルゴリズムでは、この操作を 回で行える。自然数 を具体的な大きな数値にするとこの計算量の少なさは明らかだ。例えば 、つまり のビット列の場合、古典的な方法では560兆あまりのステップが必要となるが、当アルゴリズムでは103ステップで完了するのである。当然ながら、量子アルゴリズムでは重ね合わせを利用するために、ブラックボックスの入出力は量子ビットで行われる。入力用に3つの量子ビット、結果の出力用に1つの量子ビット、合計4つの量子ビットを使う。先頭ビットに対する答えが知りたければ 、2つ目であれば 、3つ目であれば をセットする。例えば をセットしたとした場合、3つ目のビットが0の場合は、出力用ビットの値がそのまま出力される(出力用量子ビットは予め決められた初期値が設定されなければならない)が、1の場合には出力量量子ビットが反転されて出力される。
例えば、ブラックボックスの中身が という均一であった場合、そのブラックボックスは量子回路によって以下のように実装できる。
どんな入力を受け付けても、全て出力を反転してしまえば良い。これを、BBAとする。
例えば、ブラックボックスの中身が という等分であった場合、そのブラックボックスは量子回路によって以下のように実装できる。
入力が 以降となった場合に反転させなければ良い。これをBBBとする。ドイチュ-ジョサの量子アルゴリズムはこのような量子ブラックボックスに対して、等分が均一かを確実に超高速で判別することができるアルゴリズムである。まず、そのアルゴリズムを実装した量子回路を以下に示す。
上から4つの量子ビットそれぞれを とする。 をアドレスビット、 をレジスタビットという。回路の動きを追っていく。
- まず量子ビットは全て にセットされ、アダマールゲートによって となる。中身を具体的に書くと、 という具合だ。
- 次のステップで、量子ブラックボックス回路に入る。この時、量子ブラックボックスBBAを通過した段階では、 であり、量子ブラックボックスBBBを通過した段階では、 である。この段階で特徴として挙げられるのが、それぞれの項のレジスタビット が、ブラックボックスに蓄えられていたビット列と完全に一致することである。これはつまり、一度の操作でブラックボックスの中身を読み出せたことを意味する。
- ここからさらに、レジスタビット に、制御位相シフトを行う。制御位相シフトは、対象とする量子ビットが である場合のみ、その位相をプラスからマイナスへと変化させるので、当操作によってそれぞれ 、 となる。
- さらに、量子ブラックボックスを通過し、それぞれ、 、 となる。簡単のため、アドレスビットとレジスタビットを分けて、、 とする。
- 最後にアダマールゲートを作用させる。 に作用させると に、 に作用させると となるため、例えば の状態に焦点を当てると、まず となり、真ん中のビットに作用させると となり、同じく右側のビットに作用させ、 となる。この具合に、全ての項をアダマール変換すると、BBA側の変換結果は、1回目のアダマール変換によって全ての量子ビットに位相シフトが起きた事から、 である事が言えるため、これらに対し再度アダマール変換を施すと、それぞれの量子ビットは となり、BBB側の変換結果は となる。
結果、ブラックボックスBBAは全て状態 である事から、観測すると必ず状態 が得られるため均一である事が言え、ブラックボックスBBBはそうではなく、どれを観測しても全て状態 が得られるわけではない事から、等分であることを当アルゴリズムによって立証することができる。等分の場合に部分的に位相が反転するようにする事で、プラスマイナスによる打ち消しを妨害し、 への収束を避ける事が当アルゴリズムのポイントである。
次回はデーターベース検索のアルゴリズムに続く。