表題番号：2019C-167 日付：2020/02/12
研究課題イジング計算機による組合せ最適化問題の高速解法の可能性
研究者所属（当時） 資格 氏名
（代表者） 理工学術院 基幹理工学部 教授 戸川　望
研究成果概要
　内閣府資料によれば，モビリティ，金融，創薬など，Society5.0を実現する産業分野では，数多くの「組合せ最適化問題」の高速・実時間解法が最大の困難点であり，NP困難問題など難しいクラスの組合せ最適化問題に対し，いかに「高速・実時間で」（準）最適解を求めるかがその成否を決めると言われる．　一方，非ノイマン型コンピューティング技術の決定打として量子アニーリングマシンをはじめとする「イジング計算機」が注目されている．イジング計算機は物理現象を利用することで組合せ最適化問題を高速に解法するものであり，カナダD-Wave，我が国では日立，NTT，富士通，NEC，東芝等が次々にイジング計算機を発表している．ところが，これら既存のイジング計算機が対象とした組合せ最適化問題の多くは，グラフ最大カット問題等のイジング計算機に都合が良い単純な問題ばかりであり，現実的な組合せ最適化問題の解法に至っていない．しかも現状，イジング計算機は「物理的特性」（複数のスピンのコヒーレンス時間の長時間化等）が注目されるばかりであり「イジング計算機の実応用」はあまり注目されていない．つまりイジング計算機による高速化・低電力化等はまだサンプル評価段階であり，ここに最大の問題点がある．　以上の背景のもと，本研究では，イジング計算機にブレークスルーを与え， Society5.0の実現に不可欠となる「現実的な」組合せ最適化問題に対して，イジング計算機により高速に解法することを目的に研究に取り組んだ．2019年度には，他の研究資金の成果を補うことを目的に，二次割当問題の最適解法，長方形敷き詰め問題（矩形パッキング問題）の解法，長方形敷き詰めを3次元に拡張した直方体敷き詰め問題の解法，グラフの同型判定問題の解法など，これまでイジング計算機で解法されて来なかった数々の問題の解法に挑戦し，一定の成果を得た．