Connecting Coined Quantum Walks with Szegedy's Model

DOI10.4036/IIS.2017.A.15zbMATH Open1470.81035arXiv1612.02448MaRDI QIDQ5147828FDOQ5147828

R. Portugal, Etsuo Segawa

Publication date: 28 January 2021

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

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.

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)

Cites Work

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

Cited In (9)

• 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 Walks on Two-Dimensional Grids with Multiple Marked Locations
• Quantum search on simplicial complexes

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)