数理最適化における量子優位性の探求

量子最適化ワーキンググループのメンバーが発表したホワイトペーパーは、現実的な組み合わせ最適化問題での量子コンピューターの価値の可能性について新たな視点を提供しています。

最適化の問題は、私たちの生活のあらゆる側面に関わっています。用事を済ませる時に一番時間を節約できる順番を決めたり、地図アプリを使って渋滞を避ける最短ルートを見つけたりするのも最適化問題です。また最適化は、私たちの生活に関わるビジネスにも広く用いられています。たとえばエネルギー・グリッドやサプライチェーンなどの運用においても、安定性、安全性、効率性の確保に不可欠です。

私たちは、これらの最適化問題に対して直感で解を決めたり、過去の経験に基づいて常識的な判断で対応したりすることもあります。しかし考慮しなければならないタスクが複雑である時には、それらを数学で取り組むことができる最適化問題として表現する必要があります。これまでの長年で、組合せ最適化問題を解くための計算手法は、ビジネスや科学において重要な役割を果たすようになり、これらの問題の多くを効率的に解決するのに役立っています。しかし、一部の組み合わせ最適化問題は、最も強力な古典スーパーコンピューターで実行される最先端の方法を使っても、依然として非常に困難です。

量子コンピューターには、最適化問題を解く私たちの能力を高めてくれる可能性があります。しかし、どの量子手法と最適化問題クラスが実用的な量子優位性を達成できるのかはまだわかっていません。量子最適化の分野では、量子最適化アルゴリズムと従来の古典最適化アルゴリズムとの間の公正な性能比較を可能にする体系的で再現性のあるベンチマークが存在しなかったため、そしてまた研究者が現在の量子ハードウェアで実際に実行できる計算に制限があるため、これまでこれらの質問に答えるのは困難でした。量子最適化ワーキンググループの代表者がこの問題に取り組むためにNature Reviews Physicsにホワイトペーパーを発表しました。

このホワイトペーパーは、アムステルダム大学、MIT、Zuse Institute Berlin、IBM、Hartree Centre、E.ON、Wells Fargoなどの企業や学術研究機関の代表者を含む、ワーキンググループのメンバー46人が共著したもので、最適化手法の広範なオーバービューを提供し、そしてさまざまな問題設定における量子優位性を論じ、さらには、既存の量子手法を改善する可能性のあるアプローチを検討しています。ホワイトペーパーで言及されている一つの注目すべき例は、IBM、ロスアラモス国立研究所、およびバーゼル大学が実施した有望な新しい共同研究です。この研究では、Conditional Value at Risk (CVaR) と呼ばれる考え方を量子コンピューターの出力するサンプルに適用して、さまざまな最適化タスクにどのように役立つかを詳しく説明しています。これについては後でまた触れます。

また、このホワイトペーパーでは、量子最適化アルゴリズムに不可欠な構成要素の概要を説明し、量子最適化手法と古典最適化手法の間の有意義な比較を容易にするための明確な評価尺度とベンチマーク問題を提案しています。組合せ最適化の分野での量子優位性については、このホワイトペーパーに先立って研究コミュニティーの一部から疑問が表明されていたのですが、この論文は最適化問題での有用な量子優位性に十分な理論的可能性があると再確認する重要な役割を果たしています。

量子最適化は、量子アルゴリズムの研究において最も誤解され、意見が二分している領域かもしれません。初期には量子コンピューターが、考えられるすべての解決策を並行して探索することで、難しい最適化問題を効率的に解決できると考えられていましたが、この誤解は今でも時折見られます。また、問題のサイズに対して指数関数的にスケーリングしてしまう古典アプローチに比べた時に、量子最適化手法がもたらす高速化は、最大でも2次の高速化であると主張している人もいますが、指数的な実行時間に対して2次の高速化をしたとしてもそれでもまだ指数的な実行時間であるため、最終的にはほとんど価値をもたらしません。

この新しい最適化ホワイトペーパーで著者らは、真実は、よくあることですが、これらの両極端のどちらよりも繊細なところにあると説明しています。量子コンピューターは、少なくとも最適化にすぐに価値をもたらすような形では、すべての解を並行して探索するわけではありません。一方で、量子手法が最適化問題に対して 2次の高速化のみを提供するという仮定は通常、最悪のケースの問題設定での話であって、考えられるすべての代替案よりも優れていることが証明された最適解を見つけなければならないという考え方に基づいています。

