QUBOを効率的に解く富士通のデジタルアニーラ - ISC 2019

ISC 2019において富士通研究所の田村泰孝フェローが富士通のデジタルアニーラについて発表を行った。デジタルアニーラは「Quadratic Unconstrained Binary Optimization(QUBO)」という問題を解く専用システムである。

• 富士通のデジタルアニーラについてISC 2019で発表を行う田村泰孝フェロー

いきなり数式が出てきてとっつきが悪いのであるが、次の式は系全体のエネルギーを表すHamiltonianという式で、x_iとx_jが例えばiとjの位置の2つのスピンで、W_ijがその2つのスピンの間の結合係数である。そのスピンペアのエネルギーがW_ijx_ix_jと表される。このスピンx_iとx_jの値が逆の場合、x_iとx_jの符号が反対になり、シグマの前にーがあるので、正のエネルギー寄与となる。

そしてb_ix_iはiの位置のスピンの持つバイアス成分である。ここで、系のエネルギーEが最小になる各位置のスピンの値が求める最適解になるように解くべき問題を変形しておけばアニーリングでエネルギーが最小になる状態を見付ければ、解くべき問題の最適解が得られることになる。

• QUBOという形で、系のエネルギーが最小の状態が求める最適解であるように解くべき問題を変形してやれば、アニーリングで、最適化問題が解ける。アニーリングをシミュレーションしてQUBOを解くという方法は以前から知られているが解を得る速度が遅いのが問題である (このレポートのすべての図は、ISC 2019での富士通研究所の田村氏の発表スライドを撮影したものである)

富士通の開発した「Digital Annealer(DA)」は、D-Waveのマシンのような量子ビットを使うアニーラではない。量子ビットを使うアニーラでは、断熱的にハミルトニアンを変形して最低エネルギー状態を見つける。しかし、富士通のDAは普通のCMOS回路で系のエネルギー状態の勾配などを元に、最低エネルギー状態を探す。

そのため、D-Waveのマシンのように雑音の小さい超電導状態を作るために10mKというような超低温を作る必要が無く、使いやすい。しかし、CMOSによるシミュレ―テッドアニーリングでは、ローカルなエネルギー最低状態に陥ると、どの向きに移動してもエネルギーが増えてしまい、グローバルな最低エネルギーの状態にたどり着けないということが起こる。このため、富士通のDAは、ローカルミニマムに陥った時にも、そこから抜けられる近傍状態に最短の回数で移動できる仕組みを持っている。

• 量子アニーラは断熱的にハミルトニアンを変形して最低エネルギー状態を探す。一方、通常のアニーラは確率論的に最低エネルギー状態を探すが、局所的な最小エネルギー状態に捕まってしまうことが多い。富士通のDAは量子アニーラではないが、局所的な最適解から抜け出す仕組みを持っている

シミュレ―テッドアニーリングでは「Markov Chain Monte Carlo(MCMC)」という探し方を使っている。次のスライドには3つの式が書いてあるが、最初の式は前のスライドの系全体のエネルギーの式である。2番目の式はx_iをx_i'に変えた時に系のエネルギーがどれだけ変わるかを示す式である。

そして、3番目の式が、その状態変更を採用するかどうかの確率を計算する式で、exp(-βΔE_i)が1より大きければ採用確率A_i=1であるが、小さければexp( )の値がA_iの値になる。つまり、状態の変更により系のエネルギーが減少しΔE_iが負であれば採用確率は1.0となる。

ΔE_iが正であれば系のエネルギーは増加する変化であるが、そのような変化もまったく採用されないわけではなく、増加するエネルギーが大きくなるにつれてそのような変化の採用確率は減少する採用確率はゼロではない。

コンピュータによる普通の計算は何度やっても同じ結果になるが、モンテカルロ法の場合は、おみくじを引くように当たりはずれがあり、毎回、計算結果が違ってくる。しかし、成功と失敗の確率が50%:50%であれば、多数回繰り返して実行すれば成功と失敗はほぼ50%:50%で発生する。

ただし、モンテカルロ法を使う場合、実行のたびに結果が異なるとデバグなどに差し支えるので、疑似乱数が使われ、毎回、同じ乱数列が発生されるようにするのが一般的である。

そして、ベータは絶対温度Tの逆数であり、温度が高くなるとexp( )の項は小さくなる。シミュレ―テッドアニーリングでは、高い温度の状態からスタートして、単調減少ではないが、全体的には温度を下げて最低エネルギー状態を探索していく。

• ノードiの状態x_iによる系のエネルギーは、最初の式で表される。ノードiの状態がx_i’と変化した場合のエネルギーの状態の増減は2番目の式で表される。そして、その状態変化は3番目の式の確率で採用される。DAではすべての計算は確率的に行われる