pith. sign in

arxiv: 2604.15886 · v1 · submitted 2026-04-17 · 🪐 quant-ph

Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm

Kun Zhang , Kang-Yuan Chen , Xiao-Hui Wang , Vladimir Korepin This is my paper

Pith reviewed 2026-05-10 08:51 UTC · model grok-4.3

classification 🪐 quant-ph
keywords algorithmoptimalityproblemsearchpartialasymptoticcomplexitygrover-radhakrishnan-korepin
0
0 comments X

The pith

The GRK algorithm is asymptotically optimal for partial quantum search in the large-block limit, proven via a control-theoretic analysis using the Pontryagin maximum principle.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Grover's algorithm finds a target in an unsorted database with quadratic speedup using quantum effects. Partial search is a relaxed version where the task is only to identify the block containing the target rather than the exact item. The GRK algorithm was previously known for this task but its optimality remained a conjecture. This work reformulates the quantum evolution during search as finding the shortest-time control sequence to reach the desired state. Applying the Pontryagin maximum principle from optimal control theory, the authors derive the dynamics of the switching function, establish that optimal controls are bang-bang, and rule out other switching patterns. They conclude that the optimal strategy has a global-local-global form, matching GRK and proving its asymptotic optimality when blocks are large.

Core claim

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.

Load-bearing premise

The partial search problem can be accurately formulated as a time-optimal control problem to which the Pontryagin maximum principle applies directly, and that analysis in the large-block limit suffices to establish asymptotic optimality.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Circularity Check

0 steps flagged

No circularity: standard PMP applied to independent control formulation

full rationale

The derivation formulates partial search as a time-optimal control problem and invokes the Pontryagin maximum principle (an external theorem) to analyze regular extremals and derive the global-local-global structure. No step reduces a claimed result to a fitted parameter, self-definition, or load-bearing self-citation whose validity is presupposed by the present work. The large-block limit and bang-bang analysis for regular controls are obtained from the PMP switching-function dynamics without circular reduction to the GRK algorithm itself. The paper remains self-contained against external benchmarks (PMP and control theory) and does not rename known results or smuggle ansatzes via citation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard assumptions from optimal control theory and the modeling of partial search as a time-optimal control problem. No free parameters or new invented entities are introduced based on the abstract.

axioms (2)
  • domain assumption The quantum partial search dynamics can be modeled as a controlled quantum system suitable for time-optimal control analysis.
    This is the foundational modeling step described in the abstract.
  • standard math Pontryagin's maximum principle applies to derive the switching-function dynamics and bang-bang structure for regular extremals.
    Invoked to establish the form of optimal controls and exclude non-optimal patterns.

