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.
Le voir en mouvement
Après une inscription gratuite, vous revenez directement à ce concept.
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
Notions liées
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 qui contrôle ses réponses et indique leur degré de certitude. Les niveaux 1–5 sont gratuits.