Asymptotic optimality of Grover–Radhakrishnan–Korepin algorithm

Authors: 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 & Korepin settle a long-standing open conjecture: in the asymptotic large-block regime, the Grover–Radhakrishnan–Korepin (GRK) global–local–global ordering G_n G_m^k₂ G_n^k₁ is the time-optimal way to solve quantum partial search, with no other operator ordering yielding a strictly shorter oracle-query count to leading order. The proof recasts the discrete optimisation over operator sequences as a continuous-time bang–bang control problem with two generators X, Y ∈ 𝔰𝔬(3) on a three-dimensional invariant subspace, applies the Pontryagin Maximum Principle (PMP) to derive a closed scalar dynamics for the switching function, then uses three-bang compression theorems to rule out every alternating pattern except the single non-trivial form XYX. For Yuan, the relevance is method-axis: this is the first structural optimality proof for a Grover-family search ordering, and the geometric-control toolkit it deploys (PMP, switching-function reduction, bang–bang compression) is portable to the cardinality-constrained Grover setting in Y4 — where the analogous "what is the optimal interleaving of two reflection types" question has not been settled.

Main contribution

The paper recasts asymptotic partial search as a minimum-time geometric-control problem on the three-dimensional reduced subspace ℋ_red = span{|t⟩, |ntt⟩, |u⟩}, where the global and local Grover operators correspond to two skew-symmetric generators X, Y ∈ 𝔰𝔬(3). Bang–bang controls correspond exactly to alternating sequences of global and local Grover stages; the PMP (Lemma 3.1) then certifies that in the regular normal regime the control is determined by the sign of a single scalar switching function Φ(t) = ⟨p(t), (X − Y)ψ(t)⟩. The technical core is a Lie-closure argument (Lemma 4.2) showing that the switching function and its first descendants close on a finite-dimensional space of observables, allowing a fully costate-free reduced dynamics. Two compression theorems (Theorems 7.1, 7.2) then show every interior YXY or XYX three-bang block is reducible to a single shorter bang with the same reduced effect. Combined with endpoint lemmas in the appendix forcing the first and last bang to be of type X, this collapses every regular normal time-optimal extremal to either a single X arc or the pattern XYX — i.e., global–local–global. Standard GRK parameter optimisation within this fixed pattern then yields full asymptotic optimality.

Key theorems / lemmas / algorithms

Lemma 3.1 (PMP sign rule): on a regular normal extremal, the maximising control is X when Φ(t) > 0 and Y when Φ(t) < 0; switchings can occur only at Φ(t) = 0.
Lemma 4.1 (reduced observable transport): for any fixed F ∈ ℝ^3×3 and pure A-arc, (d/dt)⟨p, Fψ⟩ = ⟨p, [F, A]ψ⟩.
Lemma 4.2 (XY Lie closure): the iterated commutators of X − Y with X, Y close on a finite-dimensional observable space, giving costate-free reduced dynamics for Φ and its descendants.
Lemmas 4.3–4.4 (X-arc / Y-arc reduced dynamics): closed-form ODE on each pure arc, integrable to switching-to-switching propagation laws (Lemmas 4.5, 4.6).
Proposition 4.7 (universal reduced switching map): the shortest switching-to-switching X- and Y-arcs both induce the involution (0, a, b) ↦ (0, −a, b) on the switching surface.
Proposition 5.4 / Lemma 5.5 (no singular arcs): regular normal extremals contain no singular subarcs of positive length.
Theorem 7.1 (YXY compression): any interior Y(ℓ₁) X(τ_X) Y(ℓ₂) block with τ_X = π/sin γ and ℓ₁ + ℓ₂ = 2π is reducible to a single shorter X-arc; total length 2π + π/sin γ versus π/sin γ.
Theorem 7.2 (XYX compression): any interior X(τ_X) Y(ℓ) X(τ_X) block is reducible to a single Y-arc of length ℓ < 2π/sin γ + ℓ.
Theorem 7.3 (at most two switchings): every regular normal time-optimal bang–bang extremal contains at most three bangs, and the only nontrivial pattern is XYX.
Theorem 7.4 (GRK structural optimality): the asymptotically time-optimal partial-search ordering is G_n G_m^k₂ G_n^k₁ with the standard GRK parameters (Eq. 2.13).
Appendix A (endpoint arc lemmas): the first and last bangs on any regular normal time-optimal extremal must both be X.

Detailed walkthrough

§2 (GRK and 3D formulation) recapitulates the partial-search setup: a database of size N = 2ⁿ is partitioned into K = 2^n−m blocks of size b = 2^m, with the goal of identifying the target block rather than the full target. The GRK algorithm has the form G_n G_m^k₂ G_n^k₁; the three-dimensional invariant subspace {|t⟩, |ntt⟩, |u⟩} reduces both Grover operators to SO(3) rotations whose infinitesimal generators are skew-symmetric X (global) and Y (local). The terminal condition for partial search is that the projection of the final state onto |u⟩ (non-target blocks) vanishes — geometrically, the trajectory must hit a 2-plane Σ in ℝ³.

