Introduction to Quantum Physics and Information Processing

148 Introduction to Quantum Physics and Information Processing

superposition

|ψ

1

i =

1

√

2

n

2

n

−1

X

x=0

(−1)

f(x)

|xi. (8.9)

After the Hadamard, this state becomes

H

⊗n

|ψ

1

i =

1

2

n

2

n

−1

X

x,y=0

(−1)

[f(x)+x·y]

|yi. (8.10)

Here, we have used the result of Equation 7.28 and x ·y is the bitwise product

of x and y summed modulo 2, as in Equation 7.29. Now when f(x) is constant,

the amplitude for the state |0i in this superposition is

coefficient of |0i =

1

2

n

X

x

(−1)

f(x)

= 1.

In other words the probability of getting |0i is one for a constant function.

Whereas if f(x) is balanced, then the amplitude for |0i is a sum of an equal

number of +1s and −1s, that is, zero. Thus if the function ...