量子アニーリングと断熱量子計算の基本的な論文のまとめ

はじめに

量子アニーリング（Quantum Annealing）は、量子ゆらぎを利用して組み合わせ最適化問題の近似解を求めるヒューリスティックなアルゴリズムです。一方、断熱量子計算（Adiabatic Quantum Computation）は量子計算のモデルの1つで、基底状態からスタートする断熱時間発展を利用しています。量子アニーリングと断熱量子計算は、断熱時間発展を利用するという点で類似していますが異なるものです¹。本記事では量子アニーリングと断熱量子計算の基本的な理論の論文についてまとめます。本記事では基礎理論に焦点を当て、D-Waveのマシンを使った研究や量子アニーリングの応用については触れません。

レビュー論文

今までの量子アニーリングや断熱量子計算の研究成果を整理したレビュー論文が複数出版されています。

比較的最新の研究成果を含め網羅的にまとめたレビュー論文が、2018年のAlbashとLidarによる次の論文です。

• Tameem Albash and Daniel A. Lidar, “Adiabatic quantum computation” Rev. Mod. Phys. 90, 015002 (2018)
  , arXiv:1611.04471

このレビューでは主に断熱量子計算と、外界からのノイズがない孤立した系での理想的な量子アニーリングについてまとめられてます。定性的な説明よりも、数学的に厳密な定理等がよくまとめられています。外界との相互作用がある開放系での量子アニーリングに関する研究については、他のレビューが出る予定です。

上記の論文の出版より10年前、量子アニーリングが今ほどバズっていなかった時代のレビューもあります。

• Arnab Das and Bikas K. Chakrabarti, “Colloquium: Quantum annealing and analog quantum computation.” Rev. Mod. Phys. 80 1061 (2008), arXiv:0801.2193

基本的には、AlbashとLidarのレビューを読めば良いと思います。

量子アニーリング・断熱量子計算の提案

まず研究の源流となった論文について紹介します。

問題ハミルトニアンとしてIsing模型を、量子ゆらぎ項として横磁場を利用した形の量子アニーリングが提案されたのは、上のレビューからさらに10年昔の1998年のことです。提案者は現在DENSOにいる門脇さんと東工大の西森先生です。

• Tadashi Kadowaki and Hidetoshi Nishimori, "Quantum annealing in the transverse Ising model." Phys. Rev. E 58, 5355 (1998), arXiv:9804280

この論文では、シュレディンガーダイナミクスを利用した横磁場イジング模型による量子アニーリングと、温度を徐々に下げていく通常のシミュレーテッド・アニーリングの比較を行っています。少数スピンの系での数値計算による研究です。この時点では「断熱的」という考えや量子アルゴリズムという認識はなかったように思えます。

量子効果（トンネル効果）を利用してスピングラス模型の最小エネルギー状態を求めるというアイデア自体は、門脇・西森以前にも提案されています。例えば次の論文があります。

• P. Ray, B. K. Chakrabarti, and Arunava Chakrabarti, "Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations." Phys. Rev. B 39 11828

また、量子アニーリングという言葉自体も門脇・西森以前の論文で使われています。

• A. B. Finnila, et al. "Quantum annealing: a new method for minimizing multidimensional functions." Chemical physics letters 219, 5 (1994)

一方、断熱量子計算はアメリカのEdward Farhiらにより2000年に提案されました。

• E. Farhi, et al. "Quantum computation by adiabatic evolution." arXiv preprint quant-ph/0001106 (2000)
• E. Farhi, et al. "A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem." Science 292, 5516 (2001), arXiv:quant-ph/0104129

ただし、この時点では万能量子計算が可能であることは示されておらず、組合せ最適化問題を解くという量子アニーリングの研究とほぼ同じことが行われていました。その新規性は量子アルゴリズムとしてプレゼンテーションをした部分と断熱定理を用いて解析をした部分です。

断熱定理

基底状態からスタートしたあとに無限に長い時間をかけて横磁場を減少させれば、最終的なハミルトニアンの基底状態を見つけることができます。これを保証している数学的な定理が「断熱定理」です。名前に断熱とついていますが熱力学の熱とは関係なく、非常にゆっくり（準静的）であること指しています。断熱定理自体は、量子力学の黎明期に発見されいます。この断熱定理を拡張して、量子アニーリングや断熱量子計算において最終的に得られる結果のエラーを厳密に評価したのが次の論文です。

S. Jansen, M. B. Ruskai, and R. Seiler "Bounds for the adiabatic approximation with applications to quantum computation." J. Math. Phys. 48, 102111 (2007), arXiv:quant-ph/0603175

断熱量子計算

