Papers › Computing solution space properties of combinatorial optimization problems via generic...
Computing solution space properties of combinatorial optimization problems via generic tensor networks
Jin-Guo Liu, Xun Gao, Madelyn Cain, Mikhail D. Lukin, Sheng-Tao Wang
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections