Optimal Coherent Quantum Phase Estimation via Tapering

Quantum phase estimation is one of the fundamental primitives that underpins many quantum algorithms, including quantum amplitude estimation, the HHL algorithm for solving linear systems of equations, and quantum principal component analysis. Due to its significance as a subroutine, in this work, we study the coherent version of the phase estimation problem, where given an arbitrary input state and black-box access to unitaries U and controlled-U, the goal is to estimate the phases of U in superposition. Unlike most existing phase estimation algorithms, which employ intermediary measurements steps that inevitably destroy coherence, only a couple of algorithms, including the well-known standard quantum phase estimation algorithm, consider this coherent setting. In this work, we propose an improved version of this standard algorithm that utilizes tapering/window functions. Our algorithm, which we call tapered quantum phase estimation algorithm, achieves the optimal query complexity (total number of calls to U and controlled-U) without requiring the use of a computationally expensive quantum sorting network for median computation, which the standard algorithm uses to boost the success probability arbitrarily close to one. We also show that the tapering functions that we use are optimal by formulating optimization problems with different optimization criteria. Beyond the asymptotic regime, we also provide non-asymptotic query complexity of our algorithm, as it is crucial for practical implementation. Finally, we also propose an efficient algorithm that prepares the quantum state corresponding to the optimal tapering function.