東北大ら,量子アニーリングマシンを効率的に利用

東北大学とデンソーは共同で,カナダD-WaveSystemsが販売する量子アニーリングマシンを用いて大規模な組合せ最適化問題を高精度に解く方法を発見した(ニュースリリース)。

組合せ最適化問題は離散変数によって定義される評価関数を最小化する問題であり,多くの実用的な場面で高速かつ高精度に解くことが要求される。多岐にわたる最適化問題を解く方法として注目されているのが,原子や分子など非常に小さいスケールのものを支配する量子力学の原理に基づく量子アニーリングとなる。

量子アニーリングは,様々な可能性を重ね合わせの状態を利用して探索することで,組合せ最適化問題を効率的に解くことができると期待されている。最近では,ベンチャー企業であるD-Wave Systemsがその原理に基づく世界初の量子アニーリングマシンを製造,販売して更に注目を集めている。現在販売されている量子アニーリングマシンは20µsという短時間で最適解の候補を出力するが,現在広く使われている古典コンピューターと違い,取り扱い可能な最適化問題のサイズと形式に強い制約がある。

そこで,大規模な最適化問題を解く場合には,量子アニーリングマシンで取り扱い可能な一部の変数を抜き出してきて,これらから成る部分問題を繰り返し最適化するという方法が広く使われている。

今回,研究グループは,この量子アニーリングマシンに解かせる部分問題の選定方法と量子アニーリングマシンへの埋め込み方法における従来法の問題点の解消方法を見出して,実際に量子アニーリングマシンの性能が向上することを確認した。従来法(qbsolv)では解きたい問題の形式に関わらず埋め込みの準備が整っている部分問題を抜き出して分割をしていたため,一度に載せられる部分問題を大きくする工夫の余地が残されていた。

研究グループは,解きたい大規模な問題から,量子アニーリングマシン特殊な形状をしたチップに合う埋め込みのし易い部分問題の選定とその埋め込み方法の探索を並行して実行することで,従来法に対して大幅に短い処理時間で大きな部分問題を埋め込むことに成功した。

さらに,大きな部分問題を量子アニーリングマシンで解くことにより,コスト関数の低減に見られるように解の精度向上,最適解への接近速度が向上することを,いくつかの例で実験的に確認したという。研究グループは,今回の研究により,将来的に取り扱い可能な最適化問題のサイズがさらに大きくなった場合,量子アニーリングマシンが実社会で広く利用されることが期待できるとしている。

その他関連ニュース

  • 東大ら,チップ量子コンピューターへ一歩 2019年10月22日
  • 電通大,磁場で量子化した固体電子エネルギーを決定 2019年10月11日
  • 理研ら,クーパー対を2本の細線に弾道的に分離 2019年10月09日
  • 東北大ら,「疑似」量子ビット素子を開発 2019年09月19日
  • NTTとNII,光で解を求めるコヒーレントイジングマシンと量子アニーリングマシンを比較 2019年09月13日
  • OIST,電子の量子状態を新たな方法で検出 2019年09月10日
  • 市大ら,ESR分光法で電子スピンの量子状態を制御 2019年08月23日
  • 東工大ら,量子干渉効果による磁気準粒子を観測 2019年08月22日