Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
arXiv:1509.08852 · doi:10.1007/s11128-015-1230-7
Abstract
Coined Quantum Walks (QWs) are being used in many contexts with the goal of understanding quantum systems and building quantum algorithms for quantum computers. Alternative models such as Szegedy's and continuous-time QWs were proposed taking advantage of the fact that quantum theory seems to allow different quantized versions based on the same classical model, in this case, the classical random walk. In this work, we show the conditions upon which coined QWs are equivalent to Szegedy's QWs. Those QW models have in common a large class of instances, in the sense that the evolution operators are equal when we convert the graph on which the coined QW takes place into a bipartite graph on which Szegedy's QW takes place, and vice versa. We also show that the abstract search algorithm using the coined QW model can be cast into Szegedy's searching framework using bipartite graphs with sinks.
arXiv comment23 pages, 7 figures, Quantum Information Processing, 2015
References in corpus (21)
- A Quantum Random Walk Search Algorithm
- Quantum walks: a comprehensive review
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Photons Walking the Line: A quantum walk with adjustable coin operations
- From quantum cellular automata to quantum lattice gases
- Realization of a quantum walk with one and two trapped ions
- Universal quantum computation using the discrete time quantum walk
- Implementing the quantum random walk
- Search via Quantum Walk
- Decoherence in quantum walks - a review
- Faster quantum walk algorithm for the two dimensional spatial search
- Quantum quincunx in cavity quantum electrodynamics
- Localization of Two-Dimensional Quantum Walks
- Quantum walk-based search and centrality
- Quantum walks can find a marked element on any graph
- The Staggered Quantum Walk Model
- Quantum Random Walks do not need a Coin Toss
- Spatial search in a honeycomb network
- One-Dimensional Coinless Quantum Walks
- Spatial quantum search in a triangular network
- Quantum walks on a circle with optomechanical systems
Cited by in corpus (18)
- Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
- Quantum walk approach to simulating parton showers
- Staggered Quantum Walks on Graphs
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Equivalence of Szegedy's and Coined Quantum Walks
- Staggered Quantum Walks with Hamiltonians
- Quantum walk-based search algorithms with multiple marked vertices
- Quantum walks induced by Dirichlet random walks on infinite trees
- Staggered quantum walks with superconducting microwave resonators
- Discrete-time quantum walks as fermions of lattice gauge theory
- Coined Quantum Walks as Quantum Markov Chains
- Element Distinctness Revisited
- Boundary-induced coherence in the staggered quantum walk on different topologies
- Decoherence on Staggered Quantum Walks
- SQUWALS: A Szegedy QUantum WALks Simulator
- Transport and Localization in Quantum Walks on a Random Hierarchy of Barriers
- Effective simulation of state distribution in qubit chains
- Cloud-Assisted Contracted Simulation of Quantum Chains