Grover’s Model with Single Oracle Call and Log( N ) Different Diffusion Calls

Abstract

The author has recently presented the Single-Iteration Quantum Search Algorithm, which achieves amplitude-amplification with exactly one oracle call and one π/4 rotation [1] . For N = 2 n search spaces, the algorithm achieves success probability exactly 1/2 with one iteration of oracle operator and one π/4 rotation with log( N ) different diffusion calls, compared to O ( N ) iterations ( O ( N ) oracle calls and O ( N ) same diffusion calls) for Grover’s algorithm. This work presents a simpler and cleaner derivation for one oracle call and log( N ) diffusion calls, while the original proof was based on Cartan-Dieudonné theorem [1] . The standard lower bounds for unstructured quantum search still apply even though the number of oracle calls is reduced from O ( N ) to O (1) and the number of diffusion calls is reduced from O ( N ) to O (log N ).