Probability distributions for Markov chain based quantum walks
From MaRDI portal
Central limit and other weak theorems (60F05) Sums of independent random variables; random walks (60G50) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Quantum stochastic calculus (81S25)
Abstract: We analyze the probability distributions of the quantum walks induced from Markov chains by Szegedy (2004). The first part of this paper is devoted to the quantum walks induced from finite state Markov chains. It is shown that the probability distribution on the states of the underlying Markov chain is always convergent in the Cesaro sense. In particular, we deduce that the limiting distribution is uniform if the transition matrix is symmetric. In the cases of non-symmetric Markov chain, we exemplify that the limiting distribution of the quantum walk is not necessarily identical with the stationary distribution of the underlying irreducible Markov chain. The Szegedy scheme can be extended to infinite state Markov chains (random walks). In the second part, we formulate the quantum walk induced from a lazy random walk on the line. We then obtain the weak limit of the quantum walk. It is noted that the current quantum walk appears to spread faster than its counterpart-quantum walk on the line driven by the Grover coin discussed in literature. The paper closes with an outlook on possible future directions.
Recommendations
Cites work
- Coins make quantum walks faster
- Computing Communities in Large Networks Using Random Walks
- Decoherence in quantum walks – a review
- Efficient quantum circuits for Szegedy quantum walks
- Equivalence of Szegedy's and coined quantum walks
- Exponential algorithmic speedup by a quantum walk
- Faster quantum-walk algorithm for the two-dimensional spatial search
- Finding Is as Easy as Detecting for Quantum Walks
- From quantum cellular automata to quantum lattice gases
- scientific article; zbMATH DE number 5899272 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 1024108 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- One-dimensional quantum walks
- Probability and Computing
- QUANTUM HITTING TIME ON THE COMPLETE GRAPH
- Quantum Random Walks – New Method for Designing Quantum Algorithms
- Quantum simulations of classical random walks and undirected graph connectivity
- Quantum verification of matrix products
- Quantum Walk Algorithm for Element Distinctness
- Quantum Walk Based Search Algorithms
- Quantum Walks
- Quantum walks and search algorithms
- Quantum walks on graphs
- Quantum walks: a comprehensive review
- Search via Quantum Walk
- Spatial search and the Dirac equation
- Szegedy's quantum walk with queries
- Time averaged distribution of a discrete-time quantum walk on the path
Cited in
(18)- A spectral analysis of discrete-time quantum walks related to the birth and death chains
- Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks
- Correlated Markov quantum walks
- Absorption probabilities of quantum walks
- Quantum walks on regular graphs with realizations in a system of anyons
- Electric circuit induced by quantum walk
- Efficient quantum circuits for Szegedy quantum walks
- Topological quantum structures from association schemes
- Equal superposition transformations and quantum random walks
- Analytical solutions for quantum walks on 1D chain with different shift operators
- Kinematics and dynamics of quantum walks in terms of systems of imprimitivity
- Quantum mixing of Markov chains for special distributions
- Evaluating the convergence of tabu enhanced hybrid quantum optimization
- Discrete-time semiclassical Szegedy quantum walks
- On limiting distributions of quantum Markov chains
- Spectral analysis for a multi-dimensional split-step quantum walk with a defect
- Average mixing in quantum walks of reversible Markov chains
- Perfect state transfer using Markovian quantum walk
This page was built for publication: Probability distributions for Markov chain based quantum walks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603660)
