Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
arXiv:2411.16431 · doi:10.1103/PhysRevApplied.23.054049
Abstract
Optimization problems pose challenges across various fields. In recent years, quantum annealers have emerged as a promising platform for tackling such challenges. To provide a new perspective, we develop a heuristic tensor network (TN) based algorithm to reveal the low-energy spectrum of Ising spin-glass systems with interaction graphs relevant to present-day quantum annealers. Our deterministic approach combines a branch-and-bound search strategy with an approximate calculation of marginals via TN contractions. Its application to quasi-two-dimensional lattices with large unit cells of up to 24 spins, realized in current quantum annealing processors, requires a dedicated approach that utilizes sparse structures in the TN representation and GPU hardware acceleration. We benchmark our approach on random problems defined on Pegasus and Zephyr graphs with up to a few thousand spins, comparing it against the D-Wave Advantage quantum annealer and Simulated Bifurcation algorithm. Apart from the quality of the best solutions, we compare the diversity of low-energy states sampled by all the solvers. For the biggest considered i.i.d. problems with over 5000 spins, the state-of-the-art TN approach leads to solutions that are to worse than the best solutions obtained by Ising machines while being two orders of magnitude slower. We attribute those results to approximate contraction failures. For embedded tile planting instances, our approach gets to approximately from the planted ground state, a factor of better than the Ising solvers. While all three methods can output diverse low-energy solutions, e.g., differing by at least a quarter of spins with energy error below , our deterministic branch-and-bound approach finds sets of a few such states at most. On the other hand, both Ising machines prove capable of sampling sets of thousands of such solutions.
16+7 pages, 12+7 figures; close to published version
References in corpus (33)
- Ising formulations of many NP problems
- 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
- Parallel Tempering: Theory, Applications, and New Perspectives
- Theory of Quantum Annealing of an Ising Spin Glass
- Criticality, the area law, and the computational power of PEPS
- The computational complexity of PEPS
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- Coherent quantum annealing in a programmable 2000-qubit Ising chain
- Lecture Notes of Tensor Network Contractions
- Optimized simulated annealing for Ising spin glasses
- Two-Dimensional Tensor Product Variational Formulation
- A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
- Tensor Network Algorithms: a Route Map
- Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
- A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
- Unifying Projected Entangled Pair States contractions
- Beyond-classical computation in quantum simulation
- Simple universal models capture all classical spin physics
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Tropical Tensor Network for Ground States of Spin Glasses
- The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps
- Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
- Scaling Advantage in Approximate Optimization with Quantum Annealing
- Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
- Computational hardness of spin-glass problems with tile-planted solutions
- Snapshot Observation for 2D Classical Lattice Models by Corner Transfer Matrix Renormalization Group
- Efficient and Scalable Architecture for Multiple-chip Implementation of Simulated Bifurcation Machines
- 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
- Sign problem in tensor network contraction
- Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices