Quantum algorithms for search and optimization

Date: Wednesday, January 25, 2023
Time: 11:00
Location: Quantum Computing Colloquium
Passcode: teamnet
seminar

Speaker: Andris Ambainis (Center for Quantum Computer Science, Faculty of Computing, University of Latvia)

Abstract Quantum algorithms are useful for a variety of problems in search and optimization. This line of work started with Grover’s quantum search algorithm which achieved a quadratic speedup over naive exhaustive search but has now developed far beyond it. In this talk, we describe three recent results in this area: (i) We show that, for any classical algorithm that uses a random walk to find an object with some property (by walking until the random walker reaches such an object), there is an almost quadratically faster quantum algorithm (arxiv:1903.07493). (ii) We show that the best-known exponential time algorithms for solving several NP-complete problems (such as Travelling Salesman Problem or TSP) can be improved quantumly (arxiv:1807.05209). For example, for the TSP, the best-known classical algorithm needs time O(2^n) but our quantum algorithm solves the problem in time O(1.728…^n). (iii) We show an almost quadratic quantum speedup for a number of geometric problems such as finding three points that are on the same line (arxiv:2004.08949). About the speaker Andris Ambainis is a professor of computer science at the University of Latvia. He has invented widely used methods for constructing quantum algorithms and has constructed record-breaking examples of quantum advantage for quantum computers. Andris Ambainis’ work has been recognized by an Advanced Grant from the European Research Council (2012) and the Grand Medal of the Latvian Academy of Sciences (2013).