Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
From MaRDI portal
Publication:291465
DOI10.1007/S11128-015-1230-7zbMATH Open1338.81143arXiv1509.08852OpenAlexW3125790998MaRDI QIDQ291465FDOQ291465
Authors: R. Portugal 
Publication date: 10 June 2016
Published in: Quantum Information Processing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1509.08852
Recommendations
- Equivalence of Szegedy's and coined quantum walks
- Connecting coined quantum walks with Szegedy's model
- The staggered quantum walk model
- Exact simulation of coined quantum walks with the continuous-time model
- Quantum stochastic walk models for quantum state discrimination
- Quantum walk with a general coin: exact solution and asymptotic properties
- Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models
- Analysis of quantum walks with time-varying coin on \(d\)-dimensional lattices
- Discrete-time semiclassical Szegedy quantum walks
- Szegedy's quantum walk with queries
quantum walkscoined quantum walkequivalence among quantum walksstaggered quantum walkSzegedy's quantum walk
Cites Work
- Search via Quantum Walk
- Faster quantum-walk algorithm for the two-dimensional spatial search
- From quantum cellular automata to quantum lattice gases
- Quantum walks: a comprehensive review
- Quantum random walks in one dimension
- Quantum walks can find a marked element on any graph
- Coins make quantum walks faster
- Quantum random walks do not need a coin toss
- Finding Is as Easy as Detecting for Quantum Walks
- Quantum walks on graphs
- Quantum Walks
- Quantum Algorithms for the Triangle Problem
- Quantum Walk Algorithm for Element Distinctness
- Quantum walks and search algorithms
- Spatial quantum search in a triangular network
- Spatial search on a honeycomb network
- Decoherence in quantum walks – a review
- Quantum walks on a circle with optomechanical systems
Cited In (18)
- The staggered quantum walk model
- Element distinctness revisited
- Quantum walks induced by Dirichlet random walks on infinite trees
- The role of tessellation intersection in staggered quantum walks
- Szegedy quantum walks with memory on regular graphs
- The spectra of the unitary matrix of an \(n\)-tessellable staggered quantum walk on a graph
- On the equivalence between quantum and random walks on finite graphs
- Szegedy's quantum walk with queries
- The spectral analysis of the unitary matrix of a 2-tessellable staggered quantum walk on a graph
- Partition-based discrete-time quantum walks
- Phase measurement of quantum walks: application to structure theorem of the positive support of the Grover walk
- Effective simulation of state distribution in qubit chains
- A quantum walk induced by Hoffman graphs and its periodicity
- Equivalence of Szegedy's and coined quantum walks
- Connecting coined quantum walks with Szegedy's model
- Exact simulation of coined quantum walks with the continuous-time model
- Discretization of continuous-time quantum walks via the staggered model with Hamiltonians
- Transport and localization in quantum walks on a random hierarchy of barriers
This page was built for publication: Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q291465)
