The Exponential Speedup Algorithm: O(logN) Amplitude Amplification via Geometric Series

Grover’s algorithm achieves O( N ) query complexity for unstructured search, a result proven optimal by Zalka for algorithms using a fixed oracle operator. This paper presents the Exponential Speedup Algorithm, a modified amplitude amplification algorithm that escapes Zalka’s optimality bound by using a sequence of iteration-dependent rotation operators U0, U1, ..., UK−1, where each operator implements a different rotation angle that depends explicitly on the iteration number k, rather than repeatedly applying a single fixed operator. The algorithm achieves geometric series convergence in the amplitude ratio, where r(k) = βk for a parameter β > 1, compared to the arithmetic series r(k) ≈ 2k + 1 in standard Grover. This geometric growth reduces the iteration count from O( N ) to O(logN) = O(n), where N = 2n. The mathematical framework for this approach was established in the author’s previous work, which proved that K = O(logN) iterations suffice to amplify the marked state probability from 1/N to ≥1/2. This paper addresses three questions left open in that work, rigorously proving that: 1) Zalka’s O( N ) lower bound applies only to algorithms using fixed operators; 2) the iteration-dependent rotation operators Uk are unitary and physically realizable; and 3) the explicit N × N unitary matrix for Uk can be derived with closed-form expressions for all matrix elements.