Quantum Searching

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 52/2 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 \left|6\right\rangle will therefore represent the ace of spades.

2. Let \left|\phi\right\rangle be the superposition of states:

\displaystyle \left|\phi\right\rangle =  \frac{1}{2^{n/2}} \sum_{k=0}^{2^n-1} \left|x\right\rangle = \frac{1}{2^{n/2}} \Big( \left|0\right\rangle + \ldots + \left|7\right\rangle \Big) = \frac{1}{\sqrt{8}} \left[ \begin{array}{c}  1\\  1\\  1\\  1\\  1\\  1\\  1\\  1  \end{array} \right]

3. Let f be a function such that

f(x) = \begin{cases}  1 & x \text{ corresponds to ace of spades}\\  0 & \text{ otherwise}  \end{cases}

Define the operator \mathbf{V}

\mathbf{V} = \mathbf{I} - 2\left|a\right\rangle \left\langle a\right|

where a is the unique value where

f(a) = 1

In our example, the value of a is 6. Therefore,

\mathbf{V} = \begin{bmatrix}    1.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 \\     0.00 & 1.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 \\     0.00 & 0.00 & 1.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 \\     0.00 & 0.00 & 0.00 & 1.00 & 0.00 & 0.00 & 0.00 & 0.00 \\     0.00 & 0.00 & 0.00 & 0.00 & 1.00 & 0.00 & 0.00 & 0.00 \\     0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 1.00 & 0.00 & 0.00 \\     0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & -1.00 & 0.00 \\     0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 1.00 \\     \end{bmatrix}

Observe that the matrix element \mathbf{V}_{6,6} = -1

4. Define the operator W:

\mathbf{W} = 2\left|\phi\right\rangle \left\langle\phi\right| - \mathbf{I} = \begin{bmatrix}    -0.75 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 \\     0.25 & -0.75 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 \\     0.25 & 0.25 & -0.75 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 \\     0.25 & 0.25 & 0.25 & -0.75 & 0.25 & 0.25 & 0.25 & 0.25 \\     0.25 & 0.25 & 0.25 & 0.25 & -0.75 & 0.25 & 0.25 & 0.25 \\     0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.75 & 0.25 & 0.25 \\     0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.75 & 0.25 \\     0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.75 \\     \end{bmatrix}

5. Compute the operator \mathbf{WV}:

\mathbf{WV} = \begin{bmatrix}    -0.75 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.25 & 0.25 \\     0.25 & -0.75 & 0.25 & 0.25 & 0.25 & 0.25 & -0.25 & 0.25 \\     0.25 & 0.25 & -0.75 & 0.25 & 0.25 & 0.25 & -0.25 & 0.25 \\     0.25 & 0.25 & 0.25 & -0.75 & 0.25 & 0.25 & -0.25 & 0.25 \\     0.25 & 0.25 & 0.25 & 0.25 & -0.75 & 0.25 & -0.25 & 0.25 \\     0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.75 & -0.25 & 0.25 \\     0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.75 & 0.25 \\     0.25 & 0.25 & 0.25 & 0.25 & 0.25 & 0.25 & -0.25 & -0.75 \\     \end{bmatrix}

6. Multiply \mathbf{WV} to \left|\phi\right\rangle a number of times, about \pi/4 \cdot 2^{n/2} = \pi/4 \cdot \sqrt{8} = 2.2 \approx 2:

\mathbf{WV}\left|\phi\right\rangle = \begin{bmatrix}    0.18 \\     0.18 \\     0.18 \\     0.18 \\     0.18 \\     0.18 \\     0.88 \\     0.18 \\     \end{bmatrix}, \mathbf{(WV)^2}\left|\phi\right\rangle = \begin{bmatrix}    -0.09 \\     -0.09 \\     -0.09 \\     -0.09 \\     -0.09 \\     -0.09 \\     0.97 \\     -0.09 \\     \end{bmatrix}

As you can see, the probability of getting the state \left|6\right\rangle becomes very close to 1.

Making a measurement of the input register at this point will give us the state \left|6\right\rangle with a probability very close to 1.

