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.

Creator(s) Ashley Montanaro
Publication date 09 Jul 2019
Language eng
Publisher University of Bristol
Licence Non-Commercial Government Licence for public sector information
DOI 10.5523/bris.19va21gun3c7629f291kmd6w37
Complete download (zip) https://data.bris.ac.uk/datasets/tar/19va21gun3c7629f291kmd6w37.zip
Citation Ashley Montanaro (2019): Data from Quantum algorithms for CSPs (07-2019). https://doi.org/10.5523/bris.19va21gun3c7629f291kmd6w37
Total size 6.4 MiB

Sub-levels

Data Resources