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

作     者：FU Jianling XU Ming QIAN Haifeng LI Zhibin 

作者机构：Shanghai Institute for AI Education East China Normal University Shanghai Key Laboratory of Trustworthy Computing East China Normal University 

出 版 物：《Journal of Systems Science & Complexity》 (系统科学与复杂性学报(英文版))

年 卷 期：2024年

核心收录：

学科分类：07[理学] 070201[理学-理论物理] 0702[理学-物理学] 

基　　金：supported by the National Natural Science Foundation of China under Grant Nos. 12271172 and 11871221 the National Key R&D Program of China under Grant No. 2018YFA0306704 the Fundamental Research Funds for the Central Universities under Grant No. 2021JQRH014 the “Digital Silk Road”Shanghai International Joint Lab of Trustworthy Intelligent Software under Grant No. 22510750100 

摘      要：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.