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

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

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

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

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

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

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