現実の世界では、最適化問題の最悪のケースが実際の利用シーンに現れることはめったにありません。これは、これらの問題を理論的な最適性で解くために必要な実行時間がたとえ指数的だとわかっていても、古典アルゴリズムが実際の環境で非常に有用であると経験的に示されている主な理由の1つです。実際に、古典最適化アルゴリズムとヒューリスティクスは、大きな問題サイズであっても、多くの有用な問題に対して適切な解を得ることができているのです。

しかし一方で、より優れた最適化アルゴリズムによって解き放たれる可能性はまだたくさんあります。金融やサプライチェーン管理などの分野では、小さな改善でも大きな成果を得ることができます。古典手法だけで現実世界の問題を解決するには、たとえば、特定の要因を取り除いたり、関連するダイナミクスを近似したりするなど最初に問題を単純化する必要があります。それに対し、単純化が少ない精緻なモデルに対して優れた解を見つけることがもしできれば大きな違いを生む可能性があります。比較的小規模の問題でも、古典アルゴリズムでは良い解を見つけることができない種類の問題があります。

量子コンピューティングは、古典手法では困難な実世界の最適化問題の、少なくとも一部については、私たちの能力を向上させる可能性のある新しいツールと機能を提供してくれます。何らかの意味で質が良かったり、コストが低くかったり、あるいはあらゆる古典手法よりも速かったりするというような、量子アルゴリズムから得られる「十分良い」ソリューションには、非常に高い価値がある可能性があります。

私たちが知る限り、量子コンピューターは、すべての最適化問題のすべての実例に対して指数的高速化を提供することはありません。しかし、量子最適化手法が古典の代替手段よりも指数加速をする一部の特定の問題はわかっています。

たとえば、一部の最適化問題は素因数分解に帰結させることができますが、素因数分解についてショアのアルゴリズムは既知のすべての古典手法に対して指数加速を提供します。これは、量子最適化における指数的優位性の最も有名な例ですが、そのような問題が実際に現れる可能性は低いため、最も有用な例とは言えません。それでも、Googleの研究者による最近の報告のように、実世界との関連性がより高い問題クラスに対して古典手法よりも優れた解決策を効率的に見つけることにおいて同様のスピードアップを約束している他のケースもあり、このような例は量子最適化分野全体にとっての希望になっています。

上記のような理論的性能保証を備えた量子アルゴリズムには、通常、フォールト・トレランスが必要ですが、今日のノイズのあるハードウェアで実行でき、少なくともいくつかの問題に対して優れた解を出力することができる量子最適化アルゴリズムもすでに存在しています。新しいアルゴリズム、あるいは既存のアルゴリズムの新しい変種が発見され、古典手法の品質に匹敵するかそれを凌ぐような、ノイズのあるハードウェアに基づいた量子手法が実現する可能性は十分にあります。

これらのアルゴリズムは通常、ヒューリスティクスですが、特にノイズのある量子コンピューターで実行される場合はなおさらそうです。ヒューリスティクスとは、先験的な性能保証のないアルゴリズムのことで、多くの場合、考慮対象の問題の深く直感的な理解に基づいているか、正確な最適化アルゴリズムの計算を途中で打ち切る形で行われるものです。

ヒューリスティクスは、量子計算にも古典計算にも存在します。実際、私たちが使用しているほとんどの古典最適化アルゴリズムはヒューリスティクスです。遺伝的アルゴリズム、A*サーチ、シミュレーテッド・アニーリングはすべて、開発者が何十年にもわたって使用してきた影響力のある古典最適化手法の例であり、実際にはかなりうまく機能します。

つまり、性能保証がなくても、ヒューリスティクスは悪いことではないということです。多くの場合、解こうとしている問題が量子手法でも古典手法でも難しいことがわかっているため、ヒューリスティクスこそが期待できる最善の手法なのです。必要なのは、古典アルゴリズムが苦手とする問題の一部に対してうまく機能する新しい量子ヒューリスティクスです。したがって、コミュニティーとしての私たちの仕事は、少なくとも一部の問題に対して、どんな古典手法よりも優れた、正確な、近似的な、またはヒューリスティックな量子最適化アルゴリズムを見つけることと、最適化における実用的な量子優位性への道筋を組み立てるための体系的なベンチマークを開発することです。

