Related papers: Quantum walk search by Grover search on coin space

Quantum walk search by Grover search on coin space

URL: http://arxiv.org/abs/2503.04031v1
Date: Thu, 06 Mar 2025 02:30:37 GMT
Title: Quantum walk search by Grover search on coin space
Authors: Pulak Ranjan Giri,
Abstract summary: Lackadaisical quantum walk can search for target vertices on graphs without the help of any additional amplitude amplification technique.<n>We propose a modified coin for the lackadaisical quantum walk search.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Quantum walk followed by some amplitude amplification technique has been successfully used to search for marked vertices on various graphs. Lackadaisical quantum walk can search for target vertices on graphs without the help of any additional amplitude amplification technique. These studies either exploit AKR or SKW coin to distinguish the marked vertices from the unmarked vertices. The success of AKR coin based quantum walk search algorithms highly depend on the arrangements of the set of marked vertices on the graph. For example, it fails to find adjacent vertices, diagonal vertices and other exceptional configurations of vertices on a two-dimensional periodic square lattice and on other graphs. These coins also suffer from low success probability while searching for marked vertices on a one-dimensional periodic lattice and on other graphs for certain arrangements for marked vertices. In this article, we propose a modified coin for the lackadaisical quantum walk search. It allows us to perform quantum walk search for the marked vertices by doing Grover search on the coin space. Our model finds the marked vertices by searching the self-loops associated with the marked vertices. It can search for marked vertices irrespective of their arrangement on the graph with high success probability. For all analyzed arrangements of the marked vertices the time complexity for 1d-lattice and 2d-lattice are $\mathcal{O}(\frac{N}{M})$ and $\mathcal{O}\left(\sqrt{ \frac{N}{M}\log \frac{N}{M}}\right)$ respectively with constant and high success probability.

Related papers

Quantum walk search on a two-dimensional grid with extra edges [0.0]
Quantum walk has been successfully used to search for targets on graphs with vertices identified as elements of a database. We show that the optimal time complexity of $mathcalO(sqrtN/M)$ with constant success probability can be achieved for quantum search on a two-dimensional periodic grid with long-range edges.
arXiv Detail & Related papers (2025-03-06T02:11:02Z)
Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z)
Graph Neural Network Bandits [89.31889875864599]
We consider the bandit optimization problem with the reward function defined over graph-structured data. Key challenges in this setting are scaling to large domains, and to graphs with many nodes. We show that graph neural networks (GNNs) can be used to estimate the reward function.
arXiv Detail & Related papers (2022-07-13T18:12:36Z)
Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
arXiv Detail & Related papers (2022-07-04T19:33:06Z)
Walking on Vertices and Edges by Continuous-Time Quantum Walk [0.0]
We define a version of the continuous-time quantum walk that allows the walker to hop from vertices to edges and vice versa. We analyze the spatial search algorithm on the complete bipartite graph by modifying the new version of the Hamiltonian.
arXiv Detail & Related papers (2022-06-07T15:10:18Z)
Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices.
arXiv Detail & Related papers (2022-03-27T20:22:17Z)
The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
Graph Neural Network (GNN) whose output is identical to the graph function? In this paper, we fully answer this question and characterize the class of graph problems that can be represented by GNNs. We show that this condition can be efficiently verified by checking quadratically many constraints.
arXiv Detail & Related papers (2022-02-17T18:54:27Z)
Random Subgraph Detection Using Queries [29.192695995340653]
The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph.
arXiv Detail & Related papers (2021-10-02T07:41:17Z)
Lackadaisical quantum walk in the hypercube to search for multiple marked vertices [0.0]
In this article, we experimentally address several problems related to quantum walk in the hypercube with self-loops. We show that, in the case where neighbors are marked, the probability of success increases to close to $1$.
arXiv Detail & Related papers (2021-08-20T23:19:55Z)
On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z)
Lackadaisical quantum walks on 2D grids with multiple marked vertices [0.0]
Lackadaisical quantum walk (LQW) is a quantum analog of a classical lazy walk. We numerically study search by LQW for different types of 2D grids -- triangular, rectangular and honeycomb.
arXiv Detail & Related papers (2021-04-20T13:33:16Z)
Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods [44.007522460918565]
Mining dense subgraphs is an important primitive across a spectrum of graph-mining tasks. We show that mining cliques and quasi-cliques of non-trivial sizes from real-world graphs is often not a difficult problem.
arXiv Detail & Related papers (2020-08-18T15:50:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.