Abstract

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.