We study a natural notion of decoherence on quantum random walks over the hypercube. We prove that this model possesses 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.

• Received 1 August 2005

DOI:https://doi.org/10.1103/PhysRevA.72.062304