36 CHAPTER 3. AMPLITUDE AMPLIFICATION

then a measurement applied to the superposition will give a solution with probability a, which means

the expected time to ﬁnd a solution is O(1/a). Indeed, if the probability of measuring a solution is

1/3, then we expect to perform the same procedure about 3 times to extract a solution.

Measuring the above superposition of states is essentially a random search algorithm, which

will require expected O(1/a) repetitions of the procedure. Let us consider the case where A generates

a uniform superposition. Then, there are N states in a uniform superposition of n-qubits. If there

is only one solution state, then the probability of measuring it is 1/N, and the expected complexity

is, therefore, O(N). This complexity is no better than a classical exhaustive examination of all the

states. The purpose of amplitude ampliﬁcation is to transform the superposition of states so that

a ≈ 1, i.e., the probability of measuring the solution state is much higher than 1/N.

3.1 QUANTUM SEARCH

General and provably optimal algorithms exist for performing amplitude ampliﬁc ation to identify a

desired solution from a superposition of states. Speciﬁcally, it applies O

N

1/2

transformations to

the superposition of states in a quantum register so that a subsequent measurement will obtain the

desired solution state with high probability. In other words, quantum search provides a quadratic

speedup over classical exhaustive search.

3.1.1 QUANTUM ORACLES

A quantum oracle is a quantum implementation of the orac le described on the previous section.

Clearly, any classical functional criteria can be described by means of a classical oracle. And any clas-

sical oracle can be implemented in the quantum domain by simply adding extra qubits to guarantee

the reversibility of the operation.

In such a case, the effect of a quantum oracle O for a solution f(x) = 1 for an indicator

Boolean function f is:

|x|q

O

→|x|q ⊕ f(x) (3.6)

where ⊕ indicates module 2 addition. By choosing the right input state, we can conveniently rewrite

this expression as:

|x

|0−|1

√

2

O

→ (−1)

f(x)

|x

|0−|1

√

2

. (3.7)

Clearly, the effect of the oracle is to change the phase of the solution, while leaving unchanged

the rest of the elements of the superposition.

In the above formula we have added an extra qubit to the register in the form of |q. This has

actually helped in moving the information of the quantum oracle into a phase change. However, as

the state of the extra qubits remain unchanged after the application of the oracle, these can be safely

ignored. Then, the effect of the orac le is often written as:

|x

O

→ (−1)

f(x)

|x . (3.8)

Get *Quantum Computer Science* now with O’Reilly online learning.

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