補遺: AQCと量子アニーリングの広がり

量子アニーリングを学んでいると、同じような式が QA、QAA、AQC、AQO、StoqAQC という少し違う名前で現れます。さらに、シミュレーテッド量子アニーリング、QAOA、反断熱項、non-stoquastic ハミルトニアン、diabatic quantum annealing まで出てくると、どこまでが同じ話で、どこからが別の話なのかが見えにくくなります。

これらは、名前の違いとして暗記するよりも、一つの変形過程として見た方が分かりやすいです。出発点は単純です。解きたい問題を対角ハミルトニアンに埋め込み、簡単な初期ハミルトニアンから少しずつ変形していきます。そこに、断熱定理、符号問題、小ギャップ、量子相転移、非断熱遷移、経路設計という複数の見方が重なっています。

1. 名前の整理

まず、言葉を整理しておきます。厳密な境界線がいつも共有されているわけではありませんが、次のように分けると混乱が少ないです。

AQC は adiabatic quantum computation の略で、閉じた量子系の断熱時間発展を計算モデルとして使う立場です。初期ハミルトニアンの基底状態を用意し、ハミルトニアンを十分ゆっくり変化させ、最終ハミルトニアンの基底状態に到達させます。問題を解くというより、計算モデルそのものを断熱時間発展で表す広い枠組みです。

AQO や QAA は、AQCを最適化問題に向けたものとして読むときの名前です。最終ハミルトニアンの基底状態が目的関数の最小値を表すようにしておき、断熱発展でそれを探します。

QA は、実用上はもっと広い言葉として使われます。閉じた系の断熱発展に限らず、開放系、有限温度、非断熱過程、実機ノイズ、ヒューリスティックな短時間実行まで含めて呼ばれることが多いです。したがって「QAで解く」と言ったとき、それが厳密な断熱計算を意味しているのか、有限時間の量子ダイナミクスを利用した探索を意味しているのかは、文脈を確認する必要があります。

StoqAQC は、stoquastic ハミルトニアンに制限したAQCです。標準的な横磁場Ising型の量子アニーリングは、この理想化に近いです。

標準的な出発点は、多くの場合、次の補間ハミルトニアンで書けます。

$$\hat{H}(s)=(1-s){\hat{H}}_0+s{\hat{H}}_1,0\le s\le 1.$$

ここで ${\hat{H}}_0$ は基底状態を作りやすい初期ハミルトニアン、${\hat{H}}_1$ は解きたい問題を符号化した問題ハミルトニアンです。実機や連続時間の記法では、横磁場項と問題項の係数を別々のスケジュールで書くことが多いです。

$$\hat{H}(t)=A(t){\hat{H}}_X+B(t){\hat{H}}_Z,{\hat{H}}_X=-\sum _{i=1}^N{\hat{X}}_i,$$

$${\hat{H}}_Z=-\sum _i{h}_i{\hat{Z}}_i-\sum _{(i,j)\in E}{J}_{ij}{\hat{Z}}_i{\hat{Z}}_j.$$

$A(t)$ を大きく、$B(t)$ を小さく始めれば、最初は横磁場の基底状態が支配的です。最後に $A(t)$ を小さく、$B(t)$ を大きくすれば、測定で得られる計算基底のビット列がIsingエネルギーを反映します。1日目、2日目、補遺の多くの式は、この形を少しずつ別の角度から見ています。

2. 断熱条件の「民間公式」と厳密な見方

断熱定理を最初に使うときは、次の形を覚えておけば十分に役立ちます。

$$t_f\gg \underset{s}{max}\frac{|⟨{\epsilon }_m(s)|{\partial }_s\hat{H}(s)|{\epsilon }_0(s)⟩|}{{\mathrm{\Delta }}_{m0}(s{)}^2},{\mathrm{\Delta }}_{m0}(s)={\epsilon }_m(s)-{\epsilon }_0(s).$$

ここで $s=t/t_f$ であり、$t_f$ は全実行時間です。分子はハミルトニアンを変える速さに対する結合、分母はエネルギーギャップの二乗です。ギャップが小さい場所では、状態は瞬時基底状態から漏れやすいです。

最も単純には、第一励起状態との最小ギャップ

$${\mathrm{\Delta }}_{min}=\underset{0\le s\le 1}{min}\{{\epsilon }_1(s)-{\epsilon }_0(s)\}$$

が実行時間を支配すると考えます。したがって「小さいギャップが危ない」という直観が出てきます。

