TITLE:
The Exponential Speedup Algorithm: O(logN) Amplitude Amplification via Geometric Series
AUTHORS:
Ying Liu
KEYWORDS:
Quantum Computing, Grover’s Algorithm, Amplitude Amplification, Geometric Series, Quantum Circuits, Zalka Optimality Bound, Unitary Matrix
JOURNAL NAME:
Journal of Quantum Information Science,
Vol.16 No.1,
March
19,
2026
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 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.