A quantum perspective on random walks on graphs

Abstract

The term 'quantum random walk' was coined by Aharonov, Davidovich and Zagury in 1993, when they showed that the average path length of a quantum random walk may be larger than that of a classical random walk due to quantum interference effects. Random walks are prevalent in the design of algorithms and the use of quantum random walks over their classical counterpart may provide an advantage when it comes to solving certain problems. Also, the introduction of small amounts of decoherence has been shown to improve the uniformity in the spreading of the walk in some cases, without necessarily losing all quantum features. This project will consider the discrete model of the quantum random walk generalised to certain types of graphs, and will look into the effect of different rates of decoherence on this type of walk.