The Staggered Quantum Walk Model
arXiv:1505.04761 · doi:10.1007/s11128-015-1149-z
Abstract
There are at least three models of discrete-time quantum walks (QWs) on graphs currently under active development. In this work we focus on the equivalence of two of them, known as Szegedy's and staggered QWs. We give a formal definition of the staggered model and discuss generalized versions for searching marked vertices. Using this formal definition, we prove that any instance of Szegedy's model is equivalent to an instance of the staggered model. On the other hand, we show that there are instances of the staggered model that cannot be cast into Szegedy's framework. Our analysis also works when there are marked vertices. We show that Szegedy's spatial search algorithms can be converted into search algorithms in staggered QWs. We take advantage of the similarity of those models to define the quantum hitting time in the staggered model and to describe a method to calculate the eigenvalues and eigenvectors of the evolution operator of staggered QWs.
21 pages, 9 figures
References in corpus (4)
Cited by in corpus (37)
- Experimental Implementation of Quantum Walks on IBM Quantum Computers
- Staggered Quantum Walks on Graphs
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Staggered Quantum Walks with Hamiltonians
- From classical to quantum walks with stochastic resetting on networks
- Quantum walk-based search algorithms with multiple marked vertices
- Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians
- Discrete-Time Quantum-Walk & Floquet Topological Insulators via Distance-Selective Rydberg-Interaction
- Staggered quantum walks with superconducting microwave resonators
- The Witten Index for 1D Supersymmetric Quantum Walks with Anisotropic Coins
- Exceptional Quantum Walk Search on the Cycle
- Discrete-time quantum walks as fermions of lattice gauge theory
- Coined Quantum Walks as Quantum Markov Chains
- Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk
- Virtually Abelian Quantum Walks
- The tessellation problem of quantum walks
- Element Distinctness Revisited
- The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
- Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk
- Boundary-induced coherence in the staggered quantum walk on different topologies
- Discrete-time Semiclassical Szegedy Quantum Walks
- Walking on Vertices and Edges by Continuous-Time Quantum Walk
- Staggered Quantum Walk on Hexagonal Lattices
- Limit properties of global interaction stochastic quantum walks on directed graphs
- SQUWALS: A Szegedy QUantum WALks Simulator
- Decoherence on Staggered Quantum Walks
- On the equivalence between quantum and random walks on finite graphs
- Discrete-Time Quantum Walks on Oriented Graphs
- Effective simulation of state distribution in qubit chains
- Quantum walks on hypergraphs
- Experiments with Schrödinger Cellular Automata
- Complex-Phase Extensions of Szegedy Quantum Walk on Graphs
- Asymptotic reduced density matrix of discrete-time quantum walks
- Response to glassy disorder in coin on spread of quantum walker
- Projection Theorem for Discrete-Time Quantum Walks