非断熱遷移の例: 接合木問題(Glued two binary trees problem)

この記事の概要

通常、量子アニーリングでは断熱的に状態を変化させながら解を見つけます。しかし解を見つけさえできれば、断熱的に時間発展をさせなくても、それは解を発見する手法として十分なはずです。この記事ではエネルギースペクトルの特殊な構造を利用して、より素早く最適解にたどり着く方法とその問題例[3][4]をご紹介します。

この記事の概要
断熱定理
非断熱遷移
接合木問題
なぜ多項式時間で解けるのか
この問題のインパクト
結言
参考文献
文責

断熱定理

今、系のハミルトニアンが

$\displaystyle{ H(s) = (1-s) H_0 + s H_1 }$

とします。ここで $s$ は時間のようなもので $s : 0 \rightarrow 1$ に変化すると考えてください。 $H_0$ の自明な基底状態を初期に選び、 $H(s)$ で記述される系を時間に依存したシュレディンガー方程式にしたがって時間発展させます。このとき $s$ の発展が十分ゆっくりであれば、量子力学の断熱定理を適用することができます。すると、 $H_0$ の基底状態を初期条件としたこの系は、各瞬間の基底状態を連続的に追っていきます。そして、最終的に $H_1$ の基底状態に到達するのです。これが量子アニーリングによって最適解(エネルギーの基底状態)を求めるときの基本戦略と言えるでしょう [1]。

実際にどのくらいゆっくりすればいいのかを以下に示します。

$\displaystyle{ s = \frac{t}{T} }$

のように、 $s$ を時刻 $t$ と実際のアニーリング時間 $T$ で表すことにしましょう(ただし $0\leq t \leq T$ )。あるエネルギー準位とその励起状態とのエネルギーギャップを $\Delta$ とすると

$\displaystyle{ T \propto \frac{1}{\Delta^2} }$

のときに断熱定理が成り立つことがわかります[2]。

非断熱遷移

上述の断熱定理による手法は、さながら「エネルギーの低い状態を潜り続ける戦法」でした。確かにこれならば、エネルギーの低い終状態を見つけることができそうです。しかし、冒頭でも記述した通り「解を見つけさえすれば、ゆっくり断熱変化させる手法にこだわる必要はない」というのがこの戦法です。以下の図の黒線で表現されているようなエネルギースペクトル上で状態が変化していく様子をみてみましょう。

断熱過程では(どのようなエネルギーランドスケープであっても)基底状態をゆっくり移動していきます。下図の青色ルートです。
非断熱過程では基底状態をゆっくり移動する必要はなく、途中励起状態を経由して移動することを確率的に許します。下図のピンク色ルートです。

Adiabatic and Non-Adiabatic processes. — 断熱過程と非断熱過程

青色ルートをゆっくり移動するのではなく、途中でエネルギーギャップを飛び越え状態をわざと遷移させることで、より高速に求めたい終状態へとたどり着くことができます[2]。

接合木問題

この問題の概要

この非断熱遷移過程を利用して、古典アルゴリズムに比べて指数関数的な高速化を達成した問題例に、接合木問題があります。これは下図のように表される問題です。

一歩進むと2つに枝分かれする経路を左右に2つ用意して中心に向かって枝を伸ばしていき、端の部分で2つをランダムに接合します。2つの木を接合する中央部分の枝の長さだけ、他の部分の枝の長さの $\sqrt{2}$ 倍にしておきます。図の $n$ は片方のツリーの深さを表します。よってこの接合木は $2n+2$ のカラムを持つことがわかります。
左端のENTRANCE点から出発(初期状態, j=0)し、右端のEXITへと到達(終状態, j=2n+1)するのにかかる最小ステップ(最小時間)を求めなさい、というオラクル(ブラックボックス)問題です[3]。

オラクルと今回の問題設定

オラクルとは神からのお告げ、「神託」と訳されるものです。神はなんでも知っており、何かを問いかけるとそれに対して $\mathcal{O}(1)$ の計算時間で答えを返してくれます。

今回の問題は迷路、そこに迷い込んだ人間、そしてそれを上から眺めていてドアの情報を与えてくれる神様に例えることができます。迷路に迷い込んだ人間は方向感覚を失い、どの経路を辿ってきたのか、どのドアを入って現在の部屋に入ってきたのかを記憶しておくことができません。ただし上空からそれを見ている神様は、その人間へのアドバイスとして、その部屋のドアの情報だけを与えてくれます。

maze, human, the God. — 迷路、そこに迷い込んだ人間、そして神の役割図。

