Introduction to Quantum Physics and Information Processing

168 Introduction to Quantum Physics and Information Processing

this becomes really large, the problem becomes harder. In fact, classically this

problem has a complexity O(N ). Grover’s algorithm turns out to be O(

√

N).

As in most quantum algorithms, the first step exploits quantum paral-

lelism, and inputs the uniform superposition of all x’s to the oracle U

f

k

, the

unitary implementation of f

k

(x):

|ψi =

1

√

2

n

N−1

X

x=0

|xi. (8.71)

It also uses the phase kickback trick to give f-dependent phases to the states

in this superposition:

|ψi ⊗ |−i

U

f

k

−−→

1

√

2

n+1

N−1

X

x=0

(−1)

f

k

(x)

|xi ⊗ |−i. (8.72)

We need to look more closely at the form of the output state. Remember

that ...