论文标题
在恒定时间量子退火和保证图形优化问题的近似值
On constant-time quantum annealing and guaranteed approximations for graph optimization problems
论文作者
论文摘要
量子退火（QA）是一个计算框架，其中使用量子系统的连续进化来在非结构化搜索空间上找到目标函数的全局最小值。如果我们允许呈指数级的运行时间，则可以将其视为优化问题的一般元疗法，包括NP-HARD。尽管从启发式的角度对质量保证进行了广泛的研究，但关于在多项式时间中获得的解决方案质量的理论保证知之甚少。 在本文中，我们使用从理论物理学，Lieb-Robinson（LR）结合的一种技术，并开发了新工具，证明短而恒定的时间量子退火可确保恒定的因子近似值比限制在有限程度图的情况下。在非正式的情况下，在有限度图上，LR结合使我们能够检索一个（放松的）局部性参数，通过研究近似值，可以通过研究边界半径的子图来推断出近似值。 我们说明了有关Cubcic图的MaxCut和最大独立设置的工具，提供明确的近似值和获得它们所需的运行时间。我们的结果与在不同但相关但相关的QAOA（量子优化算法）框架中获得的众所周知的结果相似。 最终，我们讨论了理论和实验论点以进行进一步的改进。
Quantum Annealing (QA) is a computational framework where a quantum system's continuous evolution is used to find the global minimum of an objective function over an unstructured search space. It can be seen as a general metaheuristic for optimization problems, including NP-hard ones if we allow an exponentially large running time. While QA is widely studied from a heuristic point of view, little is known about theoretical guarantees on the quality of the solutions obtained in polynomial time. In this paper we use a technique borrowed from theoretical physics, the Lieb-Robinson (LR) bound, and develop new tools proving that short, constant time quantum annealing guarantees constant factor approximations ratios for some optimization problems when restricted to bounded degree graphs. Informally, on bounded degree graphs the LR bound allows us to retrieve a (relaxed) locality argument, through which the approximation ratio can be deduced by studying subgraphs of bounded radius. We illustrate our tools on problems MaxCut and Maximum Independent Set for cubic graphs, providing explicit approximation ratios and the runtimes needed to obtain them. Our results are of similar flavor to the well-known ones obtained in the different but related QAOA (quantum optimization algorithms) framework. Eventually, we discuss theoretical and experimental arguments for further improvements.
