Quantum algorithms from foundations to applications

Add to your list(s) Download to your calendar using vCal

• Ashley Montanaro, University of Bristol
• Friday 31 May 2019, 12:00-13:00
• MR14, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact Johannes Bausch.

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 talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR14, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.