A quadratic speedup means reducing a corresponding classical runtime from O(N) to O(√N). Grover’s search achieves this for an unstructured black-box problem: finding one input among N possibilities requires O(√N) oracle calls instead of O(N). section 1.3.1 section 7.2.2
Interpret the speedup carefully:
- Compare equivalent oracle-query models; the advantage concerns the number of function evaluations, not automatically total wall-clock runtime. section 1.3.1 section 7.2.2
- Account for problem structure: indexed or partitioned classical data can outperform Grover’s black-box approach, even when the asymptotic comparison favors the quantum algorithm. section 1.3.1
- Account for hardware and arithmetic costs, because slower quantum operations can outweigh the theoretical reduction in queries. section 1.3.1
Grover search with multiple solutions
If M of N inputs satisfy the oracle, Grover’s algorithm needs approximately √(N/M) queries, compared with an average N/M classical queries. Its iterations apply a phase oracle and a reflection about the mean before measurement; too many iterations reduce the success probability. section 7.2.2
