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


When 
Jun 20, 2018 from 11:00 AM to 12:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
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 generalpurpose 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.