Chapter 10. Quantum Search
In Chapter 6 we saw how the amplitude amplification (AA) primitive changes differences in phases within a register into detectable variations in magnitude. Recall that when introducing AA, we assumed that applications would provide a subroutine to flip the phases of values in our QPU register. As a simplistic example, we used the
flip circuit as a placeholder, which simply flipped the phase of a single known register value. In this chapter we will look in detail at several techniques for flipping phases in a quantum state based on the result of nontrivial logic.
Quantum Search (QS) is a particular technique for modifying the
flip subroutine such that AA allows us to reliably
READ solutions from a QPU register for a certain class of problems. In other words, QS is really just an application of AA, formed by providing an all-important subroutine1 marking solutions to a certain class of problems in a register’s phases.
The class of problems that QS allows us to solve is those that repeatedly evaluate a subroutine giving a yes/no answer. The yes/no answer of this subroutine is, generally, the output of a conventional boolean logic statement.2 One obvious problem that can be cast in this form is searching through a database for a specific value. We simply imagine a boolean function that returns a
1 if and only if an input is the database element we’re searching for. This was in fact the prototypical use of Quantum Search, and is known, after its discoverer, ...