Algorithme de Grover
Cherche dans un ensemble non trié en la racine carrée du nombre d'étapes plutôt qu'en la moitié — un gain quadratique, pas exponentiel.
Lov Grover l'a publié en 1996. Trouver la bonne entrée parmi un million sans aucune structure à exploiter demande classiquement, en moyenne, un demi-million d'essais. L'algorithme de Grover y parvient en environ mille. La méthode s'appelle amplification d'amplitude : l'amplitude de la bonne réponse est augmentée pas à pas pendant que les autres sont réduites, et après environ √N itérations, elle domine.
Le gain est réel mais modeste comparé à celui de Shor. La conséquence pratique pour la cryptographie est que les longueurs de clé symétriques sont effectivement réduites de moitié — AES-128 conserve une marge équivalente à 64 bits, tandis qu'AES-256 reste largement suffisant. C'est pourquoi le chiffrement symétrique n'a pas besoin d'être remplacé face aux ordinateurs quantiques, contrairement à l'asymétrique.