Deterministic quantum search on all Laplacian integral graphs

• URL: http://arxiv.org/abs/2506.21108v1
• Date: Thu, 26 Jun 2025 09:06:08 GMT
• Title: Deterministic quantum search on all Laplacian integral graphs
• Authors: Guanzhong Li, Jingquan Luo, Shiguang Feng, Lvzhou Li,
• Abstract summary: We propose a different and elegant approach to quantum spatial search, obtaining deterministic quantum search algorithms.<n>This work discovers the largest class of graphs that allow deterministic quantum search.
• Score: 0.3124884279860061
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Searching for an unknown marked vertex on a given graph (also known as spatial search) is an extensively discussed topic in the area of quantum algorithms, with a plethora of results based on different quantum walk models and targeting various types of graphs. Most of these algorithms have a non-zero probability of failure. In recent years, there have been some efforts to design quantum spatial search algorithms with $100\%$ success probability. However, these works either only work for very special graphs or only for the case where there is only one marked vertex. In this work, we propose a different and elegant approach to quantum spatial search, obtaining deterministic quantum search algorithms that can find a marked vertex with certainty on any Laplacian integral graph with any predetermined proportion of marked vertices. Thus, this work discovers the largest class of graphs so far that allow deterministic quantum search, making it easy to design deterministic quantum search algorithms for many graphs, including the different graphs discussed in previous works, in a unified framework.

Related papers

• Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
  This paper examines the quantum walk search algorithm on complete multipartite graphs. We employ the coined quantum walk model and achieve quadratic speedup. We also provide the numerical simulation and circuit implementation of our quantum algorithm.
  arXiv  Detail & Related papers  (2024-10-07T11:13:41Z)
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
  This article presents a novel and succinct algorithmic framework via alternating quantum walks. It unifies quantum spatial search, state transfer and uniform sampling on a large class of graphs. The approach is easy to use since it has a succinct formalism that depends only on the depth of the Laplacian eigenvalue set of the graph.
  arXiv  Detail & Related papers  (2024-07-01T06:09:19Z)
• Universal approach to deterministic spatial search via alternating quantum walks [2.940962519388297]
  We propose a novel approach for designing deterministic quantum search algorithms on a variety of graphs via alternating quantum walks. Our approach is universal because it does not require an instance-specific analysis for different graphs.
  arXiv  Detail & Related papers  (2023-07-30T05:14:19Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• 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)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions. For its practicability and wide-applicability, we give a brief review of typical graph learning techniques. We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
  arXiv  Detail & Related papers  (2022-02-19T02:56:47Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
  Existing quantum walk-based search algorithms suffer from the souffl'e problem. We present a new quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup.
  arXiv  Detail & Related papers  (2021-11-17T10:04:44Z)
• 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)
• Quantum walk-based search algorithms with multiple marked vertices [0.0]
  The quantum walk is a powerful tool to develop quantum algorithms. We extend previous analytical methods based on Szegedy's quantum walk. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.
  arXiv  Detail & Related papers  (2021-03-23T22:57:07Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.