Source code and experimental results from Applying quantum algorithms to CSPs (10-2018)

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 comprises numerical results from computational experiments, as well as corresponding source code.

Creator(s) Ashley Montanaro
Publication date 12 Oct 2018
Language eng
Publisher University of Bristol
Licence Non-Commercial Government Licence for public sector information
DOI 10.5523/bris.17mjvdv1u7udm2u9frlh61ltvp
Complete download (zip) https://data.bris.ac.uk/datasets/17mjvdv1u7udm2u9frlh61ltvp/17mjvdv1u7udm2u9frlh61ltvp.zip
Citation Ashley Montanaro (2018): Source code and experimental results from Applying quantum algorithms to CSPs (10-2018). https://doi.org/10.5523/bris.17mjvdv1u7udm2u9frlh61ltvp
Total size 6.4 MiB

Sub-levels

Data Resources