Bounds for mixing time of quantum walks on finite graphs
Vladislav Kargin · Journal of Physics A Mathematical and Theoretical · 2010
Several inequalities are proved for the mixing time of discrete-time quantum walks on finite graphs. The mixing time is defined differently than in Aharonov et al (2002 Proc. 33rd STOC ( 2001 ) (New York: ACM) pp 50–9 arXiv:quant-ph/0012090v2) and it is found that for particular examples of walks on a cycle, a hypercube and a complete graph, quantum walks provide no speedup in mixing over the classical counterparts. In addition, non-unitary quantum walks (i.e. walks with decoherence) are considered and a criterion for their convergence to the unique stationary distribution is derived.