Introduction

The advantage of the quantum function evaluator is that it can take all

possible inputs simultaneously as a superposition of states, and the corre-

sponding outputs are all simultaneously present in the output state. This has

often been called quantum parallelism. However, in this basic form it gives us

no advantage, since to actually discover the value of the function, we must

measure the output, upon which the output state will collapse to one of the

possible outputs at random. The trick to making quantum computing work

is to cleverly manipulate this basic function evaluator in such a way that the

probability amplitude for the answer to the problem is maximum. It is quan-

tum interference that enables this to happen. If this had not been possible,

quantum computing would have been a forgotten chapter in the history of

science. As it happens, this field received new impetus when Peter Shor shook

up the world in 1994 with his famous algorithm for finding the prime factors

of large integers.

All known quantum algorithms seem to fall into three broad classes:

1. Based on the Fourier transform: Deutsch–Josza, Shor’s algorithm etc.

2. Based on quantum search, involving amplitude amplification: Grover’s

algorithm etc.

3. Quantum simulations.

In this chapter we will examine the first two kinds, leaving the last to more

physics-specific texts. The algorithms are typically framed as yes-no answers

to inputs to the function evaluator treated as a black box (Figure 8.2). This

is also referred to as querying the oracle, as the unknown function evaluator

is regarded, like a mysterious priestess who will only give single-bit answers

when questioned!

?

?

1

FIGURE 8.2: Classical black box function evaluator as an oracle