Pour chercher, parmi 1 million d'éléments rangés sans ordre particulier, l'unique élément qui satisfait une condition, quelle valeur est la plus proche de l'ordre de grandeur du nombre de requêtes (appels à l'oracle) nécessaires à l'algorithme de Grover ?

Réponse : B. Environ 1000

Vérifier les éléments un à un sur un ordinateur classique demande en moyenne environ 500 000 essais (la moitié des éléments), et 1 million dans le pire cas. L'algorithme de Grover amplifie progressivement l'amplitude de la bonne réponse et la trouve avec une forte probabilité après environ √N itérations, précisément (π/4)√N ≈ 785 : l'ordre de grandeur est donc √(1 million) = environ 1000. L'accélération n'est que quadratique, sans écart exponentiel comme celui de l'algorithme de Shor. Pour la cryptographie symétrique, le nombre d'essais d'une recherche exhaustive de la clé passe de 2ⁿ à environ 2^(n/2) : on estime donc que doubler la longueur de clé (passer d'AES-128 à AES-256) est une réponse suffisante.