Asymptotic optimality of the Grover–Radhakrishnan–Korepin algorithm

Kun Zhang, Kang-Yuan Chen, Xiao-Hui Wang, Vladimir Korepin · arXiv:2604.15886 · submitted 2026-04-20 · 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

Zhang, Chen, Wang, and Korepin close a 20-year-old conjecture: the global–local–global structure of the GRK partial Grover search algorithm is asymptotically optimal among all admissible alternating-sequence schemes in the large-block limit. The proof recasts partial search as a time-optimal control problem on a 3D real subspace generated by two infinitesimal generators (X = global Grover generator, Y = local Grover generator), applies the Pontryagin Maximum Principle (PMP) to obtain bang-bang necessary conditions, excludes singular arcs, and proves that no interior three-bang block YXY or XYX can survive on a regular time-optimal extremal. Combined with endpoint lemmas forcing first and last bangs to be X, this leaves XYX as the unique nontrivial optimal pattern, which is exactly the GRK structure. For Yuan (Y4 author) the relevance is directly to the structured-Grover line: this paper is a foundational proof of asymptotic optimality that any cardinality-constrained Grover variant inherits as a lower bound, and the control-theoretic toolkit suggests how to attack analogous optimality questions for Y4's setting.

Main contribution

A control-theoretic proof of the asymptotic structural optimality of GRK. The reduction passes through three layers: (1) the partial-search problem on the 3D invariant subspace span{|t⟩, |ntt⟩, |u⟩} with terminal set Σ = {ψ : ⟨u|ψ⟩ = 0}; (2) the continuous-time control problem with admissible controls in {X,Y} ⊂ so(3); (3) PMP-based switching dynamics whose bang-bang regular extremals are shown to have at most two switchings — the unique optimal nontrivial pattern XYX. Within the XYX family, the standard GRK parameters tan(2η_K/√K) = √(3K−4)/(K−2), cos(2α_K) = (K−2)/(2(K−1)) are then optimal by the well-known inner optimisation, completing the proof.

Key theorems / lemmas / algorithms

Lemma 3.4 (PMP sign rule): Maximised-Hamiltonian sign condition gives the bang-bang structure of regular extremals.
Lemma 4.1–4.3 (X/Y arc dynamics and Lie closure): Reduced switching variables form a closed dynamical system under both generators; the Lie algebra of {X,Y} closes after taking [X,Y].
Proposition 4.6 (universal reduced switching map): Any switching-to-switching X-arc has fixed length τ_X = π/sin γ; Y-arcs have lengths in (0, 2π).
Lemma 5.5 (no singular arcs): Regular normal extremals have no singular subarcs of positive length.
Theorem 6.1 (compress-YXY): Every interior three-bang block YXY can be replaced by a single X-arc of strictly shorter time with identical reduced endpoint data.
Theorem 6.2 (compress-XYX): Every interior three-bang block XYX can be replaced by a single Y-arc of strictly shorter time with identical reduced endpoint data.
Theorem 6.3 (at-most-two-switchings): Any regular normal time-optimal bang-bang extremal has at most two switchings; combined with endpoint lemmas, the unique nontrivial pattern is XYX.
Theorem 6.4 (GRK structural optimality): In the asymptotic continuous-limit problem, the optimal operator ordering is global–local–global, namely G_n · G_m^k₂ · G_n^k₁ with the GRK parameters from Eq. 2.13.

Detailed walkthrough

The setting is the partial-search problem: a database of N = 2ⁿ items partitioned into K = 2^n−m blocks of size b = 2^m; the goal is to identify only the block t₁ containing the unique marked item, not the full bitstring. Grover and Radhakrishnan first showed that block-search admits a quadratic-with-better-constants algorithm faster than full Grover, and Korepin reduced the construction to a three-step global–local–global sequence G_n · G_m^k₂ · G_n^k₁ with a closed-form choice of k₁, k₂ (Eq. 2.10–2.13). The optimality of this arrangement among all admissible operator sequences has been an open question since 2005: the number of admissible sequences grows exponentially with database size, and only restricted classes had been ruled out before.

The authors' insight is that in the large-block (asymptotic) limit, the discrete iteration count becomes a continuous time variable and the algorithmic ordering question becomes a time-optimal switching control problem. The state lives on the 3D invariant subspace spanned by the marked item |t⟩, the equal superposition over the rest of the target block |ntt⟩, and the equal superposition over non-target blocks |u⟩ (Eq. 2.16). The terminal set Σ is the plane where the amplitude on |u⟩ vanishes — i.e. all probability has been concentrated inside the target block, regardless of where in the block the mark sits. The global Grover operator G_n and the local G_m reduce to two 3×3 orthogonal matrices, and in the continuous limit they are generated by X, Y ∈ so(3). The control problem: pick a measurable switching function u(t) ∈ {X,Y} that drives the system to Σ in minimum total time T = k₁ + k₂ + … (oracle-query count).

