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

Grover’s algorithm achieves O($\sqrt{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 U₀, U₁, ..., U_K？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($\sqrt{N}$ ) to O(logN) = O(n), where N = 2ⁿ. 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($\sqrt{N}$ ) lower bound applies only to algorithms using fixed operators; 2) the iteration-dependent rotation operators U_k are unitary and physically realizable; and 3) the explicit N × N unitary matrix for U_k can be derived with closed-form expressions for all matrix elements.