 |
Center for Nonlinear Studies |
We devise a heuristic deterministic physics-inspired classical algorithm to efficiently reveal the structure of low-energy spectrum for certain low-dimensional spin-glass systems that encodeoptimization problems. We employ tensor networks to represent Gibbs distribution of all possible configurations. We then develop techniques to extract the relevant information from the networks for quasi-two-dimensional Ising Hamiltonians. Motivated by present-day quantum annealers, we mainly focus on hard structured problems on thechimera graph with up to 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 largestBoltzmann 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.
Host: Wojciech Zurek