University of Cambridge > Talks.cam > CQIF Seminar > Quantum algorithms from foundations to applications

Quantum algorithms from foundations to applications

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity