论文标题
分裂和诱导Qubo量子退火的嵌入
Divide-and-conquer embedding for QUBO quantum annealing
论文作者
论文摘要
量子退火有望成为复杂NP问题的有效启发式。但是，量子优势的明确证明是需要，主要受到将问题嵌入量子硬件的困难的限制。吉尔文 - 新人算法等社区检测方法可以为大型问题提供分裂和纠纷方法。在这里，我们提出了一个以问题为中心的分裂来嵌入，故意恶化了嵌入质量的典型措施，以改善我们获得的部分解决方案。我们首先将这种方法应用于整数分解问题的高度不规则图，并通过此初步测试，继续考虑更常规的几何沮丧系统。我们的结果表明，以问题为中心的嵌入方法可以通过数量级来提高性能。
Quantum annealing promises to be an effective heuristic for complex NP-hard problems. However, clear demonstrations of quantum advantage are wanting, primarily constrained by the difficulty of embedding the problem into the quantum hardware. Community detection methods such as the Girvin--Newman algorithm can provide a divide-and-conquer approach to large problems. Here, we propose a problem-focused division for embedding, deliberately worsening typical measures of embedding quality to improve the partial solutions we obtain. We apply this approach first to the highly irregular graph of an integer factorisation problem and, passing this initial test, move on to consider more regular geometrically frustrated systems. Our results show that a problem-focused approach to embedding can improve performance by orders of magnitude.
