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 $\Theta_g:\{0,1\}^n\to[0,\pi]$ is multilinear of degree at most $d$. Membership is classically checkable in $O(n2^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\binom{n}{k}$ 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^\alpha[0,1]$, total gate count $O((\log(1/\varepsilon))^d\varepsilon^{-1})$ suffices for $\varepsilon$-accuracy with constant probability; in the affine case $d=1$ this is $O(\varepsilon^{-1}\log(1/\varepsilon))$ 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',2}(0,1)$ for all $s'<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

Quantum Physics (quant-ph); Numerical Analysis (math.NA)

arXiv:2604.24289 [quant-ph]

(or arXiv:2604.24289v2 [quant-ph] for this version)