新しい量子最適化ベンチマーク・ライブラリを使ってアルゴリズムをテストしてみませんか

量子最適化ワーキング・グループは最近の論文で、10の問題クラスを含んだ量子最適化ベンチマーク・ライブラリ(QOBLIB)、通称「難題デカスロン（intractable decathlon）」を紹介しました。このベンチマークは、量子手法と古典手法の比較を容易にして、組み合わせ最適化問題における量子的優位性の探求を助けます。（注：「デカスロン」自体は、オリンピック種目にもなっている十種目の複合陸上競技です。非常に高い総合的な運動能力が求められます。）

最適化において量子的優位性はどうすれば達成できるのでしょうか？ 力を合わせることが必要です。ではその量子優位性とはどのようなものでしょうか？　それは長い話になります。

量子や古典の最適化アルゴリズムの研究者の皆様へ：

 量子最適化ワーキング・グループの新しい論文では、「難題デカスロン」に含まれる10個の最適化ベンチマーク問題（のどれか）でアルゴリズムをテストし、結果をオープンソースの Quantum Optimization Benchmarking Library (QOBLIB) に提出するよう呼びかけています。

そのようにして貢献をしていただくと、提出した結果が量子のものであっても古典であっても、最適化アルゴリズム研究の最先端を前進させ、最適化における量子的優位性の達成の実現に役立ちます。

昨年、量子最適化ワーキング・グループは、最適化における量子優位性を定義し発見する取り組みについてホワイトペーパーをNature Reviews Physics誌に発表しました。今年は、その取り組みをさらに進め、私たちが「難題デカスロン」と呼ぶものを詳述した新しい論文を発表しています。これは最先端の量子手法と古典手法の限界を研究者がテストできるように設計された10個の最適化問題クラスで構成されています。このホワイトペーパーで説明している最適化問題は、研究者がベンチマーク結果を提出・追跡・比較するためのオープンソース・リポジトリQuantum Optimization Benchmarking Library (QOBLIB) の基礎を形成しています。今、私たちは研究者の皆様のご協力を必要としています。

組み合わせ最適化問題は、選択肢となる解の離散的な集合から、問題に対する最良の解を見つけることをタスクとする数学の分野です。私たちは最適化技術を使って、業界や科学分野を超えてさまざまな価値ある問題に取り組んでいます。しかし、現実の最適化問題の多くでは、証明可能な最適解を見つけることは依然として非常に困難です。そのため、このトピックに関する以前のブログで説明したように、最も効果的で広く使用されている量子最適化アルゴリズムや古典最適化アルゴリズムの多くはヒューリスティクスであり、多くの場合、そのテーマに対する深い直感的理解に支えられた「経験則」に基づいて、複雑な問題を効率的に解決しています。

定義上、ヒューリスティック・アルゴリズムは先験的な性能保証をできないため、どの問題をうまく解決するかを事前に判断することは通常できません。多くの場合、実用的な目的に「十分良い」解を生み出すことができますが、量子優位性の事例を特定したいという今のような場合には、チャレンジングで実用的な意義を持ったたくさんの問題を実際の量子ハードウェアで広範にテストする必要があります。

この新しいQuantum Optimization Benchmarking Library (QOBLIB)には、最適化研究者が協力して量子と古典最適化手法の両方を評価・推進できる一元化されたリソースとテストの場が構築されました。この作業は、一人の研究者や一つの研究機関が成し遂げるには、対象の問題や方法が多すぎます。そのためQOBLIBは、量子最適化ワーキング・グループと、より広範な最適化研究コミュニティーの専門知識を結集して分野を前進させるために構築されました。

量子最適化ワーキング・グループは、IBM®が協力パートナーと立ち上げた5つの量子ワーキング・グループの一つであり、価値ある量子優位性を提供する強力な可能性を秘めた領域で量子アルゴリズム開発を促進することを目的としています。この新しい最適化ベンチマーク論文は、Zuse Institute Berlin、Technische Universität Berlin、Purdue University、National University of Singapore、E.ON Digital Technology GmbH、Kipu Quantum GmbH、Forschungszentrum Jülich (the Jülich Research Center)、南カリフォルニア大学、IBM Quantum®など、多数のメンバー組織の研究者によって執筆されました。

