Programming Quantum Computers

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 subroutine¹ 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.² 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, ...