Krylov Polynomials and Quantum Query Complexity
Adhikari, Kiran · arXiv (Cornell University) · 2025
We show that the minimal query complexity for preparing $f(H)\ket{ψ_0}$ is exactly the optimal polynomial approximation degree of $f$ in $L^2(μ)$, where $μ$ is the spectral measure of $(H,\ket{ψ_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.