Computing solution space properties of combinatorial optimization problems via generic tensor networks

Abstract

We introduce a unified framework to compute the solution space properties of a broad class of combinatorial optimization problems. These properties include finding one of the optimum solutions, counting the number of solutions of a given size, and enumeration and sampling of solutions of a given size. Using the independent set problem as an example, we show how all these solution space properties can be computed in the unified approach of generic tensor networks. We demonstrate the versatility of this computational tool by applying it to several examples, including computing the entropy constant for hardcore lattice gases, studying the overlap gap properties, and analyzing the performance of quantum and classical algorithms for finding maximum independent sets.

Github repo: https://github.com/QuEraComputing/GenericTensorNetworks.jl

References in corpus (2)

• Array Programming with NumPy
• Monte Carlo simulations of 2d hard core lattice gases

Cited by in corpus (19)

• Quantum-Informed Recursive Optimization Algorithms
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Benchmarking Quantum Computer Simulation Software Packages: State Vector Simulators
• Tensor networks for interpretable and efficient quantum-inspired machine learning
• Trimer quantum spin liquid in a honeycomb array of Rydberg atoms
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization
• The minimal canonical form of a tensor network
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• State Diagrams to determine Tree Tensor Network Operators
• Probabilistic Inference in the Era of Tensor Networks and Differential Programming
• Cons-training Tensor Networks: Embedding and Optimization Over Discrete Linear Constraints
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm
• Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem
• Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• Quick design of feasible tensor networks for constrained combinatorial optimization
• Variational matrix product states for combinatorial optimization
• The product structure of MPS-under-permutations