Meta-Grover Algorithm: Recursive Oracle Reduction and Convergence to Constant Query Complexity
We present a recursive construction based on the observation that the oracle in Grover's algorithm is itself defined by a decision problem. The oracle must "know" how to decide membership, and this knowledge constitutes a searchable description. By applying Grover's algorithm to search for the oracle's description, and recursively applying this construction, we obtain a hierarchy of meta-algorithms. We show that the query complexity at level $k$ is $O(N^{1/2^{k+1}})$, which converges to $O(1)$ as $k \to \infty$.
Authors
- Kaoru Aguilera Katayama
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-01-22
- DOI
- https://doi.org/10.5281/zenodo.18333426
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- article
- Field-Weighted Citation Impact
- 0.00