Decoherence in Quantum Walks on the Hypercube

Abstract

We study a natural notion of decoherence on quantum random walks over the hypercube. We prove that in this model there is a decoherence threshold beneath which the essential properties of the hypercubic quantum walk, such as linear mixing times, are preserved. Beyond the threshold, we prove that the walks behave like their classical counterparts.

7 pages, 3 figures; v2:corrected typos in references; v3:clarified section 2.1; v4:added references, expanded introduction; v5: final journal version