Quantum Circuit Implementing Grover's Search Algorithm

number of qubits: n

2

3

4

hidden item: k

0

1

2

3

number of iterations: m

1

2

optimal number of iterations:

1

Probability takes a maximum P = 1.0 for x = 0

The search problem is formulated as follows: some

n

-bit integer

k

is hidden in a black-boxed subroutine that indicates, when presented with any

n

-bit integer

x

, whether or not

x

coincides with

k

, returning this information as the value of the

n

-bit binary function. The function is implemented by the quantum circuit bounded by two dashed lines in the diagram. The problem is to find

k

in a minimum number of applications of the subroutine.

This Demonstration shows a quantum circuit implementing Grover's search algorithm that enables finding any given integer

k

from the list

{0,1,...,N-1}

, where

N=

n

2

, with a probability that is very close to 1, repeating Grover's iterations

m

opt

times, where

m

opt

is the integer part of the number

π4arcsin1

N



.