ただし、上の断熱条件は便利な目安であって、そのまま厳密な誤差評価ではありません。厳密な断熱定理では、瞬時基底状態ベクトルそのものよりも、基底空間への射影演算子を比べる形が自然です。基底状態が非縮退なら

$$\hat{P}(s)=|{\epsilon }_0(s)⟩⟨{\epsilon }_0(s)|$$

と書けます。縮退がある場合も、低エネルギー部分空間への射影として同じ考え方が使えます。時間発展で得られた状態の射影を ${\hat{P}}_{t_f}(s)$ とすれば、断熱近似の誤差は

$$\Vert {\hat{P}}_{t_f}(s)-\hat{P}(s)\Vert \le ϵ$$

のように測ります。この形にすると、ゲージ位相や基底ベクトルの取り方に依存しないです。

実際の厳密評価には、ギャップだけでなく ${\partial }_s\hat{H}$ や ${\partial }_s^2\hat{H}$ のノルム、端点での滑らかさ、射影空間の幾何が入ります。概念的には

$$ϵ\lesssim \frac{1}{t_f}[\underset{s}{max}\frac{\parallel {\partial }_s\hat{H}(s)\parallel }{\mathrm{\Delta }(s{)}^2}+\underset{s}{max}\frac{\parallel {\partial }_s^2\hat{H}(s)\parallel }{\mathrm{\Delta }(s{)}^3}+\cdots ]$$

のような構造を持ちます。係数や仮定は定理の版によって異なりますが、大事なのは「ギャップだけを見ればよい」わけではないという点です。

この違いは、森田・西森型の収束定理やSomma--Batista--Ortizの構成を読むときにも効いてきます。講義ではしばしば ${\mathrm{\Delta }}^{-2}$ の目安から議論を始めますが、証明として扱うときには、どの距離で、どの空間に、どのくらい近いのかを明示する必要があります。

3. 実行時間とエネルギースケール

断熱計算で「何秒かかるか」を比べるには、ハミルトニアンのエネルギースケールも固定しなければなりません。もしハミルトニアン全体を $\lambda$ 倍すれば、ギャップも行列要素も変わり、同じ物理的制限のもとで許される時間も変わります。したがって、単に $t_f$ だけを見て計算量を比べることはできません。

粗い尺度としては

$$\mathcal{C}=t_f\underset{0\le s\le 1}{max}\parallel \hat{H}(s)\parallel$$

のように、時間とエネルギーの積を考えます。実機では、結合強度、局所場、制御精度、温度、デコヒーレンス時間が別々に制限を与えます。理論式では $t_f$ を自由に大きくできても、物理装置では大きなハミルトニアンを自由に強くできるわけではありません。

この点は、QAの性能比較でよく見落とされる。アニーリング時間を短くしても、同時にエネルギースケールを非現実的に大きくしていれば、計算資源を減らしたとは言えません。逆に、実機でアニーリング時間を長くしても、熱平衡化や制御誤差が支配的になれば、閉じた系の断熱定理だけでは説明できません。

4. stoquastic性と符号問題

横磁場Ising型QAが古典計算で比較的扱いやすい理由の一つが、stoquastic性です。計算基底 $\{|x⟩\}$ において、ハミルトニアンの非対角成分がすべて実数で非正であるとき、

$$⟨x|\hat{H}|x^{\prime }⟩\le 0(x\ne x^{\prime })$$

を満たします。このようなハミルトニアンを、その基底で stoquastic といいます。

標準的な横磁場

$${\hat{H}}_X=-\sum _i{\hat{X}}_i$$

は、計算基底で一つのビットを反転させる非対角成分を負に持ちます。問題ハミルトニアン ${\hat{H}}_Z$ は計算基底で対角なので、横磁場Ising型の標準形は stoquastic です。

stoquasticであることの重要性は、量子系を古典確率過程のように扱いやすくする点にあります。Suzuki--Trotter分解を使うと、分配関数

$$Z=\mathrm{Tr}{e}^{-\beta \hat{H}}$$

を、虚時間方向に並んだ古典スピンの和として表せます。非対角成分の符号がそろっていると、その重みを非負の確率重みとして解釈しやすいです。これが、シミュレーテッド量子アニーリングや経路積分量子モンテカルロが標準的な横磁場QAと相性がよい理由です。

ただし、ここで二つ注意があります。

第一に、stoquastic性は基底に依存します。ある基底では非対角成分が非正でも、別の基底ではそうでないことがあります。量子アニーリングでは、最後に計算基底でビット列を読むため、計算基底でのstoquastic性が自然に重視される。

