We can concisely summarise the quantum phase estimation (QPE) algorithm as follows:
Generate the state $\sum_{k=0}^{2^n-1} \lambda^k |k\rangle$ efficiently using a series of controlled-unitary operations. Here $\lambda\equiv e^{2\pi i\phi}$, and $\phi\in\mathbb{R}$ is the phase we want to estimate.
Apply $\mathrm{QFT}_n^{-1}$ and do a projective measurement in the computational basis. Equivalently, we can say we're "Fourier sampling", that is, performing a projective measurement in the orthonormal basis $\{|u_k\rangle\}_{k=0}^{N-1}$ where $|u_k\rangle\equiv\sum_j \omega_N^{jk} |j\rangle$, $N\equiv 2^n$, $\omega_N\equiv e^{2\pi i/N}$.
In other words, neglecting all the aspects about implementing these operations in a circuit using few layers, we're using the fact that measuring in the basis $\{|u_k\rangle\}$ allows to efficiently retrieve $\phi$ from a states of the form $\sum_k e^{2\pi ik\phi}|k\rangle$.
On the face of it, this is hardly surprising: after all, the inverse QFT applied to $\sum_k e^{2\pi i kj/N}|k\rangle$ gives $|j\rangle$ for all $j\in\mathbb{N}$, and thus it stands to reason that even if $\phi\neq j/N$, we get a decently good approximation to $\phi$ if $N$ is large enough.
Nevertheless, the question remains: is there a rigorous way to make statements about the QFT being optimal to retrieve $\phi$ in this context? Putting aside issues of implementation efficiency, is there possibly another choice of unitary that can replace the QFT and make for an even better estimation? Or is there a way to argue that this is not/should not be the case?
