量子振幅増幅、グローバーのアルゴリズム、量子振幅推定

量子コンピュータの教科書ではグローバーのアルゴリズムを利用した検索システムというのが有名ですが、2021年のトレンドを把握するには、そのような検索システムに対する用途はあまり考えられておらず、他用途への適用が想定されています。それらをまとめてみます。


グローバーのアルゴリズムを見る前に

グローバーのアルゴリズムはある条件を決めたもとで、その条件を満たす答えを高速に探索するというアルゴリズムで、教科書では検索システムに利用されたり、最近では組合せ最適化問題を解いたりという用途が想定されています。ただ、2021年現在ではそのような大規模な回路を実装するめどがまだ立っていないため、あまりグローバーのアルゴリズムを使うことはありません。グローバーのアルゴリズムはある答えの出る確率を最大化するために、振幅を最大化しますが、2021年では必ずしも最大化に焦点を当てず、振幅のシミュレーションに使われることが多いので、グローバーのアルゴリズムをもう少し紐解いた量子振幅増幅を先に見てみます。


量子振幅増幅

細かい理論は様々な文献があるので割愛させていただきますが、グローバーのアルゴリズムは振幅増幅と呼ばれる仕組みに乗っかっています。量子コンピュータは、波動関数もしくは状態ベクトルと呼ばれるものを操作します。状態ベクトルの一つ一つの要素は振幅と言って、それに対応するビット列の状態が出る確率の平方根に対応しています。ある特定の振幅を小さくしたり、大きくしたりすることでほしい答えが出る確率を操作することができます。量子振幅増幅は、


1,マーキング

2,増幅反転


と呼ばれる二つの操作を行うことで、マーキングを行った特定の状態の振幅だけを増幅させることができます。これを複数回行うことでさらに特定の振幅を操作することができます。量子振幅増幅は基本的なアルゴリズムで実用的にはそこから派生したグローバーのアルゴリズムと量子振幅推定のアルゴリズムの用途が考えられています。


参考:

https://github.com/Blueqat/Blueqat-tutorials/blob/master/tutorial-ja/110_amplitude_amplification_ja.ipynb


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

グローバーのアルゴリズムは上記の量子振幅増幅を利用して、ある特定の振幅を「最大化」します。また、グローバーのアルゴリズムは一番最初のスタート状態をシンプルな「重ね合わせ状態」とすることによって、振幅の初期値が決まり、ターゲットとなる振幅をsinの三角関数で置くことによって、初期の位相とsinを最大にするpi/2によって、2n+1から何回振幅増幅を実行すればsinが最大になるか繰り返し回数のnが最初に導出されます。


よって、グローバーのアルゴリズムは振幅を最大にするために初期状態の重ね合わせと、量子振幅推定の仕組みを利用した計算方法ということになります。


https://github.com/Blueqat/Blueqat-tutorials/blob/master/tutorial-ja/111_grover_ja.ipynb


しかし、2021年における量子振幅増幅の有用アプリケーションはグローバーのアルゴリズムではなく、次に説明する量子振幅推定が出てくることが多いです。


キラーアプリ、量子振幅推定

金融計算では現在のコンピュータで夜通しリスクの計算をしています。これは複雑な条件を入れて、会社や金融商品がよくなるのか悪くなるのかをシミュレーションしています。シミュレーション結果は確率の分布として出てきて、それらの平均などを取ることによってリスクを評価し、リスクによって金額が変わってきます。そのようなリスクを予測する側とそれを利用し、リスクを減らしたい人に金融商品を売ります。


量子振幅推定はこれらのシミュレーションの速度を加速させることが理論的に見えてきたので世界中の投資銀行を中心に注目されているアルゴリズムです。


量子振幅推定は量子振幅増幅の仕組みを使いますが、振幅を最大化することが目的ではありません。あるシミュレーションをしたときに最終的にその答えが出る確率である、確率振幅を精度よく推定したいというのが目的です。


量子振幅推定はグローバーと異なり、初期状態から試行回数を推定しませんので、初期状態を重ね合わせ状態に保つ必要がなく、任意の状態を利用し、シミュレーションの回数を行ったあとの振幅の値を推定します。


量子振幅増幅は、


1,マーキング

2,増幅反転


の2ステップで行いますが、これからそれぞれユニタリ行列と呼ばれる量子ゲートの塊で行われます。これらのステップは連続して行われるので、まとめて大きな一つのユニタリ行列Uとすると、そのUは固有値を持つことが分かっていて、


U|psi> = λ|psi>


という固有値問題に落とすことができます。ラムダは実際には位相αの形であらわされますが、固有値問題を解くには量子位相推定というアルゴリズムがあります。量子振幅増幅のステップを固有値問題に落とし込むことで、求めたい振幅の位相を推定できます。これが量子振幅推定です。


https://github.com/Blueqat/Blueqat-tutorials/blob/master/tutorial-ja/112_amplitude_estimation_ja.ipynb


量子振幅推定は、


1,位相キックバック

2,逆量子フーリエ変換


というステップですが、最近では逆量子フーリエ変換の実行が難しいため、サンプリングを利用する方法など工夫がされています。また、量子振幅推定は数値積分やナビエストークスなど多くの誤差精度を改善することで恩恵を受ける計算機上の数値演算の多くへと応用が展開され始めています。


量子振幅増幅および量子振幅推定は量子古典ハイブリッド計算ではなく、FTQCと呼ばれる量子誤り訂正必須のアルゴリズムですので、今後の各社の開発ロードマップに準じて発展していく予定となっています。以上です。

Yuichiro Minato
blueqat CEO/CTO 2015年総務省異能vation最終採択 2017年内閣府ImPACTプロジェクトPM補佐 2019年文科省さきがけ量子情報処理領域アドバイザー
Comments
Yuichiro Minato
blueqat CEO/CTO 2015年総務省異能vation最終採択 2017年内閣府ImPACTプロジェクトPM補佐 2019年文科省さきがけ量子情報処理領域アドバイザー
Related posts

blueqat Inc.

Shibuya Scramble Square 39F 2-24-12, Shibuya, Shibuya-ku, Tokyo
Contact: info@blueqat.com