← Back to digest

Asymptotic optimality of Grover–Radhakrishnan–Korepin algorithm

Kun Zhang, Kang-Yuan Chen, Xiao-Hui Wang, Vladimir Korepin · arXiv:2604.15886 · new submission 2026-05-24 · score 8/10

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 (the same Korepin in the algorithm's name) settle a long-open conjecture: the Grover–Radhakrishnan–Korepin (GRK) algorithm is asymptotically optimal for partial search in the large-block limit. The paper recasts partial search as a time-optimal control problem on the 3-dimensional reduced space spanned by |t⟩, |ntt⟩, |u⟩, applies the Pontryagin maximum principle to get a bang-bang structure between the two skew-symmetric generators X, Y ∈ 𝔰𝔬(3) corresponding to global and local Grover, and proves that the only optimal pattern is XYX — exactly the global–local–global structure of GRK. For Yuan, the directly relevant theme is Y4: the Grover-family techniques and the design of structured oracles/diffusion stages are the same ingredients underlying Y4's cardinality-constrained algorithm, and the control-theoretic optimality framework presented here is a methodological template that could be adapted to argue (in)optimality of multi-stage Grover algorithms with structured feasible spaces.

Main contribution

The paper proves a structural optimality theorem (Theorem 5.4) for partial quantum search: within the asymptotic continuous-limit formulation, the only nontrivial time-optimal operator ordering is G_n G_m^{k₂} G_n^{k₁} (global–local–global), with the GRK parameters tan(2η_K/√K) = √(3K−4)/(K−2) and cos(2α_K) = (K−2)/(2(K−1)). Mechanically: in the large-block limit each elementary Grover step is a near-identity rotation, so the discrete operator sequence becomes a time-optimal switching problem between two SO(3) generators. The Pontryagin maximum principle then forces a bang-bang structure on regular extremals. Two key compression theorems exclude all longer alternating sequences: any interior three-bang block of the form YXY or XYX can be replaced by a single shorter bang with the same reduced endpoint data. Together with endpoint arc lemmas in the appendix (the optimal extremal must start and end with X), this collapses the admissible patterns down to X (trivial) and XYX (the GRK structure).

Key theorems / lemmas / algorithms

• 3D reduction (Sec. 2.2). Partial search lives on ℋ_red = span{|t⟩, |ntt⟩, |u⟩} with terminal condition ⟨u|ψ⟩ = 0. The global Grover G_n and local Grover G_m act as 3×3 matrices; their large-block limit generators X, Y ∈ 𝔰𝔬(3) are explicit.
• Time-optimal switching formulation (Sec. 3). ψ̇(t) = A(t) ψ(t), A(t) ∈ {X, Y}, with the cost being total time. Oracle complexity ↔ control time.
• Pontryagin sign rule (Lemma 3.1). Switching functions ϕ_X(t), ϕ_Y(t) obey a closed ODE on the switching surface.
• Universal reduced switching map (Proposition 4.1). Single switching-to-switching X- and Y-arcs both implement (0, a, b) ↦ (0, −a, b) on the switching surface — the same reduced endpoint map.
• Exclusion of singular arcs (Lemma 4.6). No regular normal time-optimal extremal contains a singular subarc of positive length.
• YXY compression (Theorem 5.1). Any interior Y(ℓ₁) X(τ_X) Y(ℓ₂) block with τ_X = π/sin γ and ℓ₁ + ℓ₂ = 2π can be replaced by a single shorter X-arc of length τ_X; total length 2π + π/sin γ > π/sin γ.
• XYX compression (Theorem 5.2). Any interior X(τ_X) Y(ℓ) X(τ_X) block can be replaced by a single shorter Y-arc; total length 2π/sin γ + ℓ > ℓ.
• At-most-two-switchings (Theorem 5.3). Combining the two compression theorems with endpoint arc lemmas, every regular normal time-optimal bang-bang extremal has at most three bangs.
• Main result — GRK structural optimality (Theorem 5.4). The only nontrivial asymptotically optimal pattern is XYX; combined with the GRK parameter optimisation, the GRK algorithm G_n G_m^{k₂} G_n^{k₁} is asymptotically optimal.

Detailed walkthrough

The partial-search problem asks: in an unstructured database of N = 2ⁿ items with a unique target |t⟩, decompose t = t₁ t₂ with |t₁| = n−m, partition the database into K = 2n−m blocks of size b = 2m, and identify the block t₁ without recovering t₂. Grover & Radhakrishnan (2005) showed this is faster than full search; the GRK algorithm G_n G_m^{k₂} G_n^{k₁}|s_n⟩ with optimised k₁, k₂ achieves an asymptotic query count of (π/4)√N − (η_K − α_K)√b + O(1). Multiple alternative orderings (global-local, local-global-local-global, etc.) were studied but no one proved XYX was best.

The 3D reduction (Sec. 2.2) collapses the entire dynamics to the basis {|t⟩, |ntt⟩, |u⟩}, where |ntt⟩ is the equal superposition over non-target states inside the target block and |u⟩ is the equal superposition over states in non-target blocks. With sin θ₂ = 1/√b and sin γ = 1/√K, the initial state is |s_n⟩ = sin γ sin θ₂ |t⟩ + sin γ cos θ₂ |ntt⟩ + cos γ |u⟩ and the success condition is simply that the |u⟩-amplitude vanish. In the large-block limit, both θ_1 = arcsin(1/√N) and θ_2 = arcsin(1/√b) are infinitesimal, so the global and local Grover operators become exponentials of skew-symmetric generators X, Y ∈ 𝔰𝔬(3): X = [[0, s², sc], [−s², 0, 0], [−sc, 0, 0]], Y = [[0, 1, 0], [−1, 0, 0], [0, 0, 0]], with s = sin γ, c = cos γ.

The time-optimal control problem (Sec. 3) is then: starting from |s_n⟩, choose a piecewise control A(t) ∈ {X, Y} to reach the terminal plane Σ = {⟨u|ψ⟩ = 0} in minimum total time. The Pontryagin maximum principle gives necessary conditions through a switching function ϕ_X(t) − ϕ_Y(t); positive ⇒ use X, negative ⇒ use Y. Switching can happen only at zeros of the switching difference.

The technical core is Sec. 4. The authors derive a "universal reduced switching map": although the individual switching functions ϕ_X, ϕ_Y, ϕ_Z (with Z = [X, Y]) are nontrivial along each arc, at each switching point they collapse to canonical coordinates (0, a, b) (with a ≠ 0 for regular switchings), and one full switching-to-switching arc — of either type X or type Y — sends (0, a, b) ↦ (0, −a, b). This is the key observation: both arc types implement the same reduced map on the switching surface; only their durations differ. The X-arc has duration τ_X = π/sin γ (Lemma 4.2); the Y-arc has duration in (0, 2π), and consecutive Y-arcs separated by one bang satisfy ℓ₁ + ℓ₂ = 2π (Lemma 4.3).

The compression argument (Sec. 5.1) then becomes a simple time-comparison. An interior YXY block sends (0,a,b) ↦ (0,−a,b) overall and has total length 2π + π/sin γ; a single X-arc induces the same map in time π/sin γ. Hence the YXY block is strictly suboptimal. The dual argument excludes interior XYX blocks (overall length 2π/sin γ + ℓ > ℓ, beaten by a single Y-arc). Combined with two appendix lemmas showing the first and last bang must be X, every regular normal time-optimal extremal has the structure X (trivial) or XYX (non-trivial). The XYX pattern is precisely the global–local–global structure of GRK.

The final step (Theorem 5.4) is to optimise arc lengths within the XYX family; this reduces to the standard GRK parameter optimisation, recovering tan(2η_K/√K) = √(3K−4)/(K−2) and cos(2α_K) = (K−2)/(2(K−1)). So GRK is asymptotically optimal in oracle-query complexity in the large-block regime.

The discussion (Sec. 6) raises two caveats Yuan should note. First, the optimality is in oracle-query count; circuit depth — the actually-relevant resource on NISQ hardware — is a different question, and Zhang et al. explicitly flag that "GRK remains optimal in depth only in the regime where the oracle depth dominates the total circuit cost." Second, a recent companion paper (Jiang et al., 2026) shows that for m > n/2 GRK is not efficient relative to classical, and the authors leave open whether alternative diffusion operators can recover an advantage in that regime — a natural opening for follow-up.

Figures

No figures extracted from source (the paper is purely analytical and contains no figures).

Citations to Yuan's papers

Overlap with Y1–Y6

• Y4 (Grover + ADMM cardinality-constrained BO): direct method overlap. Both papers live in the Grover-family algorithm-design space, with Y4 designing a Grover-style algorithm over a structured feasible space (k-of-n bitstrings, cost O(√(C(n,k)/M))) and this paper proving optimality of a different structured Grover variant (block-partitioned partial search). The Pontryagin-maximum-principle framework — recasting a discrete operator-sequence optimisation as a continuous time-optimal control problem — is a methodological template that could be adapted to argue optimality (or suboptimality) of cardinality-constrained Grover variants.
• Y1 (iterative warm-started QAOA): shared scope (iterative quantum-optimisation primitives) but different methodology — Y1 is variational/measurement-based, this paper is control-theoretic over fixed unitaries. The "no-arbitrary-switching" structural result is conceptually similar to Y1's observation that not all warm-starting schedules are useful, but the proof techniques are unrelated.
• Y3 (QAOA DGMVP portfolio): only weak overlap — Y3 focuses on end-to-end optimisation under realistic noise, this paper is asymptotic and noise-free.
• Y2 (quasi-binary portfolio QAOA): weak overlap; Y2 is QAOA-side encoding/mixer design, this paper is Grover-side optimality.
• Y5, Y6: no real overlap.

Recommended action for Yuan

• Read deeper (PMP framework). The control-theoretic recasting of Grover-style algorithms as time-optimal switching problems on 𝔰𝔬(3) (Sec. 3, 4) is a powerful framework that Yuan has not yet used in Y4. A natural follow-up: can the cardinality-constrained Grover oracle be reduced to a low-dimensional invariant subspace, and if so, what's the PMP analysis say about the optimal mix of global/local stages? This could either confirm Y4's algorithm is asymptotically optimal in its class or expose a structural improvement.
• Possibly cite in Y4 follow-up. Y4 makes claims about quadratic speedup for cardinality-constrained binary optimisation; this paper is the canonical reference for "what does asymptotic optimality of a Grover-family algorithm even mean in the structured-feasible-space setting." Worth citing whenever Y4 or its descendants discuss optimality.
• Email authors / discuss with collaborators. Korepin's group is the historical centre of GRK work; if Yuan is contemplating depth-efficient partial-search variants (which Sec. 6 of this paper explicitly calls out as an open problem), reaching out for a collaboration on the cardinality-constrained case may be high-value.

Deep analysis generated from LaTeX source · not peer review · author claims not verified.