Related Experiment Video
Updated: Oct 9, 2025

Quantum State Engineering of Light with Continuous-wave Optical Parametric Oscillators
Published on: May 30, 2014
Robust Quantum Search with Uncertain Number of Target States
Yuanye Zhu1, Zeguo Wang1, Bao Yan1,2
1State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China.
Abstract:
The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given λ=M/N, where M is the number of marked state and N is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover-Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity ON as the Grover's algorithm, and shows high tolerance of the uncertainty in the ratio M/N. In particular, for a database with an uncertainty in the ratio M±MN, our algorithm will find the target states with a success rate no less than 96%.
Related Concept Videos
Propagation of Uncertainty from Random Error
The Uncertainty Principle
Propagation of Uncertainty from Systematic Error
Uncertainty: Overview
Stability of Equilibrium Configuration: Problem Solving
Problem-solving in the context of the stability of equilibrium configuration...
Uncertainty: Confidence Intervals

