  Phase estimation, due to Kitaev [arXiv'95], 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 will be the number of applications of $U$ and $U^{-1}$.
  We tightly characterize the cost of several variants of phase estimation
where we are no longer given an arbitrary eigenstate, but are required to
estimate the maximum eigenphase of $U$, aided by advice in the form of states
(or a unitary preparing those states) which are promised to have at least a
certain overlap $\gamma$ with the top eigenspace.
  We give algorithms and matching lower bounds (up to logarithmic factors) for
all ranges of parameters.
  We show that a small number of copies of the advice state (or of an
advice-preparing unitary) are not significantly better than having no advice at
all. We also show that having lots of advice (applications of the
advice-preparing unitary) does not significantly reduce cost, and neither does
knowledge of the eigenbasis of $U$. As an immediate consequence we obtain a
lower bound on the complexity of the Unitary recurrence time problem, matching
an upper bound of She and Yuen~[ITCS'23] and resolving one of their open
questions.
  Lastly, we show that a phase-estimation algorithm with precision $\delta$ and
error probability $\epsilon$ has cost
$\Omega\left(\frac{1}{\delta}\log\frac{1}{\epsilon}\right)$, matching an easy
upper bound. This contrasts with some other scenarios in quantum computing
(e.g., search) where error-reduction costs only a factor
$O(\sqrt{\log(1/\epsilon)})$. Our lower bound technique uses a variant of the
polynomial method with trigonometric polynomials.
