Optimal Coherent Quantum Phase Estimation via Tapering

Due to its significance as a subroutine, in this work, we consider the coherent version of the quantum 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. Most existing phase estimation algorithms involve intermediary measurements that disrupt coherence. Only a couple of algorithms, including the standard quantum phase estimation algorithm, consider this coherent setting. However, the standard algorithm only succeeds with a constant probability. To boost this success probability, one can employ the coherent median technique, resulting in an algorithm with asymptotically optimal query complexity (the total number of calls to $U$ and controlled-$U$). However, this coherent median technique requires a large number of ancilla qubits and a computationally expensive quantum sorting network. To address this, in this work, we propose an improved version of the standard algorithm called the tapered quantum phase estimation (tQPE) algorithm, which leverages tapering (or window) functions commonly used in classical signal processing. Our algorithm achieves the asymptotically optimal query complexity without requiring the expensive coherent median technique to boost success probability. Moreover, we find the absolutely optimal taper - not only in the asymptotic scaling but in terms of exact performance. We provide an efficiently preparable ancilla state based on an approximation of the optimal taper, which incurs at most a factor-of-two increase in the probability of error, thereby maintaining near-optimal performance in practice. In the appendices, we give an explicit construction of the taper state preparation circuit. Finally, we derive an error bound for coherent QPE when the phase estimate is used as a control and subsequently uncomputed.