量子コンピューターはディシジョンメーカー（意思決定者）にとって優れた道具になるでしょうか？量子最適化ワーキング・グループの新しい研究が今後の道筋を示しています。
研究者たちは長い間、量子コンピューターが、実用的な価値のある最適化問題を、純粋に古典計算のみを用いた手法を超えるレベルでいつか解決できる可能性があると示唆してきました。最適化問題は至る所に存在します。最適化問題は金融市場を形作り、エネルギーグリッドを動かし、さらには帰宅経路や夕食の配達経路を決めるモバイル・アプリにさえも使われています。しかし、本当に量子手法を必要とするのはどんな最適化問題でしょうか？量子コンピューティングは古典ソルバーを超えた本当のインパクトをどんなところで生み出せるのでしょうか？
Nature Computational Scienceの表紙を飾った量子最適化ワーキング・グループの最新論文は、この探求の新たな興味深い道筋を示しています。この論文は、よく知られた量子近似最適化アルゴリズム（QAOA、quantum approximate optimization algorithm）を基盤とした新しいアルゴリズムである量子近似多目的最適化（QAMOO、quantum approximate multi-objective optimization）手法を導入して、複数の競合する目的関数をバランス調整する必要があるような複雑な問題に適用しています。Zuse Institute Berlin、ロスアラモス国立研究所、IBMの研究者で構成された著者グループは、このQAMOO法は産業界や科学界全体で非常に重要な意義を持っており、組合せ最適化分野における短期的な量子優位性の最も有望な提案の一つであると述べています。
組合せ最適化とは、実行可能な離散的選択肢の中から最良の選択を見つけることです。この種の問題は特に、可能な解の選択肢が膨大である場合や、複雑な制約を満たす必要がある場合には、古典計算手法にとって非常に難しい問題になります。
そのような難しさにもかかわらず、最適化コミュニティーは、数多くある実際の最適化問題に対して「十分に良い」解が得られる多くの強力な古典アルゴリズムを開発してきました。このことは、量子最適化で達成しなければいけないゴール水準を引き上げています。量子手法が産業的に価値を持つためには、古典手法がうまくいかないような難しい、実用的価値のある現実問題に対して画期的なブレイクスルーをもたらす必要があります。
そのような点で多目的最適化には注目する意味があります。このクラスの問題は、最適化分野で量子優位性を探す上で、可能性の高い「スイートスポット」と考えられます。なぜならこの問題は、実用的でアルゴリズム的に難しいだけでなく、量子計算手法を用いた探求にも適したコンピューティングの問題として取り組む必要があるからです。
そして実際にこれまで得られた初期の結果は、まださらなる調査とベンチマークは必要ではあるものの、QAMOO法が特定の条件下で古典手法を上回る可能性があることを示しています。
今日の古典計算手法は、目的関数（評価基準）が単一の最適化問題に取り組む際にはしばしば非常に効果的です。単一目的の最適化問題とは、可能な解（選択肢）の集合を分析し、単一の目的関数を最大化するのに最適な選択肢を特定する問題です。たとえば金融分野の「期待リターンを最大化する投資ポートフォリオを構築しなさい」という問題が一例です。
しかし、このような問題を単一目的として解くには、リスク、流動性、取引コスト、規制要件といった期待リターン以外の要素を無視するか（それによって実世界での価値は損なわれることになります）、これらの要素について目標値を設定してそれを最適化問題の制約として扱う必要があります。
「一定のリスクレベルを超えずに期待リターンを最大化する投資ポートフォリオを構築せよ」が、この後者のアプローチの簡単な例となります。このようにして目的を単一にしてしまえば問題は解決しやすくなりますが、現実の最適化問題はそれほど単純ではありません。
多目的最適化問題ははるかに複雑で、私たちが日々直面する現実世界の問題をよりよく反映しています。多目的最適化問題では、単一の目的を達成する単一の解ではなく、相反する目的間のさまざまなトレードオフを表す多様な解の集合を求める必要があります。競合する目的間の最適なトレードオフの全集合をパレートフロントと呼びます。パレートフロントを構成する全ての解は、そのどれも、目的のうちのどれか一つについて改善できたとしても少なくとも他の一つの目的については悪化するという意味での最適解になっています（たとえばあるパレート解があったとして、その解を少し変えてそれが持つリスクを改善しようとしたら、代わりに期待リターンが悪化することを容認しなければならない、など）。
数学的には、パレートフロントのすべての解は同等に有効です。パレートフロントは、たとえるならば、投資マネージャーが、顧客が容認できるリスクの多寡に応じて、期待リターンのレベルが異なる投資オプションを複数そろえて提示するようなものです。その中から「最良」の選択肢を決めるには、意思決定者の好みや優先順位が必要です。
多目的問題が計算的に非常に難しい理由は容易に理解できます。古典手法では、たった一つの目的に対して組合せ解空間を探求するだけでも十分に難しいですわけですが、多目的最適化問題として扱って、そこにリスクの最小化やセクター間でのアセット分散など、新たな目的を追加するたびに、さらに複雑さの次元が計算に加わります。
複数の目的がある場合、解の選択肢の数は同じままですが、他のすべての解よりも客観的に優れている単一の最適解が存在するとはもはや言えません。その代わりに、それぞれ異なる点で最適とみなせる解で構成される非常に大きな解集合、すなわちパレートフロントが定義されます。
今の現場で古典最適化の専門家は、多目的問題を制約付きの単一目的の定式化に変換することで単純化するという方法を、実務的によく使っています。このアプローチは古典手法で扱いやすくする現実的な方法ではありますが、問題に実際に取り組みたい人（意思決定者）がこのアプローチを使おうとしたら、直感や専門知識に基づいた選択を強いられるので、より良いトレードオフの機会を見逃す可能性があります。
たとえば、ポートフォリオ最適化の取り組みをリスク最小化の目的に絞って解くとしましょう。そのためには投資収益の最大化というもう一つの競合する目的を制約として再定義することになります。たとえば、恣意的に決めた5%のリターン率が得られることを制約条件とする、などです。
こうすれば古典手法で扱いやすい問題にはなりますが、こうすることによってもっと良い解を見逃してしまっていないと自信を持って言えるでしょうか？もしかしたらリターン率をわずかだけ落とし4.9%に妥協することで、リスクを大幅に低くする解が得られる可能性はありませんでしょうか。本来はそのような可能性がありますが、単一の目的に限定した定式化では、その可能性を探求する柔軟性は得られません。
このような問題を2目的最適化問題として解決できる古典手法も多く存在します。しかし、二つ以上に目的を追加していくと、すぐに問題は複雑になりすぎて古典手法では扱えなくなります。
一方で、パレートフロントの全体をもし捉えることができれば、情報に基づいた意思決定ができ、より良い結果を得ることができます。ところがそうしようにも効率的にそれを行うことは古典計算のみの手法では困難でした。最適化研究者は、例えば二つまたは三つの目的を持つ問題を解決できる手法を開発してきましたが、目的の数が増えるにつれて計算難易度が急激に上がり、すぐに古典計算のみを用いた手法ではまったく扱えなくなってしまいます。
量子コンピューターは本質的に、多くの異なる解を迅速に返すことができるサンプリング・マシンであるため、広大な解空間の探索に長けています。量子コンピューターから情報を引き出すには、測定を行う必要があります。量子回路で使われる各量子ビットを測定し、その結果である0と1の並びが、量子回路の出力、つまり「サンプル」を表すビット列を形成します。
量子シミュレーションの問題で、量子系の観測値（オブザーバブル）の期待値を計算したい場合には、それら個々のサンプルだけでは役に立ちません。期待値の有用な推定値を得るためには、たとえば100万回の測定を行って、得られたすべてのデータを集約する必要があるかもしれません。しかし最適化問題の場合、サンプリングした各ビット文字列が最適化問題の潜在的な解を表します。つまり、出力ひとつひとつが貴重な洞察をもたらす可能性を持った有益な情報であるということです。
この性質があるため、サンプリングは多目的最適化問題において有力なアプローチとなります。多目的最適化問題でのゴールは完璧な解をひとつ見つけることではありません。さまざまなトレードオフをカバーする、良質な多様な解の集合を生成することです。QAOAはそのような多様性を自然に実現します。そしてサンプリング・アプリケーションは正確な期待値を必要とする回路に比べて、ハードウェア・ノイズの影響を緩和するのに必要なオーバーヘッドがしばしばはるかに低く済みます。
詳細については、以前の最適化ブログや、量子サンプリング・アプリケーションに対するノイズの影響を調査したこちらの2024年の論文をご覧ください。
サンプリングは量子コンピューターでできる最も基本的な操作です。他のすべての量子アプリケーションは最終的にそこから派生しています。つまり、量子コンピューターは、高速サンプリングが必要で、結果へのノイズの影響に許容範囲があるタスクに適しています。そして、多目的最適化問題はまさにそのような性質を持っています。
多目的最適化問題を解くために、QAMOOアルゴリズムはまず問題の複数の目的を別々の制約なし二項最適化問題に変換します。これは、すべての制約を目的に組み込んだ、2進変数（0 or 1）の式として定式化できる一種の最適化問題です。この変換により問題は、量子コンピューターでアプローチ可能な、多目的で、制約のない二項最適化問題に変換されます。
制約のない二値最適化問題は、古典最適化ソルバーやQAOA（量子近似最適化アルゴリズム）のような量子最適化アルゴリズムの両方で自然に扱うことができるため、量子最適化で広く研究されています。QAMOOの論文では、特に「二次制約なし二項最適化(QUBO)」を用いています。ただし、最近の研究ではQAOAの高次問題への適用可能性が探られており、多目的最適化の手法は高次問題にも応用可能です。
次にQAMOOは、元の複数目的のパラメーター化された重み付け和を用いて、単一目的のQAOA回路を定義します。言い換えれば、このアルゴリズムが本質的にしていることは、目的のそれぞれに、調整可能なパラメーターで重み付けをした上で、一つの値に統合するということです。ここで、ある目的を重み付けするパラメーターは、後で、他の目的に対するその目的の相対的な重要度を表現するのに使われます。
このプロセスによって多目的問題は、重み付けパラメーターによってそれぞれが定義された単一目的問題の集合に変換されます。ここで、それら個々の単一目的問題は、QAOAで解決可能なものです。次に、QAOA回路のパラメーター（重み付きパラメーターとは別）を、代表的と考えられる、目的の重み付き組み合わせの１インスタンスに対して一度だけ最適化します。
私たちの研究では、フルスケールの問題よりも小さい代表的な訓練インスタンスを生成することができ、回路パラメーターを古典計算で最適化することを選びました。古典コンピューターは、少なくとも回路が比較的単純な場合には、パラメーター最適化のタスクにおいて量子コンピューターよりもはるかに高速かつ信頼性が高いことがあります。
それは、量子回路の訓練がサンプリングよりも簡単だからであり、それはまた量子回路の訓練を近似することが容易だからです。また、回路パラメーターを小規模インスタンスで訓練しておき、似たインスタンスであれば大きなインスタンスに転移することも可能です。これにより、古典でパラメーター訓練をして量子サンプリングをするというワークフローは、より大きな問題スケールでも有用なパターンとなります。
最適化パラメーターが設定されると、QAMOOはそれらを多くの異なる重みの組み合わせに適用します。それぞれの重みが、元の目的間の異なるバランスを表すことで、トレードオフの効率的な探索を可能にします。各重みセットは目的の新しい組み合わせを作成し、事前訓練済みQAOA回路がそれぞれから解をサンプリングします。
このアプローチにより、重み付けごとに回路を毎回訓練しなおすことなく、さまざまなトレードオフを探ることが容易になります。これらのサンプリング解はパレートフロントの近似を形成します。QAMOOは一つの良い答えだけを提供するのではなく、高品質な解のメニューを提供します。それを見て意思決定者は全体像を評価し、自分のニーズに最も合った選択肢を選ぶことができます。
QAMOO論文では、IBM Quantumハードウェアと古典シミュレーターの両方を用いて、広く研究されている最適化問題であるMax-Cut問題の多目的バージョンでアルゴリズムを評価しました。結果は、量子シミュレーションが従来の古典手法よりも速く、高い解品質を達成することを示しています。ハードウェア実機での実行も同様の傾向を示しましたが、デバイス・ノイズの影響でアルゴリズムの速度がやや遅くなりました。
原文ブログにある図では、QAMOO法の古典シミュレーション、量子ハードウェア実機での実行、そして主要な古典最適化ソルバーを比較した結果を見ることができます。図は、多目的Max-Cut最適化問題に対する各手法のパフォーマンスを示しています。特に、QAMOO論文でテストされた中で最も層の多い、6層の演算を持つQAOA回路を用いたQAMOO法実行の結果を示しています。
図の上部にある赤い点線は、この問題の最もよく知られた解、すなわち可能な超体積（HV）の最大値を表します。すなわち、解の集合がパレートフロントをどれだけうまく近似できているかの指標です。実線の青線はQAMOOアルゴリズムの古典シミュレーションを表し、破線（ibm_fez）は量子ハードウェアの実行、点線はそれぞれ異なる古典ソルバーを表します。
全体として、シミュレーションされたQAMOOの実行は古典ソルバーよりも速く最適解に到達していることを示しています。古典ソルバーのうちの一つは与えられた時間内に最適解に到達できませんでした。QAMOOアルゴリズムは量子ハードウェア実機上で実行された際にも最適解に達しました。さらに将来的には量子コンピューターの成熟とエラー率の低下に伴い、その性能は大幅に向上すると期待されます。
QAMOO法を量子最適化ワーキング・グループは、最適化分野における短期的な量子優位性の有力候補と見なしています。量子ハードウェアの継続的な改良により、その利点はさらに増幅され、競合する目的間の微妙なトレードオフをよりよく表現する、より深く複雑な回路が実行可能になるでしょう。
長期的には、QAMOOアルゴリズムは非常に重要で、金融や物流から医療や消費者向けテクノロジーに至るまで幅広いユースケースで大きな価値をもたらす可能性があります。数十億ドル規模の企業であれ、最小限の有料道路代でなるべく早く帰宅しようとする人であれ、私たちは皆、多目的最適化の問題に囲まれています。良質で多様な解を提供するツールへのアクセスは、目標にコミットする前にトレードオフを探る方法に根本的な変化をもたらす可能性があります。
しかし、この未来を実現するには、QAMOOアルゴリズムを最も強力で洗練された最先端の古典最適化手法と比較する、広範かつ厳密なテストを行う必要があります。古典アルゴリズムの研究者には、純粋な古典手法でQAMOO法を上回るために最善を尽くしてもらう必要があります。最適化における量子優位性の最初の実証に向けた、今まさに行われている旅路において、このような量子手法と古典手法の友好的な競争が不可欠な役割を果たしていきます。