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.
arXiv commentmain paper: 5 pages, 2 figures. supplemental material: 9 pages, 1 figure. comments welcome
References in corpus (36)
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
- A Quantum Random Walk Search Algorithm
- 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
- Quantum mechanical evolution towards thermal equilibrium
- Observation of topologically protected bound states in a one dimensional photonic system
- From quantum cellular automata to quantum lattice gases
- Universal quantum computation using the discrete time quantum walk
- Strongly Correlated Quantum Walks in Optical Lattices
- Search via Quantum Walk
- Decoherence in quantum walks - a review
- Quantum walk on the line as an interference phenomenon
- Open Quantum Random Walks
- Electric quantum walks with individual atoms
- The -divergence and Mixing times of quantum Markov processes
- Observing Topological Invariants Using Quantum Walk in Superconducting Circuits
- Breakdown of an Electric-Field Driven System: a Mapping to a Quantum Walk
- Ergodic and Mixing Quantum Channels in Finite Dimensions
- Simulation of quantum random walks using interference of classical field
- Quantum speedup of classical mixing processes
- Quantum walks can find a marked element on any graph
- Almost uniform sampling via quantum walks
- Positive contraction mappings for classical and quantum Schrodinger systems
- Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
- Mixing Times in Quantum Walks on the Hypercube
- Implementation of multidimensional quantum walks using linear optics and classical light
- Optical implementability of the two-dimensional Quantum Walk
- Mixing Times in Quantum Walks on Two-Dimensional Grids
- Thermodynamics of N-dimensional quantum walks
- Efficient quantum walk on the grid with multiple marked elements
- 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