Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Ashley Montanaro: Opportunities and challenges for quantum algorithms for constraint satisfaction problems

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

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
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 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.

Document Actions