早稲田大学、最適化を高速化する新しい量子アルゴリズムを報告

John Russell オリジナル記事「Waseda U. Researchers Reports New Quantum Algorithm for Speeding Optimization」

最適化問題は幅広い応用分野をカバーしており、量子コンピューティングの有力な候補としてしばしば挙げられている。しかし、量子デバイス上での制約付き組合せ最適化アプリケーションの実行時間には問題がある。早稲田大学の研究者らは、新しいアルゴリズム（post-processing variationally scheduled quantum algorithm：pVSQA）を開発し、パフォーマンスを高速化したと報告している。

早稲田大学のウェブサイトに、この研究についての簡単な説明が掲載されている。制約条件付き組合せ問題（COP）は、物流、サプライチェーン管理、機械学習、材料設計、創薬などでよく見られる。研究者らは、このアルゴリズムの新しさは、変分スケジューリングと組み合わせた後処理技術の使用により、COPの高品質な解を短時間で達成することにあると報告している。

量子デバイスを用いたCOPの解法には、変分スケジューリングと後処理という2つの主要な手法がある。我々のアルゴリズムは、変分スケジューリングと、実行不可能な解を実行可能な解に変換する後処理法を組み合わせることで、量子アニーラとゲートベース量子コンピュータの両方で、制約付きCOPの最適解に近い解を得ることができます」と、IEEE Transactions on Quantum Engineeringに今月掲載されたこの研究のリーダーである白井達彦氏は語った。

以下はその記事の抜粋である：

「革新的なpVSQAアルゴリズムは、まず量子デバイスを使って量子計算によって変分量子状態を生成します。次にこれを用いて、COPの制約の範囲内にあるすべての実現可能な解と実現不可能な解からなる確率分布関数を生成します。次に、後処理法によって実行不可能な解を実行可能な解に変換し、確率分布には実行可能な解のみを残します。その後、古典的なコンピュータを用いて、この新しい確率分布を用いてコスト関数のエネルギー期待値を計算します。この計算を繰り返すことで、最適解に近い解が得られます。」

「研究者らは、シミュレータと、量子アニーラーやゲート型量子デバイスなどの実量子デバイスの両方を用いて、このアルゴリズムの性能を分析しました。実験の結果、pVSQAは、シミュレータ上では所定の時間内にほぼ最適な性能を達成し、実際の量子デバイス上では後処理なしで従来の量子アルゴリズムを上回ることが明らかになりました。」

現在の量子デバイス（断熱アニーラーやゲート型システム）の限界を考えると、研究者らは、この新しいアルゴリズムが、特に制約条件付き組合せ最適化の適用範囲の広さを考えると、重要な前進であることを示唆している。

彼らは論文の要旨で次のように述べている：

「COPは通常、量子アニーラーまたはゲートベースの量子デバイス上でイジングモデルの基底状態探索問題に変換さ れます。変分法は、短時間で高品質な解を導く最適なスケジュール関数を見つけるために用いられます。ポスト処理技術は、COPの制約条件を満たすように量子デバイスの出力解を変換します。」

「pVSQAは変分法と後処理技術を組み合わせたもので、制約付き解の十分条件を得ることができます。本研究では、制約付きCOPがpVSQAを適用するための十分条件を、利便性の高い後処理アルゴリズムに基づいて求めています。提案手法をグラフ分割問題と2次ナップザック問題という2つのNP困難な制約付きCOPに適用し、シミュレータ上でpVSQAを実行した結果、少数の変分パラメータで所定の演算時間内に（ほぼ）最適な性能を達成できることが示されました。次に、シミュレータの結果を基に、pVSQAを量子アニーラとゲートベース量子デバイスに実装しました。実験結果は、提案手法の有効性を示しています。」

早稲田大学論文へのリンク、https://www.waseda.jp/top/en/news/80146
IEEE論文へのリンク、https://ieeexplore.ieee.org/document/10472069