Introduction
L'algorithme de Grover est un algorithme quantique pour les problèmes dits de recherche non structurée qui offre une amélioration quadratique par rapport aux algorithmes classiques. Cela signifie que l'algorithme de Grover nécessite un nombre d'opérations de l'ordre de la racine carrée du nombre d'opérations requises pour résoudre une recherche non structurée de manière classique — ce qui revient à dire que les algorithmes classiques pour la recherche non structurée ont un coût au moins de l'ordre du carré du coût de l'algorithme de Grover.
L'algorithme de Grover, avec ses extensions et sa méthodologie sous-jacente, s'avère être largement applicable, offrant un avantage quadratique pour de nombreuses tâches de calcul intéressantes qui ne ressemblent pas nécessairement à des problèmes de recherche non structurée en surface.
Bien que la large applicabilité de la technique de recherche de Grover soit convaincante, il faut reconnaître dès le début de cette leçon que l'avantage quadratique qu'elle offre semble peu susceptible d'apporter un avantage pratique du quantique sur le classique dans un avenir proche. Le matériel informatique classique est bien plus avancé que le matériel quantique — et l'avantage quadratique du quantique sur le classique offert par l'algorithme de Grover sera inévitablement effacé par les vitesses d'horloge impressionnantes des ordinateurs classiques modernes pour tout problème de recherche non structurée susceptible d'être exécuté prochainement.
Au fur et à mesure que la technologie quantique progressera, cependant, l'algorithme de Grover pourrait avoir du potentiel. En effet, certains des algorithmes classiques les plus importants et les plus influents jamais découverts, notamment la transformée de Fourier rapide et les algorithmes de tri rapide (par exemple, le tri rapide et le tri fusion), offrent un avantage légèrement inférieur à quadratique par rapport aux approches naïves des problèmes qu'ils résolvent. La différence clé ici, bien entendu, est qu'une technologie entièrement nouvelle (à savoir l'informatique quantique) est nécessaire pour exécuter l'algorithme de Grover. Bien que cette technologie soit encore très jeune par rapport à l'informatique classique, nous ne devons pas sous-estimer trop vite le potentiel des avancées technologiques qui pourraient un jour permettre à un avantage quadratique du quantique sur le classique d'offrir des bénéfices pratiques tangibles.
Vidéo de la leçon
Dans la vidéo suivante, John Watrous te guide à travers le contenu de cette leçon sur l'algorithme de Grover. Tu peux également ouvrir la vidéo YouTube de cette leçon dans une fenêtre séparée. Télécharge les diapositives de cette leçon.