Abstract
Quantum search combines two global reflection operators: one about the target state, the oracle, and one about an initial state that has some overlap with the target, the diffusion operator. We demonstrate that this latter operator doesn't always need to be global and that search can instead be achieved with all non-oracle operators acting locally on non-overlapping sets of qubits. When the state preparation unitary and the target state both decompose as tensor products across a partition of the search register --- a condition naturally satisfied by Grover search for a single target --- a recursive construction from the oracle and local diffusion operators yields an exact closed-form expression for the success probability. Each round amplifies the target component within one register, which is then measured, and the process is repeated until the full target is recovered. When the decomposition constraint on the target state is relaxed, we show that the target can still be extracted with high probability.
We prove that, despite the exponentially increasing rank of the reflection projectors at each level of the recursion, the principal angles between successive reflections collapse to just two distinct values governed by a single recursively defined angle determined entirely by the local overlaps between the prepared and target states within each register. This yields an exact closed-form expression for the success probability and optimal iteration count, with an oracle overhead of $O\!\left(1\big/\prod_{i=1}^{m}\cos(\theta_i)\right)$ relative to standard amplitude amplification, where $m$ is the number of partitioned registers and $\theta_i$ is the overlap angle between the prepared and target states within each register. For unstructured search of a single target, this overhead converges to 1 for partition sizes $n_i \geq \log_2(\log_2 N)$. As every non-oracle operation acts on at most $n_i$ qubits rather than the full register, the approach yields a significant reduction in the non-oracle circuit depth, making it well suited to practical implementation.
We verify the approach against standard Grover search through circuit simulation: on a $16$-qubit space with partition size $n_i = 4$, the non-oracle circuit depth is $34\times$ for a fully connected device ($48\times$ on heavy-hex) smaller at $45\%$ more oracle calls; at $n_i = 8$, the reduction is $10\times$ ($13\times$) at only $5\%$ additional oracle calls. More broadly, we demonstrate that the quadratic speedup of quantum search can be preserved even when the operators applied between successive oracle calls are extremely sparse and act on only a few qubits at a time. This flexibility enables the algorithm to be tailored to the connectivity constraints of the underlying hardware, and offers new perspective on the role of the diffusion operator in achieving the quantum search speedup.
Link to the paper:
