AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

60 Minutes

Saarbrücken

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

Christina Fries

+49 681 9325 5722

--email hidden

Yes

945 7732 1297

Zoom

945 7732 1297

205903

public