Krylov Polynomials and Quantum Query Complexity

Abstract

We show that the minimal query complexity for preparing $f(H)|\ddot{I}{ˆ}_0⟩$ is exactly the optimal polynomial approximation degree of $f$ in $L^2(\hat{I}¼)$, where $\hat{I}¼$ is the spectral measure of $(H,|\ddot{I}{ˆ}_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.

9 pages