When searching 1 million items in no particular order for the one item that meets a condition, which is closest to the order of the number of queries (oracle calls) needed by Grover's algorithm?

Answer: B. About 1,000

Checking the items one by one on a classical computer takes about 500,000 tries on average (half the items) and 1 million in the worst case. Grover's algorithm gradually amplifies the amplitude of the correct answer and finds it with high probability after about √N iterations, precisely (π/4)√N ≈ 785, so the order is √(1 million) = about 1,000. The speed-up is only quadratic, with no exponential difference like that of Shor's algorithm. For symmetric-key ciphers, the number of tries for an exhaustive key search falls from 2ⁿ to about 2^(n/2), so it is thought that doubling the key length (moving from AES-128 to AES-256) is an adequate response.

• A. log₂(1 million) ≈ 20 is the number of steps of binary search on sorted data, which cannot be used on unordered data.
• B. Correct. √(1 million) = 1,000 is the order.
• C. This is the average number of tries when checking items one by one on a classical computer.