Welke waarde ligt het dichtst bij de orde van het aantal zoekvragen (orakelaanroepen) dat het algoritme van Grover nodig heeft om in 1 miljoen ongeordende gegevens het ene item te vinden dat aan een voorwaarde voldoet?

Antwoord: B. Ongeveer 1000

Op een klassieke computer de items één voor één controleren kost gemiddeld ongeveer 500.000 pogingen (de helft van de items) en in het slechtste geval 1 miljoen. Het algoritme van Grover versterkt geleidelijk de amplitude van het juiste antwoord en vindt het met hoge kans na ongeveer √N iteraties, precies (π/4)√N ≈ 785, dus de orde is √(1 miljoen) = ongeveer 1000. De versnelling is alleen kwadratisch, zonder exponentieel verschil zoals bij het algoritme van Shor. Bij symmetrische cryptografie daalt het aantal pogingen voor een uitputtende zoektocht naar de sleutel van 2ⁿ tot ongeveer 2^(n/2), dus naar verwachting volstaat het om de sleutellengte te verdubbelen (van AES-128 naar AES-256).