Algorithme de recherche de Grover

L'algorithme de Grover atteint O(√N) requêtes, et c'est prouvablement optimal. Chaque itération tourne l'état de θ ≈ 2/√N radians.

Dans une superposition uniforme, chaque candidat démarre avec la même amplitude minuscule. Chaque tour fait deux choses : un oracle inverse le signe de l'amplitude de la cible, puis une 'inversion autour de la moyenne' réfléchit toutes les amplitudes autour de leur moyenne — celle qui est marquée monte, les autres descendent. En répétant, la probabilité de la cible s'approche de 1. Pour une liste de N = 1,000,000, une recherche classique examine 500,000 entrées en moyenne ; Grover n'en demande qu'environ 1,000.

Pour N = 4 — une recherche à deux qubits — Grover n'est pas seulement rapide, il est exact : une seule itération atteint la cible avec 100% de probabilité. L'angle de rotation vérifie sin(θ/2) = 1/√N = 1/2, donc θ = 60°, et après un pas l'état a tourné d'exactement (2·1+1)·30° = 90° jusqu'à l'axe de la cible. C'est le cas rare où un algorithme quantique donne une réponse garantie, et non simplement probable.