[challenge]: Automated symmetry reduction for NC moment hierarchies

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

Symmetry is the largest known lossless reduction of moment-SDP hierarchies: block-diagonalizing the moment matrix over the commutant algebra shrinks the SDP by orders of magnitude with zero loss of tightness (invariant-SDP theory, arXiv:1007.2905; regular *-representation, de Klerk–Pasechnik–Schrijver, Math. Prog. 2007). Yet every application in the NC setting is hand-crafted: Ioannou–Rosset's symmetrization framework (arXiv:2112.10803), the SU(2) swap-operator hierarchy for Quantum Max Cut (arXiv:2307.15688), Pauli charge/singlet reductions in NCTSSoS. Numerical *-algebra decomposition is its own research problem (de Klerk–Dobre–Pasechnik, Math. Prog. 2011; Murota et al., JJIAM 2010).

Research objective

A fully automated pipeline: input a Hamiltonian (or NC objective) plus generating symmetries; output reduced SDP blocks with a per-instance proof of equivalence — covering Pauli charge/parity, permutation, and SU(2) swap symmetries in one framework. Certify equivalence per instance rather than proving the general algorithm correct up front.

Verification plan

• Success gate: on a 50-model corpus, reduced-SDP and dense-SDP optimal values agree to solver tolerance at every level where the dense problem is computable — a value-equality test the loop cannot game — with block-size reductions logged.
• Hope signal: equality holds for abelian symmetries but nonabelian blocks disagree — isolates the irrep bug class; keep iterating.
• Pivot signal: commutant computation dominates runtime at useful sizes — pivot to symmetry-class-specific precomputed decompositions.

Why this may lead to research output

A general symmetry pipeline would be the SymDPoly successor the field lacks (arXiv:1808.09598) and would commoditize the largest known exact speedup — every symmetric application downstream (Bell inequalities, Quantum Max Cut, spin models) benefits immediately.

References

1. Bachoc, Gijswijt, Schrijver, Vallentin, Invariant semidefinite programs, arXiv:1007.2905.
2. Ioannou, Rosset, Noncommutative polynomial optimization under symmetry, arXiv:2112.10803.
3. Takahashi et al., An SU(2)-symmetric semidefinite programming hierarchy for Quantum Max Cut, arXiv:2307.15688.
4. Rosset, SymDPoly, arXiv:1808.09598.

No files, tests, or entry points are named. Start by locating the repository's moment-SDP construction and any symmetry-related entry points, then define the 50-model dense-versus-reduced comparison. Done means reduced blocks, per-instance equivalence evidence, solver-tolerance agreement, and logged block-size reductions across the computable corpus.