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
- 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
- scientific article; zbMATH DE number 3102314 (Why is no real title available?)
- Moments of coinless quantum walks on lattices
- Quantum Algorithms for the Triangle Problem
- Quantum random walks do not need a coin toss
- Quantum Walk Algorithm for Element Distinctness
- Quantum Walk Based Search Algorithms
- 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
(46)- Partition-based discrete-time quantum walks
- Exceptional quantum walk search on the cycle
- Quantum algorithm design: techniques and applications
- The spectral analysis of the unitary matrix of a 2-tessellable staggered quantum walk on a graph
- Quantum walks via quantum cellular automata
- Element distinctness revisited
- Effective simulation of state distribution in qubit chains
- The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
- Quantum walks on hypergraphs
- Quantum walks on embeddings
- Total tessellation cover: bounds, hardness, and applications
- Factoring discrete-time quantum walks on distance regular graphs into continuous-time quantum walks
- A computational complexity comparative study of graph tessellation problems
- The spectra of the unitary matrix of an n-tessellable staggered quantum walk on a graph
- A quantum walk induced by Hoffman graphs and its periodicity
- Eigenbasis of the evolution operator of 2-tessellable quantum walks
- Exact simulation of coined quantum walks with the continuous-time model
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Quantum walk and its application domains: a systematic review
- Supersymmetry for chiral symmetric quantum walks
- An infinite family of circulant graphs with perfect state transfer in discrete quantum walks
- The Witten index for 1D supersymmetric quantum walks with anisotropic coins
- Implementation of quantum walks on IBM quantum computers
- On the equivalence between quantum and random walks on finite graphs
- Walking on vertices and edges by continuous-time quantum walk
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Virtually Abelian quantum walks
- Adjacent vertices can be hard to find by quantum walks
- Unitary equivalent classes of one-dimensional quantum walks
- Limiting properties of stochastic quantum walks on directed graphs
- The spectra of the unitary matrix of a 2-tessellable staggered quantum walk on a graph
- scientific article; zbMATH DE number 7453155 (Why is no real title available?)
- Projection theorem for discrete-time quantum walks
- Spatial search on Johnson graphs by discrete-time quantum walk
- Asymptotic reduced density matrix of discrete-time quantum walks
- Szegedy's quantum walk with queries
- A note on the spectral mapping theorem of quantum walk models
- Connecting coined quantum walks with Szegedy's model
- Unitary coined discrete-time quantum walks on directed multigraphs
- The role of tessellation intersection in staggered quantum walks
- Discrete-time semiclassical Szegedy quantum walks
- Discretization of continuous-time quantum walks via the staggered model with Hamiltonians
- Lackadaisical discrete-time quantum walk on Johnson graph
- Zeta functions of periodic graphs derived from quantum walk
- Search algorithm on strongly regular graph by lackadaisical quantum walk
- The absolute zeta function with respect to a bipartite walk on a bipartite graph
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)
