A. Ambainis (Faculty of Computing, Univ. of Latvia): Quantum algorithms for search and optimization
Channel: Centrum Fizyki Teoretycznej PAN
Date: 14/03/2023

Andris Ambainis (Center for Quantum Computer Science, Faculty of Computing, University of Latvia).
Quantum algorithms for search and optimization.
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:

1. 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 (https://arxiv.org/abs/1903.07493).

2. 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  (https://arxiv.org/abs/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).

3. We show an almost quadratic quantum speedup for a number of geometric problems such as finding three points that are on the same line (https://arxiv.org/abs/2004.08949)."
This is based on https://arxiv.org/abs/2109.04248 which is a joint work with Daniel Szilagyi and Iordanis Kerenidis.

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).

Team-Net QC Colloquium 2023.01.25

The purpose of the Team-Net Quantum Computing Colloquium series is to expose Polish and international researchers, as well as interested peers, to the most important recent achievements and trends in the field of quantum computing. Topics of the colloquium include, but are not limited to:
Near-term quantum algorithms
Quantum supremacy experiments
Resource-theoretic approaches to quantum computing
Quantum machine learning
Practical quantum error correction and error mitigation
Mathematical aspects of quantum computing and many body physics
webpage of the project: https://nisq.pl/