広島大、「順列生成イジングモデル」のサイズと要求分解能の削減に成功

広島大学は10月12日、「順列生成イジングモデル」のサイズと要求分解能を削減する新たな設計手法「dual-matrix domain-wall法」を開発したことを発表した。

同成果は、広島大大学院先進理工系科学研究科の中野浩嗣教授、NTTデータグループとの共同研究チームによるもの。詳細は、多彩な技術研究に関する論文を扱うオープンアクセスジャーナル「Technologies」に招待論文として掲載される予定だという。

「巡回セールスマン問題」のように、数多くの順列型組合せの中から最適解を選ぶことで、効率化できるような作業や業務、さらには社会問題などはいくつもある。しかし、膨大な組合せの中から最適解を見つけるのは総当たりとなるため、最新鋭のコンピュータを用いても容易ではなく、膨大な計算時間を要してしまう。そこで近年注目され、実際に活用されつつあるのが、量子効果を利用して組合せ最適化問題の解を求める量子アニーラーだという。

量子コンピュータの一種である量子アニーラーに対し、組合せ最適化問題を等価な「イジングモデル」(複数のスピン変数の二次式)に変換した上で埋め込み、量子焼きなまし(アニーリング)を行うことにより、イジングモデルの評価値をなるべく最小化するようなスピン変数へのスピン値の割り当てを求めることが可能であり、求めたイジングモデルの解を逆変換することで、もとの組合せ最適化問題の解が得られるという仕組みである。従来の古典的コンピュータ(アルゴリズム)では扱うのが困難だった複雑な組合せ最適化問題であっても、高速かつ効率的に求められるとして期待されている。

しかし、量子アニーラーの規模と計算精度に制限があるため、イジングモデルのサイズと要求分解能をなるべく小さくすることが望まれている。そこで研究チームは今回、新たな手法を開発することにしたとする。

今回開発されたdual-matrix domain-wall法は、順列生成のためのイジングモデルであり、従来のone-hot表現で順列を表すスピン変数の行列に、新たな行列を2種類追加したもの。変数の個数がおよそ3倍に増加することになるが、イジングモデルのサイズと要求分解能を削減することが可能だという。

順列型組合せ最適化問題には、例えば巡回セールスマン問題のほかにも、グラフ同型問題、二次割当問題などがあるが、順列生成イジングモデルはこれらの問題に適用可能とされている。例えば、重み付きの無向グラフが与えられた巡回セールスマン問題で、すべての頂点を一度ずつ訪問する最短巡回を求める場合、グラフの頂点数が多くなると、従来法として知られる「one-hot法」ではサイズが急激に増加してしまい、頂点数が300の場合、イジングモデルのサイズは2743万4400となってしまう。

この数式を展開して得られる二次式が順列生成イジングモデルとなる。このイジングモデルのサイズはn³-n^{2であり、要求分解能は2n-4となる (出所:広島大プレスリリース)}

巡回セールスマン問題の解[3,1,0,2,4]とそれをone-hot表現で表す大きさ5×5の行列 (出所:広島大プレスリリース)

これに対しall-different domain-wall法を用いた場合1526万4150と、サイズを約半分(55.6％)に節約することはできるとする。しかし、今回考案されたdual-matrix domain-wall法であれば、頂点数の増加に伴うサイズの増加が2つの従来法に比べ緩やかであり、同じ頂点数が300でも106万2000で済み、one-hot法の約3.9％、all-different domain-wall法に対しても約7％にまで削減可能だという。

今回のDual-matrix domain-wall法によるイジングモデルの最適解の例。この最適解は、順列[3,1,0,4,2]とその逆順列[2,1,4,0,3]が表されている (出所:広島大プレスリリース)

40頂点の有向グラフと最短巡回路 (出所:広島大プレスリリース)

無向グラフの巡回セールスマン問題を解くイジングモデルの二次項の個数 (出所:広島大プレスリリース)

順列型組合せ最適化問題は多くのアプリケーションがあるにも関わらず、それを解くためのイジングモデルはサイズと要求分解能が大きいため、現在の量子アニーラーでは最適解を得るのが困難だったという。今回開発されたdual-matrix domain-wall法は、これらの課題を解決することが可能であると研究チームでは説明する。ただし、現在の量子アニーラーはまだ規模が小さく、計算精度も十分ではないため、従来の古典計算機を用いた問題解法を凌駕するには、量子アニーラーの大規模化と高性能化を待つ必要があるとしているほか、それまでの代替として、量子効果に基づかず、イジングモデルの解を求める疑似量子アニーラーの研究も盛んに進められているとのことで、研究チームでもGPUを用いた疑似量子アニーラー「ABS2」の開発を進めているとしている。

なお研究チームでは今後も、dual-matrix domain-wall法を含めた、さまざまな手法を用いて組合せ最適化問題の高速解法を探求していく予定としている。