Heuristic optimization and sampling with tensor networks for quasi-2D spin glass problems

Abstract

We devise a deterministic physics-inspired classical algorithm to efficiently reveal the structure of low-energy spectrum for certain low-dimensional spin-glass systems that encode optimization problems. We employ tensor networks to represent Gibbs distribution of all possible configurations. We then develop techniques to approximately extract the relevant information from the networks for quasi-two-dimensional Ising Hamiltonians. Motivated by present-day quantum annealers, we focus in particular on hard structured problems on the chimera graph with up to N = \(2048\) spins. To this end, we apply a branch and bound strategy over marginal probability distributions by approximately evaluating tensor contractions. Our approach identifies configurations with the largest Boltzmann weights corresponding to low energy states. Moreover, by exploiting local nature of the problems, we discover spin-glass droplets geometries. This naturally encompasses sampling from high quality solutions within a given approximation ratio. It is thus established that tensor networks techniques can provide profound insight into the structure of disordered spin complexes, with ramifications both for machine learning and noisy intermediate-scale quantum devices. At the same time, limitations of our approach highlight alternative directions to establish quantum speed-up and possible quantum supremacy experiments.