Linear-time classical approximate optimization of cubic-lattice classical spin glasses

Recent theoretical work opens the possibility of universal polynomial time complexity for quantum annealing, and (D-Wave) quantum annealing can now achieve approximate optimization of cubic-lattice classical Ising spin glasses with ∼ 10⁴ spins. It is therefore timely to ask which short-range classical spin glasses are good candidates for superpolynomial quantum advantage in the time complexity of approximate optimization. One intuition is to consider models where optimization is extremely slow for state-of-the-art Monte-Carlo methods. However, here we provide evidence that short-range-correlated classical spin glasses may be approximately optimized in linear time and space with a very simple deterministic tensor-network heuristic regardless of how hard their optimization is for Monte-Carlo methods. On the simple cubic lattice, at the largest tested size of 50 × 50 × 50 spins, we obtain relative energy errors of ≤6% for tunably-hard planted-solution instances, and <3% for the ±J model used in recent D-Wave experiments. We also test cubic-lattice instances that encode Max-Cut on random, three-regular graphs; at the largest tested size of 100 vertices, we find relative energy errors of <1% and approximation ratios of 75 − 85%. These results inform the search for quantum advantage and suggest an efficient classical method for generating warm starts for other spin-glass optimization algorithms.