In this note, we clarify a small problem concerning our recent work “On validity of quantum partial adiabatic search”. The conclusion here is that, the success probability of the quantum partial adiabatic search algorithm in the paper indeed can be bounded by the same quantity as that of early work of Kay’s, even though the Hamiltonian settings in those works are different. This fact is not mentioned in our prior paper, so the purpose here is to explicitly point it out for clarity.
In this note, we clarify a small problem concerning our recent work “On validity of quantum partial adiabatic search”. The conclusion here is that, the success probability of the quantum partial adiabatic search algorithm in the paper indeed can be bounded by the same quantity as that of early work of Kay’s, even though the Hamiltonian settings in those works are different. This fact is not mentioned in our prior paper, so the purpose here is to explicitly point it out for clarity.
ABSTRACT In this paper, we revisit the problem of success probability of quantum partial adiabatic search algorithms, which has been studied in a series of our prior works. The conclusions presented here can be divided into positive and negative aspects. On the one hand, for the quantum partial adiabatic evolution with time complexity of , where and denote the sizes of the total elements and the target elements in the search problem, respectively, our choice of narrow evolution paths in the related papers is in fact acceptable. This is reflected in the finite success probability of the quantum algorithm. On the other hand, for the quantum partial adiabatic computation (QPAC) with time complexity of , the choice of narrow evolution paths in the previous paper is indeed invalid, as evidenced by the low success probability. These findings demonstrate that previous criticisms of our work are not fully justified, and they highlight the necessity of a careful treatment of success probability calculations in quantum partial adiabatic evolutions.
Abstract In this paper, we further verify the validity of the quantum partial adiabatic search algorithm which was initialized in the previous related works by revisiting its quantum circuit model. The main results got here are as follows. When considering implementing quantum partial adiabatic evolution on a quantum circuit, a correction is given for the time slice estimation for the first stage during this approximation in the previous related works, new evidence is provided for a time complexity cost O(N/M) O ( N / M ) of quantum partial adiabatic algorithm is impossible, and the correct time complexity O(N/M) O ( N / M ) of it is emphasized once more according to its circuit correspondence, in which N is the total number of elements in the search problem of which M of them are the marked ones. The findings exposed are hopeful for revisiting quantum partial adiabatic evolution and its connection with the quantum circuit model.
This paper presents a framework for quantum partial adiabatic evolution and applies it to re-examine the well-known quantum search problem. We particularly focus on a detailed analysis of the algorithm’s success probability, which serves as a clear criterion for differentiating valid implementations from invalid ones. Specifically, when the time complexity aligns with the optimal quantum computation, the algorithm achieves a substantially high success probability. Conversely, so-called “improved” versions that exceed the quadratic speedup characteristic of quantum computing exhibit a negligibly low success probability with the increase of target elements. These findings underscore the critical importance of selecting the appropriate evolution interval and the correct method for calculating the success probability in studies of quantum partial adiabatic evolution.
The partial adiabatic search algorithm was introduced in Tulsi's paper [Phys. Rev. A 80, 052328 (2009)] as a modification of the usual adiabatic algorithm for a quantum search with the idea that most of the interesting computation only happens over a very short range of the adiabatic path. By focusing on that restricted range, one can potentially gain an advantage by reducing the control requirements on the system, enabling a uniform rate of evolution. In this Comment, we point out an oversight in Tulsi's paper [Phys. Rev. A 80, 052328 (2009)] that invalidates its proof. However, the argument can be corrected, and the calculations in Tulsi's paper [Phys. Rev. A 80, 052328 (2009)] are then sufficient to show that the scheme still works. Nevertheless, subsequent works [Phys. Rev. A 82, 034304 (2010), Chin. Phys. B 20, 040309 (2011), Chin. Phys. B 21, 010306 (2012), AASRI Procedia 1, 5862 (2012), and Quantum Inf. Process. 12, 2689 (2013)] cannot all be recovered in the same way.
This paper first demonstrates that by appropriately specifying the evolution interval in quantum partial adiabatic evolution, the time complexity of the resulting quantum search algorithm can achieve the well-known quadratic speedup bound of quantum computation. Then this result is used as a reference to remedy invalid quantum partial adiabatic search schemes, which means its time complexity doesn’t align with the optimal quantum speedup. And, it is found that the two versions of quantum partial adiabatic evolutions, i.e. “global” and “local” ones must be treated separately, despite previous studies indicating only minor differences in algorithmic performance between the two cases. Additionally, for the “local” variant of the quantum partial adiabatic search algorithm, it can be seen that there are other possible choices for the evolution interval besides the referred one. Our findings further show that significant variations in the resulting single-round success probabilities occur between valid and invalid quantum partial adiabatic evolutions.
Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.