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, ...

Get Programming Quantum Computers now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.