量子コンピュータの仕組みをエクセルで理解してみよう ～量子アニーリングの古典版「シミュレーテッドアニーリング」の実装～

ITエンジニアのための量子コンピュータ入門 第2回

解き方の概要

　さて、SAによる解き方の説明に入りましょう。SAには、3つの重要な物理量（変数）が出てきます。「スピンS」と「スピン間の相互作用J」、そして「エネルギーE」です。この「スピン間の相互作用J」をうまく満たすような「スピンS」の組み合わせを、「エネルギーE」が最小になるように求めるというのが、基本的なアルゴリズムの目的となります。

　そもそも今回のSAでは、何を“アニーリング”するかというと、イジングモデルと呼ばれる金属原子の単純なモデルをアニーリングします。このモデルでは、金属原子が規則正しく格子状に並んでいるとし、原子一つ一つがスピンと呼ばれる量を持ちます。スピンは上向きと下向きの2種類が存在し、それぞれS＝＋1、S＝－1とします。今回のエクセルでは、各セルが原子1つに対応しており、スピンの量を色で表しています。

　隣り合うスピンには、スピン間相互作用が決められています。相互作用とは、隣どうしのスピンが「同じ方向にいたがる」か「反転していたがる」か、を決めるパラメータです。「同じ方向にいたがる」場合は相互作用Jを、J＝＋1と設定し、「反転していたがる」場合はJ＝－1と設定します。

　この相互作用こそが解きたい問題の“入力（引数）”に対応しており、「Bond_h」および「Bond_v」ワークシートに表示されています。「Answer」ワークシートの正解から、それに対応する各セルの横方向の差と縦方向の差をそれぞれ「Bond_h」および「Bond_v」ワークシートにて、差が0の場合は相互作用が＋1、差が±1の場合は相互作用－1となるよう「差の絶対値×－2＋1」が計算されています。つまり隣り合うスピンが同じ向きのとき＋1、反転のとき－1となります。

　SAでは、このスピンの＋1と－1の最適な組み合わせを、スピン1つずつを反転させていきながら探索していきます。一方、量子アニーリングでは、このスピンを上向き（＋1）と下向き（－1）の重ね合わせ状態として物理的に用意し、量子力学的な効果を使って高速に探索することになります。

シミュレーテッドアニーリングのイメージ

量子アニーリングのイメージ

　次に、エネルギーの計算方法です。SAの最終ゴールは全体のエネルギーが最も小さくなるように、各スピンの組み合わせを決定することです。エネルギーEの計算は、

　という式を使います。S_iは注目するスピン、S_jはその周りの隣接するスピンを表し、共に±1のどちらかの値です。J_ijはスピン間相互作用でこれも±1のどちらかの値となります。エネルギーはこれらの積を隣り合うすべてのスピンで計算して和をとり、マイナスをつけたものと言うことになります。式を見ると確かに、J_ij=+1のときは隣り合うスピンが同じ向きのときEは最小に、J_ij=－1のときは隣り合うスピンが反転しているときEが最小になることが分かり、スピン間の相互作用を正しく満たしている時にエネルギーが小さくなっていることが確認できます。

シミュレーテッドアニーリングで扱う物理量