← Back to papers
Krylov Polynomials and Quantum Query Complexity
Kiran Adhikari·October 13, 2025
Quantum Physicshep-th
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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.