2017/03/31 by Thomas G. Wong · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics #Discrete mathematics #Graph #Lattice (music) #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum computer #Quantum mechanics #Quantum walk #Quantum-Dot Cellular Automata #Random walk #Vertex (graph theory) #quant-ph
paper · pdf · doi:10.1088/1751-8121/aa8c17
published as J. Phys. A: Math. Theor. 50, 475301 (2017) · 14 pages, 5 figures
openalex publication_date 2017/09/13 · arxiv created 2017/09/14 · arxiv updated 2017/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mstyle displaystyle="false"> <mml:mi>l</mml:mi> <mml:mo><</mml:mo> <mml:mn>3</mml:mn> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> <mml:msqrt> <mml:mn>2</mml:mn> </mml:msqrt> <mml:mo>≈</mml:mo> <mml:mn>5.828</mml:mn> </mml:mstyle> </mml:math> .