Connecting coined quantum walks with Szegedy's model

DOI10.4036/IIS.2017.A.15MaRDI QIDQ5147828zbMATH OpenFDO

Authors Etsuo Segawa, R. Portugal

Publication date 28 January 2021

Published in Interdisciplinary Information Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.02448

zbMATH Keywords

subdivision graphcoined quantum walkSzegedy walk

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68) Random walks on graphs (05C81) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35) Quantum dynamics and nonequilibrium statistical mechanics (general) (82C10) Quantum stochastic calculus (81S25) Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics (82C41)

Abstract: We analyze the equivalence between discrete-time coined quantum walks and Szegedy's quantum walks. We characterize a class of flip-flop coined models with generalized Grover coin on a graph $Gamma$ that can be directly converted into Szegedy's model on the subdivision graph of $Gamma$ and we describe a method to convert one model into the other. This method improves previous results in literature that need to use the staggered model and the concept of line graph, which are avoided here.

Recommendations

• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Equivalence of Szegedy's and coined quantum walks
• Exact simulation of coined quantum walks with the continuous-time model
• Szegedy quantum walks with memory on regular graphs
• The staggered quantum walk model

Cites work

• scientific article; zbMATH DE number 2229025 (Why is no real title available?)
• Decoherence in quantum walks – a review
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Finding Is as Easy as Detecting for Quantum Walks
• Generator of an abstract quantum walk
• Physical implementation of quantum walks
• Quantum Algorithms for the Triangle Problem
• Quantum Walks
• Quantum walks and search algorithms
• Quantum walks on graphs
• Quantum walks: a comprehensive review
• Search via Quantum Walk
• The staggered quantum walk model

Cited in

(11)

• The staggered quantum walk model
• Szegedy quantum walks with memory on regular graphs
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• A spectral analysis of discrete-time quantum walks related to the birth and death chains
• On the equivalence between quantum and random walks on finite graphs
• Partition-based discrete-time quantum walks
• Discrete-time quantum walks and graph structures
• Equivalence of Szegedy's and coined quantum walks
• Quantum search on simplicial complexes
• Exact simulation of coined quantum walks with the continuous-time model
• Quantum walks on two-dimensional grids with multiple marked locations

This page was built for publication: Connecting coined quantum walks with Szegedy's model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5147828)