Quantum Search without Global Diffusion

Authors: John Burke, Ciaran Mc Goldrick · arXiv: 2604.15435 · submitted 2026-04-20 (announced 2026-05-09 cycle) · score 8/10 (HIGH)

Abstract

Quantum search is among the most important algorithms in quantum computing, offering fundamentally new approaches to optimisation and information processing. At its core is quantum amplitude amplification, a technique that achieves a quadratic speedup over classical search by combining two global reflections: the oracle, which marks the target, and the diffusion operator, which reflects about the initial state. We show that this speedup can be preserved when the oracle is the only global operator, with all other operations acting locally on non-overlapping partitions of the search register. We present a recursive construction that, when the initial and target states both decompose as tensor products over these chosen partitions, admits an exact closed-form solution for the algorithm's dynamics. This is enabled by an intriguing degeneracy in the principal angles between successive reflections, which collapse to just two distinct values governed by a single recursively defined angle. Applied to unstructured search, a problem that naturally satisfies the tensor decomposition, the approach retains the O(√N) oracle complexity of Grover search when each partition contains at least log₂(log₂ N) qubits. On an 18-qubit search problem, partitioning into two stages reduces the non-oracle circuit depth by as much as 51%–96% relative to Grover, requiring up to 9% additional oracle calls. For larger problem sizes this oracle overhead rapidly diminishes, and valuable depth reductions persist when the oracle circuit is substantially deeper than the diffusion operator. More broadly, these results show that a global diffusion operator is not necessary to achieve the quadratic speedup in quantum search, offering a new perspective on this foundational algorithm. Moreover, the scalar reduction at the heart of our analysis inspires and motivates new directions and innovations in quantum algorithm design and evaluation.

Executive summary

Burke & Mc Goldrick prove that the global diffusion operator in Grover-style amplitude amplification can be replaced by a recursive cascade of local reflections acting on non-overlapping qubit partitions, while still preserving the quadratic O(√N) oracle scaling. The construction works whenever the initial and target states factorise as tensor products across the partition — a condition that unstructured single-target search satisfies trivially. The trade-off is a controlled oracle overhead of 1/∏cos(θᵢ) that decays to unity once each partition has at least log₂ log₂ N qubits, in exchange for non-oracle circuit depth reductions of 51–96% on the 18-qubit numerical demonstration. For Yuan, the central appeal is conceptual: it suggests a route to running cardinality-constrained Grover (Y4) on hardware where global multi-controlled diffusion is the dominant cost, opening a depth-reduction lever orthogonal to the rotation-count O(√(C(n,k)/M)) result of Y4.

Main contribution

The paper introduces a recursive reflection family W_i = (S_{ψᵢ} W_{i-1})^{tᵢ} S_{ψᵢ} (W_{i-1} S_{ψᵢ})^{tᵢ} with base case W₀ = S_x, where each S_{ψᵢ} is a partial diffusion confined to register i. The central technical observation is that, although the eigenspaces of these reflections grow exponentially with recursion depth, the principal angles between consecutive reflections collapse onto two values governed by a single scalar recursion sin(2γᵢ) = sin(2θᵢ) sin(2t_i-1γ_i-1). This scalar collapse is what enables an exact closed-form expression for the success probability and the optimal iteration count t_m^* = ⌊π/(4γ_m) − 1/2⌉, and ultimately the oracle complexity bound C ≤ C_QAA/∏cos(θᵢ). After the outermost register is amplified, the remaining registers are measured, reinitialised, and the procedure is repeated on a strictly smaller search; the overall cost is dominated by the first round through a geometric-series argument.

Key theorems / lemmas / algorithms

Recursive reflection construction: W_i defined above is itself a reflection, with eigenspace structure characterised entirely by γᵢ and tᵢ.
Principal-angle degeneracy: the angles between consecutive reflections collapse to two values γᵢ and π/2 − γᵢ, recursively defined by sin(2γᵢ) = sin(2θᵢ) sin(2t_i-1γ_i-1) with γ₁ = θ₁.
Stage-success formula (Eq. 11): ‖P_{x_m}(S_{ψ_m}W_{m-1})^{t_m}|ψ⟩‖² = ½[1 − cos(2θ_m)/cos(2γ_m) · cos(2(2t_m+1)γ_m)].
Per-round oracle complexity (boxed Eq. 21): C ≤ C_QAA / ∏ᵢcos(θᵢ); intermediate iterates tᵢ = 1 are oracle-optimal.
Total-cost bound for unstructured search (boxed Eq. 28): C_total ≤ C_Grover⁽ⁿ⁾/∏cos(θᵢ) · 1/(1 − 2^1−s/2), with the second factor below 1.15 for stage size s ≥ 6.
Asymptotic optimality: for partition size s ≥ log₂ log₂ N, both the oracle overhead and the geometric-series factor converge to one, recovering full O(√N) Grover scaling.

Detailed walkthrough

Section §3 (Algorithm) sets up a partition of the n-qubit register into m blocks of sizes nᵢ, and assumes the state-preparation unitary A = ⊗Aᵢ and target |x⟩ = ⊗|xᵢ⟩ both factor across this partition. The partial diffusion S_ψᵢ = I − 2|ψᵢ⟩⟨ψᵢ| acts only on register i; concretely it requires Aᵢ, Aᵢ†, and a single nᵢ-qubit zero-state phase flip — locality is therefore strict, the diffusion never sees more than nᵢ qubits at once.

The recursion Wᵢ alternates the partial diffusion with the prior reflection, in a "sandwich" pattern of depth 2tᵢ + 1. The proof in §3.2 (proof.tex) shows that even though Wᵢ has dimension-2ⁱ reflected subspaces, the action on any state in the invariant span {|ψⱼ⟩, |ψⱼ^⊥⟩} reduces to a 2D rotation by γᵢ. The mechanism is a remarkable cancellation: the two reflections' principal angles, generically a full spectrum, instead collapse into the single scalar γᵢ. This is the technical engine of the paper.

