Quantum random walks on congested lattices and the effect of dephasing

Quantum information processing1 promises many interesting technologies that are not available today. Perhaps most interesting is the promise for quantum computation, whereby quantum algorithms can be implemented that outperform their classical counterparts. The best known example is Shor’s factoring algorithm2, which can factor numbers exponentially faster than the best known classical factoring algorithm. Other examples include Grover’s database search algorithm3 and various graph theoretic algorithms4,5,6. One route to implementing quantum information processing tasks is via quantum random walks7,8,9,10 whereby a particle, such as a photon, ‘hops’ between the vertices in a lattice. In this paper the effects of a congested, or obstructed, lattice on a quantum random walk (QRW) are studied and compared to a classical random walk (CRW). Congestion can be thought of as traffic and the walker is like a car trying to avoid the traffic. The quantum walkers also suffer a dephasing process as they propagate. This study provides insight into how random errors in the lattice and dephasing affect the dynamics of random walks and the robustness of certain quantum features. In our model, congestion refers to where the lattice through which the walker propagates has defects. These random defects are like blocked streets that the walker encounters and has to back out of during the next step. These defects are stationary during the evolution of the random walk, though we average over many such random lattices. Dephasing occurs when the state decoheres and is implemented via a dephasing channel acting after each step. In the limit of full dephasing the QRW becomes a CRW, so that dephasing also allows us to interpolate between the classical and quantum regimes. For an experimental demonstration of dephasing in a QRW see Broome et al.11, and for related theoretical work on QRWs with phase damping see Lockhart et al.12. For characterising the resulting probability distributions for QRWs and CRWs we use variance and ‘escape probability’, that is the probability that the walker escapes a finite region of the lattice, or more picturesquely, the probability that the walker ‘beats the traffic’.