An Efficient Circuit for the Quantum Walk Update Rule
Chen-Fu Chiang, Daniel Nagaj, Paweł Wocjan · arXiv (Cornell University) · 2009
We show how to efficiently implement quantum update rules corresponding to arbitrary sparse classical walks (Markov chains). These rules are required to realize quantum walks as defined by Szegedy [8]. Our efficient construction settles the often-raised objection against this core element of quantum walk based algorithms. The key component we use is Grover and Rudolph’s method for preparing coherent versions of probability distributions that are obtained by discretizing efficiently integrable probability densities [15]. 1