Invalid quantum partial adiabatic search can be remedied

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.