The staggered quantum walk model
From MaRDI portal
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.
Recommendations
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Partition-based discrete-time quantum walks
- Quantum walks on hypergraphs
- Connecting coined quantum walks with Szegedy's model
- The spectra of the unitary matrix of a 2-tessellable staggered quantum walk on a graph
Cites work
- scientific article; zbMATH DE number 3102314 (Why is no real title available?)
- Characterizations of derived graphs
- Congruent Graphs and the Connectivity of Graphs
- Deformations of spin structures and gravity
- Finding Is as Easy as Detecting for Quantum Walks
- From quantum cellular automata to quantum lattice gases
- Moments of coinless quantum walks on lattices
- Quantum Algorithms for the Triangle Problem
- Quantum Walk Algorithm for Element Distinctness
- Quantum Walk Based Search Algorithms
- Quantum random walks do not need a coin toss
- Quantum walks and search algorithms
- Quantum walks on graphs
- Search on a hypercubic lattice using a quantum random walk. II. \(d=2\)
- Search via Quantum Walk
- Spectral and asymptotic properties of Grover walks on crystal lattices
Cited in
(45)- The role of tessellation intersection in staggered quantum walks
- Quantum algorithm design: techniques and applications
- Factoring discrete-time quantum walks on distance regular graphs into continuous-time quantum walks
- Effective simulation of state distribution in qubit chains
- Discrete-time semiclassical Szegedy quantum walks
- A computational complexity comparative study of graph tessellation problems
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Exact simulation of coined quantum walks with the continuous-time model
- Connecting coined quantum walks with Szegedy's model
- Quantum walks on embeddings
- A note on the spectral mapping theorem of quantum walk models
- Element distinctness revisited
- A quantum walk induced by Hoffman graphs and its periodicity
- Implementation of quantum walks on IBM quantum computers
- Quantum walks via quantum cellular automata
- Supersymmetry for chiral symmetric quantum walks
- The Witten index for 1D supersymmetric quantum walks with anisotropic coins
- Partition-based discrete-time quantum walks
- Total tessellation cover: bounds, hardness, and applications
- Spatial search on Johnson graphs by discrete-time quantum walk
- scientific article; zbMATH DE number 7453155 (Why is no real title available?)
- An infinite family of circulant graphs with perfect state transfer in discrete quantum walks
- Virtually Abelian quantum walks
- Eigenbasis of the evolution operator of 2-tessellable quantum walks
- Discretization of continuous-time quantum walks via the staggered model with Hamiltonians
- Quantum walk and its application domains: a systematic review
- Exceptional quantum walk search on the cycle
- Quantum walks on hypergraphs
- The spectra of the unitary matrix of an \(n\)-tessellable staggered quantum walk on a graph
- Unitary coined discrete-time quantum walks on directed multigraphs
- Lackadaisical discrete-time quantum walk on Johnson graph
- Zeta functions of periodic graphs derived from quantum walk
- On the equivalence between quantum and random walks on finite graphs
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Adjacent vertices can be hard to find by quantum walks
- Szegedy's quantum walk with queries
- Projection theorem for discrete-time quantum walks
- Limiting properties of stochastic quantum walks on directed graphs
- Unitary equivalent classes of one-dimensional quantum walks
- Asymptotic reduced density matrix of discrete-time quantum walks
- The spectra of the unitary matrix of a 2-tessellable staggered quantum walk on a graph
- The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
- The spectral analysis of the unitary matrix of a 2-tessellable staggered quantum walk on a graph
- Walking on vertices and edges by continuous-time quantum walk
- Search algorithm on strongly regular graph by lackadaisical quantum walk
This page was built for publication: The staggered quantum walk model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q265344)
