School Colloquium Series: Dr Ashley Montanaro

11 February 2019, 4.00 PM - 11 February 2019, 5.00 PM

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.

Further information

This event is open to all University of Bristol staff and students. 

Contact information

For practical information please email

Edit this page