Polynomial-Time Classical Approximate Optimization of Wishart-Planted Spin Glasses

Approximate optimization of classical spin glasses on complete graphs is of relevance to combinatorial optimization; the Wishart planted ensemble provides a tunably-rugged testbed for this task. We propose and test a meta-heuristic that iterates over optimizations of random subsystems and keeps only subsystem updates that lower the global energy; we implement the subsystem optimizations with tensor-network contraction. The meta-heuristic empirically displays polynomial scaling and stable convergence; subsystem size has very little impact on the achievable optimality gap, but larger subsystem sizes lead to smaller scaling exponents. For system sizes up to N=4096, the algorithm achieves optimality gaps below 3% in the computationally "hard" regime and below 20% in the "easy" regime. The optimality gaps reached in the "hard" regime in polynomial time with our meta-heuristic are only reachable in superpolynomial time with certain other state-of-the-art classical heuristics. Our results demonstrate that subsystem-optimization-based meta-heuristics can sometimes have a scaling advantage over other heuristics for approximate optimization of complete-graph classical spin glasses.