LFCS seminar: Ashley Montanaro: Opportunities and challenges for quantum algorithms for constraint satisfaction problems

Quantum computers will deliver exponential speedups over their classical counterparts for important problems in cryptography and the simulation of quantum systems. However, the speedups achieved for more general-purpose problems in the domains of optimisation and constraint satisfaction are usually more modest (e.g. quadratic), raising the question of whether quantum computers will genuinely be useful for such problems. In this talk I will discuss ongoing work that aims to optimise the complexity of a quantum algorithm for solving graph colouring problems, and to calculate the performance of the resulting algorithm in detail, in order to determine the extent of the speedup achieved over a fast classical competitor.