Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights

Abstract

The lackadaisical quantum walk, which is a quantum walk with a weighted self-loop at each vertex, has been shown to speed up dispersion on the line and improve spatial search on the complete graph and periodic square lattice. In these investigations, each self-loop had the same weight, owing to each graph's vertex-transitivity. In this paper, we propose lackadaisical quantum walks where the self-loops have different weights. We investigate spatial search on the complete bipartite graph, which can be irregular with $N_1$ and $N_2$ vertices in each partite set, and this naturally leads to self-loops in each partite set having different weights $l_1$ and $l_2$, respectively. We analytically prove that for large $N_1$ and $N_2$, if the $k$ marked vertices are confined to, say, the first partite set, then with the typical initial uniform state over the vertices, the success probability is improved from its non-lackadaisical value when $l_1=k{N}_2/2N_1$ and $N_2>(3-2\sqrt{2})N_1$, regardless of $l_2$. When the initial state is stationary under the quantum walk, however, then the success probability is improved when $l_1=k{N}_2/2N_1$, now without a constraint on the ratio of $N_1$ and $N_2$, and again independent of $l_2$. Next, when marked vertices lie in both partite sets, then for either initial state, there are many configurations for which the self-loops yield no improvement in quantum search, no matter what weights they take.

arXiv comment18 pages, 12 figures

References in corpus (17)

• Emergence of scaling in random networks
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Grover's quantum searching algorithm is optimal
• From quantum cellular automata to quantum lattice gases
• On the relationship between continuous- and discrete-time quantum walk
• One-Dimensional Three-State Quantum Walk
• Grover Search with Lackadaisical Quantum Walks
• Global Symmetry is Unnecessary for Fast Quantum Search
• Quantum searches on highly symmetric graphs
• Faster Search by Lackadaisical Quantum Walk
• Coined Quantum Walks on Weighted Graphs
• Continuous deformations of the Grover walk preserving localization
• Quantum Walk Search on the Complete Bipartite Graph
• One dimensional lazy quantum walks and occupancy rate
• The Lackadaisical Quantum Walker is NOT Lazy at all
• Doubling the Success of Quantum Walk Search Using Internal-State Measurements

Cited by in corpus (12)

• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
• Analysis of Lackadaisical Quantum Walks
• Quantum walk based state transfer algorithms on the complete M-partite graph
• Lazy Open Quantum Walks
• Quantum state transfer on the complete bipartite graph
• Search of clustered marked states with lackadaisical quantum walks
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• Quantum walk state transfer on a hypercube
• Search by Lackadaisical Quantum Walk with Symmetry Breaking
• Search and state transfer between hubs by quantum walks
• Quantum spatial best-arm identification via quantum walks
• Faster Search of Clustered Marked States with Lackadaisical Quantum Walks