Abstract
We study numerical integration on [0,1] by quantum amplitude estimation (QAE), focusing on the cost of constructing the amplitude oracle. Although QAE improves the statistical component of the integration error, this advantage is relevant only when the integrand has low encoding complexity. We introduce a hierarchy of grid function classes G_n^(d), defined by requiring the angle map Θ_g:{0,1}ⁿ→[0,π] to be multilinear of degree at most d. Membership is classically checkable in O(n2ⁿ) time by the Walsh--Hadamard transform. For g∈G_n^(d), the encoding operator factorises into Σ_k=0^dnk multi-controlled R_Y gates, interpolating between an affine O(n) regime and the generic exponential regime. Combining this structure with classical discretisation estimates for g∈ C^α[0,1], we obtain a depth-versus-accuracy trade-off: gate count O((log(1/ε))^dε⁻¹) suffices to achieve ε-accuracy with constant probability. For d=1 this becomes O(ε⁻¹log(1/ε)), improving over classical Monte Carlo for every α≥1. We also prove an unconditional separation: G_n⁽¹⁾ contains functions of Sobolev regularity s<1/2 for which the quantum oracle cost is O(1/ε), whereas classical deterministic or randomised quadrature requires Ω(ε^-1/s) evaluations. These results identify explicit integrand classes for which the full cost of QAE-based integration, including state preparation, is asymptotically better than classical methods. Experiments on SpinQ Triangulum and IBM Kingston illustrate the hierarchy at n=2: circuits inside G_n^(d) run successfully, while those exceeding the Triangulum coherence budget fail as predicted.