Projects per year

### Abstract

We describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T vertices, each vertex corresponding to a test of a partial solution. Then we show that there is a bounded-error quantum algorithm which completes the same task using (Formula presented) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree.

Original language | English |
---|---|

Article number | 15 |

Number of pages | 24 |

Journal | Theory of Computing |

Volume | 14 |

DOIs | |

Publication status | Published - 3 Dec 2018 |

### Structured keywords

- QITG

### Keywords

- Quantum computing
- Quantum query complexity
- Quantum walk

## Fingerprint Dive into the research topics of 'Quantum-Walk Speedup of Backtracking Algorithms'. Together they form a unique fingerprint.

## Projects

- 1 Finished

## Activities

- 1 Fellowship awarded competitively

## EPSRC Fellowship - New insights in quantum algorithms and complexity.

Ashley Montanaro (Recipient)

Activity: Other activity types › Fellowship awarded competitively

## Profiles

## Dr Ashley M R Montanaro

- School of Mathematics - Reader in Quantum Computation
- The Bristol Centre for Nanoscience and Quantum Information
- Theory and Algorithms
- Mathematical Physics
- Quantum Information Theory

Person: Academic , Member, Group lead