§3 (PMP formulation) makes the discrete-to-continuous transition: in the asymptotic regime the operator-count-minimisation problem becomes a minimum-time hitting problem on ℋ_red with binary control A(t) ∈ {X, Y}. Lemma 3.1 derives the sign rule from the Pontryagin Hamiltonian — a direct calculation showing H(p, ψ; X) − H(p, ψ; Y) = Φ. The authors emphasise that the costate p(t) never needs an explicit form; only the switching function and its descendants matter.

§4 (Reduced switching dynamics) is where the proof's elegance lives. The Lie-closure argument (Lemma 4.2) establishes that observables of the form ⟨p, Fψ⟩, when transported by either X or Y, close on a finite-dimensional vector space. This means the reduced switching variables (φ₁, φ₂, φ₃) evolve under a closed ODE on each pure arc — the costate p is "integrated out". Lemmas 4.3 and 4.4 give explicit reduced dynamics on X-arcs and Y-arcs respectively, and Lemmas 4.5, 4.6 integrate them to derive the switching-to-switching propagation. The key takeaway is Proposition 4.7: both shortest switching-to-switching arcs (with τ_X = π/sin γ for X, and length ℓ ∈ (0, 2π) for Y) implement the same reduced-data involution (0, a, b) ↦ (0, −a, b). This is what makes compression possible.

§5 (Universal switching map and singular arcs) extends Proposition 4.7 to arbitrary regular continuations and proves there are no singular arcs of positive length on regular normal extremals (Lemma 5.5). This is essential — without it, the bang–bang structure could fail.

§6 (App. A endpoint lemmas) shows that the first and last bang must both be X (i.e., global Grover stages). The argument uses the boundary conditions: the initial state |s_n⟩ sits on a specific orbit of X, and only an X-arc can move it efficiently towards the target plane Σ; mutatis mutandis at the endpoint.

§7 (Compression and structural optimality) is the punch line. Theorems 7.1 and 7.2 use Proposition 4.7 + the universal switching-continuation map to prove that any interior YXY or XYX three-bang block can be replaced by a single shorter bang of the opposite type, while leaving the future reduced trajectory unchanged. By Theorem 7.3, this forces the time-optimal pattern to have at most three bangs total. Combined with the endpoint constraints (first and last must be X), the only nontrivial pattern is XYX — exactly global–local–global. Theorem 7.4 then concludes that the standard GRK parameter optimisation (Eq. 2.13) gives an asymptotically optimal partial-search algorithm.

§8 (Conclusion) frames the result and lists open problems: extending the proof to discrete parity sectors (the present argument is up to O(1) parity corrections), the regime m > n/2 where partial search loses its quantum advantage, and depth optimisation on hardware (where oracle dominance is no longer a given). The geometric-control formulation is portable: the same 𝔰𝔬(3) reduction and PMP machinery would apply to any two-reflection structured Grover algorithm.

No figures extracted from source — the paper is purely theoretical (theorems + proofs).

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): direct method-axis overlap. Y4 uses a Grover-style routine with O(√(C(n,k)/M)) rotations on a cardinality-constrained feasible space; the analogous structural question is "what is the optimal interleaving of cardinality-preserving and target-marking reflections?". The PMP / bang–bang / Lie-closure technique here is portable. The asymptotic SO(3) reduction in §2.2 has a counterpart for cardinality-constrained search via the Schur–Weyl decomposition that Yuan should investigate.
Y3 (DGMVP portfolio QAOA): the time-optimal-control framing is reminiscent of QAOA-as-Trotterised-adiabatic, where one optimises mixer/cost-Hamiltonian durations. The PMP machinery here may apply directly to the QAOA layer-duration optimisation that Y3 studies (where dual annealing was found most robust).
Y2 (quasi-binary QAOA, hard mixers): conceptually adjacent — the global-vs-local generator dichotomy parallels the cost-Hamiltonian-vs-hard-mixer alternation in constraint-preserving QAOA.
Y1, Y5, Y6: no significant overlap.

Recommended action for Yuan

Adapt the PMP method to Y4. The cardinality-constrained Grover analysed in Y4 is structurally a two-reflection algorithm on a Schur-component-decomposed Hilbert space. Working out the analog of the SO(3) reduction for the cardinality slice could yield the first structural optimality result for the Y4 algorithm, complementary to the existing √(C(n,k)/M) rotation-count bound.
Read deeper §4 (Lie closure) and Theorems 7.1–7.2: the compression mechanism is reusable and may give a shorter independent proof of the layerwise-optimality observation in Y3.
Email Vladimir Korepin — the geometric-control angle on quantum search aligns naturally with Yuan's optimisation programme; a direct conversation about whether the technique extends to cardinality-constrained / structured-feasible-space Grover variants would be high-leverage.