Vladislav Kargin
Published 2010-04-01, updated 2010-07-21Version 2
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, Ambainis, Kempe and Vazirani (2001) and it is found that for particular examples of walks on a cycle, a hypercube and a complete graph, quantum walks provide no speed-up 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.
Comments: This is the journal version (except formatting); it is a significant revision of the previous version, in particular, it contains a new result about the convergence of quantum walks with decoherence; 16 pages
Journal: J. Phys. A: Math. Theor. 43 (2010) 335302
The mixing time for simple exclusion
Glauber dynamics on nonamenable graphs: Boundary conditions and mixing time
percolation on finite graphs
![QR code for arXiv:1004.0188 [math.PR]](http://oss.arxitics.com/images/favicon.svg)