Hmmm... I may be wrong about this but when you run the QPE on some state $|\psi\rangle$ by simulating some Hamiltonian $H$, your precision is limited at least by:

- The error in the simulation of $U=\exp(-iHt)$ (and if you're using the product formula the limitations of your Trotter factor);
- The precision you decide to choose for the phase estimation with the (inverse) Fourier transform (which is limited by the No-Fast Forwarding Theorem); and
- The number of times you have to sample from the QPE using multiple copies of $|\psi\rangle$.

You can increase the precision with the first factor by using a larger Trotter factor or using more sophisticated Hamiltonian simulation (that I don't know muhc about), and you can increase the precision of the second by adding an additional qubit of precision at the cost of running your simulation for twice as long:

[![Phase Estimation from Wikipedia][1]][1]

As for the third factor, if we are *promised* that $|\psi\rangle$ is an eigenstate then we only need to run the circuit once.  If $|\psi\rangle$ is promised to be in a superposition of two or more eigenstates and we don't know how much each eigenstate contributes to $|\psi\rangle$ I think you're right that statistics tells us the number of times we need to call the QPE grows quadratically.

But I think it's somewhat similar to a classical test. If we are given a signal that we are *promised* is a pure tone, and we have magical box that will let us sample from the signal to return its frequency, it only takes one sample for us to know what the tone is.  If we are given a signal that's a sum of two or more tones and we don't know the weight of each pure tone with respect to our signal, then I'm still pretty sure we'd have to classically run our magic box for a quadratic number of times...?

  [1]: https://i.sstatic.net/bZ6fnbhU.png