On the encoding complexity of quantum numerical integration: an angle-structure characterization

Abstract

We study numerical integration on $[0,1]$ by quantum amplitude estimation (QAE), with emphasis on the cost of constructing the amplitude oracle. We introduce a hierarchy of grid functions ${\mathcal{G}}_n^{(d)}$ whose angle map $\hat{I}{˜}_g:\{0,1{\}}^n\to [0,\ddot{I}€]$ is multilinear of degree at most $d$. Membership is classically checkable in $O(n{2}^n)$ time by the Walsh--Hadamard transform, and each $g\in {\mathcal{G}}_n^{(d)}$ admits a canonical encoding circuit with ${\sum }_{k=0}^d\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ multi-controlled $R_Y$ gates. Combining this circuit bound with classical discretisation estimates, we obtain a depth-versus-accuracy trade-off: for $g\in C^{\hat{I}}\pm [0,1]$, total gate count $O((\log (1/\epsilon ){)}^d{\epsilon }^{-1})$ suffices for $\epsilon$-accuracy with constant probability; in the affine case $d=1$ this is $O({\epsilon }^{-1}\log (1/\epsilon ))$ at fixed discretisation. We also show that encoding degree and Sobolev smoothness are independent: for every $s\in (0,1/2)$, ${\mathcal{G}}_n^{(1)}$ contains restrictions of functions in $W^{s^{\prime },2}(0,1)$ for all $s^{\prime }<s$ but not in $W^{s,2}(0,1)$. Experiments on the SpinQ Triangulum (NMR) and IBM Kingston (superconducting) processors at $n=2$ validate the predicted hierarchy: affine encodings run reliably on both platforms, while quadratic encodings exceed the Triangulum coherence budget but execute on Kingston.

Section 6 (quantum-classical separation) is withdrawn. Lemma 6.1 extended the deterministic rate N^{-s} on the unit ball of W^{s,2}(0,1) to randomized algorithms, whose correct rate is N^{-s-1/2}; Theorem 6.3 rested on it. The construction survives in Sec. 5 as a decoupling of angle-map degree from Sobolev regularity, proof corrected (s<1/2). Midpoint estimate now N^{-s'}. Title amended