§3.3 (final_complexity) establishes that intermediate iterate counts tᵢ for i < m are oracle-optimal at tᵢ = 1: doubling any intermediate iterate produces at most a factor-of-two improvement in γᵢ, the same as doubling tᵢ directly, while costing twice the oracle calls. This gives the per-round bound C ≤ C_QAA/∏cos(θᵢ). The total cost over all rounds (since outer registers are measured one by one) forms a geometric series whose ratio is 2^−nᵢ/2+1; for stage sizes s ≥ 6 the multiplicative blow-up is bounded by 1.15 (Eq. 28).

§3.5 (grover_search) instantiates the framework for unstructured single-target search, where the tensor-product condition holds automatically: A is a product of Hadamards, |x⟩ is a computational basis state, so θᵢ = arcsin(2^−s/2). The asymptotic argument is clean: ∏cos(θᵢ) → 1 when s = log₂ log₂ N (a vanishing fraction of n), so the recursive scheme attains exactly the Grover oracle complexity to leading order. Crucially, the per-oracle-call diffusion drops from an n-qubit global multi-controlled gate to a log₂ n-qubit local one — this matches the asymptotic gate-count scaling of [Grover-trade-offs] but with a much simpler construction.

§4 (Evaluation) verifies the analysis on an 18-qubit single-target problem with both 3-stage [6,6,6] and 2-stage [9,9] configurations (Fig. 3 reproduced below). Three multi-controlled-X decomposition scenarios are compared: S1 (no ancillae), S2 (dirty V-chain), S3 (one clean ancilla). Across these scenarios, the recursive scheme's diffusion depth ranges from 3% to 49% of standard Grover, at a 9–30% oracle-call overhead. The scaling figures (Figs. 4–5) extrapolate to n = 20…50: the failure probability stays low for k = 2,3,4 stages, and the break-even oracle-to-diffusion depth ratio — the threshold above which the recursive scheme has lower total depth — is computed under all three scenarios. For oracle-heavy applications (5× or 10× the diffusion depth, common in practice), depth advantage persists across all tested sizes.

§5 (Discussion) frames the result as a structural decoupling: the quadratic speedup is preserved as long as the oracle remains a single global operator, while every other gate can be confined to O(log n)-qubit subsystems. This is a striking re-reading of where the speedup actually lives. The authors note that the scalar collapse (a single γᵢ recursion) is itself a tool that may apply elsewhere in algorithm design — an invitation to look for similar reductions in QAOA, amplitude estimation, and structured-search variants. The construction is friendly to NISQ heavy-hex topologies precisely because nothing global except the oracle is ever required.

Figures

Figure 3. Simulation and depth comparison of the recursive search scheme against standard Grover search on an 18-qubit single-target problem. Top: Measurement-outcome distributions for the 3-stage [6,6,6] (left) and 2-stage [9,9] (right) configurations. Bottom-left: Diffusion-operator circuit depth (log scale) for both configurations under three decomposition scenarios (S1: no ancillae, S2: dirty V-chain, S3: one clean ancilla). Bottom-right: total oracle calls relative to Grover at matched success probability.

Figure 4. Scaling behaviour of the recursive search scheme for k = 2, 3, 4 stages of near-equal size, computed analytically across n = 20 to n = 50 qubits. Left: failure probability 1 − p (log scale). Right: relative oracle overhead vs. standard Grover at matched success probability.

Figure 5. Depth scaling relative to standard Grover for k = 2, 3, 4 stages across n = 20 to n = 50 qubits. Top: break-even oracle-to-diffusion depth ratio under three multi-controlled-X decomposition scenarios. Bottom: total circuit depth assuming a single oracle is 1×, 5×, 10× the depth of one diffusion operator. The dashed red line marks parity with Grover; values below indicate a depth advantage.

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 overlap. Y4's algorithm uses Grover with O(√(C(n,k)/M)) rotations on a structured (cardinality) feasible space; the outermost loop calls a global multi-controlled diffusion. The Burke & Mc Goldrick construction would, in principle, allow Y4's outer Grover to use only local diffusions — provided the initial state and target factor across a chosen partition. The cardinality-constrained Dicke-state initial state is not a tensor product, so direct application requires either (a) extending the construction to non-tensor inputs (the authors hint at this in §3.4 / non_tensor_case), or (b) using the local-diffusion recursion only for the inner unstructured Grover sub-problem invoked by ADMM rounds.
Y3 (DGMVP portfolio QAOA): conclusion-axis touch. The depth-vs-oracle trade-off illuminates where the dominant non-mixer cost lives in NISQ Grover, mirroring the layerwise/dual-annealing optimisation discussion in Y3.
Y1 / Y2: only loosely related — neither paper is a QAOA variant; the recursion is amplitude-amplification, not phase-separator/mixer.
Y5 / Y6: no overlap.

Recommended action for Yuan

Read deeper, specifically §3.4 (non-tensor case) and §3.5 (oracle complexity), to determine whether the recursion can be extended to Dicke-state-initialised Grover on the cardinality slice — that would make it directly composable with Y4's outer loop.
Implement for comparison: drop the local-diffusion recursion into the inner unstructured Grover sub-problem of Y4's ADMM hybrid and benchmark non-oracle depth on a representative cardinality-constrained QUBO. The 51–96% depth reduction reported on 18 qubits is large enough that it might shift the noise crossover identified in Y3.
Cite in the next revision of Y4 as related work on Grover-search depth reduction; the scalar-recursion observation is genuinely novel and worth flagging as future-direction material.