Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks Journal Article uri icon

Overview

abstract

  • 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.

publication date

  • June 30, 2023

has restriction

  • green

Date in CU Experts

  • March 10, 2024 9:52 AM

Full Author List

  • Liu J-G; Gao X; Cain M; Lukin MD; Wang S-T

author count

  • 5

Other Profiles

International Standard Serial Number (ISSN)

  • 1064-8275

Electronic International Standard Serial Number (EISSN)

  • 1095-7197

Additional Document Info

start page

  • A1239

end page

  • A1270

volume

  • 45

issue

  • 3