データベース探索問題の量子断熱解 (Adiabatic Grover)
この記事の概要復習: グローバーのアルゴリズム探索問題とその古典オラクル量子オラクルと位相反転データベース探索をAQCで解く全ハミルトニアン終状態のハミルトニアン初期状態のハミルトニアン全ハミルトニアンスペクトル構造スケジューリング式変形可視化とその物理的意味古典に比べてどれくらい高速化を達成したか解析のポイント結言参考文献文責
この記事の概要
量子アルゴリズムの有名なものの一つにグローバーのアルゴリズムがあります。多数の項目の中から特定の項目を見つけるデータベース探索問題に用いるアルゴリズムです。これを断熱量子計算 (adiabatic quantum computing; AQC)で解くとどのようになるのか、その解法や計算速度についてご紹介します。
復習: グローバーのアルゴリズム
探索問題とその古典オラクル
探索問題とは一般に個の要素から個の解を見つける問題のことです。例として名簿データベースから佐藤さんだけを取り出したいなどが考えられます。個の要素が桁のビット列でラベル付けされているとして、この探索問題に対する「古典オラクル」を次のように定義しましょう。
つまりは要素のラベルを与えるとその要素が解であるかを2択で教えてくれる関数です。名簿の例ではのとき、となります。探索問題を解く古典アルゴリズムの計算量はが解であるかどうかを古典オラクルに尋ねる(オラクルを呼びだす)回数で評価します。こうすることで、問題の子細に依存しない統一的な評価が可能になります。
量子オラクルと位相反転
一方、探索問題を解く量子アルゴリズムの計算量は、次の(量子)オラクルを呼ぶ回数で評価します。
ここで入力状態は入力ビット列を計算基底で表した状態、は補助ビット、はmod 2の加算(XOR演算)です。が探索問題の解であるかどうかは、補助ビットが反転したかどうかをチェックすることでわかるようになっています。すなわち
他にも、補助ビットをとセットしておけば
となり、が探索問題の解のときにのみ状態の位相が反転するようにも設定することが可能です。
オラクルのもっとも大きな特徴の一つは、入力状態が重ね合わせであってもそのまま動作することです。例えば、入力状態として全ての状態の重ね合わせをとり、補助ビットをとすれば
となります。このようにが解のときのみ位相が反転する性質をうまく用いて解を見つけるのが、グローバーのアルゴリズムの概要です。古典ではオラクルの呼び出し回数は項目数のオーダーとなっていましたが、量子回路模型のグローバーのアルゴリズムではで解けることが知られています。
データベース探索をAQCで解く
項目に番号を付与し、これらに直交規格化ベクトルを対応させます。このうち特定の状態を断熱量子計算で求めることが今回の問題です。
全ハミルトニアン
終状態のハミルトニアン
断熱計算終了時には、状態のみを基底状態に持つようなハミルトニアンになっていなければ、探索が終了したとは言えないでしょう。よって
のように、状態は固有値0、そしてそれ以外の状態では固有値1となるようなハミルトニアンを設定します。上の議論から、終状態のハミルトニアンの簡単な形として
を選びます。
初期状態のハミルトニアン
AQCにおいて最初の状態は自明に用意できる状態を基底状態にもつハミルトニアンとします。よって全ての可能な状態を同じ重みで重ね合わせた状態を初期状態として
のように書きます。終状態のハミルトニアンと同様の議論から、これを基底状態に持つようなハミルトニアンとして
を選択します。
全ハミルトニアン
よってこの問題における全ハミルトニアンを
のようにして、断熱的に時間発展させることを考えます。ここでで、はアニーリング時間です。そしてはのような境界条件を持つ、単調増加関数とします。
スペクトル構造
ハミルトニアンはと、それに直交するのみを使って書けます。よって初期条件をこの空間内にとると、系はこの2つの状態ベクトルで張られるような2次元空間の中で時間発展を行います。この2つの状態を基底とするハミルトニアンは以下のように表現されます。
これを計算すると
のように変形することができます。ここで
さらにより
と求まります。(12)式の固有値は
よっては基底状態と第一励起状態のエネルギー差を表し、スペクトル構造はを挟んで対称な形であることがわかります。さらにはその関数の形からで最小の値をとります。よって、スペクトル構造を図示すると、その概形は以下のようになります。
スケジューリング
式変形
次はこの問題において最適なの形、すなわちアニーリングスケジュールについて考えてみましょう。断熱定理より
の条件を満たしていれば、エネルギーギャップを飛び越えることなく、基底状態のまま系が変化していきます。詳細な計算を行うとであることがわかります。証明は省略しますが、このはどんなにが大きくなっても有界に留まり、によらない定数で抑えられます。
の満たすべきギリギリの条件は上式の等号をとることで導くことができます。の表記より
これをの積分公式を用いて積分すると
となります。
可視化とその物理的意味
(18)式を横軸, 縦軸にしてプロットすると以下のようになります。
この図を見ると、単純な線形スケジュールでないことがわかります。これはエネルギーギャップが大きい部分(図の開始と終了付近)では状態を高速に変化させ、エネルギーギャップが小さい部分(図の真ん中付近)では状態を劇的に変化させないようにしています。これにより基底状態から励起状態へ状態を遷移させることなく、求めたいデータベース検索結果の状態を目指すことを意味しています。
古典に比べてどれくらい高速化を達成したか
このとき、検索にかかるおよそのアニーリング時間は(2)式で[tex: s = 1, f = 1]の境界条件より
となります。この結果は量子回路におけるグローバーのアルゴリズムと同じ計算時間になっており、確かに古典の場合に比べて2乗の高速化(かかる時間は平方根)になっていることがわかります。
解析のポイント
接合木問題とグローバーでのAQCの解析のポイントは、オラクルの性質によりヒルベルト空間の部分空間のみを考えればよいということです。他にも、AQCで何かしら上述と同様の主張を行う際は、ハミルトニアンの対称性を用いて部分空間のみを考慮して計算量・エネルギーギャップを解析することがあります。
結言
今回はAQCでグローバーのアルゴリズムを解く、その解法と計算量などの見積もりをご紹介いたしました。グローバーアルゴリズム自体の汎用性が高いため、これが量子アニーリングでもできるというだけでも応用分野がかなり広がりそうです。
参考文献
- [2] 西森秀稔, 大関真之, “量子アニーリングの基礎”
文責
中村翔、株式会社 Jij
Sho K. NAKAMURA, Jij Inc.
宇宙物理メモ
※ 疑問点や間違いなどございましたら、お気軽にブログ上でご質問ください。