A cube drawn in pale lines on a dark ground with axes labelled first, second and third bit, each corner labelled in red with its three-bit string from (000) to (111): the nodes of the 3-cube the walk searches.

Algorithms · Fall 2019

Quantum search algorithm using a quantum random walk

A reimplementation of quantum-walk search on a hypercube, verified numerically up to a 5-cube against the paper's own estimate.

The short version

A classical search through an unsorted list of N items takes O(N) queries; Grover's algorithm reaches O(√N) on a quantum computer. Shenvi, Kempe and Whaley reach the same scaling by a different route, a quantum walk on a hypercube. This coursework project studied their paper and reimplemented the algorithm.

Role
Solo
Period
Fall 2019
Repository
github.com/sadityakr/Quantum-Search-Algorithm
Wolfram MathematicaPythonQuantum walksNumerical simulation

View the repository →

Coursework for Quantum Information and Quantum Computation at NISER Bhubaneswar, taught by Dr Colin Benjamin, on "A Quantum Random Walk Search Algorithm" (Shenvi, Kempe & Whaley, Phys. Rev. A 67, 052307, 2003).

How

  • Turned the hypercube step into arithmetic. Each of the 2^n nodes is an n-bit string and a step along direction i is an XOR with a single set bit, which I implemented as adding 2^(i-1) modulo 2^n for both the classical and the quantum walk.
  • Simulated the classical random walk in Python first, plotting probability against position on a 3-cube and a 7-cube after 10 steps.
  • Built the quantum walk search in Wolfram Mathematica with the Quantum`Notation package: the bit-flip shift, a Grover coin operator and an oracle that inverts the target state |0⟩, iterated π/2 × 2^(n/2) times as the paper derives.
  • Ran the simulation past the point the paper analyses, which is where the non-periodic behaviour showed up.

The Mathematica code of the search on a dark ground. It loads the Quantum Notation package, sets n = 3, builds the shift operator as a double sum with BitXor over the n directions and 2^n positions, the uniform direction superposition, the direction and position identities, the Grover coin C0 = -idenc + 2 sc.sc dagger, the inversion operator C2 = C1 - C0 applied to the target state 0 as the oracle folded into the coin, the evolution operator Evolve = pcoin . shifto, the uniform initial state, t = pi/2 * 2^(n/2) iterations, and a Do loop that applies Evolve to the state t times. The whole search in one Mathematica cell: bit-flip shift, Grover coin with the oracle folded in, iterated π/2 × 2^(n/2) times.