量子アニーリング

最適化を「基底状態探し」に置き換える

量子アニーリング（Quantum Annealing, QA）は、組合せ最適化問題を物理系の基底状態探索として解く計算方式です。巡回セールスマンやジョブスケジューリングのように「膨大な組合せから最小コストの1つを選ぶ」問題は候補数が指数的に爆発し総当たりが破綻します。QA はこの探索を、最適解がエネルギー最小状態（基底状態）に一致する物理系を作り、それを最低エネルギーへ緩和させる問題に置き換えます。

古典の模擬アニーリング（シミュレーテッドアニーリング）が熱ゆらぎで谷を乗り越えるのに対し、QA は**量子ゆらぎ（トンネル効果）**でエネルギー障壁を「すり抜け」ます。狭く高い障壁では熱より量子トンネルが有利になり得る——これが期待される優位の核ですが、常に成り立つわけではありません。

断熱定理：ゆっくり変えれば基底状態に留まる

QA の理論的な土台は、量子力学の**断熱定理（adiabatic theorem）**です。主張はシンプルです。

これを計算に使うには、時間依存ハミルトニアン H(s) を初期から終端へ補間します。所要時間 T に対し s = t/T（0 から 1）で進行度を表します。

H(s) = (1 - s) · H_init  +  s · H_problem      （s = 0 → 1）

  H_init    : 基底状態が自明で、簡単に用意できる初期ハミルトニアン
  H_problem : 基底状態が「解きたい問題の最適解」になる終端ハミルトニアン

s = 0 で系を H_init の基底状態に初期化し、s を 0 → 1 へ動かします。断熱定理が守られる限り系は常に H(s) の基底状態に居続け、s = 1 で H_problem の基底状態＝最適解が得られます。最後に全量子ビットを測定すれば各変数の値（解）が読めます。実機の H_init は全ビットへの一様な横磁場で、その基底状態は全候補が等確率で重なった状態として確実に用意できます。進行につれ横磁場を弱め、問題を符号化した縦方向の相互作用を強めます。

速度の限界：最小ギャップが所要時間を支配する

「十分ゆっくり」がどれくらいかが QA の性能と限界を決める急所です。断熱定理の定量版は、必要な所要時間 T をエネルギーギャップの最小値 g_min で与えます。

T  ≳  1 / g_min²        （おおまかなスケーリング）

  g_min : アニーリング全体（s = 0..1）を通じた
          基底状態と第一励起状態のエネルギー差の最小値

途中でギャップが小さいほど、そこを安全に通過するのに長い時間が要ります。所要時間は最小ギャップの2乗の逆数でスケールするため、ギャップ縮小は計算時間に直結します。

断熱条件を破って速く走らせると、系は基底状態から第一励起状態へ飛び移る（ランダウ・ツェナー遷移）確率が上がり、得られる解は最適解より高コストな近似解になります。実機の QA は有限温度・ノイズ下で動くため、多くの場合こうした近似解を高速にサンプリングするヒューリスティックとして機能します。

イジングモデルへの写像

QA が扱えるのは、終端ハミルトニアン H_problem をイジングモデルの形に落とせる問題です。イジングモデルは磁性の物理モデルで、各サイトに +1／-1 の2値スピン s_i を置き、スピン間の相互作用と外部磁場でエネルギーを定めます。

イジングのエネルギー（ハミルトニアン）:

  E(s) = Σ_i  h_i · s_i        +    Σ_(i<j)  J_ij · s_i · s_j
         ├─ 各スピンへの縦磁場 ─┤    ├─ スピン対の結合 ─┤

  s_i ∈ {-1, +1}
  h_i  : サイト i にかかる磁場の強さ（1次の係数）
  J_ij : サイト i と j の結合の強さ（2次の係数）

h_i と J_ij を適切に設定すると、このエネルギーが最小になるスピン配置が問題の最適解に一致するよう「問題を符号化」できます。実機はこの H_problem を、各量子ビットへの縦磁場と量子ビット対の結合として物理的に実現します。

計算機科学では同じ問題を、0／1 の2値変数を使う QUBO（Quadratic Unconstrained Binary Optimization、制約なし2次2値最適化）で書くのが一般的です。QUBO とイジングは s_i = 2·x_i - 1 の線形変換で相互に等価変換できます。

QUBO:  minimize  Σ_i Q_ii · x_i  +  Σ_(i<j) Q_ij · x_i · x_j       （x_i ∈ {0, 1}）

  ・x_i·x_i = x_i （0/1 では 2乗が元に戻る）なので1次項も行列 Q に畳み込める
  ・s_i = 2·x_i - 1 を代入すればイジング形に、逆も可

グラフ分割・最大カット・集合被覆・彩色など多くのNP困難問題がイジング／QUBO形に定式化でき、これが QA の適用範囲を規定します。QA は「イジング基底状態ソルバー」であり、解く第一歩は適切な QUBO 定式化に尽きます。

埋め込み（マイナーエンベディング）という現実の壁

理論上の J_ij はどの2変数間にも結合を張れますが、実機の量子ビットは限られたグラフ構造でしか隣接結合を持ちません（超伝導 QA チップの Pegasus／Zephyr 格子など）。論理変数どうしの任意結合をこの疎な物理グラフ上で表す手続きが**マイナーエンベディング（minor embedding）**です。

埋め込みの考え方:

  論理変数 1個   →   物理量子ビット複数個を「鎖（chain）」として束ね、
                     強い結合で同じ値になるよう縛って1つの変数を代表させる

  ・全対全に近い結合が要る問題ほど、長い鎖が必要 → 使える物理ビット数の割に
    扱える論理変数が大きく目減りする
  ・鎖内の結合（chain strength）が弱いと鎖が「ちぎれ」て別々の値を取り、
    無効な解になる。強すぎると本来の問題のエネルギー差が埋もれる

ゲート式量子計算との違い

QA とゲート式（回路モデル）は「量子を使う」点は同じでも、計算モデルとしては明確に別物です。

重要な理論的事実として、断熱量子計算（AQC）はゲート式と計算能力が等価であることが証明されています（互いに多項式時間で変換可能）。原理的には AQC でもゲート式と同じ問題クラスが解けます。しかし実機 QA は、(1) 横磁場型の限られたハミルトニアンしか使わない、(2) 有限温度・ノイズ下で断熱を厳密には守れない、(3) 標準的な誤り訂正が未確立、という制約から、汎用計算ではなく最適化ヒューリスティックとして運用されるのが実情です。

まとめ

• QA は組合せ最適化をイジングモデルの基底状態探索に写像し、量子ゆらぎ（トンネル効果）で最適解へ緩和させる特化型方式。ゲート式のような汎用アルゴリズムは組めない。
• 土台は断熱定理。横磁場型の初期ハミルトニアンから問題ハミルトニアンへ十分ゆっくり時間発展させれば基底状態に留まり終端で最適解が出る。所要時間は最小ギャップ g_min の2乗の逆数でスケールし、ギャップが指数的に潰れる難問では断熱を守れない。
• 問題は QUBO（0/1の2次式）／イジング（±1スピン）に定式化し、制約はペナルティ項で表す。直接扱えるのは2次までで、高次項は補助変数で落とす。実機ではマイナーエンベディング（鎖の長さと鎖強度）が規模と解の質を左右する最大のボトルネック。
• 断熱量子計算はゲート式と計算能力は等価だが、実機 QA はノイズ・有限温度・誤り訂正未成熟ゆえ実質は近似解サンプラー。古典への普遍的速度優位は未確立で、採用時は古典ソルバーとの実測比較が必須、が実務上の結論。