東北大学大学院情報科学研究科大関真之准教授が率いる東北大学と株式会社デンソーによる共同研究チームは、
D-Wave Systems 社が販売する量子アニーリングマシンを用いて大規模な組合せ最適化問題を高精度に解く方法を発見しました。
組合せ最適化問題は離散変数によって定義される評価関数を最小化する問題であり、多くの実用的な場面で高速且つ高精度に解くことが要求されます。
多岐にわたる最適化問題を解く方法として注目されているのが、原子や分子など非常に小さいスケールのものを支配する量子力学の原理に基づく量子アニーリングです。
量子アニーリングは、様々な可能性を重ね合わせの状態を利用して探索することで組合せ最適化問題を効率的に解くことができると期待されています。
最近では、カナダのベンチャー企業である D-Wave Systems 社がその原理に基づく世界初の量子アニーリングマシンを製造、販売して更に注目を集めています。
現在販売されている量子アニーリングマシンは20マイクロ秒という短時間で最適解の候補を出力しますが、現在広く使われている古典コンピュータと違って、取り扱い可能な最適化問題のサイズと形式に強い制約があります。
そこで、大規模な最適化問題を解く場合には、量子アニーリングマシンで取り扱い可能な一部の変数を抜き出してきて、これらから成る部分問題を繰り返し最適化するという方法が広く使われています。
この枠組みを用いて高精度な解を得るためには、可能な限り大きな部分問題を繰り返し解くことが重要となります。
研究チームの岡田俊太郎と大関真之は、この量子アニーリングマシンに解かせる部分問題の選定方法と量子アニーリングマシンへの埋め込み方法における従来法の問題点の解消方法を見出して、実際に量子アニーリングマシンの性能が向上することを確認しました。
従来法(qbsolv)では解きたい問題の形式に関わらず埋め込みの準備が整っている部分問題を抜き出して分割をしていたため、一度に載せられる部分問題を大きくする工夫の余地が残されていました。
研究チームは、解きたい大規模な問題から、量子アニーリングマシン特殊な形状をしたチップに合う埋め込みのし易い部分問題の選定とその埋め込み方法の探索を並行して実行することで、従来法に対して大幅に短い処理時間で大きな部分問題を埋め込むことに成功しました。
大きな部分問題を量子アニーリングマシンで解く(図1)ことにより、コスト関数の低減に見られるように解の精度向上、最適解への接近速度が向上することを、いくつかの例で実験的に確認しました。
比較的最適化が難しい3次元スピングラス模型についての適用を行なった場合、図 2 のような結果を示しました。
図1.大きな部分問題を量子アニーリングマシンで解く様子
![【量子コンピュータ】量子アニーリングマシンの効率的利用方法が開発される [613637526]->画像>10枚](https://research-er.jp/img/article/20190215/20190215120908.png)
図2. 既存手法と提案手法の比較
![【量子コンピュータ】量子アニーリングマシンの効率的利用方法が開発される [613637526]->画像>10枚](https://research-er.jp/img/article/20190215/20190215120926.png)
https://research-er.jp/articles/view/77365
論文
Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
https://www.nature.com/articles/s41598-018-38388-4
