Quantum Walk Intro

You talk the talk, but can you walk the walk? This simple example brings together one-qubit and two-qubit gates.

Imagine flipping a coin. If it is heads take a step to the left. If it is tails, take a step to the right. Repeat this process a few times. This is an example of a classical random walk.

Where might we end up if we take 7 steps?

According to our histogram, we'll most likely end up in a range the size of the standard deviation, which in this case is $\sqrt{N}$ where N is the number of steps we took.

Now, what if we used a qubit in a superposition instead of a coin to decide if we should take a step to the left or a step to the right. This is called a quantum walk. At each step, we enter a superposition of the previous step.

Only when we finally make a measurement do we find that the histogram looks very different from the classical walk. Now there is a greater chance to be further from the center. In fact, the standard deviation of our new histogram is simply $N$​, a quadratic increase. This increase is the power of quantum computing.

A Quantum Walk on Four Nodes

Imagine a square graph with four nodes.

This is a simple circuit for one step of a quantum walk.

The first two qubits, $q_0$​ and $q_1$​, representing the network of four nodes: 00, 01, 10 and 11. We'll begin our walk on node 00. The last qubit, $q_2$​, represents the quantum coin.

This is an open-ended exercise. Clone the related project and play around with the circuit.

Here are some suggestions:

1. Change number of steps 2, then 3, 4, 5, 6. See if you find any patterns.
2. Change initial state by applying different one-qubit gates. Notice how this affects the walk after a few steps.
3. Change how to prepare the coin by applying different one-qubit gates. Notice how this affects the walk after a few steps.
4. Play around with more gates, break the walk, rebuild it. 
5. Advanced:  Can you change the circuit to change the network somehow? 
6. Advanced:  Can you make the network bigger with different connections?