Source vérifiéeNiveau 3
Algorithme de Grover
L'algorithme de Grover offre une acceleration quadratique pour la recherche non structuree avec O(√N) requetes.
Ce que cela signifie
Utilise un oracle de phase et la diffusion de Grover de maniere iterative.Optimal pour la recherche non structuree.Analogie du quotidien
Comme un effet de resonance.
Comme une echolocation quantique.
Idées reçues fréquentes
- Acceleration quadratique, pas exponentielle.
- Trop d'iterations reduit la probabilite de succes.
À retenir
- O(√N) requetes.
- Oracle de phase + amplification d'amplitude.
- Prouvé optimal.
Vérifiez votre compréhension
Complexite de Grover?
- A.O(N)
- B.O(log N)
- C.O(√N)
- D.O(N²)
Voir la réponse
Réponse: C. O(√N)
Pourquoi: O(√N) requetes oracle.
S’appuie sur
Source primaire: Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325 (1997), doi:10.1103/PhysRevLett.79.325
Apprendre en pratiquant
Ce concept fait partie d’un cursus de 46 niveaux, avec un simulateur interactif et Lumen — un tuteur dont les réponses sont vérifiées avant affichage. Les niveaux 1–5 sont gratuits.