量子アニーリングマシンの効率的利用方法を開発――大規模な組合せ最適化問題を高精度に解く方法を考案 東北大学など

東北大学は2019年2月15日、カナダの量子コンピュータ製造企業であるD-Wave Systemsの量子アニーリングマシンを用いて大規模な組合せ最適化問題を高精度に解く方法を、同大学大学院情報科学研究科とデンソー先端技術研究所の研究員が共同研究において発見したと発表した。

組合せ最適化問題とは、離散変数により定義される評価関数を最小化する問題をいう。これを高速/高精度に解く方法として注目を集めているのが量子アニーリングだ。量子アニーリングでは、重ね合わせの状態を利用してさまざまな可能性を探索することで、組合せ最適化問題を効率的に解くことができる。

その量子アニーリングが可能なコンピューターを初めて開発したのがD-Wave Systemsだ。同社の量子アニーリングマシンは20μsで最適解の候補を出力できるが、取り扱い可能な最適化問題のサイズと形式に制約がある。同機で大規模な最適化問題を高精度で解く場合、可能な限り大きな部分問題を繰り返し解く必要があった。

そこで共同研究チームは、一度に取り扱える部分問題を大きくするために、量子アニーリングマシンのチップに埋め込みやすい部分問題の選定と、その埋め込み方法の探索を並行して行った。結果として、従来よりも大幅に短い時間で大きな部分問題を埋め込むことに成功した。

新手法を3次元スピングラスに適用したところ、コスト関数に低減が見られた。そのことから、以前よりも解の精度と最適解への接近速度が向上したことが確認された。研究チームは「将来的に取り扱い可能な最適化問題のサイズがさらに大きくなっていった時、量子アニーリングマシンが実社会で広く利用されることが期待できる」としている。

関連リンク

プレスリリース

関連記事

アーカイブ

fabcross
meitec
next
メルマガ登録
ページ上部へ戻る