QOBLIBのベンチマーク問題は、モデルやアルゴリズムやハードウェアに依存しないため、あらゆる種類の量子/古典計算ハードウェアにデプロイされた任意の量子/古典最適化手法でチャレンジしてみることができます。さまざまな最適化アルゴリズムでこれらの問題に挑戦し、一般公開されているオープンソースのQOBLIBリポジトリに解を提出することで、組み合わせ最適化問題において実用的に意義ある量子優位性を発見する歩みをコミュニティーは加速させることができるものと、私たちは信じています。ただし、そのためには本物の研究者の協力が得られることが条件です。もし読者のあなたが、最適化アルゴリズムに研究経験がある研究者や実務家なら、まさにあなたのような方のご協力が必要だということです。

一般に量子コンピューティングとコンピューター・サイエンスにおけるベンチマークの目標は何でしょうか？それは、特定のプラットフォームまたは特定のシステム上の決まった問題に対して決められたアルゴリズムを実行する、より良い方法を決定することでしょうか？あるいは、ボトルネックを特定して、どのようにスケーリングできるかを理解することで、特定のアルゴリズムを改善するより良い戦略を見つけることでしょうか？はたまた、量子であろうと古典であろうと、特定のアプリケーション問題に取り組むのに最善の方法を選び出すことでしょうか？

システムやアルゴリズムのベンチマークは、問題や問題解決方法の特定のモデリング・アプローチに限定されている場合、つまりモデルまたはアルゴリズムが固定されている場合でも、非常に価値があります。アプリケーションのベンチマークはモデルに依存しない必要がありますが、量子優位性を追求する上で最も重要なのはアプリケーションのベンチマークです。つまるところ、ベンチマークが、問題の定式化と解決のためのあらゆるアプローチに対応可能である場合にのみ、量子優位性は示すことができます。

長年にわたり、研究コミュニティーは最適化ベンチマーキングにおいて優れた成果をあげてきました。しかしこれまでの先行研究は、主にシステムとアルゴリズムのベンチマークに重点を置いてきたため、モデルに依存する傾向があります。私たちの新しい論文の背後にある主要な目標の一つは、最適化アプリケーションのためのモデル非依存ベンチマークの一般的な不足を補うことです。モデル非依存ベンチマークの開発は、最適化問題クラスとそれに対する解法に膨大な多様性と複雑さが存在することで、確かに難題ではありますが、量子優位性を追求するためには克服しなければならない課題です。

任意のアプリケーション・ドメインにおける量子優位性の主張は、二つの重要な基準を満たさなければなりません。まず、その主張は、すべての既知の古典手法にとって本当に難しい問題に関してである必要があります。古典コンピューターが妥当な時間とコストで十分に優れた解を提示できるのであれば、量子コンピューターを使用する意味はありません。次に、量子アルゴリズムと量子ハードウェアが、既知のすべての古典代替手段よりも効率的、正確、または低コストで問題を解決できることを示す必要があります。

概して両方の基準を満たす最適化問題を見つけることは非常に困難です。現実のビジネスや科学的問題と関連性がある未解決の最適化問題が発表されることはほとんどありません。研究者は、これらの一見解決できない問題を放棄して、その代わりに一部の実用的なユースケースで「十分良い」解がある単純化バージョンに置き換える傾向があります。しかし、単純化にはしばしば品質が犠牲になります。単純化への依存を減らして、より複雑な問題を解くことがもしできれば、実際には最適化の効果を高めることができます。

私たちの「難題デカスロン」は、比較的小さな問題サイズでありながら最先端の最適化ソルバーにとって難しい、科学的および実用的に興味深い最適化問題の最初のコレクションであると私たちは信じています。また、これらの問題は、その能力が高まっているにもかかわらず、量子ビット数や実行できる量子回路の長さの点でまだ限界がある短期的な量子デバイスでの探求に適しているという点でも際立っています。これらが組み合わせ最適化で量子優位性をもたらす問題であるという保証はありません。しかし、これらは量子優位性が見出される可能性があると信じられる領域の力強いヒントになっています。私たちはこの領域での量子優位性の探索を容易にし、あらゆる種類の量子手法と古典手法の間で公正な比較を可能にするように、明確に定義された指標を提供します。

新しい最適化ベンチマーク論文は、各問題クラスについて、有用な背景情報の簡単な要約、きちんとした問題記述、オープンソースQuantum Optimization Benchmarking Libraryで実験用に提供される特定の問題インスタンスの説明、研究者が量子手法と古典手法の比較を容易にするための古典ベースライン結果をあわせて提示し、詳しく説明しています。また、一部の問題については量子ベースラインの結果も含まれています。現在、最適化コミュニティーからの貢献が求められています。最適化アルゴリズムに取り組んだことのある研究者や実務家である読者の皆様はぜひご協力をお願いします。

