6 Quantum search and probability estimation

In this chapter, we will see how quantum measurement can help us with our second main pattern of quantum computations: searching for specific outcomes. Specifically, we will learn about Grover’s algorithm and related methods, such as amplitude amplification. Grover’s algorithm can offer quadratic speed up (with respect to the number of queries) over classical approaches for certain problems. Therefore, the methods introduced in this chapter have broad applications, such as search, optimization, and machine learning. To start, we will dive into one of the most common and consequential computational challenges: unstructured search.

6.1 Amplitude amplification: Intuition and classical implementation

6.1.1 Finding good outcomes with oracles

6.1.2 Computing similarity with inner products

6.1.3 The inversion operator

6.1.4 Putting it together: The Grover iterate

6.1.5 A classical but quantum-friendly implementation of the inversion operator

6.2 Magnitude amplification: Quantum circuit implementation

6.2.1 Quantum oracle

6.2.2 The inversion operator

6.2.3 Grover iterate

6.2.4 Putting it all together: Grover’s algorithm

Summary