Staggered Quantum Walks on Graphs

Abstract

The staggered quantum walk model allows to establish an unprecedented connection between discrete-time quantum walks and graph theory. We call attention to the fact that a large subclass of the coined model is included in Szegedy's model, which in its turn is entirely included in the staggered model. In order to compare those three quantum walk models, we put them in the staggered formalism and we show that the Szegedy and coined models are defined on a special subclass of graphs. This inclusion scheme is also true when the searching framework is added. We use graph theory to characterize which staggered quantum walks can be reduced to the Szegedy or coined quantum walk model. We analyze a staggered-based search that cannot be included in Szegedy's model and we show numerically that this search is more efficient than a random-walk-based search.

14 pages, 9 figs

References in corpus (11)

• The Staggered Quantum Walk Model
• Asymptotic dynamics of coined quantum walks on percolation graphs
• Weak Limit of the 3-State Quantum Walk on the Line
• Continuous deformations of the Grover walk preserving localization
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Quantum walks and quantum search on graphene lattices
• One-Dimensional Coinless Quantum Walks
• Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2
• Localization in Quantum Walks on a Honeycomb Network
• Continuous Limit of Discrete Quantum Walks
• Relation between coined quantum walks and quantum cellular automata

Cited by in corpus (24)

• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
• Staggered Quantum Walks with Hamiltonians
• From classical to quantum walks with stochastic resetting on networks
• Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians
• Deterministic quantum search with adjustable parameters: implementations and applications
• Discrete-Time Quantum-Walk & Floquet Topological Insulators via Distance-Selective Rydberg-Interaction
• Staggered quantum walks with superconducting microwave resonators
• Discrete-time quantum walks as fermions of lattice gauge theory
• Circuit Implementation of Discrete-Time Quantum Walks via the Shunt Decomposition Method
• The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
• The tessellation problem of quantum walks
• Element Distinctness Revisited
• Optimal exact quantum algorithm for the promised element distinctness problem
• Boundary-induced coherence in the staggered quantum walk on different topologies
• Scoring Anomalous Vertices Through Quantum Walks
• Discretization of continuous-time quantum walks via the staggered model with Hamiltonians
• Partition-based discrete-time quantum walks
• Index Theorems for One-dimensional Chirally Symmetric Quantum Walks with Asymptotically Periodic Parameters
• Eigenbasis of the Evolution Operator of 2-Tessellable Quantum Walks
• The Witten Index for One-dimensional Non-unitary Quantum Walks with Gapless Time-evolution
• Eigenvalues of quantum walk induced by recurrence properties of the underlying birth and death process: application to computation of an edge state
• The spectra of the unitary marix of a 2-tessellable staggered quantum walk on a graph
• Phase measurement of quantum walks: application to structure theorem of the positive support of the Grover walk