  We obtain a query lower bound for quantum algorithms solving the phase
estimation problem. Our analysis generalizes existing lower bound approaches to
the case where the oracle Q is given by controlled powers Q^p of Q, as it is
for example in Shor's order finding algorithm. In this setting we will prove a
log (1/epsilon) lower bound for the number of applications of Q^p1, Q^p2, ...
This bound is tight due to a matching upper bound. We obtain the lower bound
using a new technique based on frequency analysis.
