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

We devise a deterministic classical algorithm to reveal the structure of low energy spectrum for certain spin-glass systems that encode classical optimization problems. We employ tensor networks to represent probability distributions of all possible configurations. We then develop efficient techniques for approximately extract the relevant information from the networks for a class of quasi-two-dimensional Ising Hamiltonians. To this end, we apply a branch and bound approach over marginal probability distributions by approximately evaluating tensor contractions. Our approach identifies configurations with the largest Boltzmann weights corresponding to low energy states. We discover spin-glass droplet structures at finite temperatures, by exploiting local nature of the problems. This droplet finding algorithm naturally encompass 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 large low-dimension spin-glass problems, with ramifications both for machine learning and noisy intermediate-scale quantum devices. Morever, limitations of our approach highlight alternative directions to establish quantum speed-up and possible quantum supremacy experiments.