量子アニーリングの解説

西森秀稔 (最終更新 2022/3/23)

全体像

最初の提案
量子アニーリングは、組み合わせ最適化問題を解くための汎用近似解法として開発された。1998年の門脇と西森の論文において現在広く使われている形で提案・定式化された。
意義と展開
多くの実用的に重要な問題が組み合わせ最適化問題として定式化できるので、その解法の研究は大きな社会的意義を持つ。また、確率分布を生成するサンプリングやある種の量子シミュレーションへの適用の研究も進んでいる。
開発の現状
D-Wave社が量子アニーリングを実現するデバイスを開発し、Google, NASA, ロッキードマーティン, ロスアラモス国立研究所、ユーリッヒ総合研究機構などが実機を導入している。また、多くの企業、大学、研究所がクラウドで使用している。高機能の量子アニーリング装置のプロトタイプを作成する国家プロジェクトがで進行している。
高速性
量子アニーリングが最適化問題を古典コンピュータより効率よく解けるのかについての一般的な理論はまだ確立していない。様々な具体例や近似理論、特定の条件下での理論などによる研究が進んでいる。下記の解説の最下部の古典コンピュータとの比較の項も参照。量子アニーリングに関する最近の論文リストはこちらこちら
基礎と応用
基礎研究と並行して、実社会の問題への応用の実証実験も活発に行われている。基礎と応用が同時進行しているのがこの分野の顕著な特徴である。
ゲート式、特性
極めて大規模かつ安定に動作するゲート模型の量子コンピュータが出来たとすれば、ある種の問題を古典コンピュータより指数関数的に高速に処理できるようになる。なお、古典コンピュータより指数関数的に速くなる計算課題で実用性を持つものはごく限られていることに注意が必要である。米国科学アカデミーの報告書は「量子コンピュータは、コプロセッサやアクセラレータに似た、古典プロセッサを補完する特殊用途デバイスとして設計されている。」と述べている。この点は、量子アニーリングでも同様である。

解説や動画

米国科学・工学・医学アカデミーによる量子コンピュータの進歩と展望 (西森秀稔訳) 共立出版
量子アニーリングの基礎(西森秀稔、大関真之著)共立出版
P. Hauke, H. G. Katzgraber, H. Nishimori, and W. D. Oliver, Rep. Prog. Phys. 83, 054401 (2020).
T. Albash and D. A. Lidar, Rev. Mod. Phys. 90, 015002 (2018)
E. K. Grant and T. S. Humble, Oxford Research Encyclopedia of Physics (2020)
京大MACSコロキウム講演の動画
D-WaveのEdward (Denny) Dahl 氏によるウェビナー

量子アニーリングの動作原理

概念

量子アニーリングは、量子効果を制御して、多変数1価関数(目的関数)の最小値を探す問題(組み合せ最適化問題)を解く手法である。 経路最適化、ポートフォリオ最適化、ジョブシフト最適化などを始めとする多くの重要な課題が組み合せ最適化問題として定式化できるため、最適化問題の効率的な解法は社会的に大きなインパクトを持つ。また、量子アニーリング装置を量子力学系のシミュレーションに使う動きもある。
量子アニーリングを実行するためには、まず目的関数を2値変数の関数(イジング模型)として表現し、その関数の最小値を求める問題として定式化しなければならない。その目的関数に量子効果を現す項を追加する。最初に量子項の係数を大きく取り、すべての許される解候補を同じ重みで重ね合わせた状態(下の図の左側)を実現する。そして、ゆっくりと量子項の係数を小さくしていく。このプロセスにより、容易に実現できる初期状態から出発して、自然な時間変化を経て、下の図の右側のように最適解を高い確率で実現することを目指す。



横軸は2値変数の組の取るいろいろな値の組(古典状態)、縦軸の黒の曲線は目的関数の値、青の線は各配位の存在確率を表す。
左の初期状態から始めて次第に変化していき、最後には右の最終状態に至る。

定式化

目的関数をイジング模型で表したら、それに横磁場を加えて量子ゆらぎによる解探索を行う。次のハミルトニアンで表現される。

