Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
arXiv:1811.06518 · doi:10.1103/PhysRevE.104.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 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.
arXiv commentFinal version; 7+6 pages, 4+6 figures; added benchmarks on time-to-solution and fair sampling/counting versus PT and QA. Code and problem instances can be found at https://github.com/marekrams/tnac4o
References in corpus (42)
- Quantum Computing in the NISQ era and beyond
- The density-matrix renormalization group in the age of matrix product states
- Area laws for the entanglement entropy - a review
- Ising formulations of many NP problems
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Efficient classical simulation of slightly entangled quantum computations
- Quantum Annealing in the Transverse Ising Model
- A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
- Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
- Adiabatic Quantum Computing
- Parallel Tempering: Theory, Applications, and New Perspectives
- Criticality, the area law, and the computational power of PEPS
- Stripe order in the underdoped region of the two-dimensional Hubbard model
- Tensor networks for complex quantum systems
- The computational complexity of PEPS
- Unsupervised Generative Modeling Using Matrix Product States
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Gradient methods for variational optimization of projected entangled-pair states
- Entanglement in a quantum annealing processor
- Lecture Notes of Tensor Network Contractions
- Two-Dimensional Tensor Product Variational Formulation
- A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
- Perfect Sampling with Unitary Tensor Networks
- Unifying Projected Entangled Pair States contractions
- Tensor Networks in a Nutshell
- Density Matrix Renormalization Group and Reaction-Diffusion Processes
- Diagonalizing transfer matrices and matrix product operators: a medley of exact and computational methods
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Variational Approach to Projected Entangled Pair States at Finite Temperature
- A deceptive step towards quantum speedup detection
- Pegasus: The second connectivity graph for large-scale quantum annealing hardware
- The backtracking survey propagation algorithm for solving random K-SAT problems
- Contracting projected entangled pair states is average-case hard
- Dynamical simulations of classical stochastic systems using matrix product states
- Tensor Network Contractions for #SAT
- Fast counting with tensor networks
- Stochastic Matrix Product States
- Fractal Droplets in Two Dimensional Spin Glasses
- Virtual Parallel Computing and a Search Algorithm using Matrix Product States
- Fair sampling of ground-state configurations of binary optimization problems
- Verifying the output of quantum optimizers with ground-state energy lower bounds
- Solving Spin Glasses with Optimized Trees of Clustered Spins
Cited by in corpus (14)
- Tensor Network Algorithms: a Route Map
- Hybrid quantum annealing for larger-than-QPU lattice-structured problems
- Optimal sampling of dynamical large deviations in two dimensions via tensor networks
- The three phases of quantum annealing: fast, slow, and very slow
- Collective Monte Carlo updates through tensor network renormalization
- Efficient Representation of Minimally Entangled Typical Thermal States in two dimensions via Projected Entangled Pair States
- Sampling diverse near-optimal solutions via algorithmic quantum annealing
- Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
- Post-Error Correction for Quantum Annealing Processor using Reinforcement Learning
- Quantum annealing in the NISQ era: railway conflict management
- Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
- SpinGlassPEPS.jl: Tensor-network package for Ising-like optimization on quasi-two-dimensional graphs
- Variational matrix product states for combinatorial optimization
- Sampling two-dimensional isometric tensor network states