Performance Analysis and Parameter Optimization of the Optimal Fixed-Point Quantum Search

The optimal fixed-point quantum search (OFPQS) algorithm [Phys. Rev. Lett. 113, 210501 (2014)] achieves both the fixed-point property and quadratic speedup over classical algorithms, which gives a sufficient condition on the number of iterations to ensure the success probability is no less than a given lower bound (denoted by 1 − δ 2 ). However, this condition is approximate and not exact. In this paper, we derive the sufficient and necessary condition on the number of feasible iterations, based on which the exact least number of iterations can be obtained. For example, when δ = 0 . 8 , iterations can be saved by almost 25%. Moreover, to find a target item certainly, setting directly 1 − δ 2 = 100 % , the quadratic advantage of the OFPQS algorithm will be lost, then, applying the OFPQS algorithm with 1 − δ 2 < 100 % requires multiple executions, which leads to a natural problem of choosing the optimal parameter δ . For this, we analyze the extreme and minimum properties of the success probability and further analytically derive the optimal δ which minimizes the query complexity. Our study can be a guideline for both the theoretical and application research on the fixed-point quantum search algorithms.