なお、この迷路の入り口の部屋にはENTRANCE、迷路の出口の部屋にはEXITと名前がついており、入り口と出口の見分けだけはつくものとします。迷路の全体像を把握していない人間が神からのアドバイスのみを読みとって迷路探索を行う、オラクル問題と言えます。元々はこれを量子ウォークで高速に解くというものが先行研究として存在しておりました。
それではこれを量子アニーリングで解くことを考えていきましょう。

状態ベクトルとハミルトニアン

状態ベクトル

あるノード(迷路の部屋)にいないときの状態ベクトルを

$\displaystyle{ \left| 0 \right> = \left( \begin{array}{c} 1 \\ 0 \end{array}\right) }$

そしてあるノードにいるときの状態ベクトルを

$\displaystyle{ \left| 1 \right> = \left( \begin{array}{c} 0 \\ 1 \end{array}\right) }$

のようにビットを使って表現しましょう。するとi番目のノードにいる状態を $\left| a(i) \right>$ は、全ノード数を $N = 2^{n+2}-2$ とすると

$\displaystyle{ \left| a (i) \right> =\underbrace{\left| 0 \right> \otimes \left| 0 \right> \otimes \cdots \otimes \overbrace{\left| 1 \right>}^{i番目だけ1} \otimes \cdots \otimes \left| 0 \right>}_{N個の状態ベクトルのテンソル積} }$

のように、 $2^N$ 次元のベクトルで表すことができます。
するとENTRANCEを0番目のカラムと定義したときに、j番目のカラムにいるときの状態 $\left| {\rm col}_j \right>$ は、その状態を重ね合わせたものとして

$\displaystyle{ \left| {\rm col}_j \right> = \frac{1}{\sqrt{N_j}} \sum_{i \in j{\rm -th \ colomn}} \left| a (i) \right> }$

のように書くことができます。以降ではこの $\left| {\rm col}_j \right>$ で物事を考えていくことにしましょう。

初期状態のハミルトニアン: $H_0$

$\left| {\rm col}_j \right>$ の定義から、j=0(すなわちENTRANCE)にいるときを基底状態にもつ、すなわち

$\displaystyle{ H_0 \left| {\rm col}_0 \right> = - \left| {\rm col}_0 \right> }$

となるようなハミルトニアン $H_0$ は、 $\left| {\rm col}_j \right>$ を基底とする形で書くと

$\displaystyle{ H_0 = \left( \begin{array}{cccc} -1 & & &{\bf 0} \\ & 0 & & \\ & & \ddots & \\ {\bf 0} & & & 0 \end{array} \right) }$

のような $2n+2 \times 2n+2$ の行列で書かれます。

終状態のハミルトニアン $H_1$

同様に考えると、終状態のハミルトニアン $H_1$ は、基底状態として $\left| {\rm col}_{2n+1} \right>$ (EXITにいる状態)をもつことから

$\displaystyle{ H_1 \left| {\rm col}_{2n+1} \right> = - \left| {\rm col}_{2n+1} \right> }$

より

$\displaystyle{ H_1 = \left( \begin{array}{cccc} 0 & & &{\bf 0} \\ & 0 & & \\ & & \ddots & \\ {\bf 0} & & & -1 \end{array} \right) }$

となります。

全ハミルトニアン

量子アニーリングの思想から、初期に「 $\left| {\rm col}_0 \right>$ を基底状態に持つハミルトニアン」からスタートし、終状態として「 $\left| {\rm col}_{2n+1} \right>$ を基底状態に持つハミルトニアン」を選ぶことで、状態を $\left| {\rm col}_0 \right>$ から $\left| {\rm col}_{2n+1} \right>$ に遷移させることができます。上述より、前者は $H_0$ 、後者は $H_1$ のように書けることから、全ハミルトニアンは

$\displaystyle{ H (s)= (1-s) H_0 + s H_1 + (量子項) }$

のように書くことができます。ここで$`s`$はアニーリングのスケジュールを決める時間のパラメータ( $s=0$ がスタート、 $s=1$ がゴール、 $0\leq s \leq 1$ )です。

非対角成分 (量子項)

量子項を含めない場合、シュレディンガー方程式から

$\displaystyle{ \left| {\rm col}_j \right> = e^{-iHt/\hbar} \left| {\rm col}_0 \right> }$

のように量子ダイナミクスを考えることができます。しかしハミルトニアンの対角化された形から、右辺は

$\displaystyle{ e^{it/(2 \hbar)} \left| {\rm col}_0 \right> }$

のように求まります。これは $\left| {\rm col}_0 \right>$ の位相を変化させているだけであり、この量子項を含めないハミルトニアンではダイナミクスに影響を及ぼしません。
よって、j番目からj+1番目への状態の遷移を表す行列 $A$ を用いて、先ほどのハミルトニアンに以下のような非対角成分を加え、これを量子項とします。

