Présentation

L'algorithme de Grover est un algorithme quantique pour les problèmes de recherche non structurés 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 nécessaires pour résoudre une recherche non structurée de manière classique, ce qui revient à dire que les algorithmes classiques de recherche non structurée doivent avoir un coût au moins égal au carré du coût de l'algorithme de Grover.

L'algorithme de Grover, ainsi que ses extensions et la méthodologie sous-jacente, s'avèrent largement applicables, ce qui permet d'obtenir un avantage quadratique pour de nombreuses tâches informatiques intéressantes qui, à première vue, ne ressemblent pas à des problèmes de recherche non structurés.

Bien que l'applicabilité étendue de la technique de recherche de Grover soit convaincante, il convient de reconnaître ici, au début de la leçon, que l'avantage quadratique qu'elle offre semble peu susceptible de conduire à un avantage pratique de l'informatique quantique par rapport à l'informatique classique dans un avenir proche. Le matériel informatique classique est beaucoup plus avancé que le matériel informatique quantique - et l'avantage quadratique quantique sur classique offert par l'algorithme de Grover sera certainement balayé par les vitesses d'horloge stupéfiantes des ordinateurs classiques modernes pour tout problème de recherche non structuré qui pourrait être exécuté dans un avenir proche.

Toutefois, à mesure que la technologie de l'informatique quantique progresse, l'algorithme de Grover pourrait avoir du potentiel. En effet, certains des algorithmes classiques les plus importants et les plus percutants jamais découverts, notamment la transformée de Fourier rapide et le tri rapide (par exemple, le tri rapide et le tri par fusion), offrent un avantage légèrement inférieur à un quadratique par rapport aux approches naïves des problèmes qu'ils résolvent. La différence essentielle ici, bien sûr, est qu'une technologie entièrement nouvelle (c'est-à-dire l'informatique quantique) est nécessaire pour exécuter l'algorithme de Grover. Bien que cette technologie en soit encore à ses balbutiements par rapport à l'informatique classique, nous ne devrions pas sous-estimer le potentiel des avancées technologiques qui pourraient permettre à un avantage quadratique de l'informatique quantique par rapport à l'informatique classique d'offrir un jour des avantages pratiques tangibles.

Vidéo de cours

Dans la vidéo suivante, John Watrous vous explique le contenu de cette leçon sur l'algorithme de Grover. Vous pouvez également ouvrir la vidéo YouTube pour cette leçon dans une fenêtre séparée. Télécharger les diapositives de cette leçon.