現在、研究者たちは、エラー緩和と呼ばれる古典計算での後処理の助けを借りて、価値ある特定の問題に対して量子コンピューターを使って正確な期待値を求められることを実証し始めています。測定したい系と属性があった時に、期待値は、量子コンピューターから出力される結果の加重平均です。これらは化学や物理学にとって非常に有用な計算ですが、最適化の場合には、期待値よりもプロセッサーから出力されたサンプルの方に興味があることがよくあります。

今回、Nature Computational Science誌に最近発表された論文では、近い将来にノイズのある量子コンピューターからサンプリングする際に有用な手法に焦点を当てています。具体的には、著者は、量子最適化アルゴリズムでノイズを補正するのに必要なサンプリング・オーバーヘッドを決定する方法を定式化し示しています。この特定のコンテキストでのオーバーヘッドは、期待値の推定量をバイアスなしで取得するのに使用されるエラー緩和手法で必要な計算オーバーヘッドに比べて、はるかに小さいことが判明しています。

言い換えれば、最適化問題に対して妥当な確率で良い解を返すことがわかっている量子回路がある場合、ノイズの影響を打ち消すために必要な追加のサンプル数を定量化できるようになったということです。これは、ノイズの影響を定量化する方法と、それを補正するために何をする必要があるかの両方を本質的に教えてくれる強力な知見です。

これに基づいて、著者たちは、Conditional Value at Risk(CVarR)と呼ばれる関数が、ノイズフリーの期待値についての理論的な境界を与えることができることを示しました。しかも、この場合もオーバーヘッドは、期待値に対するエラー緩和手法よりも大幅に少なくて済みます。

CVaRとは正確には何でしょうか? CVaR (期待ショートフォール)は、金融領域で使用される重要な関数で、分布のテール（裾）に関する情報を提供します。金融では、この数値は投資家にとって、市場が悪化した時に失うと予想される平均金額の指標です。量子最適化のコンテキストでは、ノイズフリーの場合と少なくとも同じくらい良い解を得るためにどれだけサンプリングをする必要があるかがわかっているため、それを使用して目的の期待値の下限と上限を導き出すこともできます。つまり、解きたい最適化問題に対する解として得られる可能性のある最小値を求めるのに有用である可能性があります。

Probabilistic error cancellation (PEC)や zero noise extrapolation (ZNE)などの他のより一般的なエラー緩和手法は、高い計算コストと引き換えに正確な期待値を提供しますが、CVaRは計算コストが少なく、正確な出力ではなく、期待値の境界を提供します。その結果として、量子コンピューターの出力に関するノイズフリーな情報が得られ、これを量子最適化アルゴリズムで使用できます。

CVaRはパラメーター付き回路を訓練するためのロバストな損失関数として2019年に提案され、現在でもよく用いられています。しかし、2019年当時は直感のみに基づいて利用されていました。今回の新しい結果は、CVaRを損失関数として理論的に理解する際のギャップを埋め、パラメーター付き回路の学習に対するエラー緩和能力を実証するものです。

この最近のCVaRの論文で見られるような理論的な結果は、ノイズのあるハードウェア上で量子最適化手法をスケールするための潜在的な方向性を示しています。また、理論的なアプローチが現実で発揮する価値を見出すために、理論的な研究と実証的な研究を組み合わせていくことがいかに重要であるかを強調しています。

古典計算では、完全な理論的理解が得られるよりもだいぶ前から、経験的にうまく機能することが証明されているアルゴリズムの例が数多くあります。量子計算では状況が異なり、量子ハードウェアの能力と可用性が限られているため、歴史的に、量子アルゴリズムは実験的にテストされる前に主に理論的に開発されてきました。

しかし、今すでに、そういった制限はあまり気にしなくてよくなってきています。正確な古典シミュレーション手法を超えて回路を実行できる数百の量子ビットを備えたゲート型量子デバイスに、量子コミュニティーがアクセスできるようになった今日、理論研究と実験的研究を組み合わせた作業をさらに活発化する必要があります。このことは、最適化における量子的優位性への道筋を描くための体系的なベンチマークの重要性も浮き彫りにしています。

私たちは、この分野での継続的な進歩を期待しています。組み合わせ最適化における量子優位性への道筋についての詳細な視点については、Nature Reviews Physicsに掲載された量子最適化ワーキンググループのホワイトペーパーや、Nature Computational Scienceに掲載されたCVaR論文をご参照ください。それ以外の他の量子ワーキンググループの詳細については以前のブログをご覧ください。

この記事は英語版IBM Researchブログ「Exploring the potential for quantum advantage in mathematical optimization」（2025年2月5日公開）を翻訳し一部更新したものです。