  We develop a phase estimation method with a distinct feature: its maximal
runtime (which determines the circuit depth) is $\delta/\epsilon$, where
$\epsilon$ is the target precision, and the preconstant $\delta$ can be
arbitrarily close to $0$ as the initial state approaches the target eigenstate.
The total cost of the algorithm satisfies the Heisenberg-limited scaling
$\widetilde{\mathcal{O}}(\epsilon^{-1})$. As a result, our algorithm may
significantly reduce the circuit depth for performing phase estimation tasks on
early fault-tolerant quantum computers. The key technique is a simple
subroutine called quantum complex exponential least squares (QCELS). Our
algorithm can be readily applied to reduce the circuit depth for estimating the
ground-state energy of a quantum Hamiltonian, when the overlap between the
initial state and the ground state is large. If this initial overlap is small,
we can combine our method with the Fourier filtering method developed in [Lin,
Tong, PRX Quantum 3, 010318, 2022], and the resulting algorithm provably
reduces the circuit depth in the presence of a large relative overlap compared
to $\epsilon$. The relative overlap condition is similar to a spectral gap
assumption, but it is aware of the information in the initial state and is
therefore applicable to certain Hamiltonians with small spectral gaps. We
observe that the circuit depth can be reduced by around two orders of magnitude
in numerical experiments under various settings.