We have just demonstrated the quantum search algorithm!

Why it works

Let f be a function such that

f(x) = \begin{cases}  1 & x \text{ the item we are looking for}\\  0 & \text{ otherwise}  \end{cases}

Define the operator \mathbf{U}_f whose action on an n qubit register and 1 qubit output register is

\mathbf{U}_f(\left|x\right\rangle \otimes \left|y\right\rangle) = \left|x\right\rangle\otimes\left|y\oplus f(x)\right\rangle

Prepare the n qubit input register and 1 qubit output register in the following state:

\underbrace{\left|0\right\rangle\ldots \left|0\right\rangle}_{\text{n times}} \otimes \left|1\right\rangle

Applying the Hadamard operator on the input and output qubits gives us a superposition of N=2^n states:

\begin{array}{rl}  \displaystyle \mathbf{H}^{\otimes n}\otimes\mathbf{H}(\left|0\ldots 0\right\rangle\otimes \left|1\right\rangle )&= \mathbf{H}^{\otimes n}\left|0\ldots 0\right\rangle\otimes \mathbf{H}\left|1\right\rangle\\  &= \displaystyle \frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes \frac{1}{\sqrt{2}} \left(\left|0\right\rangle - \left|1\right\rangle\right)    \end{array}

Next apply the operator \mathbf{U}_f to get

\begin{array}{rl}  \displaystyle \mathbf{U}_f \left[\frac{1}{2^{n/2}}\sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes \frac{1}{\sqrt{2}} \left(\left|0\right\rangle - \left|1\right\rangle\right)\right] &= \displaystyle \frac{1}{\sqrt{2}} \frac{1}{2^{n/2}}\left[\sum_{x=0}^{2^n-1} \mathbf{U}_f \left|x\right\rangle \otimes  \left|0\right\rangle - \sum_{x=0}^{2^n-1} \mathbf{U}_f \left|x\right\rangle \otimes \left|1\right\rangle\right]  \\  &= \displaystyle \frac{1}{\sqrt{2}} \frac{1}{2^{n/2}}\left[\underbrace{\sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes  \left|0\oplus f(x) \right\rangle }_{\text{first underbrace}}  - \underbrace{\sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes \left|1\oplus f(x) \right\rangle}_{\text{second underbrace}}\right]  \end{array}

When f(x) = 1 for x=a, the first underbrace will expand to

\displaystyle \sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes  \left|0\oplus f(x) \right\rangle = \left|0\right\rangle\otimes\left|0\right\rangle + \ldots + \underbrace{\left|a\right\rangle\otimes\left|1\right\rangle} + \ldots + \left|2^n-1\right\rangle \otimes \left|0\right\rangle

The second underbrace will expand to

\displaystyle \sum_{x=0}^{2^n-1} \left|x\right\rangle \otimes  \left|1\oplus f(x) \right\rangle = \left|0\right\rangle\otimes\left|1\right\rangle + \ldots + \underbrace{\left|a\right\rangle\otimes\left|0\right\rangle} + \ldots + \left|2^n-1\right\rangle \otimes \left|1\right\rangle\\

The underbraces in the above summations can be swapped so that we get

\displaystyle \frac{1}{\sqrt{2}} \frac{1}{2^{n/2}} \left[ \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle \otimes  \left|0\right\rangle - \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle \otimes \left|1\right\rangle\right]

\begin{array}{rl}  &= \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle \otimes \frac{1}{\sqrt{2}} \left( \left|0\right\rangle - \left|1\right\rangle\right)\\  &= \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle \otimes \mathbf{H}\left|1\right\rangle  \end{array}

This means that the action of \mathbf{U}_f 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 \mathbf{V} defined by

\mathbf{V} \left|\phi\right\rangle = \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle

where

\left|\phi\right\rangle = \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} \left|x\right\rangle

We can derive the expression of \mathbf{V} by expanding \mathbf{V} \left|\phi\right\rangle, noting that at x=a, f(x) = 1:

