Tight Bounds for Quantum Phase Estimation and Related Problems

Quantum 10, 2140 (2026). https://doi.org/10.22331/q-2026-06-15-2140 Phase estimation, due to Kitaev [ 17 ], is one of the most fundamental subroutines in quantum computing. In the basic scenario, one is given black-box access to a unitary $U$, and an eigenstate $\lvert \psi \rangle$ of $U$ with unknown eigenvalue $e^{i\theta}$, and the task is to estimate the eigenphase $\theta$ within $\pm\delta$, with high probability. The cost of an algorithm for us is the number of applications of $U$ and $U