Approximate optimization, sampling, and spin-glass droplet discovery with tensor networks
Open Access
- 23 August 2021
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 104 (2) , 025308
Abstract
We devise a deterministic algorithm to efficiently sample high-quality solutions of certain spin-glass systems that encode hard optimization problems. We employ tensor networks to represent the Gibbs distribution of all possible configurations. Using approximate tensor-network contractions, we are able to efficiently map the low-energy spectrum of some quasi-two-dimensional Hamiltonians. We exploit the local nature of the problems to compute spin-glass droplets geometries, which provides a new form of compression of the low-energy spectrum. It naturally extends to sampling, which otherwise, for exact contraction, is #P-complete. In particular, for one of the hardest known problem-classes devised on chimera graphs known as deceptive cluster loops and for up to 2048 spins, we find on the order of degenerate ground states in a single run of our algorithm, computing better solutions than have been reported on some hard instances. Our gradient-free approach could provide new insight into the structure of disordered spin-glass complexes, with ramifications both for machine learning and noisy intermediate-scale quantum devices.
Keywords
All Related Versions
Funding Information
- Narodowe Centrum Nauki (2016/20/S/ST2/00152, 2020/38/E/ST3/00269)
- European Commission (2017/25/Z/ST2/03028)
- Fundacja na rzecz Nauki Polskiej (POIR.04.04.00-00-17C1/18-00)
This publication has 50 references indexed in Scilit:
- The density-matrix renormalization group in the age of matrix product statesAnnals of Physics, 2011
- Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systemsAdvances in Physics, 2008
- Computational Complexity of Projected Entangled Pair StatesPhysical Review Letters, 2007
- Criticality, the Area Law, and the Computational Power of Projected Entangled Pair StatesPhysical Review Letters, 2006
- Density matrix renormalization group and reaction-diffusion processesThe European Physical Journal B, 1999
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- Nonuniversal critical dynamics in Monte Carlo simulationsPhysical Review Letters, 1987
- Ordered Phase of Short-Range Ising Spin-GlassesPhysical Review Letters, 1986
- Optimization by Simulated AnnealingScience, 1983
- The Monte Carlo MethodJournal of the American Statistical Association, 1949