\begin{array}{rl}  \mathbf{V} \left|\phi\right\rangle &= \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} (-1)^{f(x)} \left|x\right\rangle\\  &= \displaystyle \frac{1}{2^{n/2}} \left[\left|0\right\rangle + \ldots - \left|a\right\rangle +\ldots + \left|2^n-1\right\rangle\right]\\  &= \displaystyle \frac{1}{2^{n/2}} \left[\left|0\right\rangle + \ldots + \left|a\right\rangle +\ldots + \left|2^n-1\right\rangle - 2\left|a\right\rangle\right]\\  &= \displaystyle \frac{1}{2^{n/2}} \sum_{x=0}^{2^n-1} \left|x\right\rangle - \frac{2}{2^{n/2}} \left|a\right\rangle\\  &= \left|\phi\right\rangle - 2\left\langle a|\phi\right\rangle \left|a\right\rangle\\  &= \Big[\mathbf{I} - 2\left|a\right\rangle \left\langle a\right|\Big] \left|\phi\right\rangle\\  \end{array}

which means

\mathbf{V} = \mathbf{I} - 2\left|a\right\rangle \left\langle a\right|

The two vectors \left|\phi\right\rangle and \left|a\right\rangle determine a plane P. Let \left|a_{\perp}\right\rangle be the vector in the plane perpendicular to \left|a\right\rangle. We can write \left|\phi\right\rangle as

\left|\phi\right\rangle = \phi_1 \left|a_\perp\right\rangle + \phi_2\left|a\right\rangle

Applying \mathbf{V} to \left|\phi\right\rangle gives us:

\begin{array}{rl}  \mathbf{V}\left|\phi\right\rangle &= \left(\mathbf{I} - 2\left|a\right\rangle \left\langle a\right| \right) \left(  \phi_1 \left|a_\perp\right\rangle + \phi_2\left|a\right\rangle \right)\\  &= \phi_1 \left|a_\perp\right\rangle + \phi_2\left|a\right\rangle - 2\phi_2\left|a\right\rangle\\  &= \phi_1 \left|a_\perp\right\rangle - \phi_2\left|a\right\rangle  \end{array}

The effect of the operator \mathbf{V} is therefore to reflect the vector \left|\phi\right\rangle with respect to the vector \left|a_\perp\right\rangle.

Now, we want to reflect this vector \mathbf{V}\left|\phi\right\rangle with respect to \left|\phi\right\rangle. To accomplish this, we define the operator \mathbf{W} by

\mathbf{W} = 2\left|\phi\right\rangle \left\langle\phi\right| - \mathbf{I}

Apply this operator to \mathbf{V}\left|\phi\right\rangle:

\begin{array}{rl}  \mathbf{WV}\left|\phi\right\rangle &= \Big[ 2\left|\phi\right\rangle \left\langle\phi\right| - \mathbf{I} \Big]\mathbf{V}\left|\phi\right\rangle\\  &= 2\left|\phi\right\rangle \left\langle\phi\right|\mathbf{V}\left|\phi\right\rangle -\mathbf{V}\left|\phi\right\rangle  \end{array}

If we express \mathbf{V}\left|\phi\right\rangle as a linear combination of \left|\phi\right\rangle and a vector \left|\phi_\perp\right\rangle in the plane P,

\mathbf{V}\left|\phi\right\rangle = \alpha \left|\phi\right\rangle + \beta \left|\phi_\perp\right\rangle

We have,

\begin{array}{rl}  \mathbf{WV}\left|\phi\right\rangle &= \Big[ 2\left|\phi\right\rangle \left\langle\phi\right| - \mathbf{I} \Big]\mathbf{V}\left|\phi\right\rangle\\  &= 2\left|\phi\right\rangle \left\langle\phi\right|\mathbf{V}\left|\phi\right\rangle -\mathbf{V}\left|\phi\right\rangle\\  &= 2\alpha\left|\phi\right\rangle  - \alpha \left|\phi\right\rangle - \beta \left|\phi_\perp\right\rangle\\  &= \alpha\left|\phi\right\rangle  - \beta \left|\phi_\perp\right\rangle  \end{array}

