Lackadaisical quantum walk in the hypercube to search for multiple marked vertices

Abstract

Adding self-loops at each vertex of a graph improves the performance of quantum walks algorithms over loopless algorithms. Many works approach quantum walks to search for a single marked vertex. In this article, we experimentally address several problems related to quantum walk in the hypercube with self-loops to search for multiple marked vertices. We first investigate the quantum walk in the loopless hypercube. We saw that neighbor vertices are also amplified and that approximately $1/2$ of the system energy is concentrated in them. We show that the optimal value of $l$ for a single marked vertex is not optimal for multiple marked vertices. We define a new value of $l=(n/N)\cdot k$ to search multiple marked vertices. Next, we use this new value of $l$ found to analyze the search for multiple marked vertices non-adjacent and show that the probability of success is close to $1$. We also use the new value of $l$ found to analyze the search for several marked vertices that are adjacent and show that the probability of success is directly proportional to the density of marked vertices in the neighborhood. We also show that, in the case where neighbors are marked, if there is at least one non-adjacent marked vertex, the probability of success increases to close to $1$. The results found show that the self-loop value for the quantum walk in the hypercube to search for several marked vertices is $l=(n/N)\cdot k$.

12 pages, 20 figures

References in corpus (8)

• Optimized quantum random-walk search algorithms
• Quantum Random Walks Hit Exponentially Faster
• Quantum walk-based search algorithms with multiple marked vertices
• Classical Artificial Neural Network Training Using Quantum Walks as a Search Procedure
• Quantum Walk to Train a Classical Artificial Neural Network
• Adjustable self-loop on discrete-time quantum walk and its application in spatial search
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids

Cited by in corpus (1)

• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids