変分的な量子ビット効率の良い MaxCut ヒューリスティックアルゴリズム

小さな量子チップが大きな難問で重要な理由

回路配置から物質のモデリングに至るまで、多くの実世界の課題はネットワークを二つのグループに分け、グループ間で切断される辺の数を最大化する問題に還元されます。この課題は MaxCut として知られ、従来のコンピュータでは非常に難しい問題です。本稿は、少数の量子ビット（キュービット）だけで驚くほど大きなネットワークを扱える、量子に着想を得た新しい手法を紹介し、量子および古典の最適化手法の評価と改善に新たな道を提供します。

ネットワークを有用な二分に切る

MaxCut は一見単純な問いを投げかけます。点（ノード）とそれらを結ぶ線（辺）があるとき、各ノードを青または白のように塗り分けて、異なる色どうしを結ぶ辺をできるだけ多くするにはどうすればいいか、というものです。この最良の分割は回路設計や統計物理学などで有用ですが、ネットワークが大きくなると厳密解を見つけるのは非常に困難です。古典的によく使われる手法である Goemans–Williamson（GW）アルゴリズムは問題を巧妙に緩和しており、真の最適解の少なくとも約88％の性能を保証します。量子計算はこうした問題に新たなアプローチをもたらす可能性がありますが、現行のデバイスはノイズが多く規模も限られているため、大きく深い回路を実行するのは難しいのが現状です。

わずかなキュービットで大規模グラフを解く

Quantum Approximate Optimization Algorithm（QAOA）などの標準的な量子アプローチはノードごとに1つのキュービットを必要とするため、1,000ノードのグラフには1,000個のキュービットが必要になり、現状の機械ではとても実現できません。新手法「Qubit-Efficient MaxCut（QEMC）」はこのスケーリングを逆転させます：必要なのはノード数の対数程度のキュービットだけで、例えば11キュービットで2,000以上のノードに関する情報を符号化できます。各キュービットを単一ノードに対応させるのではなく、QEMC は小さなレジスタの全体の量子状態をコンパクトなアドレス空間として用い、異なるノードをレジスタの異なる基底状態に対応させます。このキュービット節約により回路は浅くなり、ノイズの多いハードウェア上でも実行しやすく、それでも非常に大きなグラフを表現できます。

固定状態ではなく確率でノードを塗り分ける

QEMC の主要な革新点は、各ノードの“色”の符号化方法です。各ノードを単一の量子状態で厳密に青か白かに決める代わりに、ノードの色は測定で観測される確率から推定されます。ある基底状態が観測される確率が低ければ一方の色に、確率が高ければもう一方の色に割り当てる、というふうにしきい値で二つの領域を分けます。これにより、多くの異なる量子状態が実質的に同じグラフ分割に対応します。QEMC が最小化するコスト関数は、つながったノードが確率のしきい値の反対側に配置されることを促すように設計されており、結果として色の異なるグループ間を横切る辺の数が増え、カットが改善されやすくなります。

実機とシミュレーションで性能を検証

著者らは QEMC を実際の量子プロセッサと量子回路の古典的シミュレーションの両面で検証しています。2〜5キュービットで扱える最大32ノードの小さな正則グラフでは、IBM の超伝導ハードウェア上で実行した QEMC が全探索で得られる最良解と一致するかほぼ一致するカットを見つけ、ランダム推定や従来の QAOA に基づく量子研究を明らかに上回りました。ノイズのないシミュレーションでは、これら小規模グラフに対して QEMC は一貫して最適カットの97％以上を達成しました。符号化方式の強みはより大規模なグラフでさらに明確になります：最大2,048ノードの9正則グラフに関する古典シミュレーションでも、QEMC は平均および最良カットで GW を数パーセント上回り、異なる密度の128ノードのランダムグラフでも同様の優位が見られました。

速度、制約、そして量子インスパイアドの可能性

成功を収めているとはいえ、QEMC が正式な量子優越を示したわけではありません。対数的なキュービット数しか使わないため、その回路を古典的にシミュレートするコストはノード数にほぼ線形にスケールし、コスト関数の評価時間は辺の数に応じて増加します。経験的な研究では、GW レベルの性能に到達する総時間はグラフサイズに対しておおむね二次的に増加することが示唆されており、多くの問題で実用的な範囲に収まります。したがって現状の QEMC は、量子優位の証明というよりは強力な量子インスパイアドなヒューリスティックとしての役割を果たします。

この研究が未来に意味すること

専門外の読者にとっての主なメッセージは、小さくノイズの多い量子デバイスでも、その強みに合わせたアルゴリズムを設計すれば科学的に有用であり得るという点です。ノードの色を硬直したビット値ではなく柔軟な確率領域で符号化することで、QEMC は非常に少ないキュービットで大規模なネットワーク問題に取り組み、ハードウェアノイズに自然に耐性を持ちます。この手法は量子最適化アルゴリズムの試験の新たなベンチマークを設定すると同時に、同じ考えに基づく実用的な古典アルゴリズムも生み出します。より広く見れば、単により大きな機械を作るのではなく、情報の符号化方法を再考することが、難しい計算問題を解く有望な道を開くことを示しています。

引用: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

キーワード: MaxCut, 量子最適化, 変分アルゴリズム, グラフ分割, 量子インスパイアド計算