Mixing Times in Quantum Walks on Two-Dimensional Grids
arXiv:1006.4625 · doi:10.1103/PhysRevA.82.042341
Abstract
Mixing properties of discrete-time quantum walks on two-dimensional grids with torus-like boundary conditions are analyzed, focusing on their connection to the complexity of the corresponding abstract search algorithm. In particular, an exact expression for the stationary distribution of the coherent walk over odd-sided lattices is obtained after solving the eigenproblem for the evolution operator for this particular graph. The limiting distribution and mixing time of a quantum walk with a coin operator modified as in the abstract search algorithm are obtained numerically. On the basis of these results, the relation between the mixing time of the modified walk and the running time of the corresponding abstract search algorithm is discussed.
11 pages
References in corpus (4)
Cited by in corpus (13)
- Quantum walks: a comprehensive review
- Equivalence of Szegedy's and Coined Quantum Walks
- Quantum walks and quantum search on graphene lattices
- How fast do quantum walks mix?
- Quantum walk-based search algorithms with multiple marked vertices
- Analog quantum algorithms for the mixing of Markov chains
- Simulation of Quantum Walks and Fast Mixing with Classical Processes
- Exceptional Quantum Walk Search on the Cycle
- The quantum walk search algorithm: Factors affecting efficiency
- Quantum Walks on Sierpinski Gaskets
- Search by quantum walks on two-dimensional grid without amplitude amplification
- The Fourier and Grover walks on the two-dimensional lattice and torus
- Quantum Walks on Necklaces and Mixing