Quantum search algorithm using a quantum random walk
A coursework project studying Shenvi, Kempe, and Whaley's quantum random-walk search algorithm, which searches an unsorted list of N items in O(√N) steps, the same order as Grover's algorithm. I implemented their algorithm's walk on a hypercube in Wolfram Mathematica and verified it numerically up to a 5-cube, after first writing a Python simulation of the classical random walk on a hypercube for comparison.
This was coursework for Quantum Information and Quantum Computation at NISER Bhubaneswar, taught by Dr Colin Benjamin.
The problem
A classical search through an unsorted list of N items takes O(N) queries in the worst case. Grover's algorithm reaches O(√N) on a quantum computer. Neil Shenvi, Julia Kempe, and K. Birgitta Whaley reach the same O(√N) scaling by a different route, a quantum walk on a hypercube rather than Grover's direct amplitude amplification. My report studies their paper, "A Quantum Random Walk Search Algorithm" (Shenvi, Kempe & Whaley, Phys. Rev. A 67, 052307, 2003), and reimplements the algorithm.
The approach
A random walk on a graph works by a coin flip that picks a direction, then a shift that moves the walker. On an n-dimensional hypercube (n-cube), each of the 2^n nodes is an n-bit string, and moving along direction i is an XOR with a bitstring holding a single 1 in position i. I implemented that as adding 2^(i-1) modulo 2^n to the node's decimal index, the same trick for both the classical and the quantum version of the walk.
I first wrote the classical random walk on a hypercube in Python, plotting probability against position for a 3-cube and a 7-cube after 10 steps, to see how it behaved before working with its quantum counterpart.
The quantum walk search itself I built in Mathematica, using the QuantumNotation`` package. It reuses the same bit-flip shift operator, adds a Grover coin operator and an oracle that inverts the target state |0⟩, and iterates the resulting evolution operator π/2 × 2^(n/2) times, the iteration count Shenvi, Kempe, and Whaley derive. I verified the implementation up to n = 5, where a single run took overnight. For n = 3 (8 position states, 3 coin states per position, 24 states in total), the simulation gives a probability of measuring the target state of 0.347 after 4 iterations, matching the paper's own estimate of 1/2 - O(1/n).
The outcome
Running the walk past its optimal stopping point showed the target probability falling away again and continuing to evolve, rather than settling into the periodic oscillation Grover's algorithm shows. The paper does not discuss this behaviour; it is something I noted while extending the simulation past the point the paper analyses.