Krylov polynomials and quantum query complexity

We show that the query complexity of preparing f ( H )| ψ 0 ⟩ is controlled by the optimal L 2 ( μ ) polynomial approximation degree of f , where μ is the spectral measure induced by ( H , | ψ 0 ⟩). Equivalently, the minimal number of queries is bounded below by the smallest Krylov–Favard truncation achieving error ε and bounded above, up to QSVT normalization overhead, by a linear function of that degree. This state-aware formulation sharpens worst-case bounds, unifies orthogonal-polynomial Krylov methods with quantum query complexity, and highlights how input-dependent spectral structure can yield substantial savings over uniform approximation schemes.