Studying Quantum Walks on Near-Term Quantum Computers
By Stina Andersson and Ellinor Wanzambi
Researchers have been working on quantum algorithms since physicists first proposed using principles of quantum physics to simulate nature decades. One important component in many quantum algorithms is quantum walks, which are the quantum equivalent of the classical Markov chain, i.e., a random walk without memory. Quantum walks are used in algorithms in areas such as searching, node ranking in networks, and element distinctness.
What is a random walk?
Consider the graph in Figure 1 and imagine that we randomly want to move between nodes A, B, C, and D in the graph. We can only move between nodes that are connected by an edge, and each edge has an associated probability that decides how likely we are to move to the connected node. This is a random walk. In this article, we are working only with Markov chains, also called the memory-less random walks, meaning that the probabilities are independent of the previous steps. For example, the probabilities of arriving at node A are the same no matter if we got there from node B or node D.
The probabilities in the graph in Figure 1 show how likely a walker is to move between the different nodes. If the walker stands at node A, they have a 50% chance to move to B and a 50% chance to move to D. In this graph, the walker is equally likely to move to each of its neighbors. Generally, Markov chains are not constrained by equal probabilities like this, but in this article, we will work with only such Markov chains.
Quantum walks
A quantum walk is the quantum equivalent of a Markov chain, and we will now see how we can implement a quantum walk using the Qiskit open source software development kit. Let’s start with some definitions. We start by giving all nodes a binary representation: A is now 00, B is 01, C is 10, and D is 11. Figure 2 shows the graph from figure 1 with binary representations. We can now represent the nodes in the graph by two-qubit quantum states: |00>, |01>, |10>, |11>. If the walker stands at node A, it is in state |00>. We call this state the position state. We also need a method to determine where the walker will go next. The walker could, for example, toss a coin. If the coin lands on heads, the walker moves to the right, and if the coin lands on tails, the walker moves to the left. We can use a Hadamard gate to achieve just this. Henceforth, we refer to it as a Hadamard coin or the coin operator. The Hadamard coin puts a qubit in an equal superposition, so it is 50% in state |0> and 50% in state |1>. So, if the coin is |0>, we move the walker to the right, and if the coin is |1>, we move it to the left. We call the state of the coin the coin state.
Now we have a position state and a coin state plus the coin operator, which in this case is a Hadamard coin that puts the qubit in superposition and creates the coin state. The final thing we need is some operator that actually moves the walker from the current state to the next state. We call this the shift operator. Let us now look at how the shift operator should move the walker.
If the coin state is |1>, we should move to the left. If the walker stands at position state |00> (A), it should move to |11> (D). Here are the left transitions for the four position states A-D:
|00> to |11> (A to D)
|01> to |00> (B to A)
|10> to |01> (C to B)
|11> to |10> (D to C)
If we look at the transitions above, we can see that, to get the correct binary representation for the next node, we always flip the last qubit, and then we will flip the first qubit if the new state of the last qubit is |1>. We can see the circuit for this left rotation below.
The third qubit here that controls the movement is the Hadamard coin, so we begin by applying the coin operator. q1 and q2 represent the position, so if q1 is |0> and q2 is |1>, we have state B, etc.
We know from the transitions above that if q3 is |1> (since we only move to the left if the coin is |1>), then we always invert q2. We achieve this with the CNOT gate. Then, if both q3 and q2 are |1> we invert q1. This is accomplished with the Toffoli gate, also known as the CCNOT gate.
Now that we have implemented the transitions to the left, let us do the same for transitions to the right, when the coin state is |0>. The transitions in this case are:
|00> -> |01> (A -> B)
|01> -> |10> (B -> C)
|10> -> |11> (C -> D)
|11> -> |00> (D -> A)
We can see that we here always flip the second qubit and flip the first qubit if the second qubit is in state |0>. The quantum circuit for the right rotation is therefore:
As we can see, this circuit is very similar to the left rotation circuit. The only difference is the NOT gates on the second and third qubit. This has to do with how CCNOT and CNOT gates work; they invert the target qubit if the control qubits are in state |1>. First of all, we only want to move the walker to the right if the coin (q3) is in state |0>. If we want the CNOT gate to invert the target qubit if the control qubit is in state |0> instead of state |1>, we have to apply a NOT gate on the control qubit before we apply the CNOT gate. Similarly, we want to invert q1 if the second qubit is in state |0>, so we must apply a NOT gate here also. Then, once we are done with the CNOT and CCNOT gates, we must add another two NOT gates that invert the qubits back to their correct states.
Now we put it all together to get one step of the quantum walk on a 4-node cycle. Qiskit always initializes the qubits to |0>, so we will start in node A (because q1 and q2 are both 0). Then we have the Hadamard coin and the left and right rotations. Because of the superposition, the walker will move both to the left and right simultaneously. So, if we measure the first and second qubits after one step, the walker will be in |01> (node B) and |11> (node D) around 50% each. We can see the full implementation of the circuit in figure 5.
Figure 6 shows the output of the circuit in figure 5. We can see in the figure that the walker is equally likely to move to state |11> and |01>, while the probability of going to any of the other states is 0. This is the expected result since the starting node (|00>) is only connected to the states |11> and |01>.
To implement more than one step, we just continue to apply the left and right rotations as many times as steps we want to implement before we measure. In figure 7, we see the quantum circuit for two steps of the walk.
So, now that you know how to implement rudimentary quantum walks, the next step is to employ these walks in an algorithm. I demonstrate this in the following section.
Quantum walk search algorithm
The quantum walk search algorithm solves the problem of finding marked vertices in a graph by a quantum walk. That is, we mark some set of vertices M, start at an arbitrary node in the graph and move according to the walk until we find the marked nodes. This algorithm would theoretically have a quadratic speed-up compared to its classical counterpart (as previously covered in the Qiskit blog, it’s not clear whether quadratic speedups will provide real world value but they’re still interesting to study).
Here we will describe the implementation of the algorithm on an N-node complete graph with self-loops. This is a graph where the walker can move to any other node, including the node they’re currently standing on. A complete graph with 4 nodes is shown below:
We start by showing how we can implement one step of the quantum walk on the graph. The number of node qubits equals two (to represent four positions) and the number of coin qubits also equals two (to represent four possible movements). We can therefore implement the shift operator by swapping the node qubits with the coin qubits. This is because the computational basis for a complete graph with self-loops is the same for both the node qubits and the coin qubits. The coin qubits return A, B, C, or D, and each node can shift to either A, B, C, or D in this graph, so there’s no more work required to tell the nodes how to shift than just assigning the node the value of the coin.
This implementation uses a Grover coin (which is the diffusion operator in Grover’s algorithm — check it out here in the Qiskit textbook) as the coin operator and the shift operators consist of swap gates to swap the node qubits with the coin qubits, as explained above. The implementation for N nodes is shown in figure 9 and the implementation of the Grover coin is found in figure 10.
Once we have implemented one step of a coined quantum walk, we can use it to implement a quantum walk search algorithm. This algorithm finds a marked node within O(1/√ϵ) iterations, where epsilon is the fraction of marked nodes.
This algorithm consists of three steps (More information about how to implement a phase oracle and a phase estimation is found in the Qiskit textbook):
First, put the node and coin qubits into superposition by using Hadamard gates.
Then, repeat O(1/√ϵ) times:
a) Apply a phase oracle that rotates the marked nodes
b) Use phase estimation followed by marking an auxiliary qubit when the theta qubits are not 0, where theta qubits are qubits we use as part of the computational requirements for the phase estimation algorithm. During the phase estimation, the phase is estimated in the theta qubit register, so if we to measure these qubits, they would return the estimated phase.
c) Reverse the phase estimation.
Finally, Measure the node qubits. The output should be a marked node for the majority of the time.
The complete implementation appears as follows:
We can implement steps 2b) and 2c) as follows. The QWALK gate used for the phase estimation in the image below is one step of a quantum walk with a Grover coin.
The results from running this implementation on a quantum simulator and a complete graph with self-loops and 16 nodes is shown below. Here 1011 and 1111 were the marked nodes and we did step 2 twice. As we can see in the figure, the algorithm returns a marked node 94.5% of the times.
Hopefully, this blog has provided a useful introduction to quantum walks and how to implement them on near-term quantum computers. While we probably won’t see quantum walk-based algorithms used in real-world applications just yet, they still serve as a useful topic to pursue as quantum computers develop.
