Applying quantum algorithms to constraint satisfaction problems. (arXiv:1810.05582v2 [quant-ph] UPDATED)

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 $10^5$ 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.

Article web page: