Unlocking Faster Search with Quantum Algorithms 🚀

We will describe several quantum speedups for search problems of various type that go beyond simple uses of Grover's algorithm. The talk will cover:
- quantum speedups for exponential time dynamic programming problems such as the famous Travelling Salesman Problem (arXiv:1807.05209);
- quantum speedups for geometric problems (such as finding three points that lie on the same line, arXiv:2004.08949);
- quantum speedups for reconstructing tracks of particles in the Large Hadron Collider (arXiv:2104.11583);



Andris Ambainis holds B.Sc. (1996) and M.Sc. (1997) from University of Latvia and Ph.D. (2001) from University of California, Berkeley. He has been a postdoc at Institute for Advanced Study, Princeton and a faculty member at University of Waterloo, Canada, before returning to University of Latvia in 2007. Andris Ambainis has made many important contributions to quantum algorithms and complexity theory and is one of the leading experts in the world in computer science aspects of quantum computing. He is an author of over 100 research papers, including 18 papers in two leading theoretical computer science conferences, FOCS and STOC. Andris Ambainis was the youngest ever person elected to Latvian Academy of Sciences in 2007, at the age of 32.