[challenge]: The exact approximability threshold of Quantum Max Cut

Released by

Jie Wang (AMSS, Chinese Academy of Sciences) & Jin-Guo Liu (Hong Kong University of Science and Technology (Guangzhou))

Contact email

cacate0129@gmail.com

Method

Other

Challenge issue

Difficulty: ★★★ (rated by Jie Wang)

Background

Quantum Max Cut is the flagship problem of Hamiltonian approximation. Best rounding algorithms sit near 0.6 (arXiv:2504.11120, arXiv:2512.09896, arXiv:2309.10957); NP-hardness of approximation is known (arXiv:2510.07995); swap-algebra exactness results suggest the ncSoS hierarchy is the right lens (arXiv:2307.15688, arXiv:2206.08342). The classical analogue — Goemans–Williamson optimality under UGC — shaped a generation of approximation theory.

Research objective

Close the gap: determine the optimal polynomial-time approximation ratio. Two coordinated loops: (i) rounding-scheme search over product+entangled ansatz families with per-scheme worst-case ratios certified by SOS identities on the dual; (ii) hardness-gadget search with soundness/completeness certified by exact diagonalization of constant-size gadgets.

Verification plan

• Success gate: a rounding scheme whose ratio r is proved by an exact SOS identity, plus a gadget reduction achieving hardness at r + ε for vanishing ε — matching constants verified independently; they either meet or they don't.
• Hope signal: certified ratio improvements on structured graph classes (triangle-free, bipartite) — each a standalone paper.
• Pivot signal: evidence the threshold depends on UGC-like assumptions — reframe as a conditional-threshold paper; the precise conjecture is the contribution.

Why this may lead to research output

The quantum Grothendieck-constant story in the making — the definitive answer would anchor quantum approximation theory the way GW anchors classical.

References

1. Gribling et al., Improved approximation ratios for Quantum Max-Cut, arXiv:2504.11120.
2. Apte et al., A 0.8395-approximation algorithm for the EPR problem, arXiv:2512.09896.
3. Piddock et al., Quantum Max-Cut is NP-hard to approximate, arXiv:2510.07995.
4. Takahashi et al., SU(2)-symmetric hierarchy for QMC, arXiv:2307.15688.

No repository files, tests, or entry points are named. Start with the research objective and the cited Quantum Max Cut papers; done means either an SOS-certified rounding ratio and matching hardness gadget, or a clearly justified conditional-threshold result.