Quantum-walk search in motion
- URL: http://arxiv.org/abs/2310.14345v3
- Date: Sat, 3 Feb 2024 06:07:29 GMT
- Title: Quantum-walk search in motion
- Authors: Himanshu Sahu and Kallol Sen
- Abstract summary: In quantum computing, the quantum walk search algorithm is designed for locating fixed marked nodes within a graph.
We introduce additional quantum states to label the marked nodes and extend the algorithm to track a moving particle on a two-dimensional surface.
This concept holds promise for a range of applications, from real-time object tracking to network management and routing.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In quantum computing, the quantum walk search algorithm is designed for
locating fixed marked nodes within a graph. However, when multiple marked nodes
exist, the conventional search algorithm lacks the capacity to simultaneously
amplify the marked nodes as well as identify the correct chronological ordering
between the marked nodes, if any. To address this limitation, we explore a
potential extension of the algorithm by introducing additional quantum states
to label the marked nodes. The labels resolve the ambiguity of simultaneous
amplification of the marked nodes. Additionally, by associating the label
states with a chronological ordering, we can extend the algorithm to track a
moving particle on a two-dimensional surface. Our algorithm efficiently
searches for the trajectory of the particle and is supported by a proposed
quantum circuit. This concept holds promise for a range of applications, from
real-time object tracking to network management and routing.
Related papers
- Quantum Counting on the Complete Bipartite Graph [0.0]
Quantum counting is a key quantum algorithm that aims to determine the number of marked elements in a database.
Since Grover's algorithm can be viewed as a quantum walk on a complete graph, a natural way to extend quantum counting is to use the evolution operator of quantum-walk-based search on non-complete graphs.
arXiv Detail & Related papers (2023-11-17T09:22:28Z) - Quantum Algorithm for Path-Edge Sampling [0.9990687944474739]
We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix.
We use this path sampling algorithm as a subroutine for st-path finding and st-cut-set finding algorithms in some specific cases.
arXiv Detail & Related papers (2023-03-06T17:45:12Z) - QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional
Networks [124.7972093110732]
We propose quantum graph convolutional networks (QuanGCN), which learns the local message passing among nodes with the sequence of crossing-gate quantum operations.
To mitigate the inherent noises from modern quantum devices, we apply sparse constraint to sparsify the nodes' connections.
Our QuanGCN is functionally comparable or even superior than the classical algorithms on several benchmark graph datasets.
arXiv Detail & Related papers (2022-11-09T21:43:16Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits.
We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
arXiv Detail & Related papers (2022-03-15T09:46:45Z) - Feedback-assisted quantum search by continuous-time quantum walks [58.720142291102135]
We address the quantum search of a target node on a cycle graph by means of a quantum walk assisted by continuous measurement and feedback.
In particular, our protocol is able to drive the walker to a desired target node.
arXiv Detail & Related papers (2022-01-12T16:59:53Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
Continuous-time quantum walks provide a framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search.
We present a new continuous-time quantum walk search algorithm that can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks.
arXiv Detail & Related papers (2021-12-23T17:57:49Z) - 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) - Purification and Entanglement Routing on Quantum Networks [55.41644538483948]
A quantum network equipped with imperfect channel fidelities and limited memory storage time can distribute entanglement between users.
We introduce effectives enabling fast path-finding algorithms for maximizing entanglement shared between two nodes on a quantum network.
arXiv Detail & Related papers (2020-11-23T19:00:01Z)
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.