← All problems

FGG conjecture for QAOA on the ring of disagrees

12 years old · traced to

For an even cycle of size NN and depth pp satisfying 2p+2≤N2p+2\leq N, is the optimal QAOA approximation ratio for MaxCut exactly

2p+12p+2 ?\frac{2p+1}{2p+2}\,?
References

Progress summary

Refreshed
Open · solution reported

A 2026 manuscript claims to prove the predicted ratio for the ring of disagrees, but the claim has not yet been independently confirmed.

The FGG conjecture asks whether, for even cycle size NN with 2p+2≤N2p+2\leq N, depth-pp QAOA achieves exactly the ratio 2p+12p+2\frac{2p+1}{2p+2}. Farhi, Goldstone, and Gutmann predicted the value numerically and proved the case p=1p=1.

Known results

  • FGG proved p=1p=1.
  • Wang et al. proved p=2p=2 using an exact fermionic analysis.
  • Mbeng, Fazio, and Santoro derived the general momentum-mode decomposition and numerical saturation through p=128p=128, but did not prove attainability when 2p+2≤N2p+2\leq N.

Claimed machine-verified proof

The manuscript claims a universal lower bound and an explicit polynomial-interpolation construction attaining residual energy 12p+2\frac{1}{2p+2}, thereby proving the conjecture. It says Claude Fable 5 generated the decisive argument; independent mathematical confirmation is not yet reported.

Sources

Solutions 0

No solutions have been posted yet.