Asymptotic optimality of Grover–Radhakrishnan–Korepin algorithm

Kun Zhang, Kang-Yuan Chen, Xiao-Hui Wang (Northwest University), Vladimir Korepin (Stony Brook C.N. Yang Institute) · arXiv: 2604.15886 · submitted 2026-04-17 · score 8/10 (HIGH)

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

This is the long-awaited optimality proof for the GRK partial-search algorithm, closing a conjecture that dates back to 2005. Zhang, Chen, Wang & Korepin recast partial search as a two-generator time-optimal control problem on SO(3), invoke the Pontryagin maximum principle, and show that every regular normal optimal extremal has a bang–bang structure with at most two switchings and the pattern XYX — i.e., global–local–global. The result rigorously places GRK at the asymptotic optimum of all admissible Grover-operator sequences in the large-block regime. For Yuan this is directly relevant to Y4: any Grover-based algorithm on a structured feasible space, including cardinality-constrained binary optimisation, is subject to the same control-theoretic ceiling, and the PMP machinery here generalises to the design of partial-search variants on Y4's feasible space.

Main contribution

The central contribution is a control-theoretic proof that the optimal operator ordering for asymptotic quantum partial search is the three-arc pattern X–Y–X (global-local-global) and nothing else. The argument proceeds in three major moves. (i) Reduction to SO(3). In the invariant basis {|t⟩, |ntt⟩, |u⟩} both the global and local Grover operators act as 3×3 rotations; in the large-block limit these become near-identity rotations generated by X,Y ∈ 𝔰𝔬(3) (Eq. 2.25 of the source). (ii) Time-optimal reformulation. Partial search is restated as minimum-time steering of the initial state |sₙ⟩ to the hyperplane Σ = {⟨u|ψ⟩ = 0} under switched dynamics Ȧ(t) ∈ {X, Y}. (iii) PMP bang–bang analysis. The authors prove exclusion of singular arcs (Lemma 5.1), then prove that both an interior YXY block and an interior XYX block are strictly compressible (Theorems 5.1 and 5.2), so no regular extremal can have more than two switchings. Endpoint lemmas (Appendix A) show the optimal path must start and end with an X-arc, forcing XYX.

Key theorems / lemmas / algorithms

Lemma 3.1 (PMP sign rule): the switching function's sign determines the active generator; the bang–bang structure follows directly from PMP with a polyhedral control set.
Lemma 4.2 (Lie closure of X and Y): the Lie brackets of X,Y ∈ 𝔰𝔬(3) close into a three-dimensional Lie algebra, ensuring controllability and reducing the analysis to one additional bracket generator.
Lemmas 4.3–4.6 (reduced X-arc and Y-arc dynamics): along each bang the switching variables obey explicit rotational ODEs on a two-dimensional reduced space, integrable in closed form, with arc lengths bounded.
Proposition 4.1 (universal reduced switching map): the next switching point depends only on the reduced switching coordinates, not on the global phase-space location.
Lemma 5.1 (no singular arcs): on the reduced switching ODE, singular arcs violate time optimality — extremals are strictly bang–bang.
Theorem 5.1 (YXY compression): any interior YXY block can be replaced by a shorter X-arc preserving the terminal state, ruling out interior YXY.
Theorem 5.2 (XYX compression): any interior XYX block has length 2π/sin γ + ℓ strictly exceeding a single Y-arc of length ℓ ∈ (0, 2π) that achieves the same endpoint — so interior XYX is excluded.
Theorem 5.3 (at most two switchings): any regular normal bang–bang time-optimal extremal contains at most three bangs; the only nontrivial pattern is XYX.
Theorem 5.4 (GRK asymptotic optimality): the asymptotic continuous-limit partial-search problem is optimised by G_n G_m^{k₂} G_n^{k₁} with the GRK parameters k₁ = π√N/4 − √(3b)/2, k₂ = π√b/6.

Detailed walkthrough

Partial search asks: given an unstructured database of size N = 2ⁿ partitioned into K = 2^(n−m) blocks of size b = 2^m, identify only the block index of a marked target |t⟩. Grover & Radhakrishnan (2005) showed that this relaxed task can be solved faster than full Grover, and Korepin's optimisations (2005, 2006) yielded the three-stage global–local–global sequence G_n G_m^{k₂} G_n^{k₁}. But why this particular ordering is optimal has remained unproven for twenty years: the number of admissible operator orderings grows exponentially with the number of switches and no closed-form ordering lemma was known.

Section 2 constructs the invariant three-dimensional subspace ℋ_red = span{|t⟩, |ntt⟩, |u⟩}, where |ntt⟩ is the normalised equal superposition over non-target states within the target block and |u⟩ is the equal superposition over non-target blocks. In this basis the global Grover operator G_n is an element of O(3) \ SO(3) with determinant −1 (a reflection), while the local Grover operator G_m is an SO(3) rotation in the {|t⟩, |ntt⟩} plane. Section 2.2 passes to the large-block limit (θ₁ ~ 1/√N → 0, θ₂ ~ 1/√b → 0), yielding infinitesimal generators X,Y ∈ 𝔰𝔬(3) with X mixing all three basis vectors and Y a rotation confined to {|t⟩, |ntt⟩} (Eq. 2.25).

