论文标题
禁忌驱动的量子邻里采样器
Tabu-driven Quantum Neighborhood Samplers
论文作者
论文摘要
组合优化是量子计算针对的重要应用。但是，与在大型实践问题上进行高性能的经典启发式方法相比，近期硬件限制使量子算法不太可能具有竞争力。使用近期设备获得优势的一种选择是将它们与经典启发式方法结合使用。特别是，我们建议使用量子方法从经典的分布中进行采样 - 这是在近期实现真正可证明的量子分离的最可能的方法 - 用于更快地解决优化问题。我们通过使用量子近似优化算法（QAOA）作为邻域采样器对禁忌搜索的适应来研究这种增强。我们表明，QAOA为在这种混合设置中提供了一种灵活的工具，可以通过节省许多禁忌迭代并实现更好的解决方案来提供更快地解决问题的证据。
Combinatorial optimization is an important application targeted by quantum computing. However, near-term hardware constraints make quantum algorithms unlikely to be competitive when compared to high-performing classical heuristics on large practical problems. One option to achieve advantages with near-term devices is to use them in combination with classical heuristics. In particular, we propose using quantum methods to sample from classically intractable distributions -- which is the most probable approach to attain a true provable quantum separation in the near-term -- which are used to solve optimization problems faster. We numerically study this enhancement by an adaptation of Tabu Search using the Quantum Approximate Optimization Algorithm (QAOA) as a neighborhood sampler. We show that QAOA provides a flexible tool for exploration-exploitation in such hybrid settings and can provide evidence that it can help in solving problems faster by saving many tabu iterations and achieving better solutions.
