Papers › Modified Iterative Quantum Amplitude Estimation is Asymptotically Optimal
Modified Iterative Quantum Amplitude Estimation is Asymptotically Optimal
Shion Fukuzawa, Christopher Ho, Sandy Irani, Jasen Zion
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
In this work, we provide the first QFT-free algorithm for Quantum Amplitude Estimation (QAE) that is asymptotically optimal while maintaining the leading numerical performance. QAE algorithms appear as a subroutine in many applications for quantum computers. The optimal query complexity achievable by a quantum algorithm for QAE is O(1/ϵlog1/α) queries, providing a speedup of a factor of 1/ϵ over any other classical algorithm for the same problem. The original algorithm for QAE utilizes the quantum Fourier transform (QFT) which is expected to be a challenge for near-term quantum hardware. To solve this problem, there has been interest in designing a QAE algorithm that avoids using QFT. Recently, the iterative QAE algorithm (IQAE) was introduced by Grinko et al. with a near-optimal O(1/ϵlog(1/α log1/ϵ)) query complexity and small constant factors. In this work, we combine ideas from the preceding line of work to introduce a QFT-free QAE algorithm that achieves a query complexity upper bound of 62/ϵln6/α which matches the optimal O(1/ϵlog1/α) query complexity. We supplement our analysis with numerical experiments comparing our performance with IQAE where we find that our modifications retain the high performance, and in some cases even improve the numerical results.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections