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
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 ⊕ f(x) (3.6)
where ⊕ indicates module 2 addition. By choosing the right input state, we can conveniently rewrite
this expression as:
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 . (3.8)