[challenge]: Low-level SOS for all 2-local Hamiltonians: a quantum PCP data point

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

Does constant level (2 or 3) of the NC-SOS hierarchy achieve a constant-factor approximation to the ground energy of every (suitably normalized) 2-local Hamiltonian? Product-state approximations give guarantees for positive-term Hamiltonians (arXiv:2206.08342); hardness results bound the other side (arXiv:2510.07995); level-wise analyses exist for specific models (arXiv:2311.09010). A universal low-level guarantee would collide with quantum-PCP-style hardness; a fooling family would be the first strong NC-SOS integrality-gap construction.

Research objective

Prove a universal constant ratio for level 2/3, or construct a certified fooling family. Gap-instance search over structured families (expander-supported interaction graphs, frustration patterns), with SOS values from symmetry-reduced solvers and true energies from certified branch-and-bound at moderate sizes; ratio conjectures then attacked via SOS rounding arguments.

Verification plan

• Success gate: either a proved universal ratio (SOS identity + rounding proof, spot-checked on the corpus), or an explicit family with certified ratio divergence — both SOS values and true energies carrying exact certificates.
• Hope signal: certified gap instances beating the worst known low-level integrality gap — each extends the map of where the hierarchy is weak.
• Pivot signal: constructions stall at known constants and proofs reduce to UGC-type open questions — publish the equivalence.

Why this may lead to research output

Either outcome is a structural statement about the tool every group in the field uses, and a genuine data point for the quantum PCP question.

References

1. Parekh, Thompson, An optimal product-state approximation for 2-local quantum Hamiltonians with positive terms, arXiv:2206.08342.
2. Piddock et al., Quantum Max-Cut is NP-hard to approximate, arXiv:2510.07995.
3. Rao, Analysis of sum-of-squares relaxations for the quantum rotor model, arXiv:2311.09010.

Start by reading the cited papers and formalizing the level-2/3 NC-SOS objective for normalized 2-local Hamiltonians. Explore structured interaction families with symmetry-reduced SOS values and certified true energies, then assess whether the success gate is met by a universal ratio proof or a family with certified ratio divergence.