断熱量子計算と量子回路モデルとの等価性（万能性）の証明

Farhiが断熱量子計算を提案した時点では、断熱量子計算が通常の量子計算（量子回路）と等価であるかどうか、つまり断熱量子計算により量子回路による計算を多項式時間のオーバーヘッドでシミュレーションできるかはわかっていませんでした。この等価性は後にDorit Aharonov（Aharonov–Bohm効果のAharonovの姪）らによって示されました。

• D. Aharonov, et al. "Adiabatic quantum computation is equivalent to standard quantum computation." SIAM review 37 1 (2007), arXiv:quant-ph/0405098

この論文以降にも、証明を改良しより簡単な相互作用のハミルトニアンでの断熱量子計算の万能性を示した論文がいくつかでています。

• A. Mizel, D. A. Lidar, M. Mitchell "Simple proof of equivalence between adiabatic quantum computation and the circuit model." Phys. Rev. Lett. 99.7 (2007), arXiv:0609067

ここらへんの詳しい話はAlbash-Lidarのレビューに書いてあります。

断熱量子計算のアルゴリズム

探索アルゴリズム

探索問題については、断熱量子計算でも通常の量子計算（Groverアルゴリズム）と同様にO(√N)の計算量で実行することができます。それを初めて示したのが次の論文です。

• J. Roland and N. J. Cerf "Quantum search by local adiabatic evolution" Phys. Rev. A 65.4 (2002), arXiv:quant-ph/0107015

この論文では、ハミルトニアンを変化させるときに局所的な断熱条件を満たすようにすることで、Groverアルゴリズムと同等の計算量が実現されることを示しています。

一方、横磁場を使った量子アニーリングでは、O(√N)の計算量で実行することは不可能だと考えられています。

素因数分解

量子回路との等価性を使うことで、素因数分解のShorのアルゴリズムを断熱量子計算で実行することができます。しかし、その手順は複雑なものとなります。現在、素因数分解を多項式時間で実行する実用的な断熱量子計算のアルゴリズムまたは量子アニーリングの手法は見つかっていません。

Stoquastic

Stoquasticハミルトニアンに限定した量子断熱計算（StoqAQC）における量子超越性を示したのが以下の論文です。

• M. B. Hastings, "The Power of Adiabatic Quantum Computation with No Sign Problem" arXiv:2005.03791

量子アニーリング

数値計算

量子アニーリングについては量子モンテカルロなどの手法を使った数値計算の研究が数多く行われています。特に横磁場を変化させたときの基底状態の相転移に着目した研究が多くあります。その代表的な論文を列挙しておきます。

• A. P. Young, S. Knysh, and V. N. Smelyanskiy, "First-Order Phase Transition in the Quantum Adiabatic Algorithm" Phys. Rev. Lett. 104, 020502 (2010), arXiv:0910.1378
• Bettina Heim, Troels F. Rønnow, Sergei V. Isakov, Matthias Troyer, "Quantum versus classical annealing of Ising spin glasses" Science 348.6231 (2015), arXiv:1411.5693

実験

量子アニーリングを実験で初めて実現したのが次の論文です。

• J. Brooke, et al. "Quantum annealing of a disordered magnet." Science 284, 779 (1999), arXiv:cond-mat/0105238

D-Waveによるマシンについての初めての論文が出たのは2011年です。

• M. H. Johnson, et al. "Quantum annealing with manufactured spins." Nature 473 7346 (2011)

あとがき

将来的には、量子アニーリングとシミュレーテッド・アニーリングの性能の比較についての研究や、D-Waveのマシンのベンチマークの研究についてもまとめていきたいです。

1. 断熱量子計算と量子アニーリングという2つ言葉の使い分けについては、学術論文でも明確にはなっていません。ただし、大まかには以下のように区別されていると思っています。断熱量子計算といった場合には、断熱時間発展を利用した万能な量子計算を指していると考えます。したがって、計算能力の面では量子回路計算と同等であり、両者を区別する必要はありません。使用するハミルトニアンを限定した断熱量子計算は、万能量子計算になるとは限らないので、具体的にどのような計算能力があるのかを明記する必要があります。例えば、横磁場Isingのハミルトニアンだけを使用した断熱量子計算（TFIM-AQC）は万能量子計算にならないことが知られています。一方、量子アニーリングは、Ising模型（QUBOと等価）に横磁場をかけて、その横磁場を変化させることで基底状態を求める限定的な手法のことを指します。もう少し広い意味での量子アニーリングは、なんらかのコスト関数に横磁場のような量子ゆらぎの項を導入して、量子ゆらぎを小さくしていくことでコスト関数の最小値を求めるヒューリスティックを指します。 ↩