量子アニーリングの効率的な最適化手法を開発 数理最適化アルゴリズムとの組み合わせで最大3.7倍の高速化を確認

量子アニーリングの効率的な最適化手法を開発数理最適化アルゴリズムとの組み合わせで最大3.7倍の高速化を確認

2023年11月 9日 11:00 | プレスリリース?研究成果

【本学研究者情报】

〇大学院情报科学研究科
教授大関真之

【発表のポイント】

量子力学の现象を利用した最适化手法である量子アニーリング^(注1)と列生成法^（注2）という数理最适化アルゴリズムを组み合わせた効率的な最适化手法を考案しました。
量子アニーリングを利用した解法では制约条件を満たすことが难しいなど、产业利用に向けてのいくつかの课题が残されていました。
列生成法を组み合わせた量子アニーリングで実用的な制约条件を満たすことが可能となり、また计算时间の観点でも非常に効率よく问题を解くことができるようになりました。

【概要】

　东北大学大学院情报科学研究科大関真之教授らの研究グループは、组合せ最适化问题について课题とされてきていた制约ありの二次计画问题を解く际に长い计算时间がかかる问题を解决する手段として、列生成法と量子アニーリングマシンを组み合わせたアルゴリズムを提案し、その効果を検証しました。

　本研究の成果によって、実社会に登场するような仓库配置の最适化や工场での製造工程の顺序の最适化、勤务シフトのスケジュール问题など様々な组合せ最适化问题をより高速に解くことが期待されます。

　本研究成果は、2023年10月20日に日本物理学会の英文誌Journal of Physical Society of Japanに掲載されました。

図1.データの大きさに対する计算时间を求めたグラフ。搁-骋耻谤辞产颈=既存の商用高速ソルバーを用いた例、量子アニーリング=我々の提案手法に量子アニーリングマシンを用いたもの)でデータサイズが大きな场合に提案手法が既存手法よりも短い时间で计算を终えることを确认しました。

【用语解説】

注1.　量子アニーリング：
極低温において、原子や分子などの非常に小さいスケールでは、結果が確率的に変動する「量子揺らぎ」が存在します。これを利用して揺らすことでひっかかりのない安定した配置へ誘導する量子アニーリングと呼ばれる技術が1998年に東京工業大学の当時大学院生であった門脇正史氏(現：デンソー株式会社)、西森秀稔名誉教授から提案されました。カナダのベンチャー企業である D-Wave Systems社が量子アニーリングの原理に従ったコンピュータを製作して販売をしています。原子や分子の振る舞いを調べる量子シミュレーションや、様々な可能性の中で最も良い回答を探索する最適化問題、人工知能の基盤技術となる機械学習への応用などが注目されています。この量子アニーリングでは、量子揺らぎにより、デジタル信号処理における0と1の重ね合わせ状態を作ることができます。この重ね合わせを巧みに利用することで、どちらの状態にあるのが最も相応しいのか、組合せ最適化問題における解答を探索することができます。

注2.　列生成法：
组合せ最适化问题のうち制约条件と呼ばれる问题固有のルールについて、必要な条件を割り出して効率的に计算を进める方法です。

详细（プレスリリース本文）