Imagine a shuffled deck of 52 cards, and you are asked to find the ace of spades. The most natural thing to do is to take the top most card, see if it’s the ace of spades. If not, put it aside, take the top most and repeat the process until you find the ace of spades. If you are lucky, the ace of spades is the top most then we’re done. If you’re not so lucky, the ace of spades is at the bottom and it will take you 52 peeks before you find the card.
If we scatter the cards face down on the floor and randomly pick a card, then on the average, we will need peeks before we can find the ace of spades.
With quantum computing we can do even better!
For the sake of demonstration, let’s say we have 8 cards as shown in the figure below. We want to find the ace of spades.
Here are the steps:
1. Label each card from 0 to 7 in random order. The positions of the cards will represent the states of cards. The state will therefore represent the ace of spades.
2. Let be the superposition of states:
3. Let be a function such that
Define the operator
where a is the unique value where
In our example, the value of a is 6. Therefore,
Observe that the matrix element
4. Define the operator W:
5. Compute the operator :
6. Multiply to a number of times, about :
As you can see, the probability of getting the state becomes very close to 1.
Making a measurement of the input register at this point will give us the state with a probability very close to 1.
We have just demonstrated the quantum search algorithm!
Why it works
Let be a function such that
Define the operator whose action on an n qubit register and 1 qubit output register is
Prepare the n qubit input register and 1 qubit output register in the following state:
Applying the Hadamard operator on the input and output qubits gives us a superposition of states:
Next apply the operator to get
When for x=a, the first underbrace will expand to
The second underbrace will expand to
The underbraces in the above summations can be swapped so that we get
This means that the action of leaves the output qubit unentangled with the input qubit. We can just ignore this moving forward and focus our attention to the input qubits.
We view the current state of the input qubit as the result of some operator defined by
We can derive the expression of by expanding , noting that at x=a, :
The two vectors and determine a plane P. Let be the vector in the plane perpendicular to . We can write as
Applying to gives us:
The effect of the operator is therefore to reflect the vector with respect to the vector .
Now, we want to reflect this vector with respect to . To accomplish this, we define the operator by
Apply this operator to :
If we express as a linear combination of and a vector in the plane P,
which demonstrates that reflects with respect to .
Therefore, the effect of on is to rotate it by an angle counter-clockwise.
We can compute this by getting the inner product of and . First, let’s find the expression of :
The quantity is
where is the angle between and .
The complementary angle, is the angle between and . Using a well-known trigonometric identity, we can compute for the angle of :
Since is very small if n is large,
The inner product of and is given by
Therefore, the angle between these two vectors is . How many times do we have to apply the operator to get to ?
Therefore, we need to apply the operator times to find our value (where ).