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

Abstract

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 U 0 , U 1 , ..., 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 ) ≈ 2 k + 1 in standard Grover. This geometric growth reduces the iteration count from O ( N ) to O (log N ) = O ( n ) , where N = 2 n . The mathematical framework for this approach was established in the author’s previous work, which proved that K = O (log N ) 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 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.