量子力学と量子コンピューターについての学習メモ #3
前回の続き。
データベース検索
データベースの例として電話帳を取り上げる。電話帳は、名前の五十音順に番号が付けられている。これは昇順ソートされたリストであると解釈できるので、バイナリーサーチの手法によって比較的高速かつ簡単にアクセスできる。次に、この電話帳に対して電話番号を入力して、誰のものなのかを問い合わせたいとしたい場合を考えると、この場合線形探索が必要となってしまい、とても効率が悪い。しかし量子コンピュータでは、この種のデータ探索をデータ数が とした場合 回で確実に完了するのである。これは、グローバーのアルゴリズムといわれている。 まず、以下のようなデータベース回路を用意する。
全ての量子ビットをアドレスビットとし、入力の値がデータベースと合致した場合、アドレスビット列の位相が反転する。この場合、 がデータベースに登録されている事となる。もしその入力が得られた場合、位相が反転する。これをDBゲートとする。
このゲートの通過結果に折り返し量子回路をかける。この折り返し量子回路は、各量子ビットに対するアダマールゲートとアドレスビット列が全て の状態のときのみその位相を反転するゲートによって容易に実現できるようだ(実装を調査したが、詳しい実装を見つける事ができなかった。もし詳細に関わるドキュメントなどをこのエントリを読んでいる方の中でご存知の方がいたら、是非ご教授願いたい)。
[ ※追記 独自に実装した。
中身が |11> なデータベースに対するグローバーのアルゴリズム,多分できた. pic.twitter.com/4j6U6shcIc
— roκi (@530506) 2017年6月19日
これは、データベースの中身が である場合の回路である。数式で流れを追うと明快である*1。
- まず初期状態として2量子ビットとも にしておく。
- アダマールゲートによって、2量子ビットとも重ね合わせ状態 となる。それぞれの確率振幅は なので、2量子ビットにおける全てのパターンそれぞれの確率振幅は である。
- 次にターゲットである の位相のみ反転するために制御Zゲートを通過させると、次の数式の通りとなる。 となる。
- 拡散変換D(折り返し回路)を通過する。アダマール変換、ビット変換、制御Zゲートにより構成される。これらを通過すると、次の式の通りとなる。
━━ 追記ここまで ]
この操作を何度か繰り返すことで、特定のビット列の発生する確率が高くなり、判定結果に対する信頼性が高まる。尚、これを繰り返すたびに、判定結果の量子ビット列の確率振り幅は 、 …と大きくなる。判定時に、そのビット列を入力してみて、正しく反転するか確認し、間違っていた場合はこれを繰り返す事で、ほぼ確実に内包するデータを取り出せる。