Coined Quantum Walks on Weighted Graphs

Abstract

We define a discrete-time, coined quantum walk on weighted graphs that is inspired by Szegedy's quantum walk. Using this, we prove that many lackadaisical quantum walks, where each vertex has $l$ integer self-loops, can be generalized to a quantum walk where each vertex has a single self-loop of real-valued weight $l$. We apply this real-valued lackadaisical quantum walk to two problems. First, we analyze it on the line or one-dimensional lattice, showing that it is exactly equivalent to a continuous deformation of the three-state Grover walk with faster ballistic dispersion. Second, we generalize Grover's algorithm, or search on the complete graph, to have a weighted self-loop at each vertex, yielding an improved success probability when $l<3+2\sqrt{2}\approx 5.828$.

14 pages, 5 figures

References in corpus (8)

• Universal computation by quantum walk
• A Quantum Algorithm for the Hamiltonian NAND Tree
• Continuous deformations of the Grover walk preserving localization
• Equivalence of Szegedy's and Coined Quantum Walks
• Engineering the Success of Quantum Walk Search Using Weighted Graphs
• Full Characterization of Oscillatory Localization of Quantum Walks
• Oscillatory Localization of Quantum Walks Analyzed by Classical Electric Circuits
• The Lackadaisical Quantum Walker is NOT Lazy at all

Cited by in corpus (24)

• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Faster Search by Lackadaisical Quantum Walk
• Quantum Walk Search on the Complete Bipartite Graph
• Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
• Lackadaisical quantum walk for spatial search
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
• Quantum routing of information using chiral quantum walks
• Isolated Vertices in Continuous-Time Quantum Walks on Dynamic Graphs
• The Lackadaisical Quantum Walker is NOT Lazy at all
• Quantum walk search by Grover search on coin space
• Quantum state transfer on the complete bipartite graph
• Quantum walk search on a two-dimensional grid with extra edges
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
• Quantum search on Hanoi network
• Staggered Quantum Walk on Hexagonal Lattices
• Search by Lackadaisical Quantum Walk with Symmetry Breaking
• Scoring Anomalous Vertices Through Quantum Walks
• Universal dynamical scaling laws in three-state quantum walks
• Multi-target quantum walk search on Johnson graph
• Optimizing topology for quantum probing with discrete-time quantum walks
• Complex-Phase Extensions of Szegedy Quantum Walk on Graphs
• Quantum walk search for exceptional configurations
• QWalkVec: Node Embedding by Quantum Walk
• How to Teach a Quantum Computer a Probability Distribution