Data from Quantum algorithms for CSPs (07-2019)

Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few examples known 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. In this project 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. The data stored in the repository is numerical results from computational experiments, as well as corresponding source code.