Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
Authors:
- Marek M. RamsMRMarek M. Rams
- Masoud MohseniMMMasoud Mohseni
- Konrad JałowieckiKJKonrad Jałowiecki
- Bartłomiej GardasBGBartłomiej Gardas
Preprint
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 $10^{10}$ 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
This publication has 42 references indexed in Scilit:
- Tensor Network Contractions2020
- Tensor networks for complex quantum systemsNature Reviews Physics, 2019
- Commercialize quantum technologies in five yearsNature, 2017
- The backtracking survey propagation algorithm for solving random K-SAT problemsNature Communications, 2016
- Computational multiqubit tunnelling in programmable quantum annealersNature Communications, 2016
- Tensor Network Contractions for #SATJournal of Statistical Physics, 2015
- The density-matrix renormalization group in the age of matrix product statesAnnals of Physics, 2011
- Parallel tempering: Theory, applications, and new perspectivesPhysical Chemistry Chemical Physics, 2005
- A cluster Monte Carlo algorithm for 2-dimensional spin glassesThe European Physical Journal B, 2001
- Density matrix renormalization group and reaction-diffusion processesThe European Physical Journal B, 1999