巡回セールスマン問題をIsing模型で表現する

巡回セールスマン問題の表現

巡回セールスマン問題をIsing模型で表現する1つのやり方は、都市の数だけの行数と列数の格子点を作り、1行目はスタートする都市番号、2行目は2番目に訪れる都市番号、3行目は3番目に訪れる都市番号……と表現する。

そして、1行目のスタートする都市番号の格子点のスピンを1にして、1行目のその他の格子点のスピンは0にする。これでスタート都市番号が表現できた。次に2行目は2番目に訪れる都市番号に対応する格子点のスピンを1にする。そして、2行目のその他の格子点のスピンは0にする。このようにして、次の行も同様にセットしていけば、TSPの1つの経路が表現できることになる。

次の表.1は、1番目の行の交点2が1になっているので、都市2がスタート点であることを表している。そして、2番目の行は交点1が1になっているので、2番目の訪問場所は都市1であることを示している。

さらに、3番目の行は交点3が1であるので、3番目の訪問場所は都市3、4番目の行は交点4が1であるので、4番目の訪問場所は都市4、同様に、5番目の行は交点5が1であり、訪問場所は都市5であることを表している。したがって、表.1に表現されているのは、都市2→都市1→都市3→都市4→都市5、そして最後に→都市2に戻るという経路となっている。

• 表.1 5都市の経路の例

この例に示すように、TSPを表現するには訪問する都市数をNとすると、N²のスピン(量子ビット、あるいはCMOSアニーラのビット)が必要になる。また、合計の距離を計算するにはこれら全部のスピンの状態を見る必要がある。

富士通のDigital Annealerはすべての(スピンを記憶する)ビットがすべての他のビットにつながっているフルコネクトというトポロジになっているので問題ないのであるが、D-Waveの量子アニーラや日立のCMOSアニーラは、2次元のLSI表面にビットを配置し、物理的にある程度隣接したビットだけに接続されているという構造になっており、それ以外のビットの状態をみることはできないという作りになっている。仮に4個の隣接ビットにしかつながっていない構成では、6個のビットが接続されているケースは実現できない。しかし、次の図のように、2つビットを中継に使い、各ビットに3つずつ接続すれば、6個のビットに接続することができる。そして、2つの中継ビットを繋いで、接続の重みの大きさを適切に設定してやれば、等価的に6入力のビットを作ることができる。

• 4入力しか無いビットを2個使って6入力のビットを作る。破線で囲んだ2個のビットの結合を調整して、1つの6入力ビットのように振舞うようにする

しかし、そのような中継ビットが必要になるし、位置が離れている場合は何個もの中継ビットを直列につなぐ必要があり必要なビット数が増える。

フィックスターズの技術者有志が運営するWebサイト「Quantum Computing Information Site」の記述によれば、D-Waveの2000Qは2000Qubitを持つマシンであるが、TSPのネットワークを組むためにフルコネクトができるようにすると、使えるQubitの数は64個で、最大8都市のTSPしか扱えないそうである。ただし、この数は現在のコンパイラでの値で、将来、コンパイラが賢くなると増える可能性はある。

以下の導出は、Quantum Computing Information Siteのものを使わせていただいている。

このように、都市2→都市1→都市3→都市4→都市5→都市2の経路で移動した場合、その総移動距離は、距離(都市2、都市1)＋距離(都市1、都市3)＋距離(都市3、都市4)＋距離(都市4、都市5)＋距離(都市5、都市2)となる。

これを数式で書くと

となる。

ここで、Lは経路全体の長さ、d_i,jは都市iと都市jの間の距離、nは表.1の各マス目のスピンの数字(0か1)となる。そして、i,jはマス目の位置、aは訪問順の番号となる。式で書くと難しそうだが、カッコの中は、都市jの前回(a-1)と次回(a+1)の値の合計で、それに今回の都市iの値を掛け、さらに都市iと都市jの距離を掛けたものになっている。

n_a,iとn_a-1,jの積は前回、都市jにいて、今回、都市iに来た場合に1になり、都市iと都市jの間の距離がLに加算される。同様に、n_a,iとn_a+1,jの積は今回、都市iにいて、次回、都市jに行く場合に対応しており、都市間の距離をLに足し込んでいる。そして、経路に含まれない移動はnがゼロになっているので距離はカウントされない。

それをΣで全部のa、i、jの組み合わせについて合計をとっている。最初の1/2は、この式ではすべてのi、jの組み合わせの合計を計算しているので、都市iから都市jの距離と都市jから都市iの距離の両方がカウントされているので、一方向の距離にするために付けられている。

これで距離の計算式にはなっているのだが、まだ、全部の都市を巡るという条件と、同じ都市を2回以上訪問してはならないという条件がはいっていない。ソフトウェアでシミュレーションする場合は、この条件を満たさない経路は計算から省いてしまうというようなことができるが、アニールだけで解を求める場合は、これらの条件を満たさない経路は系のエネルギーが大きくなってしまう項を付け加えることにより、条件を満たさない経路が最適解となってしまうことを排除するようにする。

どの列にも1は1個だけであれば、どの都市も訪問は1回だけとなる。これに加えて、どの行にも1は1個だけであれば、すべての都市を巡っていることになる。これらの条件は

と書き表せる。

この2つの式をエネルギーのコストの式に書き変えて、

とする。

カッコに2乗が付いているのはコストが負になるのを防ぐためである。これらに、それぞれの制約条件の強さを表すk1とk2を掛けて、経路の長さの式に足し込んでやれば、制約条件を満たさない解が最適経路として選ばれることを防ぐことができる。

アニールの計算を行う場合は、系の温度が高い状態から徐々に冷却していく必要があり、 Kinetic項が加えられるが、アニール終了時点では無視できる程度に小さくなり解には影響を与えないので、ここでは説明を省略する。

(次回は6月13日に掲載します)