Simulation of Quantum Walks and Fast Mixing with Classical Processes
arXiv:1712.01609 · doi:10.1103/PhysRevA.98.032115
Abstract
We compare discrete-time quantum walks on graphs to their natural classical equivalents, which we argue are lifted Markov chains, that is, classical Markov chains with added memory. We show that these can simulate quantum walks, allowing us to answer an open question on how the graph topology ultimately bounds their mixing performance, and that of any stochastic local evolution. The results highlight that speedups in mixing and transport phenomena are not necessarily diagnostic of quantum effects, although superdiffusive spreading is more prominent with quantum walks.
main paper: 5 pages, 2 figures. supplemental material: 9 pages, 1 figure. comments welcome
References in corpus (13)
- Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
- Universal computation by quantum walk
- Quantum walks of correlated particles
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Strongly Correlated Quantum Walks in Optical Lattices
- Decoherence in quantum walks - a review
- Almost uniform sampling via quantum walks
- Positive contraction mappings for classical and quantum Schrodinger systems
- Mixing Times in Quantum Walks on the Hypercube
- Thermodynamics of N-dimensional quantum walks
- Lifting Markov Chains To Mix Faster: Limits and Opportunities
Cited by in corpus (10)
- Sampling efficiency of transverse forces in dense liquids
- Experimental Control of the Degree of Non-Classicality via Quantum Coherence
- Algebraic Reduction of Hidden Markov Models
- Exact mobility edges for almost-periodic CMV matrices via gauge symmetries
- An algorithm to factorize quantum walks into shift and coin operations
- Exact model reduction for discrete-time conditional quantum dynamics
- Quantum walk processes in quantum devices
- Discrete-Time Quantum Walks on Oriented Graphs
- Model Reduction for Quantum Systems: Discrete-time Quantum Walks and Open Markov Dynamics
- For every quantum walk there is a (classical) lifted Markov chain with faster mixing time