Bounds for mixing time of quantum walks on finite graphs

DOI10.1088/1751-8113/43/33/335302MaRDI QIDQ5747556zbMATH OpenOpenAlexFDO

Authors Vladislav Kargin

Publication date 13 September 2010

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.0188

Mathematics Subject Classification ID

Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Ergodicity, mixing, rates of mixing (37A25) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35)

Abstract: 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.

Recommendations

• Quantum walks on graphs
• scientific article; zbMATH DE number 2019633
• On mixing in continuous-time quantum walks on some circulant graphs
• Mixing and decoherence in quantum walks on cycles
• NON-UNIFORM MIXING OF QUANTUM WALK ON CYCLES

Cited in

(11)

• Complete characterization of mixing time for the continuous quantum walk on the hypercube with Markovian decoherence model
• Quantum walks: a comprehensive review
• QUANTUM HITTING TIME ON THE COMPLETE GRAPH
• NON-UNIFORM MIXING OF QUANTUM WALK ON CYCLES
• Discrete-time quantum walks and graph structures
• Quantum walks on necklaces and mixing
• Quantum walk mixing is faster than classical on periodic lattices
• Mixing and decoherence in continuous-time quantum walks on long-range interacting cycles
• Optimal computation with non-unitary quantum walks
• Quantum mixing of Markov chains for special distributions
• Mixing and decoherence in quantum walks on cycles

This page was built for publication: Bounds for mixing time of quantum walks on finite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5747556)