Introduction to Quantum Physics and Information Processing

Chapter 8

Quantum Algorithms

In the last chapter, we introduced the circuit model for quantum computation,

where a computation is essentially the evaluation of a function. In the binary

system of computation a function is a map f : {0, 1}

n

7→ {0, 1}

m

. The function

takes an n-bit input and produces an m-bit output. However, this can be

regarded as m functions f

i

: {0, 1}

n

7→ {0, 1}, that take an n-bit input and

give a one-bit output, each of which is one bit of f(x). We can thus restrict our

attention to n → 1 functions alone, in other words, we can reduce our problem

to questions with yes/no answers, a so-called binary decision problem.

In order to evaluate ...