The PMP machinery (§3) gives the necessary conditions: the optimal control is bang-bang outside singular arcs, with switches occurring at the zero-crossings of a switching function φ(t) computed from a costate variable. §4 develops the closed reduced dynamics on the switching surface — crucially, the switching variables (φ₁,φ₂,φ₃) form a closed dynamical system under both X- and Y-arcs, and the Lie closure of {X,Y} in so(3) is achieved with one bracket. Lemma 4.6 (X-arc propagation) shows that any switching-to-switching X-arc has fixed length τ_X = π/sin γ regardless of the data, while Y-arcs have variable lengths in (0, 2π). §5 excludes singular arcs of positive length: the singular control would have to sit identically on the discriminant of the switching surface, but the closed dynamics forbid this.

The structural core (§6) establishes the central compression principle. Theorems 6.1 and 6.2 show that any interior three-bang block YXY or XYX can be compressed to a single bang of the opposite type with the same reduced endpoint data and strictly shorter total time. The argument is geometric: applying the universal reduced switching map (Prop. 4.6) successively to the three bangs sends the reduced data (0,a,b) to (0,−a,b), identical to the action of one bang of the opposite type. Since one X-arc has length τ_X=π/sin γ and the YXY block has length 2π+τ_X, the compression is strict; symmetrically for XYX. Therefore no interior three-bang block can survive on a regular time-optimal extremal. Combined with appendix endpoint lemmas forcing the first and last bangs to be X (the global Grover stage), this leaves at most two switchings — equivalently three bangs total — and the unique nontrivial pattern XYX (Theorem 6.3). Within the XYX family, the inner optimisation reproduces the standard GRK parameters from Korepin '05, completing the proof (Theorem 6.4).

The paper carefully flags two caveats. First, the continuous-limit reduction works in SO(3), but G_n has det = −1 (it is in O(3)\SO(3)). The PMP argument therefore proves optimality of XYX up to an O(1) parity correction; the discrete optimal sequence may be in the odd-parity sector, which is consistent with the original GRK construction (the trailing single G_n). Second, recent work (Jiang–Wang–Zhang–Korepin '26) has shown that GRK is no longer efficient versus classical search when m > n/2; whether alternative diffusion operators recover an advantage in that regime is left open. The conclusion also flags that depth (rather than oracle queries) is increasingly the relevant metric on near-term hardware — a connection point with the Burke–Mc Goldrick paper on the same listing day.

Figures

No figures extracted from source — the paper is theory-only and contains no figure files.

Citations to Yuan's papers

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

Overlap with Y1–Y6

Y4 (Grover + ADMM cardinality-constrained BO) — strongest overlap. Y4 builds on Grover-style amplitude amplification with structured feasible spaces. While GRK is partial search rather than cardinality-constrained search, the same three-dimensional reduction technique transfers: any structured Grover variant whose dynamics live in a low-dimensional invariant subspace can be analysed as a time-optimal control problem on that subspace with PMP. This is a methodological gift to any future "is the structured Grover ordering of Y4 actually optimal?" question. The asymptotic optimality bound also serves as a hard lower bound that any structured-Grover variant of Y4 must respect at parity.
Y2 (quasi-binary QAOA, hard mixer) — weak/methodological overlap. Hard-mixer QAOA-style sequences also alternate generators and admit time-optimal control formulations. The compression-of-three-bang-blocks technique is a generic tool that could potentially be applied to QAOA layer-ordering optimality questions, though QAOA's invariant subspace is generally higher-dimensional.
Y1, Y3, Y5, Y6 — no meaningful overlap.

Recommended action for Yuan

Read methodologically and adapt PMP toolkit for Y4. The Pontryagin-maximum-principle + bang-bang compression argument is reusable: a parallel question for Y4 is whether the Grover-ADMM iteration ordering is optimal. If Y4's structured-Grover dynamics admit a low-dimensional (3D or 4D) invariant-subspace reduction, the same machinery would directly apply.
Cite as a benchmark. Any future Y4 follow-up that proposes a new ordering of Grover/local rotations should cite this paper as the analogous asymptotic-optimality result for the partial-search analogue, framing Y4's claims relative to it.
Discuss with Wu/Chen (Y4 collaborators): the Korepin group is among the established voices on optimal Grover variants; a deliberate follow-up co-investigating cardinality-constrained Grover lower bounds with Korepin-style methods could be high-impact.