Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm

Abstract:Grover's algorithm is a cornerstone of quantum algorithms and is strictly optimal in oracle-query complexity. While the full search problem admits no further improvement, one may trade accuracy for speed in the partial search problem, where the task is to identify only the block containing the target item. The best known quantum algorithm for the partial search problem is the Grover-Radhakrishnan-Korepin (GRK) algorithm, whose optimality has long been conjectured but not proved. In this work, we prove the optimality of GRK in the large-block limit. We formulate partial search as a time-optimal control problem and apply the Pontryagin maximum principle to derive the switching-function dynamics, establish the bang-bang structure of regular extremals, and exclude non-optimal switching patterns. As a result, we show that the optimal regular extremal has the global-local-global form, which yields a control-theoretic proof of the asymptotic optimality of the GRK algorithm in oracle-query complexity.

arXiv:2604.15886 [quant-ph]

(or arXiv:2604.15886v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2604.15886 Focus to learn more arXiv-issued DOI via DataCite

J. Phys. A: Math. Theor. 59, 315301 (2026)

https://doi.org/10.1088/1751-8121/ae8f8d Focus to learn more DOI(s) linking to related resources

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.