Asymptotic optimality of the Grover–Radhakrishnan–Korepin algorithm

Kun Zhang, Kang-Yuan Chen, Xiao-Hui Wang (Northwest U., Xi'an), Vladimir Korepin (Stony Brook) · arXiv:2604.15886 · submitted 2026-04-17 · score 8/10 (HIGH)

← Back to digest

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.

Executive summary

The authors close a long-standing conjecture: the GRK partial-search algorithm — which alternates a "global" Grover stage, a "local" (block-restricted) Grover stage, and a final "global" stage — is the asymptotically optimal arrangement of global and local Grover operators for partial search, in the large-database / large-block limit. They prove this by recasting partial search as a time-optimal control problem on a three-dimensional invariant subspace, applying Pontryagin's Maximum Principle (PMP), and then exhaustively excluding all alternative bang–bang switching patterns. The result is structural: the global–local–global ordering is forced, not just optimal within a guessed family. For Yuan, this is mostly interesting as a proof template (PMP applied to a Grover-family algorithm) rather than as a directly usable algorithmic improvement.

Main contribution

The paper proves that any regular normal time-optimal bang–bang extremal of the asymptotic partial-search problem has at most two switchings (Thm. 5.3), and therefore at most three bangs. Combined with the endpoint-arc lemmas of the appendix (which force the first and last arcs to be the global generator X), this leaves only one non-trivial admissible pattern: XYX = global–local–global. Optimizing the durations within this fixed ordering then recovers exactly the textbook GRK parameters (Thm. 5.4). The technique combines: (i) a three-dimensional reduction of the partial-search invariant subspace span{|t⟩, |ntt⟩, |u⟩}; (ii) explicit construction of the PMP switching function Φ(t) = ⟨p(t), (X − Y)ψ(t)⟩; (iii) a reduced Lie-closed observable algebra encoding Φ and its descendants; (iv) closed-form arc propagation laws on X-arcs and Y-arcs; (v) "block compression" theorems showing that internal YXY and XYX patterns are strictly suboptimal.

Key theorems / lemmas

Lemma 3.1 (PMP sign rule): on a regular normal extremal, Φ > 0 ⇒ X-arc, Φ < 0 ⇒ Y-arc, switching only at Φ = 0.
Lemma 4.4 (Lie closure of switching observables): the observables {⟨p, F ψ⟩ : F ∈ Lie(X, Y)} close on a finite-dimensional algebra, so the switching analysis does not require an explicit costate solution.
Lemmas 4.6 / 4.7 (reduced X/Y-arc dynamics): closed first-order ODEs governing Φ and its descendants on each pure-arc segment.
Lemmas 4.8 / 4.9 (arc propagation): explicit propagation laws for Φ between switching points on X- and Y-arcs.
Proposition 4.10 (universal reduced switching map): a single map collapses arbitrary arc concatenations to switching data on a low-dimensional manifold.
Lemma 5.1 (no singular arcs): on a regular normal time-optimal extremal Φ does not vanish identically on any interval of positive length, ruling out singular regimes.
Theorem 5.2 (compression of interior YXY blocks) and Theorem 5.3 (compression of interior XYX blocks): any interior three-bang block can be strictly shortened, so no time-optimal extremal contains one.
Theorem 5.4 (at most two switchings): regular normal time-optimal extremals contain at most three bangs; combined with endpoint arc lemmas (Appendix A), the only non-trivial pattern is XYX.
Theorem 5.5 (asymptotic structural optimality of GRK): within the asymptotic continuous-limit problem, the optimal operator ordering is global–local–global, with the GRK parameters α_K, η_K (Eq. 2.7 of the paper) attaining the optimum.

Detailed walkthrough

Setup (§2). The partial-search problem fixes a database of size N = 2ⁿ with a single marked item; the goal is not to find the full bitstring but to identify which of K = 2^n−m blocks of size b = 2^m contains it. The Grover-style global operator G_n = D_n O_t uses the full uniform-superposition diffusion D_n; the partial operator G_m = D_m O_t uses the block-local diffusion. GRK iterates G_n^k1, then G_m^k2, then one more G_n; the success condition (final amplitude on every non-target block vanishes) determines k1, k2 with the optimum given by Eq. 2.7.

Three-dimensional reduction (§2.2). The orbit of |s_n⟩ under {G_n, G_m} sits inside the three-dimensional subspace ℋ_red = span{|t⟩, |ntt⟩, |u⟩} where |ntt⟩ is the uniform superposition of non-target items inside the target block and |u⟩ is the uniform superposition over all non-target blocks. Restricted to this subspace, both Grover operators are 3 × 3 orthogonal matrices, and in the asymptotic large-block limit they are generated by skew-symmetric matrices X, Y ∈ 𝔰𝔬(3). The terminal "block correctly identified" condition becomes the linear constraint ⟨u | ψ⟩ = 0, defining a target plane Σ.

Time-optimal control formulation (§3). The asymptotic partial-search question — what ordering of G_n and G_m reaches Σ in the fewest oracle queries — becomes a time-optimal hitting problem for Σ under the control system ψ̇ = A(t) ψ, A(t) ∈ {X, Y}, minimising the total time T. Each X-arc duration corresponds (in the limit) to a fractional number of global-Grover queries; the discrete optimisation becomes a continuous PMP problem.

PMP and the switching function (§3.2). The PMP Hamiltonian for a normal extremal is H(p, ψ; A) = ⟨p, Aψ⟩ − 1. The difference H(p, ψ; X) − H(p, ψ; Y) reduces to the scalar Φ(t) = ⟨p(t), (X − Y) ψ(t)⟩, and Lemma 3.1 establishes that the sign of Φ uniquely determines the optimal arc. Switching can only occur at zeros of Φ.

Reduced switching dynamics (§4). Rather than carrying around the costate p(t), the authors work with a finite collection of bilinear observables ⟨p, F ψ⟩ for F in the Lie algebra generated by {X, Y}. These close on a finite-dimensional manifold (Lemma 4.4), which yields self-contained ODEs for Φ on each pure arc. Explicit integration on X- and Y-arcs (Lemmas 4.8, 4.9) gives the propagation law for Φ from one switching time to the next.

No singular arcs, no interior three-bang blocks (§5.1, 5.2, 5.3). Two pieces of work eliminate all candidates except XYX. First, Lemma 5.1 rules out singular arcs (intervals where Φ ≡ 0): on such a sub-arc the closed reduced dynamics force inconsistencies. Second, the compression theorems 5.2 and 5.3 show that any interior YXY or XYX block can be replaced by a strictly shorter trajectory hitting Σ with the same endpoint data, hence the original was not time-optimal. Iterating this argument forces the number of switchings to be at most two.

Endpoint constraints (Appendix A). The endpoint-arc lemmas show that the first and last arcs of a regular normal extremal must both be X-arcs. Combined with §5 this leaves only the bang words X (degenerate, purely global) and XYX. The XYX pattern is exactly global–local–global; the durations are then optimised within that fixed ordering, recovering Eq. 2.7 and hence the classical GRK parameter formula.

What is not proven. The authors are careful to flag (§5.4) that the asymptotic continuous-limit reduction only sees the SO(3) connected component, whereas G_n sits in O(3) ∖ SO(3) (det = −1). The PMP argument therefore establishes structural optimality up to an O(1) parity correction (odd vs. even total global stages); this matches the discrete parity sector identified in earlier group-theoretic work (KorepinVallilo 2006). It also does not extend to the regime m > n/2 nor to depth-optimal (as opposed to query-optimal) variants — both flagged as open in the conclusion.

Figures

No figures extracted from source. The paper is purely theoretical; the LaTeX source contains no figure environments and no graphics files.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography. The single-file main.tex (70 KB, with inline bibliography) was scanned for the six arXiv IDs and for the author+title fingerprint; nothing matched. The bibliography is focused on Grover-search and optimal-control classics (Pontryagin 1962, Liberzon 2012, Agrachev–Sachkov 2004, the original Grover and Korepin partial-search papers, the recent JiangWangZhangKorepin numerical evidence, and the AES-key-search literature). The single "Yuan" string match was the surname of co-author Kang-Yuan Chen, not a citation to Haomu Yuan.

Overlap with Y1–Y6

Y4 (Grover-based cardinality-constrained binary optimisation): closest method overlap. Y4 uses a Grover-style algorithm with structured feasible space on fixed-Hamming-weight strings; this paper proves an optimality result for the specific case of a structured search where the database is partitioned into blocks. The Pontryagin-Maximum-Principle proof technique here — recasting a discrete query-count optimisation as a continuous time-optimal control problem on the SO(3) subspace generated by the Grover operators — is a method that could in principle be applied to ask whether Y4's particular Grover-search arrangement is optimal among related orderings of structured-Grover and unstructured-Grover stages. This is the strongest of the overlaps, and probably the most useful angle for Yuan.
Y1 (iterative warm-started QAOA): weak parallel — both papers care about minimising the number of "outer" iterations of a quantum-search-like operator, but Y1 is about iterative parameter refinement in QAOA rather than about discrete ordering of Grover-family operators.
Y2, Y3, Y5, Y6: no meaningful overlap.

Recommended action for Yuan

Skim §3 and §5 for proof template: the time-optimal-control framing of "what is the best ordering of global vs. local Grover stages?" via PMP and switching-function exclusion is a clean blueprint. If Y4's algorithm involves multiple stages of differently-structured Grover operators (or could be extended to such), this is the technique that decides whether the chosen ordering is optimal. Worth a focused half-hour read of Theorems 5.3–5.5 to understand the recipe.
No urgent need to cite in current portfolio-optimisation work (Y2/Y3) or the SDP/Gibbs paper (Y5); the result is about partial search, not full search or constrained combinatorial optimisation.
If Y4's revision adds an "optimality of our Grover ordering" question: this paper is the canonical reference for the PMP-on-Grover proof style, and a "for partial search, recent work by Zhang–Chen–Wang–Korepin [arXiv:2604.15886] proves the GRK ordering is asymptotically time-optimal via Pontryagin's maximum principle" sentence would be a natural fit.