Krylov Polynomials and Quantum Query Complexity

We show that the minimal query complexity for preparing $f(H)\mathrm{\mid }{\psi }_0⟩$ is exactly the optimal polynomial approximation degree of $f$ in $L^2(\mu )$, where $\mu$ is the spectral measure of $(H,\mathrm{\mid }{\psi }_0⟩)$. This state-aware perspective refines the worst-case bounds, unifies Krylov/Favard approximation with quantum queries, and explains how state-dependent spectral structure can yield substantial savings over uniform designs.