Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks

DOI10.1137/22M1501787MaRDI QIDQ6098526zbMATH OpenOpenAlexFDO

Authors Jingbo Liu, Xun Gao, Mikhail D. Lukin

Publication date 14 June 2023

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.03718

zbMATH Keywords

combinatorial optimizationgeneric tensor networkindependent setsolution space property

Mathematics Subject Classification ID

Graph polynomials (05C31) Enumerative problems (combinatorial problems) in algebraic geometry (14N10) Combinatorial optimization (90C27)

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.

Recommendations

• scientific article; zbMATH DE number 6096665
• Tensor network contractions for \#SAT
• Doubly constrained network for combinatorial optimization
• Quantum computation and the evaluation of tensor networks
• scientific article; zbMATH DE number 1163496

Cites work

• A practical introduction to tensor networks: Matrix product states and projected entangled pair states
• A review on algorithms for maximum clique problems
• Algorithm 457: finding all cliques of an undirected graph
• Anderson localization makes adiabatic quantum optimization fail
• Computing the independence polynomial: from the tree threshold down to the roots
• Fast multiplication of large numbers
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 6437647 (Why is no real title available?)
• Introduction to domination polynomial of a graph.
• Julia: a fresh approach to numerical computing
• Limits of local algorithms over sparse random graphs
• Listing all maximal cliques in sparse graphs in near-optimal time
• Local algorithms for independent sets are half-optimal
• On duality between local maximum stable sets of a graph and its line-graph
• On generating all maximal independent sets
• On independent sets and bicliques in graphs
• On the independence complex of square grids
• Pattern recognition and machine learning.
• Simulating Quantum Computation by Contracting Tensor Networks
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
• Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
• Tensor network contractions for \#SAT
• Tensor-train decomposition
• The complexity of tropical matrix factorization
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The nature of computation
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(2)

• scientific article; zbMATH DE number 6096665 (Why is no real title available?)
• Generative learning of continuous data by tensor networks

This page was built for publication: Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098526)