Asymptotic optimality of Grover–Radhakrishnan–Korepin algorithm

Kun Zhang, Kang-Yuan Chen, Xiao-Hui Wang (Northwest U.); Vladimir Korepin (Stony Brook) · arXiv:2604.15886 · new submission 2026-04-20 · 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

Zhang, Chen, Wang & Korepin (the K being Vladimir Korepin himself, co-author of the original GRK algorithm) finally prove the long-conjectured asymptotic optimality of the Grover–Radhakrishnan–Korepin partial-search algorithm. Their approach is to recast the discrete problem of finding the optimal ordering of global Grover (G_n) and local Grover (G_m) operators as a continuous-time bang-bang optimal control problem on SO(3), then apply the Pontryagin maximum principle (PMP). The result: every regular normal time-optimal extremal must have the pattern XYX (global–local–global), proving the GRK structure is the only nontrivial optimum in the large-block, large-database asymptotic regime. For Yuan, this is a foundational result for any future Grover-based optimisation work building on Y4, since it certifies the structure of the optimal Grover-style amplification schedule when one only needs partial information (e.g., a block of the cardinality-constrained feasible set rather than the exact optimum).

Main contribution

The partial-search problem for a database of size N=2^n with marked item |t⟩ is reduced to a 3-dimensional invariant subspace H_red = span{|t⟩, |ntt⟩, |u⟩}, where |ntt⟩ is the equal superposition over non-target items in the target block and |u⟩ is the equal superposition over the non-target blocks. In this basis the global and local Grover operators G_n and G_m are 3×3 orthogonal matrices, and in the large-block limit they reduce to one-parameter rotation flows generated by skew-symmetric generators X, Y ∈ so(3). The partial-search task becomes a minimum-time hitting problem: steer |s_n⟩ to the plane Σ = {⟨u|ψ⟩=0} using piecewise-constant controls A(t) ∈ {X, Y}. PMP gives a single scalar switching function Φ(t) = ⟨p(t), (X−Y)ψ(t)⟩ whose sign determines the optimal generator. The authors prove: (1) singular subarcs of positive length are excluded; (2) interior YXY and XYX three-bang blocks are compressible — they induce the same reduced switching-data map as a single bang but with strictly longer time; (3) the optimal extremal must start and end with X. Combining these: every regular time-optimal extremal has at most two switchings, and the only nontrivial pattern is XYX. Since X = global Grover and Y = local Grover, this is exactly the GRK global–local–global structure.

Key theorems / lemmas / algorithms

Detailed walkthrough

The paper's strategy is geometric. Section 2 reviews the GRK algorithm G_n G_m^{k_2} G_n^{k_1} and its standard 3-dimensional reduction following Korepin–Vallilo (2006), where the global and local Grover operators become 3×3 matrices in the {|t⟩, |ntt⟩, |u⟩} basis. The crucial scaling is k_1 = (π/4)√N − η√b, k_2 = α√b, with the constraint tan(2η/√K) = 2√K sin(2α)/(K − 4 sin²α). Optimising over (η, α) inside the global–local–global family yields the GRK parameters; in the large-K limit α_K → π/6, η_K → √3/2.

Section 3 reformulates this in the continuum limit. As b, K → ∞, the global and local Grover operators become rotation flows generated by X, Y ∈ so(3), and the discrete iteration count becomes a continuous duration. The partial-search problem then becomes the time-optimal control system ψ̇(t) = A(t)ψ(t), A(t) ∈ {X, Y}, with ψ(0) = |s_n⟩ and terminal condition ψ(T) ∈ Σ. Section 3.2 introduces the PMP and the switching function Φ(t) = ⟨p(t), (X−Y)ψ(t)⟩, where p(t) is the costate.

The technical heart is Sections 4 and 5. Section 4 introduces reduced switching variables (φ_1, φ_2, φ_3) that absorb the costate's structure into a small set of scalars whose dynamics close along X- and Y-arcs. Crucially (Proposition 4.7) the shortest switching-to-switching X-arc and Y-arc both induce a particularly simple map (0, a, b) ↦ (0, −a, b) on these reduced variables. Section 5 then proves (Lemma 5.4) that singular arcs are excluded, and that the reduced switching dynamics admit a universal continuation: once the reduced data at a regular switching point are fixed, the entire later bang-bang structure is fixed.

This setup powers the compression arguments of Section 6. Theorem 6.1 shows that an interior YXY block (Y-arc of length ℓ_1, then X-arc of length τ_X = π/sin γ, then Y-arc of length ℓ_2) can be replaced by a single X-arc with strictly shorter time. The argument: the Y-arc lengths between two consecutive switchings must satisfy ℓ_1 + ℓ_2 = 2π (Lemma 4.6), so L_YXY = 2π + π/sin γ > π/sin γ = τ_X. The reduced switching data are preserved by both, so by Proposition 5.6 the later evolution is unchanged. Theorem 6.2 gives the symmetric XYX-compression. Combining these (Theorem 6.3): if an extremal had ≥ 4 bangs, it would contain an interior 3-bang block, which is compressible — a contradiction with optimality. The appendix establishes that the first and last bangs must both be X (global). The only nontrivial possibility is therefore XYX, exactly the GRK pattern (Theorem 6.4).

The paper also notes one subtlety in the discrete-to-continuous bridge (Conclusion): the local operator G_m is orientation-preserving (det = +1) while G_n has det = −1. The PMP argument lives entirely in the orientation-preserving SO(3) subgroup, so it doesn't distinguish odd-parity vs even-parity discrete realisations. But this is only an O(1) endpoint correction, irrelevant to the leading asymptotic query count. An interesting open problem the authors flag: the standard GRK is provably not better than classical when m > n/2 (block size > √N), and the question of whether alternative diffusion operators can offer further advantage in this regime remains open. They also note that on real hardware circuit depth, not oracle queries, is the relevant resource — so GRK only remains optimal in depth when the oracle dominates the circuit cost.

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

Recommended action for Yuan

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