Exact and Optimal Recursive Quantum Search via Hilbert-Space Decomposition
2026-08-24 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors present a new method for improving quantum search algorithms by breaking down the complex quantum space into smaller parts and building the search process step-by-step from these parts. Their technique simplifies the search dynamics to rotations in two-dimensional planes, which helps avoid errors that usually build up in layered algorithms. This approach achieves precise results and works efficiently for different types of quantum search problems, including unstructured and spatial searches. Their work also offers a fresh way to analyze and use recursion in designing quantum algorithms.
Quantum searchHilbert spaceQuantum algorithmRecursive decompositionOracle complexitySpatial searchQuantum gate countRecursion analysisTwo-dimensional rotation
Authors
John Burke, Ciaran McGoldrick
Abstract
Current approaches to quantum search fail to deeply exploit extant structure in the underlying Hilbert space. Decomposing the search by this structure empowers new strategies and formulations for quantum search and algorithm design. We present a new decomposition technique acting directly on this structure by recursively decomposing the Hilbert space and constructing the search operator from reflections over the resulting partition. When initial and target states factorise over this partition, dynamics reduce to a single rotation in a two-dimensional plane at each level, with angle given by a scalar recurrence. This recurrence avoids error accumulation from separately bounding success probabilities at each level, yielding an exact state description enabling treatment of the recursion as a whole. We obtain the target state deterministically and derive oracle and non-oracle costs independently of the search setting. For unstructured search, our approach attains the simultaneously optimal $Θ(\sqrt{N})$ oracle and non-oracle gate counts. For spatial search on $d$-dimension grids, it recovers the $O(\sqrt{N})$ time for $d\geq3$ and the $O\bigl(\sqrt{N}(\log N)^{3/2}\bigr)$ bound of Aaronson and Ambainis for $d=2$. The exact description of the recursion extends over our decomposition to new subdivision structures and provides a new approach for applying and analysing recursion in quantum algorithm design.