  The random walk formalism is used across a wide range of applications, from
modelling share prices to predicting population genetics. Likewise quantum
walks have shown much potential as a frame- work for developing new quantum
algorithms. In this paper, we present explicit efficient quantum circuits for
implementing continuous-time quantum walks on the circulant class of graphs.
These circuits allow us to sample from the output probability distributions of
quantum walks on circulant graphs efficiently. We also show that solving the
same sampling problem for arbitrary circulant quantum circuits is intractable
for a classical computer, assuming conjectures from computational complexity
theory. This is a new link between continuous-time quantum walks and
computational complexity theory and it indicates a family of tasks which could
ultimately demonstrate quantum supremacy over classical computers. As a proof
of principle we have experimentally implemented the proposed quantum circuit on
an example circulant graph using a two-qubit photonics quantum processor.