Section 3 recasts the search as a minimum-time reachability problem on ℋ_red: steer |sₙ⟩ to the plane Σ = {⟨u|ψ⟩ = 0} by the switched ODE ψ̇(t) = A(t)ψ(t), A(t) ∈ {X, Y}. The total time corresponds, in the continuous limit, to the total oracle-query count. This is the first time the partial-search problem has been phrased purely as a geometric-control problem, allowing the direct import of PMP machinery.

Section 4 derives the reduced switching dynamics. A naive PMP analysis on SO(3) would have to track a full co-state trajectory. The authors circumvent this by observing (Lemma 4.2) that the Lie algebra generated by X and Y has dimension three, and that the switching function can be expressed in terms of reduced observables. Lemmas 4.3 and 4.4 then give closed-form propagation rules for these reduced observables along single-bang X-arcs and Y-arcs, and Lemmas 4.5 and 4.6 bound arc lengths. Proposition 4.1 packages all of this into a universal switching map: given the reduced state just after a switch, the next switching time is an explicit function of these reduced coordinates, independent of the remaining phase-space details.

Section 5 is the logical core. Lemma 5.1 excludes singular arcs — a PMP extremal cannot have the switching function identically zero on a subinterval, ruling out degenerate control. Given that, the extremal is bang–bang and the only remaining question is: how many switches? Theorems 5.1 and 5.2 show that both YXY and XYX interior three-bang blocks are strictly compressible — each can be replaced by a single-bang arc that reaches the same endpoint in strictly less time. The YXY compression uses conjugation by an X-arc on the symmetry algebra 𝔰𝔬(3); the XYX compression uses the fact that a composed X-Y-X arc of length 2π/sin γ + ℓ is always longer than a single Y-arc of length ℓ ∈ (0, 2π) producing the same endpoint. Theorem 5.3 combines the two exclusions with the appendix's endpoint lemma (the first and last bangs must both be X) to conclude that the only nontrivial pattern is XYX.

Theorem 5.4 then packages this as the structural optimality of GRK: since X corresponds to the global Grover stage and Y to the local Grover stage, every asymptotically optimal regular extremal has the form G_n G_m^{k₂} G_n^{k₁}. The optimal arc lengths within this family are the classical GRK parameters k₁ = π√N/4 − √(3b)/2, k₂ = π√b/6. The authors note one caveat: since G_n has determinant −1 and sits outside the connected component of SO(3), the PMP argument controls only the connected part and distinguishes parity sectors only up to O(1) corrections to iteration counts — irrelevant to the leading asymptotic query count.

The concluding Section 6 notes two open questions with immediate methodological interest. First, recent numerical work (Jiang, Wang, Zhang, Korepin 2026) shows that the GRK operator sequence ceases to be efficient for m > n/2; whether alternative diffusion operators can improve this regime is open. Second, the metric here is oracle-query count; switching to circuit depth would re-open the optimality question — this is where Burke & Mc Goldrick's paper also in today's digest (arXiv:2604.15435) becomes directly relevant, since it reduces non-oracle circuit depth at fixed oracle-query count.

Figures

No figures extracted from source.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y4 — Grover + ADMM for cardinality-constrained BO (arXiv:2603.14744) — PRIMARY overlap. Y4 implements a Grover-based search with oracle complexity O(√(C(n,k)/M)) on a structured feasible space. This result establishes the rigorous asymptotic optimality ceiling for any partial-search strategy built from global and local Grover stages — Yuan's algorithm inherits the same control-theoretic bound when run on a block-decomposable feasible space. The PMP technique also suggests a concrete path to proving optimality of Y4's oracle-complexity claim, by lifting the same bang–bang argument to the constrained-feasible-space generators.
Y1 — iterative warm-started QAOA (arXiv:2502.09704) — conceptually adjacent. Both exploit structure of the quantum algorithm's generator set. Y1 warm-starts QAOA by iterative measurement; here the authors formalise the generator-switching problem itself as a time-optimal control problem — the same PMP tooling could be applied to QAOA generator scheduling (especially layerwise schedules — cf. Y3).
Y3 — QAOA DGMVP portfolio (arXiv:2410.16265) — methodological adjacency. Y3's "layerwise optimisation most robust" empirical finding echoes what is proved here: a short, structured generator sequence beats longer/less-structured ones. A PMP-style generator-scheduling proof for QAOA would extend this paper's approach.
Y2, Y5, Y6 — no direct overlap. Y2 is encoding/ansatz design, Y5 is SDP via Gibbs states, Y6 is an experimental foundations test.

Recommended action for Yuan

Cite in the Y4 discussion. The next revision of Y4 (or a companion optimality note) should cite this paper as rigorous justification that the Grover-based oracle-query-count claim sits at an asymptotic ceiling — the PMP argument directly transfers to structured feasible spaces.
Read deeply for method reuse. The universal-switching-map construction (Proposition 4.1) and the arc-compression proofs (Theorems 5.1, 5.2) generalise to any two-generator switched system on a semisimple Lie group. This is a method Yuan could adapt to QAOA layer scheduling (Y1, Y3) — specifically to prove that a fixed-length QAOA schedule cannot be beaten by a longer alternating mixer/phase-separator sequence.
Discuss with collaborators (Barnes / Long / Lepage). This result makes a clean theoretical companion to the numerical QAOA schedule comparisons in Y3. A follow-up would ask: can PMP give a structural optimality bound for QAOA layerwise schedules analogous to GRK's global–local–global pattern?