← Back to digest

Asymptotic optimality of Grover–Radhakrishnan–Korepin algorithm

Kun Zhang, Kang-Yuan Chen, Xiao-Hui Wang, Vladimir Korepin (Northwest University, Stony Brook) · arXiv:2604.15886 · submitted 2026-04 · 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 (with Korepin himself being one of the original GRK authors) close a long-standing conjecture: in the large-block limit, the global–local–global structure of the Grover–Radhakrishnan–Korepin partial-search algorithm is provably optimal among all bang-bang switching sequences of the two Grover operators G_n and G_m. They recast partial search as a continuous-time control problem on SO(3), apply the Pontryagin maximum principle to derive a closed switching map on a reduced two-dimensional phase space, exclude singular arcs, and prove that any regular time-optimal extremal has at most two switchings — so the only nontrivial pattern is XYX (global–local–global). For Yuan's programme, this is directly relevant to Y4, where the Grover-based cardinality-constrained algorithm's structure design and query-count optimality argument follow exactly the same algebraic family as the partial-search problem analysed here.

Main contribution

The paper turns the discrete combinatorial question "which ordering of G_n and G_m minimises oracle queries?" into a continuous-time bang-bang control problem on a three-dimensional state space, then proves a global structural theorem. In the large-block limit, the Grover operators reduce to two fixed generators X (global) and Y (local) in 𝔰𝔬(3); each iteration step k_i becomes a rescaled control duration. The cost (total queries) becomes total control time. The Pontryagin maximum principle gives necessary first-order conditions: regular extremals are bang-bang with controls switching between X and Y, governed by switching functions whose zeros mark the switching instants. The technical core is to show (i) no singular arcs of positive length exist (Lemma thm:no-singular-arcs), and (ii) any interior three-bang sub-pattern YXY or XYX can be "compressed" to fewer bangs without increasing time (Theorems compress-YXY and compress-XYX). Combined with endpoint lemmas forcing the first and last bang to be X (global), the regular time-optimal pattern must be either X or XYX. Thus the GRK structure G_n G_m^{k_2} G_n^{k_1} is the unique asymptotically optimal nontrivial pattern — and with the well-known GRK parameters (eq. GRK-optimal-parameters-sec2), it attains the optimal asymptotic query count (π/4)√N − (η_K − α_K)√b + O(1).

Key theorems and lemmas

Detailed walkthrough

The partial-search problem asks for the t_1 prefix of a single marked item in a database of N = 2^n items partitioned into K = 2^{n−m} blocks of size b = 2^m. Two operators are available: the global Grover operator G_n = D_n O_t built from the global diffuser D_n = 2|s_n⟩⟨s_n| − I, and the local Grover operator G_m = D_m O_t with the block-wise diffuser. The GRK algorithm uses the three-step sequence G_n G_m^{k_2} G_n^{k_1}|s_n⟩, and in the asymptotic regime k_1 = (π/4)√N − η√b, k_2 = α√b with the constraint tan(2η/√K) = 2√K sin(2α)/(K − 4 sin² α). Optimising the total query count π/4·√N − (η − α)√b yields the canonical GRK values, but whether this global–local–global ordering — among all bang-bang sequences of G_n and G_m of any length — actually minimises queries was an open structural question.

The first technical step (Sec. 2.2) is the standard three-dimensional reduction: the partial-search problem closes on a three-dimensional invariant subspace spanned by the target |t⟩, the uniform superposition over non-target items in the target block |ntt⟩, and the uniform superposition over items outside the target block |u⟩. The global Grover operator's matrix representation lies in O(3)\SO(3) (det = −1) while the local one is in SO(3) (det = +1). Sec. 3.1 takes the asymptotic continuous limit: the discrete iterates k_1, k_2 of G_n^{k_1}, G_m^{k_2} are rescaled to continuous arc lengths, the operators reduce to two infinitesimal generators X (corresponding to G_n) and Y (corresponding to G_m) in 𝔰𝔬(3), and the total query count becomes total control time T. Partial search becomes "reach the target manifold Σ = {amplitude on non-target blocks vanishes} from |s_n⟩ in minimum time using controls u(t) ∈ {X, Y}".

The Pontryagin maximum principle (Sec. 3.2) yields the Hamiltonian H(p, x, u) = ⟨p, (X or Y)x⟩, maximised by picking whichever of X, Y has the larger ⟨p, X x⟩ vs. ⟨p, Y x⟩. The switching function is the difference, and bang-bang controls correspond to regular extremals where the switching function is nonzero except at isolated points. The Lie closure of {X, Y} under brackets (Sec. 4.1) gives a four-dimensional Lie algebra; combined with the symplectic structure on the cotangent bundle, the switching dynamics reduces to a two-dimensional ODE on a phase plane of reduced switching variables. Lemma 4.5 and 4.6 give explicit closed-form propagation along X-arcs and Y-arcs respectively, and Proposition 4.6 packages these into a universal switching map: regardless of how a trajectory interleaves X- and Y-arcs, the action on the switching state factorises through this map.

Sec. 5 then excludes singular arcs. A singular arc — where the switching function vanishes on an open interval — would correspond to a non-bang-bang control mixing X and Y continuously. Lemma thm:no-singular-arcs uses the reduced switching dynamics to show that, on regular normal extremals, vanishing of the switching function forces a contradiction with the dynamics' time-optimality. So all candidates are bang-bang.

Sec. 6 is the structural core. Theorem compress-YXY shows that any interior three-bang block of the form Y → X → Y on a regular time-optimal trajectory can be replaced by a shorter or equal-time trajectory without the interior X-bang (by exploiting the universal switching map: the reduced trajectory's image under the YXY composition coincides with that of a shorter YY or XY block). Theorem compress-XYX gives the analogous result for X → Y → X interior blocks. The proofs rely on the explicit form of the propagation maps and on the bang-bang character of the extremals — they show that the switching function returns to the same sign after the three-bang block, so a compression is feasible. Theorem at-most-two-switchings then concludes: an extremal with three or more switchings would contain an interior YXY or XYX block, contradicting the compression theorems. Hence at most two switchings, i.e., at most three bangs. Endpoint lemmas in Appendix A force the first and last bang to be X. The only nontrivial pattern is therefore XYX, i.e., global–local–global. Theorem GRK-structural-optimality completes the argument by combining the structural result with the standard GRK parameter optimisation.

The discussion (Sec. 7) is candid about scope. The proof is for the asymptotic continuous-limit problem on the connected SO(3) component; the discrete parity issue — G_n has det = −1 and the total number of global Grover steps must have the right parity for the trajectory to actually reach Σ — is handled by an O(1) endpoint correction that does not affect the leading √N · √b asymptotic. The authors also note that for m > n/2 the GRK algorithm is not efficient relative to classical partial search, but this is a different regime — they restrict to the standard partial-diffusion operator. A residual open question they highlight: depth-optimal (rather than query-optimal) partial search, which would change the cost functional and may admit a different optimal pattern.

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.