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

PHELIQS, CEA Grenoble