论文标题
绝热量子优化无法解决背包问题
Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem
论文作者
论文摘要
在这项工作中，我们尝试使用D-WAVE 2000Q绝热量子计算机来解决整数赋予背包问题。背包问题是计算机科学中众所周知的NP完整问题，并在经济学，商业，金融等方面进行了应用。我们试图解决许多已知最佳解决方案的小型背包问题。我们发现，绝热量子优化无法在所有问题实例中产生与主背包最佳填充的解决方案。我们将量子硬件上获得的结果与经典的模拟退火算法和使用混合分支结合算法的两个求解器进行了比较。模拟退火算法也未能产生背包的最佳填充，尽管通过模拟和量子退火获得的解决方案并不比对正确的解决方案更相似。我们讨论了这种观察到的绝热量子优化失败的潜在原因。
In this work, we attempt to solve the integer-weight knapsack problem using the D-Wave 2000Q adiabatic quantum computer. The knapsack problem is a well-known NP-complete problem in computer science, with applications in economics, business, finance, etc. We attempt to solve a number of small knapsack problems whose optimal solutions are known; we find that adiabatic quantum optimization fails to produce solutions corresponding to optimal filling of the knapsack in all problem instances. We compare results obtained on the quantum hardware to the classical simulated annealing algorithm and two solvers employing a hybrid branch-and-bound algorithm. The simulated annealing algorithm also fails to produce the optimal filling of the knapsack, though solutions obtained by simulated and quantum annealing are no more similar to each other than to the correct solution. We discuss potential causes for this observed failure of adiabatic quantum optimization.
