グローバーのアルゴリズムが超重要な理由

グローバーのアルゴリズムは量子アルゴリズムの中でも最も有名な概念の一つでしょう。
量子コンピュータに馴染みのない方も名前だけは聞いたことがあるかもしれません。

私もその一人でした。ただ、初めてグローバーのアルゴリズムの内容を知った時の感想はこんなかんじです。

daiki

結局このアルゴリズムはなにが重要で有名なのだろうか？

この記事ではそんな疑問に答えるために、グローバーのアルゴリズムがなぜ有名となるほど重要であるかについて紹介します。

グローバーのアルゴリズムとは

そもそもグローバーのアルゴリズムとはデータベース検索問題と呼ばれる問題を解くためのアルゴリズムです。

この問題は例えば0,1からなる$n$桁の暗証番号を当てる問題ととらえることが出来ます。

このとき関数$f(x)$とは、入力された暗証番号が正しい(1)か間違っている(0)かの結果を教えてくれるスマホのような存在だと思ってください。

グローバーのアルゴリズムが重要な理由

ではなぜこのアルゴリズムが重要とされているかについて私なりの結論を書きます。

この2点を中心に解説していきます。

古典計算に対して量子加速する

先ほどの暗証番号の例を考えましょう。
片っ端から正解を確かめようとすると、$0\cdots0$から$1\cdots1$の$N=2^n$回、つまり$\Omicron(N)$回の確認を行わないといけません。

一方でグローバーのアルゴリズムでは$\Omicron(\sqrt{N})$回の計算で確率$1-1/N$以上で正しい結果が求まることが知られています。

つまりグローバーのアルゴリズムで計算を行うと、10桁の暗証番号の場合、古典計算よりも100000倍速く計算出来ることを意味しています。

アルゴリズムを視覚的に理解する

ではなぜグローバーのアルゴリズムが量子加速が可能なのか、アルゴリズムのステップを数学的な話はせずに視覚化して理解しましょう。

初期状態を準備

まずは$n$個の量子ビットの初期状態を準備します。
初期状態は$n$個の量子ビットが全て0の状態で、測定すると出力される結果は確率1で$0\cdots0$となります。

重ね合わせの状態を作る

続いて量子計算特有の重ね合わせの状態を作ります。(アダマール変換)
重ね合わせの状態では$0\cdots0$から$1\cdots1$の$2^n$個の状態が等確率で共存しています。

量子計算の最大の特徴は、重ね合わせを作ることで$2^n$個の状態全てに対して一度に演算が可能な点です。

しかし、その結果はその内の一つだけしか取り出せず、何が出力されるかは確率的に決まるという量子そのものの性質に起因する制約があります。

つまりまだ現時点では確率$1/2^n$で$0\cdots0$から$1\cdots1$のいずれかが出力されるという意味のない状態です。

期待する量子状態の確率を増幅させる

アルゴリズムを通して知りたいことは正解の暗証番号が何かです。
そのためアルゴリズムには正解の結果(量子状態)の確率を増幅させて出力される確率を限りなく高めることが求められます。

具体的にはまずスマホに1回問い合わせをすることで、$2^n$個の暗証番号全てに対して正解不正解が一度に判定されるので、正解の量子状態の確率振幅の符号を反転させます。

次に、全ての量子状態の確率振幅の平均値を中心に各状態の確率振幅を折り返します。

この符号の反転と確率振幅の折り返しのサブルーチンは振幅増幅と呼ばれ、1回の振幅増幅で正解の状態の確率振幅を$\Omicron(\frac{1}{\sqrt{N}})$増幅することが可能です。

したがって上記のステップを$\Omicron(\sqrt{N})$回繰り返すと、正解の量子状態が取得される確率は限りなく1に近づき、正解を出力させることが出来るのです。

これがグローバーのアルゴリズムが量子加速を実現する理由となります。

グローバーのアルゴリズムの立ち位置

ここまでグローバーのアルゴリズムが量子加速可能だという話をしてきました。

しかし、他のアルゴリズムでも量子加速はあるはずなのになぜグローバーのアルゴリズムがよく取り上げられるかというと、振幅増幅の考え方は所望の量子状態を取得するという観点で様々な量子アルゴリズムに適用される普遍的な概念だからです。

先程も触れましたが、どんなに重ね合わせによりたくさんの並列計算を実行できても、期待する結果が手に入らなくては意味がありません。

グローバーのアルゴリズムの核となる振幅増幅は期待する結果を取り出すという共通の過程に対して適用可能な処理であり、それ故に最も基本的なアルゴリズムとして私達はこれを理解しなければいけないのです。

まとめ

この記事では有名なグローバーのアルゴリズムについて、なぜ重要な考え方なのかを紹介しました。

より詳しく学びたいという方はこちらの参考書が分かりやすいので是非ご覧ください。