import numpy as np
import matplotlib.pyplot as plt

Grover's Search Algorithm

Suppose we have a block box that preforms: $$U_w = I - 2 |w\rangle \langle w|$$

Applying $U_w$ to a state $\psi$ take the $w$th element of $\psi$ and flip it's sign.

We wish to figure out what $w$ is.

# Construct dimension of space
d = 40

# Construct |w>
w = np.zeros(d); w[7] = 1
w

array([0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
       0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
       0., 0., 0., 0., 0., 0.])

# Construct U_w
Uw = np.eye(d) - 2 * np.outer(w,w)
Uw

array([[1., 0., 0., ..., 0., 0., 0.],
       [0., 1., 0., ..., 0., 0., 0.],
       [0., 0., 1., ..., 0., 0., 0.],
       ...,
       [0., 0., 0., ..., 1., 0., 0.],
       [0., 0., 0., ..., 0., 1., 0.],
       [0., 0., 0., ..., 0., 0., 1.]])

Figuring out $w$

If we were able to observe the wavefunction $\psi$ after $U_w |\psi\rangle$ then we could figure out which coefficient changed. But we can't do that! QM forces linearity which also means we can only distinguish orthogonal states! So somehow we want to amplify the difference. Grover showed that using $$ U_s = 2|s\rangle \langle s| - I $$

where $s$ is an equal superposition, we can repeatedly apply $U_w$ and $U_s$ we amplify the difference

# Create equal superposition state
s = np.ones(d) / np.sqrt(d)
# Create U_s
Us = 2 * np.outer(s,s) - np.eye(d)
Us

array([[-0.95,  0.05,  0.05, ...,  0.05,  0.05,  0.05],
       [ 0.05, -0.95,  0.05, ...,  0.05,  0.05,  0.05],
       [ 0.05,  0.05, -0.95, ...,  0.05,  0.05,  0.05],
       ...,
       [ 0.05,  0.05,  0.05, ..., -0.95,  0.05,  0.05],
       [ 0.05,  0.05,  0.05, ...,  0.05, -0.95,  0.05],
       [ 0.05,  0.05,  0.05, ...,  0.05,  0.05, -0.95]])

Applying this iteration several times we can see that our $w$th coefficent has been amplifyied -- signifying that this is the answer!

iterations = 100
for i in range(iterations):
    s = Us.dot(Uw.dot(s))

plt.title('Probability of each state in s')
plt.bar(range(d), np.abs(s))

<BarContainer object of 40 artists>

Analyzing Grover's Algorithm

$|s\rangle$ and $|w\rangle$ aren't orthogonal, as $\langle w | s \rangle = \frac{1}{\sqrt{d}}$

s = np.ones(d) / np.sqrt(d)
s.conj().T.dot(w), 1 / np.sqrt(d)

(0.15811388300841897, 0.15811388300841897)

An orthogonal state however is: $$|\hat{s}\rangle = \frac{1}{\sqrt{d-1}} \sum_{i\neq w} |i\rangle$$

s_h = np.ones(d) / np.sqrt(d-1); s_h[7] = 0
s_h.conj().T.dot(w)

0.0

Define a vector $|\theta \rangle$ such that $$|\theta \rangle = \cos \theta |\hat{s}\rangle + \sin \theta |w\rangle$$

This gives us a unit circle defined by $\theta$

plt.figure(figsize=(8,8))
plt.axis('off')

# Superposition vector
s = np.ones(d) / np.sqrt(d)

# Plot a circle
t = np.arange(0, 2 * np.pi, 0.01)
plt.plot(np.cos(t), np.sin(t), linewidth=1)

def plot_vec(x,y, c, label=''):
    '''
        Helper function to plot a quiver vector
    '''
    plt.quiver(0,0, x, y, angles='xy', scale_units='xy', scale=1, color=c)
    plt.annotate(label, xy=(x,y + 0.05 * y))

def plot_g(vec, c, label=''):
    '''
        Helper function to plot a vector within |theta>
    '''
    x = s_h.conj().T.dot(vec)
    y = w.conj().T.dot(vec)
    plot_vec(x,y,c, label)

# Plot coordinate vectors
plot_g(w, 'black', label=r'$|w\rangle$')
plot_g(-w, 'black')
plot_g(s_h, 'black', label=r'$|\hat{s}\rangle$')
plot_g(-s_h, 'black')

# Plot inital state |s>
plot_g(s, 'g', label=r'$|s\rangle$')

# Plot iterations of Grover's search
steps = np.pi / 4 * np.sqrt(d-1)
for i in range(int(steps)):
    c = 'r'
    s = Uw.dot(s)
    plot_g(s,c, label=r'$U_w |s\rangle$')

    c = 'b'
    s = Us.dot(s)
    plot_g(s,c, label=r'$U_s U_w |s\rangle$')

plt.title('Geometrical picture of Grover\'s search')

Text(0.5, 1.0, "Geometrical picture of Grover's search")

We see that $U_w$ reflects $|s\rangle$ about $|\hat{s}\rangle$ and then $U_s$ reflects the state about $|s\rangle$. Each subsequent step leads to our desired state $|w\rangle$

TODO: how does this related to billards? https://arxiv.org/abs/1912.02207