インサイダーブリーフ：
- QoBlibベンチマークでは、経験的に困難で構造的に関連性のある10の組み合わせ最適化問題クラスを導入し、量子および古典的なソルバー間の公正な比較を可能にします。
- モデルに依存しないベンチマークを強調し、MIPとQUBOの両方の定式化を、再現性とパフォーマンス追跡のための標準化されたメトリックを提供します。
- ベンチマークは、QAOAのようなヒューリスティックなアプローチをサポートし、コミュニティの関与と進捗監視を促進するための例示的な量子ベースラインが含まれています。
- オープンソースのイニシアチブとして設計されたQoblibは、量子アドバンテージへの実際のパスを特定することを目的として、研究者にソリューションをテスト、提出、洗練するよう招待します。
組み合わせの最適化における量子優位性への推進は、ハードウェアの制限だけでなく、実際の困難を反映する合意されたベンチマークが顕著に欠けていることによって抑制されています。で 新しいarxivプレプリント、IBM Quantum、Zuse Institute Berlin、Kipu Quantum、およびいくつかの大学や企業の研究者チームは、量子最適化のための標準化されたベンチマークスイートを導入しています。 Quantum Optimization Benchmark Library、または略してQoblibと呼ばれるこのスイートには、マルチ期間ポートフォリオの最適化から最小のBirkhoff分解まで、経験的硬度と実用的な関連性のために選択された10の問題クラスが含まれています。
ジェイ・ガンベッタが指摘したように 最近の投稿、最適化の問題は、量子コミュニティ内で興奮と議論の両方を生み出し続けます。量子コンピューターは一般的に効率的に解決することが期待されるためではなく、QAOAのような量子ヒューリスティックアプローチがあるため かもしれない 特定のインスタンスの競争力を証明します。 「Quantumが古典よりもうまくやることができる候補者を探すことは、研究努力の価値があります」と彼は書いており、これはそれらを「量子アドバンテージへの実行可能な道」にしていると付け加えました。 Qoblibペーパーはこのビューと一致しており、そのような種類のインスタンスの包括的な概要を提供し、量子ソルバーとクラシックソルバーの両方で進捗を追跡するためのプラットフォームを提供します。
理論的な約束からテスト可能な問題まで
量子アルゴリズムは、特にNPハードとして分類された問題の問題について積極的に調査されています。ただし、提案されているアルゴリズムのほとんどは、最適性を保証することなく、ヒューリスティックです。その結果、経験的パフォーマンスが主要な評価方法になります。著者によると、ベンチマークは、量子と古典的なアプローチを公正に比較し、時間の経過とともにハードウェアとアルゴリズムの設計の進捗状況を追跡するためにモデルに依存する必要があります。
この論文は、かなり明確なベンチマーク哲学を提示します。ベンチマークは難しいはずですが、実世界または構造的に関連する問題に根ざし、モデリングとソルバータイプの点で柔軟です。選択した10の問題クラスはすべて、100未満から約100,000未満の範囲の変動カウントでクラシックソルバーにとって困難になり、著者らは、現在および短期の量子ハードウェアの範囲内にそれらをもたらすと主張しています。
10の問題クラスは3つのカテゴリに分類されます。まず、市場分割、最大の独立セット、ネットワーク設計などの「クラシック」バイナリ最適化の問題は、長い歴史とよく理解されている硬度のために含まれており、新しいアプローチの比較に適しています。第二に、低自動相関バイナリシーケンス、最小のBirkhoff分解、スポーツトーナメントのスケジューリングなどの問題はあまりベンチマークされていませんが、小さなサイズでもハードインスタンスを提供します。最後に、モデリングの変動性にもかかわらず、ポートフォリオの最適化や能力化された車両ルーティングなどの実質的に動機付けられた問題が含まれており、産業用途の重要性を反映しています。
各問題クラスには、クリアインスタンス生成方法とベースラインの古典的な結果が表示されます。通常、GurobiやCplexなどのソルバーを使用して、ILPモデルやABS2またはQUBOバリアントのその他の特殊なライブラリを使用します。 Market SplitやLabsなどのいくつかの問題は、驚くほど小さなスケールの古典的なソルバーにとっては手に負えないものになります。
考慮事項と再現性のモデリング
QAOAや量子アニーリングなどのものを含むほとんどの量子最適化アルゴリズムには、2次の制約のないバイナリ最適化または同等のISINGモデルとして問題を組み立てる必要があります。ただし、問題をquboフォームに変換することは、それが思っているよりも複雑です。著者らは、いくつかの変換により、密に接続された変数と大きな係数範囲をもたらすことが多いことを強調しています。
QOBLIBは、単一のモデリング経路を処方するのではなく、モデルに依存しないベンチマークをサポートしています。インスタンスは、実行可能な場合はMIPとQUBOの両方の形式で提供され、可変カウント、スパース、係数範囲に関する情報が付随しています。たとえば、LABSの問題にはMIP定式化に100未満のバイナリ変数が含まれる場合がありますが、そのQUBO同等物には800を超える変数が必要になり、大幅に高次の用語が必要になります。
再現性を確保するために、著者は、ソリューション品質とランタイムの両方の標準化されたメトリックを定義します。多くの量子ソルバーを含む確率的アルゴリズムの場合、ベンチマークは、コアメトリックとして成功率と時間と溶解を使用して、複数の実行にわたるレポートを促進します。重要なことに、Quantum Runtimeは慎重に定義され、キューイング時間を除外し、IBM Quantumのようなプラットフォームでのセッションベースの操作と整合する回路の準備、実行、測定の段階のみを含めます。
最適化の問題では、重要な結果は、必ずしもグローバルな最適ではなく、可能な限り最良の目的値です。これは、ほとんどの量子アプローチのヒューリスティックな性質を反映しており、理論的な完全性ではなく、実用的なパフォーマンスにベンチマークを集中させます。
最初の結果とコミュニティコール
この論文の主な目標は、1つのアルゴリズムの優位性を宣言することではなく、ベンチマークフレームワークを確立することですが、著者は、特定の問題クラスに例示的な量子ベースラインを含めます。特に、ラボ、Birkhoff分解、および最大独立したセットについて例が示されています。これらのベースラインは、最先端の量子パフォーマンスを表すことではなく、ソリューションをどのように構成および提出できるかを示すことを目的としています。
最終的に、著者はQoblibをコミュニティリソースとして位置付けています。ベンチマークリポジトリはオープンソースであり、クラシック、ハイブリッド、または量子アプローチをテストする研究者からの貢献が奨励されています。問題の定義、メトリック、および評価慣行を標準化することにより、チームは、量子最適化の進歩の体系的な追跡を可能にすることを目指しています。おそらく、おそらく、おもちゃの問題や合成例を超えて拡大する量子優位の証拠です。
意味のあるベンチマーク標準に向けて
人工的に構造化されたまたは些細な解決可能なインスタンスに焦点を当てた以前の多くのベンチマークとは異なり、Qoblibは困難なフロントとセンターを配置します。しかし、それは病理学的領域に漂うことなくそうし、それらが反論されているからではなく、実際の最適化の課題の構造と複雑さを反映しているために難しい問題を選択します。その結果、包括的で実用的で適応性のあるベンチマーク（一種の最適化の十代）が、次の量子ソルバーの波の実証済みの基盤として機能する可能性があります。
論文の貢献著者には、Thorsten Koch、David E. Bernal Neira、Ying Chen、Giorgio Cortianaが含まれます。
ダニエル・J・エッガー、ラウル・ヘーゼ、ナレンドラ・N・ヘガデ、アレハンドロ・ゴメス・カダビッド、レア・ファン、トシナリ・イトコ、トーマス・クライナート、ペドロ・マシエル・ザビエル、プロアスル、ラメシュのアヌラグ、シマーダのシマダ。
