School Colloquium Series: Dr Ashley Montanaro
Dr Ashley Montanaro, University of Bristol
Enderby Lecture Theatre, Physics
Title: Quantum algorithms from foundations to applications
Quantum computers are designed to use quantum mechanics to outperform any standard, "classical" computer based only on the laws of classical physics. Following many years of experimental and theoretical developments, it is anticipated that quantum computers will soon be built that cannot be simulated by today's most powerful supercomputers. But to take advantage of a quantum computer requires a quantum algorithm: and designing and applying quantum algorithms requires contributions to be made at all levels of the theoretical "stack", from underpinning mathematics through to detailed running time analysis. In this talk, I will describe one example of this process. First, an abstract quantum algorithm due to Aleksandrs Belovs is used to speed up classical search algorithms based on the technique known as backtracking ("trial and error"). Then this quantum algorithm can be applied to fundamental constraint satisfaction problems such as graph colouring, sometimes achieving substantial speedups over leading classical algorithms. The talk will aim to give a flavour of the mathematics involved in quantum algorithm design, rather than going into full details.
This event is open to all University of Bristol staff and students.
For practical information please email firstname.lastname@example.org.