Theoretical and Experimental Performance Analysis on Error-Bounded Quantum Search Process

Grover’s algorithm (a. k. a. quantum search process) is one of the most distinguished quantum algorithms, addressing the fundamental problem — How to find goal records from a huge but unstructured database efficiently. It can achieve a relatively optimal success probability after a few Grover iterations for amplitude amplification, which results in a quadratic speed-up in the whole process in terms of the size of database. However, it does not guarantee to achieve that probability within a user-specified error tolerance. So error-bounded quantum search process comes into being. The existing methods introduce extra qubits to meet that tolerance, or exploit high-precision (nonbasic) gates, each of which would be converted to a sequence of basic gates and thus costs much more computational units. In this paper, the authors employ the strategy of performing more Grover iterations expecting one of a series of local optima to meet the tolerance. To ensure that it works rigorously, the authors identify and exclude three exceptional instances by algebraic number theory, which is reported for the first time. Then the authors analyze the theoretical complexity of the employed method. It turns out to be in time exponential in the encoding size of the tolerance using basic gates, comparable to the existing method’s, while extra space consumption is saved. The experimental performance is validated by extensive examples from real-world data sets ASRS and public Amazon review.