第52話 大規模なデータベース中の高速検索

これまでの話
第1話 量子の夜明け
...
第46話 Shorのアルゴリズムのどこが凄いのか②？
第47話 量子ビットの間違い（量子誤り）訂正の方法・前編
第48話 量子ビットの間違い（量子誤り）訂正の方法・後編
第49話 オブザーバブル（メモ）
第50話 不確定性原理の導出（メモ）
第51話 正準交換関係

これはGroverのアルゴリズムとして知られる量子コンピュータで用いるアルゴリズム、量子アルゴリズムの数少ない一つです。
Lucent Technologiesの研究部門Bell Labsの研究者Lov K. Groverが発見しました。

ここでデータ検索を量子計算しやすいように以下のように抽象化します。N個のランダムなデータには でラベルが付いているものとする。

ここで欲しいデータの特徴を抽象化すると、

つまり、次のような関数でf(x) = 1を満たすｘを求める問題に置き換える事が出来ます。

ここでｘがラベルに対応します。これで検索問題はf(x) = 1を満たすｘを求める問題に帰着したわけです。古典的な（量子アルゴリズムを使わない）場合、この検索に要する検査回数はN回程度になります。正しくはNのオーダー（O(N)と書きます）。これはデータベースからデータを一つ取り出しては欲しいものかどうかを検査するためにN回程度の操作が必要になるということです。運がよければ１回目ですが最悪の場合はN回必要になります。

オーダーというのは言ってみれば「大体このくらい」という見積もりと思ってもらっていいと思います。なのでN/2のオーダーと書かれる場合もありますがNが巨大になると大差無いので同程度ですね。

さて、Groverのアルゴリズムではこれが

程度で済むというアルゴリズムです。データ数が膨大な場合の差は大変なもになります。
A fast quantum mechanical algorithm for database search

次回はGroverのアルゴリズムの概要とその核心となるGrover Iterationについて見てみたいと思います。