论文标题
通过通用张量网络计算组合优化问题的解决方案空间属性
Computing solution space properties of combinatorial optimization problems via generic tensor networks
论文作者
论文摘要
我们引入了一个统一的框架，以计算一系列组合优化问题的解决方案空间属性。这些属性包括找到最佳的解决方案之一，计算给定尺寸的解决方案的数量，以及给定尺寸的解决方案的枚举和采样。以独立集问题为例，我们展示了如何在通用张量网络的统一方法中计算所有这些解决方案属性。我们通过将其应用于几个示例，包括计算硬核晶格气体的熵常数，研究重叠间隙属性，并分析量子和经典算法的性能以找到最大的独立集。
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.
