[challenge]: Finite-level exactness beyond the swap algebra

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

For Quantum Max Cut, the swap-operator algebra makes a finite NPA level exact — the hierarchy stops being an approximation and becomes an exact algorithm (arXiv:2307.15688, arXiv:2307.15661). This is currently the field's only substantial example of the phenomenon.

Research objective

Determine which other symmetric operator algebras admit finite-level exactness theorems — candidates: qudit swap algebras (arXiv:2503.20942), Pauli charge-sector algebras, permutation-invariant Bell algebras (arXiv:2607.08462) — and whether the exactness level is computable from the algebra's Wedderburn data. Experimental-mathematics loop: compute moment-relaxation values at increasing levels on small instances, compare with exact diagonalization to conjecture the exactness level, then prove it from the ideal structure.

Verification plan

• Success gate: for a claimed exactness level L: SDP value at level L equals exact diagonalization on all instances up to the enumeration bound (equality of independently computed numbers), plus a written proof of the general statement; a single strict inequality falsifies the conjecture instantly.
• Hope signal: exactness holds empirically on every tested instance but the ideal-theoretic proof resists — a verified conjecture with computational evidence is publishable.
• Pivot signal: required levels grow with instance size for every candidate algebra — exactness is swap-specific; prove that no-go instead.

Why this may lead to research output

Finite exactness turns an infinite hierarchy into an exact algorithm — the most beautiful phenomenon in the area, known essentially once. One new algebra with a computed exactness level is a strong result; a general Wedderburn-data criterion would be a landmark.

References

1. Takahashi et al., An SU(2)-symmetric SDP hierarchy for Quantum Max Cut, arXiv:2307.15688.
2. Watts et al., Relaxations and exact solutions to Quantum Max Cut via the algebraic structure of swap operators, arXiv:2307.15661.
3. Klep et al., Quantum Max d-Cut via qudit swap operators, arXiv:2503.20942.

Start by reading the cited Quantum Max Cut papers and identify the repository entry points for moment-relaxation computation and exact diagonalization; no files or tests are named in the issue. Compare values at increasing levels on bounded small instances, then document either a proved finite-level exactness result or a verified counterexample/no-go pattern.