第二に、stoquasticであることは「簡単である」ことと同義ではありません。符号問題が弱い、または消えることは、量子モンテカルロで扱いやすい可能性を高めます。しかし、混合時間、自己相関、狭いトンネル、一次相転移による小ギャップは別の問題として残ります。

non-stoquastic ハミルトニアンは、上のstoquastic条件を満たさない項を含みます。たとえば全結合の横方向相互作用

$${\hat{H}}_{XX}=\frac{\gamma }{N}{\left(\sum _i{\hat{X}}_i\right)}^2,\gamma >0$$

は、横磁場に対する反強磁性的な量子揺らぎとして働きます。p-spin模型では、この種の項が一次相転移を二次相転移に変え、最小ギャップの閉じ方を改善する例が知られています。したがって non-stoquastic 項は、単に「シミュレーションを難しくする項」ではなく、量子アニーリングの経路そのものを変える設計変数です。

一方で、non-stoquasticなら必ず速い、という定理はないです。符号問題を作ることと計算上の優位性を作ることは別です。p-spin模型の成功例は重要だが、一般の最適化問題でどのような触媒項が有効かは、まだ個別性の強い研究課題です。

5. 小ギャップはどこから来るか

断熱時間発展では、小ギャップが実行時間を支配します。典型的な目安として

$$t_f\gtrsim O\left({\mathrm{\Delta }}_{min}^{-2}\right)$$

を考えると、${\mathrm{\Delta }}_{min}$ が指数的に小さくなる場合には実行時間も指数的に大きくなります。

$${\mathrm{\Delta }}_{min}(N)\sim e^{-cN}⟹t_f\sim e^{2cN}.$$

多体系でこのような小ギャップを生む代表的な機構が、一次量子相転移です。p-spin模型では、横磁場を下げる途中で常磁性相と強磁性相が一次相転移的に入れ替わる。二つの状態は巨視的に異なるため、有限サイズでは避けられた交差になりますが、トンネル振幅は系サイズとともに指数的に小さくなります。

spike問題も、同じ直観を与えます。Hamming重みに依存するエネルギー地形の途中に狭い障壁を置くと、古典的にはその障壁を熱的に越える必要があります。一方、量子的にはトンネルで抜けられる可能性があります。ここだけを見ると量子の利点が見えやすいです。しかし、障壁の幅や高さを系サイズとともにどうスケールさせるかで話は大きく変わります。

摂動的な交差も重要です。アニーリングの終盤で横磁場が小さくなると、問題ハミルトニアンの低エネルギー局所解が摂動補正によって互いに近づき、真の基底状態と局所解が狭い避けられた交差を作ることがあります。Hamming距離の大きいビット列同士の結合は高次摂動になりやすいため、ギャップが指数的に小さくなります。

この話から分かるのは、「トンネルがあるから速い」とは言えないということです。トンネルが有利に働く例はありますが、巨視的に離れた状態の間のトンネル振幅は小さくなり得ます。また、エンタングルメントが生じていることも、それだけで速度向上の証拠にはなりません。小ギャップの機構を見ずに、量子らしさだけを見ても性能は判断できません。

6. 経路を設計する

小ギャップが危ないなら、まず考えるべきはスケジュールです。ギャップが大きいところは速く進み、ギャップが小さいところはゆっくり進みます。Grover探索の局所断熱スケジュールは、この考え方を最もきれいに示す例です。

局所断熱条件を目安として書けば、

$$\frac{ds}{dt}=ϵ\frac{\mathrm{\Delta }(s{)}^2}{|⟨{\epsilon }_1(s)|{\partial }_s\hat{H}(s)|{\epsilon }_0(s)⟩|}$$

のように、遷移しやすい場所で速度を落とします。Grover探索では、一定速度で進むと古典探索と同じ次数になりますが、局所断熱スケジュールを使うと $O(\sqrt{N})$ の時間で解に到達できます。

次に、ハミルトニアンの経路そのものを変える方法があります。代表例は触媒ハミルトニアンです。

$$\hat{H}(s)=(1-s){\hat{H}}_0+s{\hat{H}}_1+s(1-s){\hat{H}}_C.$$

${\hat{H}}_C$ は $s=0$ と $s=1$ で消えるので、初期状態と最終的に解きたい問題は変えないです。しかし途中のスペクトルは変わります。うまく選べば、一次相転移を避けたり、避けられた交差を広げたりできます。

ここで non-stoquastic 触媒が自然に出てきます。p-spin模型に反強磁性的な横方向相互作用を入れると、標準横磁場だけでは一次相転移だった経路が、二次相転移を通る経路へ変わる場合があります。これは、同じ最終問題でも、通る道を変えればギャップ構造が変わることを示しています。

