最適化問題をめぐる2種類の量子手法の統一的な枠組みを提案

当社の近藤瑠歩らが慶應大学、東京大学と共同で行った研究が Quantum に掲載されました。

輸送計画やスケジューリングなどの組み合わせ最適化問題は、変数の増加とともに組み合わせ爆発を引き起こし、良い解を得ることが一般に困難とされています。量子アルゴリズムは、「重ね合わせ」といった量子性を活用することで、この問題の解決に取り組んできました。量子最適化アプローチの一つである量子近似最適化アルゴリズム（QAOA）^注1の中でも、問題サイズを段階的に縮小する再帰的QAOAは高い性能を示すことが知られていますが、その理論的な説明は十分に確立されていませんでした。また、別のアプローチである量子ランダムアクセスコード（QRACs）^注2を応用した組み合わせ最適化手法では、少ない量子ビットで大規模な問題を扱うことが可能ですが、任意の量子状態と最適化問題の解の関係は明らかになっていませんでした。

本研究では、再帰的QAOAと、QRACsを応用した最適化手法の2つのアプローチについて、それぞれの未解明な部分を明らかにし、近似方法は異なるものの両者が同じ定式化に帰着するため統合可能であることを示しました。さらに、両者の統一フレームワークに適したヒューリスティックを導入し、従来の量子最適化手法や近似比保証のある古典アルゴリズムよりも優れた解を得られることをシミュレーションで実証しました。本研究は効率的な量子最適化手法の実現に貢献し、輸送、金融、機械学習などへの応用が見込まれます。

注1）量子近似最適化アルゴリズム（Quantum Approximate Optimization Algorithm; QAOA）：量子アニーラの挙動をゲート式量子コンピュータで模したモデル。 注2）量子ランダムアクセスコード（Quantum Random Access Codes; QRACs）：1つの量子ビットに複数の古典ビット情報を符号化する手法。

タイトル: Recursive Quantum Relaxation for Combinatorial Optimization Problems
著者: Kondo, R., Sato, Y., Raymond, R., Yamamoto, N.
掲載誌: Quantum
掲載日: 2025年1月15日
https://doi.org/10.22331/q-2025-01-15-1594