Grover Algorithm Offers No Quantum Advantage (Groupe de travail Quantique)

Xavier Waintal

PHELIQS, CEA Grenoble

Tue, Apr. 18th 2023, 14:00-15:00

Pièce 50, Bât. 774, Orme des Merisiers

Grover’s algorithm has a peculiar place in the pantheon of quantum algorithms. It offers only a modest, at most quadratic, speed up with respect to its classical counterpart. Yet, it has the big advantage to be applicable to a wide range of problems while most quantum algorithms are highly specialized.
In this talk, I will analyse in details the algorithm and show that one can construct a « quantum inspired » classical version that, to some extend, mimics the quantum computer.
I will show that this classical algorithm allows us to put bonds on where a quantum computer could start to be competitive with respect to classical hardware. We find that a putative crossing point would happen for problems so hard that it would take millions of years to solve them, thereby foreclosing the possibility of Grover to be useful in practice.
[In the morning, Xavier Waintal will give a general seminar at the Maison de la simulation, see the link below.]

https://mdls.fr/quantum-computers-what-are-they-wh...

Contact : Jeremie
BOUTTIER