O'Reilly logo

Programming Quantum Computers by Mercedes Gimeno-Segovia, Nic Harrigan, Eric R. Johnston

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required