Ashley Montanaro: Applying quantum algorithms to constraint satisfaction problems

Abstract: Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, as we enter the NISQ regime and beyond, it becomes increasingly important to determine the real-world runtimes and other complexity parameters of these algorithms, taking into account all realistic overheads. In this talk I will discuss recent work applying general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. 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 long term. 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, putting these algorithms well beyond the NISQ regime, 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. The talk will be based on joint work with Earl Campbell and Ankur Khurana.