Algorithme de recherche de Grover

Trouvez une aiguille dans une botte de foin en √N étapes au lieu de N

Exemple résolu — Algorithme de recherche de Grover

Itération actuelle	0 (Superposition)
Probabilité cible	12.50%
Classique (1/N)	12.50%
Itération	0 / 2 · Superposition

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Pourquoi √N et pas plus vite ? 🖖

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

Comment la bonne réponse est amplifiée 🖖

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.

Quatre éléments, un pas, certitude 🖖

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.

Problème entièrement résolu

Deux itérations pour trouver un élément marqué parmi 8 5 étapes
L'algorithme de Grover trouve un élément marqué parmi 8 en deux itérations. Déterminez d'où vient ce deux — et ce qu'il advient si vous en exécutez une troisième.
1. Avant toute exécution, l'état est une superposition uniforme : chaque élément est équiprobable, de sorte que l'élément marqué porte 1/8 de la probabilité. Cela équivaut à un tirage aléatoire classique, et le panneau affiche les deux pour le souligner.
  
  $N = 8 : uniform superposition gives P = \frac{1}{8} = 12.50%$
2. Chaque itération de Grover est une rotation d'un angle fixe dans un plan bidimensionnel engendré par l'état marqué et tous les autres. L'angle provient de l'amplitude, et pour N = 8, il est d'environ 20,7°.
  
  $sin θ = \frac{1}{N} ⟹ θ = 20.7 0^{\circ}; P_{k} = sin^{2} ((2 k + 1) θ)$
3. La probabilité n'est donc pas une courbe qui monte et se stabilise — c'est un sinus carré, et elle augmente rapidement : 12,5 %, puis 78,1 %, puis 94,5 %.
  
  $k = 1 : 78.12%; k = 2 : 94.53%; k = 3 : 33.01%$
4. Le point d'arrêt optimal est la rotation qui se rapproche le plus de 90°, c'est-à-dire π/4 fois la racine carrée de N. Pour huit éléments, cela donne 2,22 ; comme on ne peut pas effectuer une fraction d'itération, la valeur retenue est 2.
  
  $k_{opt} = ⌊ \frac{π}{4} N ⌋ = ⌊ 2.221 ⌋ = 2$
5. Lancez-en une troisième et la rotation dépasse l'objectif. La probabilité chute à 33,0 % — un résultat pire qu'après une seule itération, qui s'en retourne vers le point de départ.
  
  $classical \sim \frac{N}{2} = 4 queries vs O (N) = 2$
Réponse

L’outil affiche 12,50 % aussi bien pour la superposition initiale que pour la probabilité classique de 1 sur N. L’exécution automatique s’arrête à 2, mais les commandes permettant d’avancer d’une étape ou d’aller directement à la fin la poursuivent jusqu’à 5. C’est ce dépassement qui surprend : augmenter le nombre d’itérations dégrade le résultat, car l’amplification d’amplitude est une rotation, et toute rotation finit par revenir sur elle-même. Voilà également pourquoi l’accélération de Grover est quadratique, et non exponentielle. Il faut environ √N rotations pour atteindre 90° : 8 éléments en demandent donc 2, et un million, 785. C’est précieux, mais bien loin de l’avantage exponentiel que pourrait laisser entendre l’expression « recherche quantique ».

$P_{k} = sin^{2} ((2 k + 1) θ) ROTATES : past k_{opt} it falls again$

Références (1)

The algorithm this tool steps through: L. K. Grover, "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219, 1996.

Par l’équipe 42Math · Mis à jour 2026-07-29

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

N = 4 - N=4 éléments — une seule itération de Grover suffit pour trouver la cible
N = 8 - N=8 éléments — ~2 itérations optimales, taille classique pour une démonstration
N = 16 - N=16 éléments — 3 itérations optimales, la croissance en O(√N) est visible
N = 32 - N=32 éléments — ~4 itérations, illustre l'avantage quadratique