Max-Cut

Max-Cut

執筆済 最適化組合せ最適化Max-Cut

グラフの頂点を 2 つに分け、両側をまたぐ辺の重みの合計を最大にする問題。

maxs∈{−1,+1}n⁡12∑(i,j)∈Ewij(1−sisj)

si がどちら側に属するかを表す。

なぜよく出てくるのか#

イジング模型そのものだから。上式を整理すると

const−12∑(i,j)wijsisj

となり、イジング模型の エネルギー最小化と一致する。変換も近似も要らず、 そのまま量子ハードウェアの問題になる。

このため QAOA の性能評価では Max-Cut が事実上の標準ベンチマークになっている。

近似の到達点#

Goemans と Williamson は、半正定値計画 (SDP) に緩和してから ランダム超平面で丸める手法により、 最適値の 0.87856 倍以上を保証した。

さらに、Unique Games 予想が正しければ、 多項式時間でこれを超える近似は不可能であることが示されている。 つまり 0.878 は理論的な限界に到達している可能性が高い。

QAOA の評価で気をつけること

QAOA の近似比を報告する論文は多いが、 浅い層では 0.878 に届かないことがほとんど。 「量子だから優れている」ではなく、 古典の SDP 緩和という強い基準線と比べる必要がある。

参考文献#