早稲田大学(早大)は1月11日、これまで、ハードウェア上の制約により入力可能な問題規模が制限されていた「量子アニーリングマシン(イジングマシン)」において、最適性を失わずに大規模な問題を小さな問題に分割する条件を解明したと発表した。
同成果は、早大 グリーン・コンピューティング・システム研究機構の跡部悠太客員次席研究員、同・多和田雅師研究院講師、早大 理工学術院の戸川望教授らの研究チームによるもの。詳細は、IEEE Computer Societyが刊行するコンピュータに関する全般を扱う学術誌「IEEE Transactions on Computers」にオンライン掲載された。
複数の都市を1回ずつ訪問する際、どのルートで回るのが一番効率的かを問う「巡回セールスマン問題」に代表される「組合せ最適化問題」は、現実世界のさまざまな場面で求められる。そして組合せ最適化問題は、大規模になればなるほど、従来型のコンピュータで最適解を得ることが困難になることから、別角度からの解決方法が模索されており、その主な1つが量子コンピュータの利用である。
中でも、組合せ最適化問題に特化した量子アニーリングマシンをはじめとしたイジングマシンと呼ばれる新しいタイプの計算機は、2011年にD-Wave Systemsが商用モデルを発表して以降、現在では一般ユーザーも利用することができるまでになっている。
しかし現状のイジングマシンは、ハードウェアの制約により、入力可能な問題の規模が制限されており、大規模な問題を直接解法することが困難とされている。そのため、これまでは発見的な手法によって、大規模な問題を小さな問題に分割することで対応が図られていたが、分割された問題の答えが、もとの大規模な問題の答えと一致しているか理論的な条件は未解明のままだったという。
そこで研究チームは今回、量子アニーリングマシンを含めたイジングマシンに入力可能な問題規模の制限を解決することを目的に、最適性を失わずに大規模な組合せ最適化問題を小さな問題に分割する条件を解明することを試みたという。その結果、イジングマシンによって条件を満たした小さな問題を解法すれば、もとの大規模な問題の答えと一致することが証明されたという。
また、大規模な問題からうまくこのような条件を抽出し、もとの大規模な問題を、イジングマシンで解法可能な問題規模まで小さくして、繰り返し解法する新たなアルゴリズムも提案。このアルゴリズムは、理論的な裏付けのもとに大規模な問題を小さな問題に分割して解法するため、従来技術と比べて精度よくもとの大規模な問題を解法することが可能となるという。
大規模な組合せ最適化問題の一部を抽出して、イジングマシンに入力可能な規模の小さな問題を作り、イジングマシンで解法することを考える際、どのように小さな問題を作るかがポイントであり、大規模な組合せ最適化問題の答えは複数のビットの集まりによって構成されることから、ビットの集まりのうち、「解として正しくないビット列」をすべて含むように規模の小さな問題を作り、イジングマシンで解法すれば、「解として正しくないビット列」はすべて「解として正しいビット列」に正しく修正されることが、今回の研究において理論的に判明したという。
実際に、実イジングマシンで解法することができる問題規模に対して、8倍から32倍という大きな問題について、提案手法と従来手法(ランダム手法とqbsolv手法)が比較されたところ、提案手法で得られる回答の方が精度が高いことが確認されたとする。
研究チームでは今回の成果を踏まえることで、量子アニーリングマシンを含むイジングマシンを使った、現実世界の組合せ最適化問題への活用事例を広げられると考えられるとしているほか、今回の研究は古典計算機とイジングマシンとを併用して問題を解法する取り組みでもあり、イジングマシンの活用範囲を広げるものとしている。なお、今後は、さらに実世界に見られるさまざまな問題に対し、今回提案された手法を適用させ、有効性を検証していく必要があるとしている。
-
手法の比較。縦軸のAccuracyは、もとの問題の最適解にどれだけ近い回答が得られるかが表されており、上に行くほど精度が高い結果が得られている(1.00が最も精度が高い)。図は、箱ひげ図が表されている。また、今回提案された手法、ランダム手法、qbsolv手法が比較されている。tai20a、tho30、tho40は問題の名称。赤矢印は、従来手法より今回提案された手法が改善されていることを示している (出所:早大Webサイト)