pith-pipeline@v0.9.0 · 5466 in / 1262 out tokens · 58661 ms · 2026-05-10T08:51:28.353634+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Grover L K 1996 A fast quantum mechanical algorithm for database searchProceedings of the 28th ACM Symposium on Theory of Computing (STOC)pp 212–219

    work page 1996

  2. [2]

    Grover L K 1997Physical Review Letters79325

    work page

  3. [3]

    Boyer M, Brassard G, Høyer P and Tapp A 1998Fortschritte der Physik46493–505

    work page

  4. [4]

    Zalka C 1999Physical Review A602746–2751

    work page

  5. [5]

    Grassl M, Langenberg B, Roetteler M and Steinwandt R 2016 Applying grover’s algorithm to aes: Quantum resource estimatesPost-Quantum Cryptography(Lecture Notes in Computer Sciencevol 9606) ed Takagi T (Cham: Springer) pp 29–43 REFERENCES22

    work page 2016

  6. [6]

    Jaques S, Naehrig M, Roetteler M and Virdia F 2020 Implementing grover oracles for quantum key search on aes and lowmcAdvances in Cryptology – EUROCRYPT 2020 (Lecture Notes in Computer Sciencevol 12106) ed Canteaut A and Ishai Y (Springer) pp 280–310

    work page 2020

  7. [7]

    Jang K, Baksi A, Kim H, Song G, Seo H and Chattopadhyay A 2025IACR Communications in Cryptology21–57

    work page

  8. [8]

    Chuang I L, Gershenfeld N and Kubinec M 1998Physical Review Letters803408–3411 URLhttps://doi.org/10.1103/PhysRevLett.80.3408

    work page doi:10.1103/physrevlett.80.3408

  9. [9]

    Zhang K, Rao P, Yu K, Lim H and Korepin V 2021Quantum Information Processing20 233

    work page

  10. [10]

    Pokharel B and Lidar D A 2024npj Quantum Information1023

    work page

  11. [11]

    Grover L K and Radhakrishnan J 2005 Is partial quantum search of a database any easier?Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and ArchitecturesSPAA ’05 (New York, NY , USA: Association for Computing Machinery) pp 186–194

    work page 2005

  12. [12]

    Korepin V E 2005Journal of Physics A: Mathematical and General38L731–L738

    work page

  13. [13]

    Korepin V E and Grover L K 2006Quantum Information Processing55–10

    work page

  14. [14]

    Korepin V E and Vallilo B C 2006Progress of Theoretical Physics116783–793

    work page

  15. [15]

    Choi B S and Korepin V E 2007Quantum Information Processing6243–254

    work page

  16. [16]

    Zhong P C, Bao W S and Wei Y 2009Chinese Physics Letters26020301

    work page

  17. [17]

    Zhang K and Korepin V E 2017Quantum Information Processing17143

    work page

  18. [18]

    Choi B S, Walker T A and Braunstein S L 2007Quantum Information Processing61–8

    work page

  19. [19]

    Ye S M and Wang Y L 2025Physics Letters A537130325

    work page

  20. [20]

    Korepin V E and Liao J 2006Quantum Information Processing5209–226

    work page

  21. [21]

    Jiang Y B, Wang X H, Zhang K and Korepin V 2026arXiv preprint arXiv:2603.01462 (Preprint2603.01462)

    work page arXiv

  22. [22]

    Pontryagin L S, Boltyanskii V G, Gamkrelidze R V and Mishchenko E F 1962The Mathematical Theory of Optimal Processes(New York: Interscience Publishers)

    work page

  23. [23]

    Liberzon D 2012Calculus of Variations and Optimal Control Theory: A Concise Introduction(Princeton, NJ: Princeton University Press)

    work page

  24. [24]

    Agrachev A A and Sachkov Y L 2004Control Theory from the Geometric Viewpoint (Encyclopaedia of Mathematical Sciencesvol 87) (Berlin, Heidelberg: Springer)

    work page

  25. [25]

    Dong D and Petersen I R 2010IET Control Theory & Applications42651–2671

    work page

  26. [26]

    Khaneja N, Brockett R and Glaser S J 2001Physical Review A63032308

    work page

  27. [27]

    Glaser S J, Boscain U, Calarco T, Koch C P, K¨ockenberger W, Kosloff R, Kuprov I, Luy B, Schirmer S, Schulte-Herbr ¨uggen T, Sugny D and Wilhelm F K 2015The European Physical Journal D69279

    work page

  28. [28]

    Boscain U, Mason P and Sigalotti M 2021PRX Quantum2030203 REFERENCES23

    work page

  29. [29]

    Coddington E A and Levinson N 1955Theory of Ordinary Differential Equations(New York: McGraw-Hill)

    work page

  30. [30]

    Hartman P 2002Ordinary Differential Equations(Philadelphia: SIAM) ISBN 9780898715101

    work page

  31. [31]

    Preskill J 2018Quantum279

    work page

  32. [32]

    Zhang K and Korepin V 2020Physical Review A101032346

    work page

  33. [33]

    Bria ´nski M, Gwinner J, Hlembotskyi V , Jarnicki W, Pli´s S and Szady A 2021Physical Review A103062425

    work page

  34. [34]

    Campos E, Rabinovich D and Uvarov A 2024Physical Review A110012428

    work page