Remarques conclusives

Dans le modèle des requêtes, l'algorithme de Grover est asymptotiquement optimal. Cela signifie qu'il n'est pas possible de concevoir un algorithme de requête pour résoudre le problème de recherche, ni même le problème de recherche unique spécifiquement, qui utilise asymptotiquement moins de $O(\sqrt{N})$ requêtes dans le pire cas. C'est quelque chose qui a été démontré rigoureusement de plusieurs façons.

Ce qui est intéressant, c'est que cela était connu avant même que l'algorithme de Grover soit découvert — l'algorithme de Grover correspondait à une borne inférieure déjà connue.

L'algorithme de Grover est également largement applicable, dans le sens où l'accélération en racine carrée qu'il offre peut être obtenue dans divers contextes différents. Par exemple, il est parfois possible d'utiliser l'algorithme de Grover conjointement avec un autre algorithme pour obtenir une amélioration. L'algorithme de Grover est également très couramment utilisé comme sous-routine dans d'autres algorithmes quantiques pour obtenir des accélérations.

Enfin, la technique utilisée dans l'algorithme de Grover, où deux réflexions sont composées et itérées pour faire pivoter un vecteur d'état quantique, peut être généralisée. Un exemple est une technique connue sous le nom d'amplification d'amplitude, où un processus similaire à l'algorithme de Grover peut être appliqué à un autre algorithme quantique pour augmenter sa probabilité de succès de manière quadratiquement plus rapide que ce qui est possible classiquement. L'amplification d'amplitude a de nombreuses applications dans les algorithmes quantiques.

Ainsi, bien que l'algorithme de Grover ne soit peut-être pas susceptible de conduire à un avantage quantique pratique pour la recherche dans un avenir proche, c'est un algorithme quantique fondamentalement important, et il est représentatif d'une technique plus générale qui trouve de nombreuses applications dans les algorithmes quantiques.