Asymptotic optimality of Grover–Radhakrishnan–Korepin algorithm
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 paper closes a 20-year-old conjecture about the optimal structure of Grover-style partial search: the well-known global–local–global (GRK) operator ordering is asymptotically optimal in oracle query count, with no longer or more elaborate alternation pattern ever beating it. The proof recasts partial search as a time-optimal switching problem on an SO(3) reduction of the algorithm's invariant 3-dimensional subspace, then applies the Pontryagin maximum principle to constrain the bang–bang structure of optimal trajectories. The key combinatorial step shows that any interior YXY or XYX three-bang block can be compressed to a single shorter bang, forcing any optimal extremal to have at most three bangs total. For Yuan, this gives a clean theoretical anchor for Y4's cardinality-constrained Grover work: it confirms there is no asymptotic free lunch from longer alternations of global/local oracle operations, and the bang-compression style of argument is directly applicable to constrained search problems of the kind Y4 studies.
Main contribution
The authors prove that, in the large-block asymptotic regime (database of size N=2^n partitioned into K=2^{n-m} blocks of size b=2^m, with n and m both large), the Grover–Radhakrishnan–Korepin partial-search algorithm with structure G_n · G_m^{k_2} · G_n^{k_1} is asymptotically optimal in oracle query complexity among all possible orderings of the two Grover operators G_n (global diffusion) and G_m (local diffusion). The proof is purely control-theoretic: in the continuous-time limit, the two Grover generators reduce to two elements X, Y ∈ so(3), and the partial-search question becomes a minimum-time control problem on a 3-dimensional state space with the bang–bang controls {X, Y}. The total integrated control time is the oracle cost, so structural optimality of the GRK ordering follows directly from constraining the optimal bang-pattern.
Key theorems / lemmas
- Lemma 2.5 (PMP sign rule) — Establishes the bang–bang structure of regular extremals via the switching function, ruling out direct control along a singular arc.
- Lemma 3.3 (X-arc / Lemma 3.4 Y-arc): Reduced dynamics close on a single-variable scalar ODE on each pure-control arc, so the algorithm's exponentially large Hilbert space collapses to a tractable scalar recursion.
- Proposition 3.7 (Universal reduced switching map): The reduced map (φ₁, φ₂, φ₃) → (φ₁, −φ₂, φ₃) is independent of which arc (X or Y) was used, provided it is a switching-to-switching arc of canonical length.
- Lemma 4.4 (No singular arcs): Singular subarcs of positive measure cannot occur on regular time-optimal extremals.
- Theorem 5.1 (YXY compression): Any interior YXY block (length 2π + π/sin γ) can be replaced by a single shorter X-arc (length π/sin γ) without changing the reduced endpoint.
- Theorem 5.2 (XYX compression): Any interior XYX block (length 2π/sin γ + ℓ) can be replaced by a single Y-arc (length ℓ < 2π).
- Theorem 5.3 (At most two switchings): A regular normal time-optimal bang–bang extremal contains at most three bangs; the only nontrivial pattern is XYX.
- Theorem 5.4 (GRK structural optimality): Within the asymptotic continuous-limit formulation, the optimal partial-search operator ordering is global–local–global (G_n · G_m^{k_2} · G_n^{k_1}) with the standard GRK parameters.
- Appendix A (Endpoint lemmas): Show that the first and last bangs of an optimal extremal must both be X (i.e., global Grover), pinning the only nontrivial bang pattern to XYX.
Detailed walkthrough
The paper is organised as a pipeline: §2 reduces partial search to a 3-dimensional SO(3) representation; §3–4 derive a control formulation and a closed switching ODE; §5 finishes the combinatorial argument that picks out XYX uniquely.
Setup (§2): The database is partitioned into K = 2^{n−m} blocks of size b = 2^m. The standard 3-dimensional reduced subspace is spanned by |t⟩ (the unique target), |ntt⟩ (the equal superposition of non-target states inside the target block), and |u⟩ (the equal superposition of all states in non-target blocks). The global Grover operator G_n and the local operator G_m both preserve this 3-dimensional subspace. In the continuous-time limit (large b, K), the discrete generators converge to two elements X and Y of so(3), with X corresponding to global Grover (rotation rate 1) and Y to local Grover (rotation rate sin γ, where sin γ = √(b/N) = 1/√K). The success condition is that the projection of the final state onto |u⟩ vanishes; the cost to minimise is the total integrated control time.
Control formulation (§3): With bang–bang controls u(t) ∈ {X, Y}, Pontryagin's maximum principle (PMP) gives a costate p(t) and a switching function s(t) = ⟨p, (X−Y)x⟩ that determines which generator is active. Lemma 2.5 fixes the sign rule. A short calculation (§3.1) shows that the switching function and its first two derivatives are closed under the dynamics, yielding three reduced scalar variables (φ₁, φ₂, φ₃) on a 2-sphere whose evolution along each pure-control arc is governed by a closed Lie-algebraic recursion (Lemma 3.3 / 3.4). The crucial structural finding (Proposition 3.7) is that the reduced map (φ₁, φ₂, φ₃) → (φ₁, −φ₂, φ₃) at the canonical switching-to-switching arc length is the same for X-arcs and Y-arcs — both leave φ₁ and φ₃ invariant while flipping the sign of φ₂.
Singular arc exclusion (§4): A singular arc would have s(t) ≡ 0 on a positive-measure interval, so all three φᵢ vanish simultaneously. Lemma 4.4 shows this is impossible on a regular normal extremal: the algebraic system that defines φᵢ ≡ 0 has no consistent solution along an arc of positive duration. So all optimal trajectories are genuinely bang–bang.
The compression argument (§5.1): Because both X- and Y-arc reduced maps act identically as (0, a, b) → (0, −a, b) when restricted to switching-to-switching length, any interior three-bang block with the same endpoint data as a single arc can be replaced by that arc. Theorem 5.1 uses this for an interior YXY block: the YXY block has length 2π + π/sin γ, while a single replacement X-arc of length π/sin γ achieves the same reduced endpoint, so YXY is strictly suboptimal. Theorem 5.2 makes the symmetric argument for XYX, replacing it with a single Y-arc of length ℓ < 2π. Together, these exclude any interior three-bang subword on a regular time-optimal extremal.
The structure theorem (§5.2): An alternating bang–bang word with ≥ 4 bangs must contain an interior YXY or XYX subword, both excluded above, so no optimal extremal can have more than 3 bangs (Theorem 5.3). Appendix A (endpoint lemmas) shows the first and last bangs must be X-type (global Grover). Therefore the only nontrivial admissible pattern is XYX, i.e., G_n · G_m^{k_2} · G_n^{k_1} — exactly the GRK structure. Optimising arc lengths within this family reduces to the standard GRK parameter optimisation of Korepin (2005), giving k_1 ≈ (π/4)√N − (√3/2)√b, k_2 ≈ (π/6)√b in the large-K limit. The total cost is (π/4)√N − (η_K − α_K)√b + O(1), exhibiting the GRK speedup over standard √N Grover.
Caveats (Conclusion): The proof is asymptotic and continuous-time. There is a residual O(1) parity correction when continuous arc lengths are converted to integer iteration counts (because G_n ∈ O(3)∖SO(3) has det = −1 while the continuous-limit dynamics live in SO(3)). The authors also note that recent work (Jiang et al. 2026) shows GRK is no longer competitive with classical search when m > n/2, and that depth — not query count — is the more relevant metric on real hardware; both are open directions.
Overlap with Y1–Y6
- Y4 (Grover-based cardinality-constrained BO): Strongest alignment. Y4 builds a Grover-based algorithm with O(√(C(n,k)/M)) rotations over a structured feasible space; this paper proves that within a structured (partitioned) Grover setting, no operator-ordering trick beats the global–local–global ansatz asymptotically. This is a useful "no free lunch" theorem to cite when defending Y4's ordering choices. The Pontryagin-based bang-compression argument may also adapt directly to cardinality-constrained Grover, where the constraint defines a natural partition of the search space — a method-import opportunity.
- Y1 (iterative warm-started QAOA): Conceptual analogue. Both papers study the optimality of structured operator orderings in quantum optimisation (XYX here, parameter scheduling in Y1). The control-theoretic framing here may suggest a parallel question for warm-started QAOA: is the warm-start–reflect–rotate ordering itself asymptotically optimal among nearby orderings?
- Y3 (DGMVP-QAOA): Tangential. Y3's layerwise optimisation could be viewed as a discrete bang–bang policy on the QAOA parameter sequence; the PMP-style structural argument here is methodologically suggestive but not directly transferable.
Recommended action for Yuan
- Cite in next iteration of Y4 as the canonical statement of GRK optimality — this paper supersedes earlier conjectural references and is the clean citation for "no better ordering exists asymptotically" in any Grover-with-structure context.
- Read §3 and §4 in depth if Y4 follow-ups want to lift the Pontryagin / switching-function machinery into the cardinality-constrained Grover setting. The bang-compression argument is genuinely portable: pick the right Lie algebra for the constrained problem and the same recipe likely applies.
- Watch the depth-optimisation open problem flagged in the conclusion (Campos et al. 2024 on QAOA depth scaling is cited) — this is a natural niche for a follow-up paper combining Y4 (cardinality Grover) with depth-aware ordering arguments.