非断熱遷移の例: 接合木問題 (glued two binary trees problem)
この記事の概要
通常、量子アニーリングでは断熱的に状態を変化させながら解を見つけます。しかし解を見つけさえできれば、断熱的に時間発展をさせなくても、それは解を発見する手法として十分なはずです。この記事ではエネルギースペクトルの特殊な構造を利用して、より素早く最適解にたどり着く方法とその問題例であるChilds et al., 2002とSomma et al., 2012をご紹介します。
断熱定理
今、系のハミルトニアンが
で与えられるとします。ここでは時間を表す変数でに変化すると考えます。の自明な基底状態を初期に選び、で記述される系を時間に依存したシュレディンガー方程式にしたがって時間発展させます。このときの発展が十分ゆっくりであれば、量子力学の断熱定理を適用することができます。すると、の基底状態を初期条件としたこの系は、各瞬間の基底状態を連続的に追っていきます。そして、最終的にの基底状態に到達するのです。これが量子アニーリングによって最適解(エネルギーの基底状態)を求めるときの基本戦略と言えるでしょう。
実際にどのくらいゆっくりすればいいのかを以下に示します。
のように、を時刻と実際のアニーリング時間で表すことにしましょう(ただし)。あるエネルギー準位とその励起状態とのエネルギーギャップをとすると
のときに断熱定理が成り立つことがわかります。
非断熱遷移
上述の断熱定理による手法は、さながら「エネルギーの低い状態を潜り続ける戦法」でした。確かにこれならば、エネルギーの低い終状態を見つけることができます。しかし、冒頭でも記述した通り「解を見つけさえすれば、ゆっくり断熱変化させる手法にこだわる必要はない」というのが今回考える手法です。以下の図の黒線で表現されているようなエネルギースペクトル上で状態が変化していく様子をみてみましょう。
断熱過程では(どのようなエネルギーランドスケープであっても)基底状態をゆっくり移動していきます。下図の青色ルートです。非断熱過程では基底状態をゆっくり移動する必要はなく、途中で励起状態を経由して移動することを確率的に許します。下図のピンク色ルートです。
青色ルートをゆっくり移動するのではなく、途中でエネルギーギャップを飛び越え状態をわざと遷移させることで、より高速に求めたい終状態へとたどり着くことができます。
接合木問題
この問題の概要
この非断熱遷移過程を利用して、古典アルゴリズムに比べて指数関数的な高速化を達成した問題例に、接合木問題があります。これは下図のように表される問題です。
一歩進むと2つに枝分かれする経路を左右に2つ用意して中心に向かって枝を伸ばしていき、端の部分で2つをランダムに接合します。2つの木を接合する中央部分の枝の長さだけ、他の部分の枝の長さの倍にしておきます。図のは片方のツリーの深さを表します。よってこの接合木はのカラムを持つことがわかります。
左端のENTRANCE点から出発(初期状態, )し、右端のEXITへと到達(終状態, )するのにかかる最小ステップ(最小時間)を求めなさい、というオラクル(ブラックボックス)問題です。
オラクルと今回の問題設定
オラクルとは神からのお告げ、「神託」と訳されるものです。神は全てを知っており、何かを問いかけるとそれに対しての計算時間で答えを返すことができます。
今回の問題は迷路、そこに迷い込んだ人間、そしてそれを上から眺めていてドアの情報を与えてくれる神様に例えることができます。迷路に迷い込んだ人間は方向感覚を失い、どの経路を辿ってきたのか、どのドアを入って現在の部屋に入ってきたのかを記憶しておくことができません。ただし上空からそれを見ている神様は、その人間へのアドバイスとして、その部屋のドアの情報だけを与えてくれます。
なお、この迷路の入り口の部屋にはENTRANCE、迷路の出口の部屋にはEXITと名前がついており、入り口と出口の見分けだけはつくものとします。これは迷路の全体像を把握していない人間が神からのアドバイスのみを読みとって迷路探索を行う、オラクル問題と言えます。元々はこれを量子ウォークで高速に解くというものが先行研究として存在しておりました。
それではこれを量子アニーリングで解くことを考えていきましょう。
状態ベクトルとハミルトニアン
状態ベクトル
あるノード(迷路の部屋)にいないときの状態ベクトルを
そしてあるノードにいるときの状態ベクトルを
のようにビットを用いて表現しましょう。すると番目のノードにいる状態は、全ノード数をとすると
のように、次元のベクトルで表すことができます。
するとENTRANCEを0番目のカラムと定義したときに、番目のカラムにいるときの状態は、その状態を重ね合わせたものとして
のように書くことができます。以降ではこので現象を考えていくことにしましょう。
初期状態のハミルトニアン:
の定義から、(すなわちENTRANCE)にいるときを基底状態にもつ、すなわち
となるようなハミルトニアンは、を基底とする形で書くと
のようなの行列で書かれます。
終状態のハミルトニアン:
同様に考えると、終状態のハミルトニアンは、基底状態としてを持つことから
より
となります。
全ハミルトニアン
量子アニーリングの思想から、初期に「を基底状態に持つハミルトニアン」からスタートし、終状態として「を基底状態に持つハミルトニアン」を選ぶことで、状態をから]に遷移させることができます。上述より、前者は、後者はのように書けることから、全ハミルトニアンは
のように書くことができます。ここではアニーリングのスケジュールを決める時間のパラメータ(がスタート、がゴール、)です。
非対角成分 (量子項)
量子項を含めない場合、シュレディンガー方程式から
のように量子ダイナミクスを考えることができます。しかしハミルトニアンの対角化された形から、右辺は
のように求まります。これはの位相を変化させているだけであり、この量子項を含めないハミルトニアンではダイナミクスに影響を及ぼしません。よって、番目から番目への状態の遷移を表す行列を用いて、先ほどのハミルトニアンに以下のような非対角成分を加え、これを量子項とします。
最終的なハミルトニアン
上の議論を踏まえて、求めたかった接合木問題のハミルトニアンは
のように書かれます。ここではに依存しないを満たすパラメータです。
「ENTRANCEからEXITに行くこと」と「EXITからENTRANCEに行くこと」は等価となるので、ハミルトニアンにはのような対称性があります。よっての部分だけ議論すれば良いことがわかります。
エネルギースペクトル
となります。先ほどの対称性の話から、でもう一つエネルギーギャップが小さくなる部分が存在することがわかります。
よってこの問題のエネルギースペクトルを図示すると以下のようになります。
近傍以外のエネルギーギャップの大きさは問題サイズの多項式で与えられます(より詳細にはとなります)。よって指数関数より速い多項式時間で時間発展させると、系はで第一励起状態状態に励起したあと、で基底状態に戻ります。この方法は、最速の古典アルゴリズムに比べて指数関数的な高速化を達成し、計算時間をまで短縮することができます。
なぜ多項式時間で解けるのか
前述の断熱定理の式から考えてみましょう。エネルギースペクトルの図から、のようにアニーリング時間を設定すれば、途中で第二励起状態に遷移することなく基底状態->第一励起状態->基底状態の順に状態が変化することが可能になります。
この問題のインパクト
この問題の凄さはChilds et al., 2002およびSomma et al., 2012に示されています。Childs et al., 2002ではこの問題を量子回路を使って解き、Somma et al., 2012ではこの問題を量子アニーリングで解きました。量子アニーリングマシンが量子コンピュータと等価である、ということは理論的に示されています。そこから発展し、「量子アニーリングによる計算が量子計算になっている」という理論を実証する大きな一例が示されたことにこの問題の重要性があります。
またこの問題が特異な例と言われるのには、そのエネルギースペクトルの形状が挙げられます。これまでは断熱定理を用いることで確実に基底状態を潜行し続けることに、世界が着目していました。Groverのアルゴリズムの断熱量子計算がその最たるものの一つです。Groverの例は、基底状態と第一励起状態のエネルギー差が大きく開いているために、状態遷移を起こすことなく基底状態を確実に潜り続けるというものでした。
しかしこの例が発見されたことにより、2箇所でエネルギー差が小さくなっているのようなスペクトル構造が存在していれば、途中で励起状態に遷移しても最終的に基底状態を探すことができるという新たな視点が加わりました。今後、このようにスペクトル構造を応用し、より困難な計算が高速で解かれる日がくることでしょう。
結言
今回は接合木問題というオラクル問題を例に、非断熱遷移を用いた量子アニーリングによる数値計算の高速化を取り上げました。この問題においては量子アニーリングが量子計算と等価である、その実証例の一つであるということも説明させていただきました。計算加速を可能にする非断熱遷移の考え方は、非常に面白い見地です。
参考文献
- [2] 西森秀稔, 大関真之, “量子アニーリングの基礎”
文責
中村翔、株式会社 Jij
Sho K. NAKAMURA, Jij Inc.
宇宙物理メモ
※ 疑問点や間違いなどございましたら、お気軽にブログ上でご質問ください。