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 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 , a quadratic increase. This increase is the power of quantum computing.
A Quantum Walk on Four Nodes
Let's image a square graph with four nodes.
This is a simple circuit for one step of a quantum walk.
The first two qubits, and , representing the network of four nodes: 00, 01, 10 and 11. We'll begin our walk on node 00. The last qubit, , represents the quantum coin.
This is an open-ended exercise. Clone the related project and play around with the circuit.
Here are some suggestions:
- Change number of steps 2, then 3, 4, 5, 6. See if you find any patterns.
- Change initial state by applying different one-qubit gates. Notice how this affects the walk after a few steps.
- Change how to prepare the coin by applying different one qubit gates to. Notice how this affects the walk after a few steps.
- Play around with more gates, break the walk, rebuild it.
- Advanced: Can you change the circuit to change the network somehow?
- Advanced: Can you make the network bigger with different connectivities?