σは2行2列の行列(パウリ行列)である。右辺第1項が量子ゆらぎを引き起こす横磁場項、第2項が通常の古典的イジング模型(最小化するべき目的関数)である。s は時間を表す変数で全計算時間を T 、途中の経過時間を t とすると s=t/T と定義される。A(s) は時間 s とともに有限値から0まで減少する関数、 同様にB(s) は0から有限値まで増加する関数である(右図)。最初は第1項(横磁場項)で大きな量子ゆらぎによりあらゆる可能性を重ね合わせて出発し、次第に目標とする目的関数(第2項)の重みを大きくしていき、最後に後者だけが残って最適解(イジング模型の基底状態)にたどり着く。

関連した計算手法

シミュレーテッド・アニーリング

確率的探索を用いて最適化問題を解くシミュレーテッド・アニーリングは、広く普及した汎用的な古典計算手法である。この論文 および この論文 によると、量子アニーリングはある種の問題に対してシミュレーテッド・アニーリングより効率がよい場合がある。こちらの論文も参照。

量子ゲート(量子回路)方式

量子ビットの組に量子ゲートを離散的に作用させて状態を望ましい方向に誘導して行く量子ゲート方式(量子回路モデル)に関しては膨大な研究の蓄積があるが、実機としての実現においては環境の影響による量子状態の破壊(デコヒーレンス)が深刻な問題である。デコヒーレンスの効果を修正する誤り訂正の技術を取り入れるとすると、実用に耐える量子コンピュータの構築には極めて多くの量子ビットの集積と精密な制御が必要であり、実現されるとしても非常に長い年月がかかると思われる。Googleを中心とするグループの論文では、特殊な乱数発生の課題に対して量子チップが古典コンピュータのシミュレーションをしのぐ結果を出して「量子超越性」を達成したとしているが、同じグループが、より実用に近い問題の解決までには多くの課題があることを指摘している。さらに、中国のグループが古典コンピュータ(スーパーコンピュータ)でGoogleの量子チップとほぼ同じ時間で彼らの結果をシミュレートできたと報告して Gordon-Bell賞を受賞し、「量子超越性」達成の行方は不透明となっている。

量子ゲート方式による本質的な高速化が何らかの形で保証されているアルゴリズムは実用性を持つものとしては、素因数分解、量子シミュレーション、線形代数の一部の演算などがある。極めて大規模で安定に動作する量子ゲート方式の量子コンピュータが将来できたとすると、これら特定の計算が高速処理できる。ただし、大規模な古典データを処理する場合には、それを量子コンピュータにどうやって乗せるかがボトルネックとなっている

近い将来における実現可能性が期待されているノイズあり中規模量子(NISQ)コンピュータでは、古典コンピュータとの組み合わせ(ハイブリッド)によって組み合わせ最適化問題や量子化学計算が実行できると考えられている。ただし、この論文この論文によると、現状ではノイズの影響が大きいため実用的な応用には距離がある。NISQによる量子・古典ハイブリッド計算で高速化が達成されるかどうかはまだ不明である。

  量子ゲート方式(回路モデル) 量子アニーリング
強み 指数関数的な高速化が保証されているアルゴリズムがいくつかある。誤り訂正方式が確立している。 最適化問題は実社会での応用範囲が広い。ノイズに比較的強い。
弱み ノイズに弱い。大規模な問題を解くためには極めて多くの安定な量子ビットが必要。 指数関数的な高速化が理論的に保証されている実用的な問題が見つかっていない。誤り訂正方式が未確立。

通常のコンピュータ(古典コンピュータ)との関係

量子アニーリングの目的は最適化問題、サンプリング、および量子シミュレーションであり、広く普及している通常のコンピュータの多くの機能を置き換えるものではない。後者の点に関しては量子ゲート方式でも同様である。

量子アニーリングが古典的なシミュレーテッド・アニーリングや量子アニーリングの古典シミュレーション(量子モンテカルロ法)、あるいはその他の古典アルゴリズムを凌駕できるかという点に対しては、ある種の課題(例えばこの論文この論文)では前向きの結果が出ているが、実用性を持つ課題ではそのような例は見つかっていない。なお、励起状態非疑似古典効果を適切に利用すればゲート模型と等価になることも知られている。