Deterministic spatial search using alternating quantum walks
- URL: http://arxiv.org/abs/2104.03806v2
- Date: Wed, 25 Aug 2021 01:35:38 GMT
- Title: Deterministic spatial search using alternating quantum walks
- Authors: S. Marsh and J. B. Wang
- Abstract summary: We prove that for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established.
This improves on the original spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability.
It is expected that this new framework can be readily extended to deterministic spatial search on other families of graph structures.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper examines the performance of spatial search where the Grover
diffusion operator is replaced by continuous-time quantum walks on a class of
interdependent networks. We prove that for a set of optimal quantum walk times
and marked vertex phase shifts, a deterministic algorithm for structured
spatial search is established that finds the marked vertex with 100%
probability. This improves on the original spatial search algorithm on the same
class of graphs, which we show can only amplify to 50% probability. Our method
uses $\left\lceil\frac{\pi}{2\sqrt{2}}\sqrt{N}\right\rceil$ marked vertex phase
shifts for an $N$-vertex graph, making it comparable with Grover's algorithm
for unstructured search. It is expected that this new framework can be readily
extended to deterministic spatial search on other families of graph structures.
Related papers
- 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) - Constant search time algorithm via topological quantum walks [0.0]
We show that it is possible to achieve a constant search-time quantum algorithm with a constant improvement of the search probability overtrivial search.
Specifically we study the spatial search algorithm implemented by a two-dimensional split-step quantum random walks.
arXiv Detail & Related papers (2024-06-26T21:36:47Z) - 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) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
We present two new classes of algorithms for efficient field integration on graphs encoding point clouds.
The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
arXiv Detail & Related papers (2023-02-02T08:33: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) - Of Shadows and Gaps in Spatial Search [0.0]
We show that some families of distance-regular graphs, such as Hamming and Grassmann graphs, have optimal spatial search.
We also show a matching lower bound on time for spatial search with constant fidelity, which extends a bound due to Farhi and Gutmann for perfect fidelity.
arXiv Detail & Related papers (2022-04-09T02:02:53Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum.
Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges.
We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
arXiv Detail & Related papers (2022-03-28T21:34:16Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
In this paper, we build the search algorithm upon a complicated search space with long-distance connections.
We present a simple yet effective algorithm named textbfIF-NAS, where we perform a periodic sampling strategy to construct different sub-networks.
In the proposed search space, IF-NAS outperform both random sampling and previous weight-sharing search algorithms by a significant margin.
arXiv Detail & Related papers (2021-12-05T06:42:48Z) - 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) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z)
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.