Variational matrix product states for combinatorial optimization

Abstract

To compute approximate solutions for combinatorial optimization problems, we describe variational methods based on the product state (PS) and matrix product state (MPS) ansätze. We perform variational energy minimization with respect to a quantum annealing Hamiltonian and utilize randomness by embedding the approaches in the metaheuristic iterated local search (ILS). The resulting quantum-inspired ILS algorithms are benchmarked on maximum cut problems of up to 50000 variables. We show that they can outperform traditional (M)PS methods, classical ILS, the quantum approximate optimization algorithm and other variational quantum-inspired solvers.

14 pages, 9 figures, 3 tables

References in corpus (39)

• The density-matrix renormalization group in the age of matrix product states
• Variational Quantum Algorithms
• 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
• Noisy intermediate-scale quantum (NISQ) algorithms
• Adiabatic Quantum Computing
• The Variational Quantum Eigensolver: a review of methods and best practices
• The ITensor Software Library for Tensor Network Calculations
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Annealing and Analog Quantum Computation
• Perspectives of quantum annealing: Methods and implementations
• What limits the simulation of quantum computers?
• Tensor Network Algorithms: a Route Map
• Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks
• Tensor operators: constructions and applications for long-range interaction systems
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Tropical Tensor Network for Ground States of Spin Glasses
• Tensor Network Contractions for #SAT
• Fast counting with tensor networks
• Simulation of many-qubit quantum computation with matrix product states
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Shortcuts to Adiabatic Classical Spin Dynamics Mimicking Quantum Annealing
• A Variational Ansatz for the Ground State of the Quantum Sherrington-Kirkpatrick Model
• Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
• A quantum-inspired tensor network method for constrained combinatorial optimization problems
• Quantum Annealing for Neural Network optimization problems: a new approach via Tensor Network simulations
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
• Generalization of group-theoretic coherent states for variational calculations
• Projected Entangled Pair States with flexible geometry
• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
• Integer Factorization via Tensor Network Schnorr's Sieving
• Cons-training Tensor Networks: Embedding and Optimization Over Discrete Linear Constraints
• Entanglement-assisted variational algorithm for discrete optimization problems
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Quick design of feasible tensor networks for constrained combinatorial optimization
• Quantum algorithms for equational reasoning
• Tensor Network Estimation of Distribution Algorithms