Bounds for mixing time of quantum walks on finite graphs

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.