| Summary: | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>λ</mi><mo>=</mo><msqrt><mrow><mi>M</mi><mo>/</mo><mi>N</mi></mrow></msqrt></mrow></semantics></math></inline-formula>, where <i>M</i> is the number of marked state and <i>N</i> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced open="(" close=")"><msqrt><mi>N</mi></msqrt></mfenced></mrow></semantics></math></inline-formula> as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>M</mi><mo>/</mo><mi>N</mi></mrow></semantics></math></inline-formula>. In particular, for a database with an uncertainty in the ratio <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mrow><mi>M</mi><mo>±</mo><msqrt><mi>M</mi></msqrt></mrow><mi>N</mi></mfrac></semantics></math></inline-formula>, our algorithm will find the target states with a success rate no less than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>96</mn><mo>%</mo></mrow></semantics></math></inline-formula>.
|
|---|