ただし、経路設計には実用上の制限があります。触媒項が問題インスタンスの答えを知っていなければ作れないなら、それはアルゴリズムとして意味が薄いです。また、実機で実装できない多体相互作用を仮定すれば、理論上の改善がそのまま実験で使えるとは限らないです。経路設計は強力だが、解をこっそり入れないこと、物理的に実装可能であること、古典的にも同じ情報を使えるかを比べることが必要です。

7. 非断熱を敵にしない

断熱定理の立場では、励起状態への遷移は避けるべき誤差です。しかし有限時間の量子アニーリングでは、非断熱遷移を完全に消すことはできません。そこで発想を変えます。励起状態へ一時的に漏れても、最後に良い解へ戻ってくるなら、それは必ずしも失敗ではありません。

この考え方が diabatic quantum annealing です。狙いは、全時間で瞬時基底状態に張り付くことではなく、有用な低エネルギー部分空間の中に状態を保つことです。たとえば低エネルギー部分空間を

$$\mathcal{L}(s)=\mathrm{span}\{|{\epsilon }_0(s)⟩,|{\epsilon }_1(s)⟩,\dots ,|{\epsilon }_{d-1}(s)⟩\}$$

とおきます。この部分空間の内部では遷移してもよいが、外側の高エネルギー空間へ大きく漏れないようにします。すると、断熱条件で問題になる最小ギャップは、基底状態と第一励起状態のギャップだけではなく、低エネルギー帯と外側を分けるギャップとして読み替えられます。

Landau-Zener遷移の言葉で言えば、避けられた交差を一度通過して励起状態に乗り移り、後の交差でもう一度戻るような経路も考えられます。これは「断熱でないから悪い」という単純な分類から外れています。有限時間の振動や干渉を、探索の資源として使うのです。

成功確率が実行時間 $t_f$ に対して単調に増えるとは限らない点も、diabatic QAでは重要です。ある時間では干渉が良く働き、別の時間では悪く働きます。したがって、性能指標としては一回の成功確率だけでなく、目標成功確率に達するまでの総時間を考えます。

$$\mathrm{TTS}(t_f)=t_f\frac{\log (1-p_d)}{\log [1-p_S(t_f)]}.$$

$p_S(t_f)$ は一回の実行で成功する確率、$p_d$ は目標成功確率です。$\mathrm{TTS}$ は time to solution の略で、独立に試行を繰り返したとき、少なくとも一回成功するまでに必要な総時間を表します。実用的なQAでは、$t_f$ をただ長くするのではなく、この量を最小にするアニーリング時間を探すことが多いです。

この見方はQAOAともつながります。深さ $p$ のQAOAは

$$|{\psi }_p(\mathit{\gamma },\mathit{\beta })⟩=\prod _{k=1}^p{e}^{-i{\beta }_k{\hat{H}}_X}{e}^{-i{\gamma }_k{\hat{H}}_Z}|+{⟩}^{\otimes N}$$

で書けます。これは、横磁場ハミルトニアンと問題ハミルトニアンを交互にかける離散時間の量子ダイナミクスです。深さを大きくし、角度列を滑らかにすれば、連続時間の横磁場IsingダイナミクスのTrotter化として読めます。逆に、角度列が非単調になる場合は、単純な断熱スケジュールではなく、diabaticな経路探索に近づく。

8. 量子スピードアップをどう主張するか

量子アニーリングで「速い」と言うとき、何と比べているのかを明確にしなければなりません。比較対象を曖昧にすると、強い主張に見えても、実際には限られた範囲のベンチマークにすぎないことがあります。

強い順に並べると、まず provable quantum speedup があります。これは、古典アルゴリズム全般に対して、数学的に量子の優位性を証明するものです。一般の最適化問題では非常に難しいです。

次に strong quantum speedup があります。これは、同じ問題クラスに対する最良級の古典アルゴリズムと比べて速いことを示します。実験的にはここが最も厳しいです。

その下に limited quantum speedup があります。これは、特定の古典アルゴリズム、たとえばSAやSQAなど、明示した比較対象に対して速いことを示します。量子アニーリング実機の議論では、このレベルの主張が多いです。

この分類は、講義ノートの読み方にも関係します。QAがSAに勝ったとしても、それは最良の古典ヒューリスティックに勝ったことを意味しないです。QAがSQAに勝ったとしても、それが閉じた系の量子コヒーレンスによるのか、開放系の熱効果によるのか、実装上の違いによるのかは別に調べる必要があります。

