Quantum walk-based search algorithms with multiple marked vertices
arXiv:2103.12878 · doi:10.1103/PhysRevA.103.062202
Abstract
The quantum walk is a powerful tool to develop quantum algorithms, which usually are based on searching for a vertex in a graph with multiple marked vertices, Ambainis's quantum algorithm for solving the element distinctness problem being the most shining example. In this work, we address the problem of calculating analytical expressions of the time complexity of finding a marked vertex using quantum walk-based search algorithms with multiple marked vertices on arbitrary graphs, extending previous analytical methods based on Szegedy's quantum walk, which can be applied only to bipartite graphs. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.
12 pages, 1 table, 2 figs
References in corpus (3)
Cited by in corpus (11)
- Circuit Implementation of Discrete-Time Quantum Walks via the Shunt Decomposition Method
- Quantum-walk search in motion
- Lackadaisical quantum walks on 2D grids with multiple marked vertices
- Walking on Vertices and Edges by Continuous-Time Quantum Walk
- Lackadaisical quantum walk in the hypercube to search for multiple marked vertices
- Multimarked Spatial Search by Continuous-Time Quantum Walk
- Quantum spatial search with electric potential : long-time dynamics and robustness to noise
- Quantum search by continuous-time quantum walk on t-designs
- Quantum walk search for exceptional configurations
- Implementation of Continuous-Time Quantum Walks on Quantum Computers
- Transition in Splitting Probabilities of Quantum Walks