论文标题
用于解决量子退火器上NP难题的分解算法
Decomposition algorithms for solving NP-hard problems on a quantum annealer
论文作者
论文摘要
NP硬性问题，例如最大集团或最小顶点涵盖问题，KARP的21个NP问题中的两个，在计算化学，生物化学和计算机网络安全性方面有多种应用。鉴于该问题可以嵌入其硬件中，因此绝热量子退火器可以搜索此类NP-HARD优化问题的最佳值。但是，由于退火器的硬件连接结构的某些局限性，这通常是不可能的。本文研究了旨在识别一组最佳顶点的NP-硬形图问题分解算法的一般框架。我们的通用算法使我们能够递归对实例进行划分，直到可以将生成的子问题嵌入量子退火器硬件并随后解决。该框架应用于最大集团和最小顶点覆盖问题，我们提出了几种修剪和还原技术，以加快递归分解。两种算法的性能在详细的仿真研究中进行了评估。
NP-hard problems such as the maximum clique or minimum vertex cover problems, two of Karp's 21 NP-hard problems, have several applications in computational chemistry, biochemistry and computer network security. Adiabatic quantum annealers can search for the optimum value of such NP-hard optimization problems, given the problem can be embedded on their hardware. However, this is often not possible due to certain limitations of the hardware connectivity structure of the annealer. This paper studies a general framework for a decomposition algorithm for NP-hard graph problems aiming to identify an optimal set of vertices. Our generic algorithm allows us to recursively divide an instance until the generated subproblems can be embedded on the quantum annealer hardware and subsequently solved. The framework is applied to the maximum clique and minimum vertex cover problems, and we propose several pruning and reduction techniques to speed up the recursive decomposition. The performance of both algorithms is assessed in a detailed simulation study.
