Robust Quantum Walk Search Without Knowing the Number of Marked Vertices

Abstract

There has been a very large body of research on searching a marked vertex on a graph based on quantum walks, and Grover's algorithm can be regarded as a quantum walk-based search algorithm on a special graph. However, the existing quantum walk-based search algorithms suffer severely from the soufflé problem which mainly means that the success probability of finding a marked vertex could shrink dramatically even to zero when the number of search steps is greater than the right one, thus heavily reducing the robustness and practicability of the algorithm. Surprisingly, while the soufflé problem of Grover's algorithm has attracted enough attention, how to address this problem for general quantum walk-based search algorithms is missing in the literature. Here we initiate the study of overcoming the soufflé problem for quantum walk-based search algorithms by presenting a new quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup. In this framework, for any adjustable parameter $\epsilon$, the quantum algorithm can find a marked vertex on an $N$-vertex {\it complete bipartite graph} with probability at least $1-\epsilon$, whenever the number of search steps $h$ satisfies $h\ge \ln (\frac{2}{\sqrt{\epsilon }})\sqrt{N}+1$. Note that the algorithm need not know the exact number of marked vertices. Consequently, we obtain quantum search algorithms with stronger robustness and practicability.

References in corpus (19)

• Quantum Amplitude Amplification and Estimation
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Universal computation by quantum walk
• Quantum walks of correlated particles
• From quantum cellular automata to quantum lattice gases
• Realization of a quantum walk with one and two trapped ions
• Universal quantum computation using the discrete time quantum walk
• An example of the difference between quantum and classical random walks
• Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
• Search via Quantum Walk
• Fixed-point quantum search with an optimal number of queries
• A different kind of quantum search
• On the absence of homogeneous scalar unitary cellular automata
• Quantum walks can find a marked element on any graph
• Quantum searches on highly symmetric graphs
• Quantum Walk Search on the Complete Bipartite Graph
• Geometric Algebra and Information Geometry for Quantum Computational Software
• Finding structural anomalies in star graphs: A general approach

Cited by in corpus (7)

• Deterministic quantum search with adjustable parameters: implementations and applications
• Quantum-walk search in motion
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• Unbounded quantum-classical separation in sample complexity for sphere center finding
• Quantum walk mixing is faster than classical on periodic lattices
• Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma
• Quantum states supported by matroids