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.
arXiv comment12 pages, 1 table, 2 figs
References in corpus (15)
- Quantum Mechanics helps in searching for a needle in a haystack
- Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
- A Quantum Random Walk Search Algorithm
- Quantum walks: a comprehensive review
- Faster quantum walk algorithm for the two dimensional spatial search
- Quantum walks can find a marked element on any graph
- The Staggered Quantum Walk Model
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- General framework for quantum search algorithms
- Mixing Times in Quantum Walks on Two-Dimensional Grids
- Exceptional Quantum Walk Search on the Cycle
- Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk
- Non-Markovian quantum interference in multilevel quantum systems: Exact master equation approach
- Upperbounds on the probability of finding marked connected components using quantum walks
- Generalized exceptional quantum walk search
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