Unter 1 Million ungeordneten Datensätzen soll der eine gefunden werden, der eine Bedingung erfüllt. Welcher Wert liegt der Größenordnung der Zahl der Abfragen (Orakelaufrufe) am nächsten, die der Grover-Algorithmus dafür benötigt?

Antwort: B. Etwa 1000

Auf einem klassischen Computer dauert es, die Datensätze einzeln zu prüfen, im Mittel etwa 500.000 Versuche (die Hälfte der Datensätze) und im schlechtesten Fall 1 Million. Der Grover-Algorithmus verstärkt schrittweise die Amplitude der richtigen Antwort und findet sie nach etwa √N Iterationen, genau (π/4)√N ≈ 785, mit hoher Wahrscheinlichkeit; die Größenordnung ist also √(1 Million) = etwa 1000. Die Beschleunigung ist nur quadratisch, ohne einen exponentiellen Unterschied wie beim Shor-Algorithmus. Bei symmetrischer Verschlüsselung sinkt die Zahl der Versuche einer erschöpfenden Schlüsselsuche von 2ⁿ auf etwa 2^(n/2); man geht daher davon aus, dass eine Verdoppelung der Schlüssellänge (von AES-128 auf AES-256) als Gegenmaßnahme genügt.