  In this work, we study the phase estimation problem. We show an alternative,
simpler and self-contained proof of query lower bounds. Technically, compared
to the previous proofs [NW99, Bes05], our proof is considerably elementary.
Specifically, our proof consists of basic linear algebra without using the
knowledge of Boolean function analysis and adversary methods. Qualitatively,
our bound is tight in the low success probability regime and offers a more
fine-grained trade-off. In particular, we prove that for any $\epsilon > 0, p
\geq 0$, every algorithm requires at least $\Omega(p/{\epsilon})$ queries to
obtain an ${\epsilon}$-approximation for the phase with probability at least p.
However, the existing bounds hold only when $p > 1/2$. Quantitatively, our
bound is tight since it matches the well-known phase estimation algorithm of
Cleve, Ekert, Macchiavello, and Mosca [CEMM98] which requires $O(1/{\epsilon})$
queries to obtain an ${\epsilon}$-approximation with a constant probability.
Following the derivation of the lower bound in our framework, we give a new and
intuitive interpretation of the phase estimation algorithm of [CEMM98], which
might be of independent interest.