一方で、limited speedupが無意味なわけではありません。明確な比較対象に対して、どの構造で、どのサイズ領域で、どのスケーリングが変わるのかを示すことは、物理を理解する上で価値があります。大事なのは、勝った相手を正確に書くことです。

9. 道具が一つにつながる

Landau-Zener遷移では、二準位系の避けられた交差を具体的に計算します。ゆっくり動かせば基底状態に残りやすく、速く動かせば励起状態へ漏れる。断熱計算の立場では、この漏れは抑えたい誤差です。しかしdiabatic QAの立場では、いったん励起状態へ上がり、別の交差で戻ってくる経路も使えます。非断熱遷移は、ただの失敗ではなく、設計対象になります。

QAの収束定理では、断熱定理とスケジュール条件を、探索が最後に正しい低エネルギー状態へ近づくための保証として読みます。そこで効いてくるのは、ギャップがどれだけ小さくなるか、ハミルトニアンをどれだけ速く動かしているか、瞬間基底状態からの距離をどう測るかです。民間公式としての断熱条件も、射影演算子で書く厳密な評価も、同じ問いを別の精度で見ています。

シミュレーテッドアニーリングでは、詳細釣り合い条件を満たす古典Markov連鎖を使い、温度を下げながら低エネルギー状態へ向かいます。stoquastic ハミルトニアンが量子モンテカルロに写りやすいという事実は、量子系と古典確率過程が思ったより近い場所にあることを教えてくれる。符号問題は、その近道が急に崩れる地点です。

適応的量子モンテカルロ法では、量子モンテカルロの重みを見ながら横磁場やサンプリングを調整します。stoquastic性、符号問題、non-stoquastic項の意味が分かっていると、何を近似していて、どこから先が本当に難しいのかが見えやすくなります。

p-spin模型、Hopfield模型、CD項、QAOAも同じ地図の上に置ける。p-spin模型は、一次相転移と小ギャップを最小限の式で見せる。Hopfield模型は、多数の記憶が作る複雑なエネルギー地形を見せる。CD項は、短い時間でも経路から外れないための補助輪です。QAOAは、連続時間のスケジュールを刻んだものとしても、diabaticな干渉を使う変分ダイナミクスとしても読めます。

10. 文献案内

量子アニーリングの歴史的な出発点として、横磁場を使う量子アニーリングは 文献 [1] に整理されています。断熱量子最適化としての初期の形は 文献 [2] が代表的です。

AQC全体の整理、断熱定理、stoquastic AQC、小ギャップ、触媒、非断熱利用のまとまった見取り図としては 文献 [7] が標準的です。局所断熱スケジュールによるGrover探索は 文献 [3] が基本文献です。

non-stoquastic触媒とp-spin模型については 文献 [5] が重要であり、その後の一般性や限界については 文献 [8] などで議論されています。一次相転移と指数的小ギャップについては 文献 [4] が典型例を与えます。

量子スピードアップの分類には 文献 [6] の用語がよく使われます。diabatic quantum annealingの見方については 文献 [9] が、QAOAや有限時間ダイナミクスとの接続も含めて整理しています。

参考文献: [1], [2], [3], [4], [5], [6], [7], [8], [9]。

参考文献

1. Tadashi Kadowaki, Hidetoshi Nishimori, “Quantum annealing in the transverse Ising model,” Physical Review E 58, 5355–5363 (1998). 出典

2. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, Daniel Preda, “A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem,” Science 292, 472–475 (2001). 出典

3. Jérémie Roland, Nicolas J. Cerf, “Quantum search by local adiabatic evolution,” Physical Review A 65, 042308 (2002). 出典

4. T. Jörg, F. Krzakala, J. Kurchan, A. C. Maggs, J. Pujos, “Energy gaps in quantum first-order mean-field–like transitions: The problems that quantum annealing cannot solve,” EPL (Europhysics Letters) 89, 40004 (2010). 出典

5. Yuya Seki, Hidetoshi Nishimori, “Quantum annealing with antiferromagnetic fluctuations,” Physical Review E 85, 051112 (2012). 出典

6. Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, et al., “Defining and detecting quantum speedup,” Science 345, 420–424 (2014). 出典

7. Tameem Albash, Daniel A. Lidar, “Adiabatic quantum computation,” Reviews of Modern Physics 90, 015002 (2018). 出典

8. Tameem Albash, “Role of nonstoquastic catalysts in quantum adiabatic optimization,” Physical Review A 99, 042334 (2019). 出典

9. E. J. Crosson, D. A. Lidar, “Prospects for quantum enhancement with diabatic quantum annealing,” Nature Reviews Physics 3, 466–489 (2021). 出典