QOBLIBリポジトリでは、各問題クラスについてサイズと複雑さのレベルの異なる複数の問題インスタンスを提供していますが、古典では困難なレベルの問題インスタンスも含まれています。この複数レベルの提供によって、量子優位性に向けてアルゴリズムとハードウェアの進捗が追跡できるようになっています。また、異なる量子手法と古典手法の公正な比較を可能にするために、明確な評価基準を備えた提出テンプレートも提供しています。選択された評価基準には、達成された解の品質、合計ウォール・クロック時間、および使用されたすべての計算リソース（古典および量子）が含まれます。

このリポジトリで研究者は、混合整数計画法（MIP）と二次制約なし二値変数最適化問題(QUBO)の両方のレファレンス・モデルにアクセスでき、これらを古典ベースライン結果と組み合わせて使って最新の量子アルゴリズムを分析することができます。MIPとQUBOは、最適化問題を定式化する二つの異なる方法であり、MIP定式化は古典研究者にとって基本的なエントリーポイントとして機能することが多い一方で、QUBOは量子研究者にとって同じ役割を果たします。

結局のところ、量子優位性を実証するためには、研究者が特定の種類のモデリングに限定されないで、任意の方法で問題に取り組めることが条件になります。MIPとQUBOは、問題を定式化する形式の一例にすぎず、それらの最適性について私たちは何の主張もしません。これらはあくまで、研究者が利用し、より適した量子処理、あるいはより優れた古典解法を可能にするかもしれない全く新しい定式化を開発するためのインスピレーションとして使える出発点として提示するものです。

原文ブログには、変数の数が増えるにつれて、各問題クラスの MIPレファレンス・モデルと QUBOレファレンス・モデルの密度がどのように変化するかを表した図があります。MIPをQUBO定式化にマッピングするプロセスが状況をどのように変化させるかが興味深いポイントです。多くの場合、このマッピングにより、変数の数、問題の密度、係数の範囲が増加し、すべてモデルの複雑さの増大に寄与します。これらの図は、「難題デカスロン」の地図と考えることができ、問題の広がる空間をナビゲートし、取り組み始めるのに最適な場所を見つけるのに役立ちます。

最適化分野における量子優位性の可能性は非常にリアルで、「難題デカスロン」で提示した10個の問題クラスで私たちはその可能性を実現する重要な一歩を踏み出しています。しかし、この旅はまだ始まったばかりで、探求すべき問題やアルゴリズムは非常に多様であるため、個人や機関が単独でそれを成し遂げることはできないと私たちは知っています。最適化における量子優位性は、コミュニティーが協力して初めて達成できるのです。

もしあなたが量子最適化アルゴリズムまたは古典最適化アルゴリズムの専門家であるならば、QOBLIBで概説されている問題クラスに対する量子および古典最適化手法の性能をテスト・分析するコミュニティーの取り組みに、ぜひご参加いただきたいと思います。モデルとアルゴリズムを改良して最先端技術を進歩させるために継続的に取り組んでいく必要があります。これらのベンチマーク問題を、長年にわたって確立されてきたアルゴリズムと、強力な新規アルゴリズムのどちらでもテストし、結果をQOBLIBに提出していただければ、量子優位性の最初の実証をもたらす可能性のあるプロジェクトに直接貢献していただくことができます。

量子コンピューター上で最適化問題を解く完全なワークフロー例は、QAOA、Advanced techniques for QAOA、Pauli Correlation Encoding for MaxcutについてのIBM Quantum Platformチュートリアルで紹介されています。QAOAについての平易な紹介や、ハードウェア実験で最高の性能を得るためのより高度なテクニックについてAdvanced techniques for QAOAやPauli Correlation Encoding for Maxcutをぜひご参照ください。

協業によって、数学的最適化の分野を計算の新時代へと導き、価値があっても古典手法だけでは解決できないような問題を世界で解決するのを助けることができます。ぜひホワイトペーパーを読んで、オープンソースのQOBLIBリポジトリを探索して始めてみてください。 🚀

この記事は英語版IBM Researchブログ「New Quantum Optimization Benchmarking Library invites researchers to put algorithms to the test」（2025年5月14日公開）を翻訳し一部更新したものです。