Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
External research report
Data sources: ZENODO
addClaim

Meta-Grover Algorithm: Recursive Oracle Reduction and Convergence to Constant Query Complexity

Authors: Aguilera Katayama, Kaoru;

Meta-Grover Algorithm: Recursive Oracle Reduction and Convergence to Constant Query Complexity

Abstract

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$.

Powered by OpenAIRE graph
Found an issue? Give us feedback