Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm

Quantum Physics [Submitted on 17 Apr 2026] Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm Kun Zhang, Kang-Yuan Chen, Xiao-Hui Wang, Vladimir Korepin 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. Comments: 23 pages Subjects: Quantum Physics (quant-ph) Cite as: arXiv:2604.15886 [quant-ph]   (or arXiv:2604.15886v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2604.15886 Focus to learn more Submission history From: Kun Zhang [view email] [v1] Fri, 17 Apr 2026 09:34:11 UTC (43 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-04 References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)