量子アニーリングの効率的な最適化手法を開発 ー 数理最適化アルゴリズムとの組み合わせで最大3.7倍の高速化を確認 ー
研究のハイライト
量子力学の現象を利用した最適化手法である量子アニーリング(注1)と列生成法（注2）という数理最適化アルゴリズムを組み合わせた効率的な最適化手法を考案しました。
量子アニーリングを利用した解法では制約条件を満たすことが難しいなど、産業利用に向けてのいくつかの課題が残されていました。
列生成法を組み合わせた量子アニーリングで実用的な制約条件を満たすことが可能となり、また計算時間の観点でも非常に効率よく問題を解くことができるようになりました。
東北大学大学院情報科学研究科大関真之教授らの研究グループは、組合せ最適化問題について課題とされてきていた制約ありの二次計画問題を解く際に長い計算時間がかかる問題を解決する手段として、列生成法と量子アニーリングマシンを組み合わせたアルゴリズムを提案し、その効果を検証しました。
本研究の成果によって、実社会に登場するような倉庫配置の最適化や工場での製造工程の順序の最適化、勤務シフトのスケジュール問題など様々な組合せ最適化問題をより高速に解くことが期待されます。
本研究成果は、2023年10月20日に日本物理学会の英文誌Journal of Physical Society of Japanに掲載されました。
研究者情報
大関真之
教授東北大学大学院情報科学研究科
用語解説
- 注1. 量子アニーリング
- 極低温において、原子や分子などの非常に小さいスケールでは、結果が確率的に変動する「量子揺らぎ」が存在します。これを利用して揺らすことでひっかかりのない安定した配置へ誘導する量子アニーリングと呼ばれる技術が1998年に東京工業大学の当時大学院生であった門脇正史氏(現：デンソー株式会社)、西森秀稔名誉教授から提案されました。カナダのベンチャー企業である D-Wave Systems社が量子アニーリングの原理に従ったコンピュータを製作して販売をしています。原子や分子の振る舞いを調べる量子シミュレーションや、様々な可能性の中で最も良い回答を探索する最適化問題、人工知能の基盤技術となる機械学習への応用などが注目されています。この量子アニーリングでは、量子揺らぎにより、デジタル信号処理における0と1の重ね合わせ状態を作ることができます。この重ね合わせを巧みに利用することで、どちらの状態にあるのが最も相応しいのか、組合せ最適化問題における解答を探索することができます。
- 注2. 列生成法
- 組合せ最適化問題のうち制約条件と呼ばれる問題固有のルールについて、必要な条件を割り出して効率的に計算を進める方法です。
