東北大学は11月9日、組み合わせ最適化問題について課題とされてきていた、“制約ありの二次計画問題”を解く際に長い計算時間を要するという問題の解決策として、列生成法と量子アニーリングマシンを組み合わせたアルゴリズムを提案し、その効果を検証したことを発表した。

同成果は、東北大大学院 情報科学研究科の大関真之教授らの研究チームによるもの。詳細は、日本物理学会が刊行する欧文学術誌「Journal of the Physical Society of Japan」に掲載された。

さまざまにある組み合わせの中から最良の選択肢を選ぶ“組み合わせ最適化問題”は、数学的に非常に難易度が高く、コンピュータを利用した効率的な解法を駆使しても長い計算時間を要するという課題がある。そうした課題の解決策としては量子アニーリングが提案され、その研究が進められている。しかし量子アニーリングはその特性上、産業応用上に必要な要請を反映した制約条件を満たすことが難しいという問題があったとのことだ。

そこで研究チームは、列生成法と呼ばれるアルゴリズムを量子アニーリングと合わせて利用することで、組み合わせ最適化問題を分解して小さな問題を繰り返し解き、制約条件を満たした現実の問題に有用な形で最終的な解を得るという新たなアルゴリズムを提案したとする。

研究チームによると、今回の研究におけるポイントは、列生成法の計算の一部に量子アニーリングが得意とする特殊な問題形式が含まれていることにあるという。先行研究では、その計算に時間がかかることで全体の計算時間が長くなってしまうという問題が残されていたのに対し、その解決のために量子アニーリングが有効であることを着想して開発された新アルゴリズムでは、計算時間を飛躍的に短縮できたとしている。

なお、今回の手法を用いた量子アニーリングマシンでの実験では、最大で3.7倍ほどの高速化が認められたとのこと。さらに同マシンだけではなく、既存のコンピュータにおける量子アニーリングのシミュレーション技法にも適用が可能で、類似手法であるシミュレーテッドアニーリングについては、約1000倍の速さで答えを求めることができたという。

  • データの大きさに対する計算時間を求めたグラフ

    データの大きさに対する計算時間を求めたグラフ(R-Gurobi＝既存の商用高速ソルバーを用いた例、量子アニーリング＝今回の提案手法に量子アニーリングマシンを用いたもの)。両者の比較により、データサイズが大きな場合に新手法が既存手法よりも短い時間で計算を終えることが確認された(出所:東北大学)

研究チームは今回の成果について、量子アニーリングをはじめとする関連技術の計算性能を大幅に向上させる画期的なものだとしており、配送や製造工程の最適化など、産業における社会課題を効率よく解決することが期待できるとする。また今後は、量子ソリューション拠点として認定された東北大として、共同研究などを通じて今回の提案手法を活用し、さまざまな産業の課題を解決して社会に還元していくとしている。