量子アニーリング方式は、組合せ最適化問題に特化した量子アルゴリズムの一つです。量子ゲート方式に比べればシンプルに実現できるため、比較的多くの量子ビットで量子コンピュータを実現することに成功しています（2017/07現在、2048 qubit）。
ここでは、組合せ最適化問題を紹介した後、量子アニーリングの概要を解説します。物理的な原理やアルゴリズムの詳細は、量子アニーリングの原理とイジング模型 にて解説します。
組合せ最適化問題 #
組合せ最適化問題は、多数の選択肢がある中で、最も良い組合せを選ぶ問題です。日常的には、乗換案内のような出発地と目的地とを結ぶ「最適」な経路の探索が挙げられます。 何をもって「最適」というかは、乗換案内であれば最短時間で到着できることや交通費を安くすることなど目的によって変わってきます。もちろん交通機関であれば電車や飛行機などの出発時間や運行区間等々の制約を受けますが、その制約下でもっとも良い組合せを決定したいわけです。
組合せ最適化問題は全ての組合せを調べれば良いので計算方法としては単純です。ですが、効率的なアルゴリズムが見つからない場合、原理的には全ての可能性を列挙する必要があり、問題の規模や複雑性に対し爆発的に組合せの数が増えていきます。
例: 巡回セールスマン問題 #
少し具体的に考えるために「巡回セールスマン問題」という組合せ最適化問題の一つを考えます。
巡回セールスマン問題とは、セールスマンが複数の都市をそれぞれ1回だけ訪問する最短距離を求めるような問題です。都市の数を \(n\) とし、都市 \(i\) と \(j\) 間の距離を \(c_{ij}\) とすると、 全ての都市を1回だけ訪問するときの距離 (コスト関数や目的関数、エネルギー関数と呼ばれます)
\[ C = \sum_{i \ne j}c_{ij}x_{ij} \]が最小となる \(x_{ij}\) の組合せを求めることになります。ここで、 \(x_{ij}\) は、都市 \(i\) から \(j\) に移動する場合は1、そうでない場合は0となります。巡回セールスマン問題に限らず、組合せ最適化問題では、目的関数を定義しその最小値を探索します。
さて、 \(n\) 都市を回る回り方は \(n!\) 通りありますが、 \(n\) を10,20,30としたときの \(n!\) の値は以下のようになります。
- 10都市： \(3628800\)
- 20都市： \(2.4 \times 10^{18}\)
- 30都市： \(2.7 \times 10^{32}\)
もし、1つの組合せに対して距離を限りなく短い時間で計算できたとしても、都市の数が多くなって行くに従いすべての組合せの距離を計算するには不可能になってしまいます。
上のGoogle Mapの例は、品川区役所から出発してその他都内の 8 つの区役所を回るルートを描いたものです。最短距離となる自動車ルートの候補は \(8! = 40320\) 通りあります。Google Map では経由地の順序を簡単に変えられるので、93 km の候補より短いルートが有るか探してみてると大変さがわかると思います。
組合せ爆発 #
一般に、変数の数 \(n\) に対して、 \(n\) の多項式オーダーで解ける問題は効率的な最適化アルゴリズムが知られている問題とされています。一方で、巡回セールスマン問題のように指数関数以上のオーダー (例えば \(2^n\) ) で解の数え上げや最適解を探索する必要がある問題は、たとえ解があることがわかっていても現実的な計算時間や計算資源では解くことができない可能性があります。
組合せの数が爆発的に増えていく実例と、効率的なアルゴリズムを構築する大切さを伝える例として下記の動画が興味深いです。
メディアラボ第11期展示「フカシギの数え方」｜日本科学未来館 常設展示
この動画の数え上げの問題には効率的なアルゴリズムが知られていますが、難しい問題 (NP 困難に分類される問題) を厳密に解くためには、指数関数的な計算時間がかかってしまいます。そのような難しい問題に対しては最適解に近い解を近似的に求めるヒューリスティックなアルゴリズムが用いられることがあります。
量子アニーリング #
量子アニーリングとは、量子効果（重ね合わせの原理など）を利用したメタヒューリスティックな最適化手法です。通常のコンピュータによる近似解法と比較して、より高速に最適解に近い解が得られると考えられています。
シミュレーテッドアニーリング #
量子アニーリングという言葉は焼きなまし法 (シミュレーテッドアニーリング) のアナロジーから来ています。焼きなまし法では、最適解の探索のために組合せを変化させていく過程で、必ずしもコスト関数が小さくならなくてもある確率で次の状態として選択します。この時、どの程度コスト(エネルギー)の低下を重要視するかを「温度」というパラメータで制御します。高い温度の場合には目まぐるしく組合せを変化させるのに対し、低い温度の場合にはエネルギーの低い方向にしか変化しなくなります。高温から低温に徐々に変化させることで局所解での凍結を回避し最適解を探索します。
量子アニーリング #
量子アニーリングでは「温度」の代わりに「量子効果」を変化させます。量子効果が非常に強い状況では、すべての組み回せ状態の重ね合わせになっています。つまりこの時に測定を行うと全状態が等しい確率で出力されます。量子効果が強いほど各状態の間でトンネル効果による状態遷移が起きますが、そこから量子効果を小さくすることで状態が動かなくなります。定性的にはシミュレーテッドアニーリングの様子とよく似ています。まさに温度アニーリングの量子版なので量子アニーリングと呼ばれます。
下図に量子アニーリングのイメージを示します。量子効果が強い状況では状態空間に対する量子力学的エネルギーの分布は単純な形状となり、量子効果が弱くなるとともに目的関数の形状に変化していきます。アニーリング開始から終了まで量子状態が最もエネルギーの低い基底状態に留まる限り、終時刻においては目的関数が最小となる量子ビット状態の測定確率が最大化されます。数値シミュレーションによる実際の様子はこちらでも紹介しています。
アニーリングと統計物理学 #
ここでは最小化したい関数のことをエネルギーと呼びました。なぜ物理の言葉であるエネルギーを最小化するという話になったのかというと、実は上で挙げた2つのアニーリングアルゴリズムは両者とも統計物理学の理論をベースに考案されたからです。
統計物理学は複数の状態を取りうる多数の粒子の性質を解明することを目的としています。対象の粒子は互いに相互作用をすることで、粒子の状態の組合せにより全体としてエネルギーという物理量が計算されます。温度が与えられると全体のエネルギーがある分布になるように要請されます。特に重要なのは温度がゼロのときです。温度ゼロでは全体としてエネルギーが最も低い状態になります。粒子は全体としてエネルギーが最小になる組合せを選びます。
例えば金属を高温にすると原子は乱雑に動き回り、低温では動かなくなります。原子は規則的な格子構造の位置に落ち着くとエネルギーが低くなります。しかし高温状態にある金属を急速に冷却すると、原子は安定な格子構造を作る前に動きが止まってしまいます。そのような金属はもろく加工にも適しません。そこで金属を高温から低温に徐々に冷却し、低温において全体のエネルギーが小さい状態になるように促します。これを焼きなまし(アニーリング)と呼びます。
焼き鈍しの過程をシミュレーションで行った場合、シミュレーテッドアニーリングと呼ばれます。ここで情報科学と統計物理の類似性を導入してみます。統計物理の粒子の状態を情報科学のビットやデータの組合せだと考えると、低温で最小化されるエネルギーはコスト関数・目的関数が対応します。シミュレーテッドアニーリングにおいて、粒子の状態の変化をビットや変数の組合わせの変化で置き換え、エネルギー計算をコスト関数の計算に置き換えると、低温において低エネルギー状態=低コスト状態が実現されます。自然を記述するための物理が汎用アルゴリズムに応用されたわけです。
量子アニーリングのプログラミング #
シミュレーテッドアニーリングでは、自然界にある物質の性質をモデル化した統計物理のシミュレーションをベースにしていました。統計物理のシミュレーションで扱われるモデルの一つとしてイジング模型というのがあります。磁石の性質を表したシンプルな模型です。この模型では粒子の取り得る状態として \(+1\) (上向き) と \(-1\) (下向き) という二種類あり、単独で上向きまたは下向きをとりたがるパラメータと、隣り合う粒子同士が同じ方向 \(({+1,+1},{-1,-1})\) または正反対の方向 \(({+1,-1},{-1,+1})\) をとりたがるというパラメータを持ちます。元々はこのような模型の性質を知りたかったのですが、これを解きたい問題に置き換えて最適化アルゴリズムとして利用したのがシミュレーテッドアニーリングでした。
量子コンピュータを使った量子アニーリングは解きたい問題をイジング模型で置き換える必要があります。なぜなら、実は量子アニーリングの量子ビットはイジング模型で記述されるからです。量子コンピュータに解きたい問題を入力する場合、問題に対応したイジング模型のパラメータを入力することになります。これは量子コンピュータに直接的に与えられるパラメータで、量子ビットは与えられたパラメータと量子効果の外的操作により状態が変化します。理想的な量子コンピュータでは、量子ビットは温度ゼロの量子力学に従い変化するため、計算結果は自然に得られることになります。ある種の自然計算(ナチュラルコンピューティング)になっているともいえます。
量子アニーリングを実行するためには、解きたい問題をイジング模型に変換する必要があります。ある程度は機械的に行うこともできますが、量子コンピュータのリソースや制約を踏まえて適切な変換を実行することがソフトウェアエンジニアの仕事です。