which demonstrates that \mathbf{W} reflects \mathbf{V}\left|\phi\right\rangle with respect to \left|\phi\right\rangle.

Therefore, the effect of \mathbf{WV} on \left|\phi\right\rangle is to rotate it by an angle \gamma counter-clockwise.

We can compute this \gamma by getting the inner product of \mathbf{WV}\left|\phi\right\rangle and \left|\phi\right\rangle. First, let’s find the expression of \mathbf{WV}\left|\phi\right\rangle:

\begin{array}{rl}  \mathbf{WV}\left|\phi\right\rangle &= \mathbf{W} \left( \mathbf{I} - 2\left|a\right\rangle \langle a |\right) \left|\phi\right\rangle\\  &= \mathbf{W} \left(\left|\phi\right\rangle - 2 \underbrace{\langle a| \phi \rangle} \left|a\right\rangle \right)  \end{array}

The quantity \langle a| \phi \rangle is

\langle a| \phi \rangle = \displaystyle \langle a| \left( \frac{1}{2^{n/2}} \sum_{k=0}^{2^n-1} \left|x\right\rangle \right) = \frac{1}{2^{n/2}} = \cos \theta

where \theta is the angle between \left|a\right\rangle and \left|\phi\right\rangle.

The complementary angle, \rho = 90-\theta is the angle between \left|\phi\right\rangle and \left|a_\perp\right\rangle. Using a well-known trigonometric identity, we can compute for the angle of \rho:

\cos \theta = \sin \rho = \displaystyle \frac{1}{2^{n/2}}

Since \displaystyle \frac{1}{2^{n/2}} is very small if n is large,

\sin \rho = \displaystyle \frac{1}{2^{n/2}} \approx \rho

Continuing,

\begin{array}{rl}  \mathbf{WV}\left|\phi\right\rangle &= \mathbf{W} \left( \mathbf{I} - 2\left|a\right\rangle \langle a |\right) \left|\phi\right\rangle\\  &= \mathbf{W} \left(\left|\phi\right\rangle - 2 \cos\rho \left|a\right\rangle \right)\\  &= (2\left|\phi\right\rangle \langle \phi| - \mathbf{I}) \left(\left|\phi\right\rangle - 2 \cos\rho \left|a\right\rangle \right)\\  &= 2\left|\phi\right\rangle - \left|\phi\right\rangle - 2\cos\rho \left|\phi\right\rangle \langle \phi |a\rangle + 2 \cos\rho \left|a\right\rangle\\  &= \left|\phi\right\rangle - 4\cos^2\rho \left|\phi\right\rangle + 2 \cos\rho \left|a\right\rangle\\  &= (1- 4\cos^2\rho) \left|\phi\right\rangle + 2 \cos\rho \left|a\right\rangle  \end{array}

The inner product of \mathbf{WV}\left|\phi\right\rangle and \left|\phi\right\rangle is given by

\begin{array}{rl}  \langle\phi|\mathbf{WV}\left|\phi\right\rangle &= \langle\phi|\left[  (1- 4\cos^2\rho) \left|\phi\right\rangle + 2 \cos\rho \left|a\right\rangle\right]\\  &= (1- 4\cos^2\rho) + 2\cos^2\rho\\  &= 1- 2\cos^2\rho\\  &= \cos 2\rho  \end{array}

Therefore, the angle between these two vectors is 2\rho = \displaystyle \frac{1}{2^{n/2}}. How many times do we have to apply the operator \mathbf{WV} to get to \pi/2?

\begin{array}{rl}  m\cdot 2\rho &= \displaystyle \frac{\pi}{2}\\  \displaystyle m \frac{2}{2^{n/2}}&= \displaystyle \frac{\pi}{2}\\  m &=\displaystyle \frac{\pi\cdot 2^{n/2}}{4}  \end{array}

Therefore, we need to apply the operator \mathbf{WV} O(\sqrt{N}) times to find our value (where N=2^n).

Advertisements