$\displaystyle{ \left< {\rm col}_j \right| A \left| {\rm col}_{j+1} \right> = \left\{ \begin{array}{cc} \sqrt{2} & j = n \\ 1 & {\rm otherwise} \end{array} \right. }$

最終的なハミルトニアン

上の議論を踏まえて、求めたかった接合木問題のハミルトニアンは

$\displaystyle{ H(s) = (1-s) \alpha H_0 - s(1-s) A + s\alpha H_1 }$

のように書かれます。ここで $\alpha$ は $n$ に依存しない $0<\alpha<1/2$ を満たすパラメータです。
「ENTRANCEからEXITに行くこと」と「EXITからENTRANCEに行くこと」は等価となるので、ハミルトニアンには $s \leftrightarrow (1-s)$ のような対称性があります。よって $0\leq s \leq 1/2$ の部分だけ議論すれば良いことがわかります[4]。

エネルギースペクトル

論文[4]のような詳細な解析を行うと、基底状態と第一励起状態のエネルギースペクトルの差が $s= s_{\times} = \alpha/\sqrt{2}$ 近傍で、そのギャップが問題サイズの指数で小さくなることがわかります。より具体的には

$\displaystyle{ \Delta_{10}(s_\times) \in \mathcal{O}(2^{-n/2}) }$

となります。先ほどの対称性の話から、 $s=1-s_\times$ でもう一つエネルギーギャップが小さくなる部分が存在することがわかります。
よってこの問題のエネルギースペクトルを図示すると以下のようになります。

Energy spectrum of glued trees problem — エネルギースペクトル。

$s = s_\times, 1-s_\times$ 近傍以外のエネルギーギャップの大きさは問題サイズの多項式で与えられます(より詳細には $\mathcal{O}(n^{-3})$ となります)。よって指数関数より速い多項式時間で時間発展させると、系は $s=s_\times$ で第一励起状態状態に上がったあと、 $s=1-s_\times$ で基底状態に戻ります。この方法は、最速の古典アルゴリズムに比べて指数関数的な高速化を達成し、計算時間を $\mathcal{O}(n^6)$ まで短縮することができます[5]。

なぜ多項式時間で解けるのか

前述の断熱定理の式から考えてみましょう。エネルギースペクトルの図[4]から、 $T\propto \mathcal{O}(n^6)$ のようにアニーリング時間を設定すれば、途中で第二励起状態に遷移することなく基底状態->第一励起状態->基底状態の順に状態が変化することが可能になります。

この問題のインパクト

この問題の凄さは論文[3]および論文[4]に示されています。論文[3]ではこの問題を量子回路を使って解き、論文[4]ではこの問題を量子アニーリングで解きました。量子アニーリングマシンが量子コンピュータと等価である、ということは理論的に示されています。そこから発展し、「量子アニーリングによる計算が量子計算になっている」という理論を実証する大きな一例が示されたことにこの問題の重要性があります。
またこの問題が特異な例と言われるのには、そのエネルギースペクトルの形状が挙げられます。これまでは断熱定理を用いることで確実に基底状態を潜行し続けることに、世界が着目していました。グローバーのアルゴリズムの断熱量子計算がその最たるものの一つです。グローバーの例は、基底状態と第一励起状態のエネルギー差が大きく開いているために、状態遷移を起こすことなく基底状態を確実に潜り続けるというものでした。
しかしこの例が発見されたことにより、2箇所でエネルギー差が小さくなっているのようなスペクトル構造が存在していれば、途中で励起状態に遷移しても最終的に基底状態を探すことができるという新たな視点が加わりました。今後、このようにスペクトル構造を応用したより困難な計算が解かれる日がくることでしょう。

結言

今回は接合木問題というオラクル問題を例に、非断熱遷移を用いた量子アニーリングによる数値計算の高速化を取り上げました。この問題においては量子アニーリングが量子計算と等価である、その実証例の一つであるということも説明させていただきました。計算加速を可能にする非断熱遷移の考え方は、非常に面白いですね。

参考文献

[1] 量子アニーリングの数理、西森秀稔
[2] 量子アニーリングの基礎、西森秀稔・大関真之著
[3] Exponential Algorithmic Speedup by Quantum Walk, Childs et al., 2002
[4] Quantum Speedup by Quantum Annealing, Somma et al., 2012
[5] Adiabatic Quantum Computing, Albash & Lider, 2016

文責

中村翔、株式会社 Jij
Sho K. NAKAMURA, Jij Inc.
憂いの篩 -Pensieve

※ 疑問点や間違いなどございましたら、お気軽にブログ上でご質問ください。

Jij Tech Blog

Jij inc.の開発日記です