Applying quantum algorithms to constraint satisfaction problems
Applying quantum algorithms to constraint satisfaction problems
复制标题
DOI：
10.22331/q-2019-07-18-167
复制
发表时间：
2019-07-18
期刊：
影响因子：
6.4
通讯作者：
Montanaro, Ashley
中科院分区：
文献类型：
--
作者：
Campbell, Earl;Khurana, Ankur;Montanaro, Ashley
量子算法可以提供相对于经典算法的渐近加速。然而，当与最好的经典算法进行比较并考虑到实际的硬件参数和容错开销时，很少有情况下已经为合理规模的问题详细制定了大量的量子加速。所有已知的这种加速的例子都与量子系统和密码学模拟相关的问题相对应。本文将通用量子算法应用于求解约束满足问题的两类典型np完全问题：布尔可满足性和图着色。我们考虑了两种量子方法：Grover算法和加速回溯算法的量子算法。我们比较了这些算法的优化版本的性能，当应用于随机问题实例，与领先的经典算法。即使只考虑可以在一天内解决的问题实例，我们也发现有潜在的大量子加速可用。在我们考虑的最乐观的参数体系中，相对于经典台式计算机，这可能是一个超过105的因素；在最不乐观的情况下，加速降低到10(3)以上。然而，所使用的物理量子位的数量非常大，并且可能需要改进的容错方法来实现这些结果。特别是，如果包括使用当前技术执行表面代码解码所需的经典处理能力的成本，量子优势就消失了。
Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few cases where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. Here we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. We compare the performance of optimised versions of these algorithms, when applied to random problem instances, against leading classical algorithms. Even when considering only problem instances that can be solved within one day, we find that there are potentially large quantum speedups available. In the most optimistic parameter regime we consider, this could be a factor of over 105 relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over 10(3). However, the number of physical qubits used is extremely large, and improved fault-tolerance methods will likely be needed to make these results practical. In particular, the quantum advantage disappears if one includes the cost of the classical processing power required to perform decoding of the surface code using current techniques.