On the complexity of quantum numerical integration: an angle-structure characterization
F. Chinesta, A. Falcó, D. Falcó–Pomares · 2026
Read On the complexity of quantum numerical integration: an angle-structure characterization by F. Chinesta, A. Falcó, D. Falcó–Pomares (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-24289.txt.
Introduction
Chinesta, Falco, and Falco-Pomares study unit-range integration by quantum amplitude estimation, focusing on oracle cost. They define functions with bounded angle maps, checkable in fast-growing time with a Walsh-Hadamard transform. Each function has an encoding circuit with multi-gated turns. Circuit bounds plus errors give a depth-accuracy trade-off for smooth functions. Encoding degree and Sobolev smoothness stand apart, and tests on Triangulum and Kingston confirm the pattern. Affine codes run on both, while square codes exceed Triangulum time limit but run on Kingston.
Catalog record
| CREATOR | F. Chinesta, A. Falcó, D. Falcó–Pomares |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110035 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.24289
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the complexity of quantum numerical integration: an angle-structure characterization F. Chinesta, A. Falcó, D. Falcó–Pomares Abstract We study numerical integration on [ 0 , 1 ] [0,1] by quantum amplitude estimation (QAE), with emphasis on the cost of constructing the amplitude oracle. While QAE improves the statistical component of the integration error, this advantage survives only when the integrand admits low encoding complexity. We introduce a hierarchy of function classes 𝒢 n ( d ) \mathcal{G}_{n}^{(d)} on the n n -qubit grid, defined by requiring the angle map Θ g : { 0 , 1 } n → [ 0 , π ] \Theta_{g}:\{0,1\}^{n}\to[0,\pi] to be multilinear of degree at most d d . Membership is classically checkable in O ( n 2 n ) O(n2^{n}) time via the Walsh–Hadamard transform (WHT). For g ∈ 𝒢 n ( d ) g\in\mathcal{G}_{n}^{(d)} , the encoding operator factorises into ∑ k = 0 d ( n k ) \sum_{k=0}^{d}\binom{n}{k} multi-controlled R Y R_{Y} gates (an upper bound on gate complexity, tight at d = n d=n ), interpolating between the affine regime O ( n ) O(n) and the generic exponential regime. Combining this with classical discretisation estimates for g ∈ C α [ 0 , 1 ] g\in C^{\alpha}[0,1] , we derive a depth-versus-accuracy trade-off: total gate count O ( ( log ( 1 / ε ) ) d ⋅ ε − 1 ) O((\log(1/\varepsilon))^{d}\cdot\varepsilon^{-1}) suffices to achieve ε \varepsilon -accuracy with constant probability. For d = 1 d=1 this gives O ( ε − 1 log ( 1 / ε ) ) O(\varepsilon^{-1}\log(1/\varepsilon)) , improving on classical Monte Carlo for every α ≥ 1 \alpha\geq 1 . We further prove an unconditional separation: the class 𝒢 n ( 1 ) \mathcal{G}_{n}^{(1)} contains functions of Sobolev regularity s < 1 / 2 s<1/2 for which the quantum oracle cost is O ( 1 / ε ) O(1/\varepsilon) , whereas every classical deterministic or randomised quadrature requires Ω ( ε − 1 / s ) \Omega(\varepsilon^{-1/s}) evaluations. These results identify a mathematically explicit class of integrands for which the full cost of QAE-based integration, including state preparation, is asymptotically superior to classical methods. Hardware experiments on the SpinQ Triangulum (NMR) and IBM Kingston (superconducting) processors illustrate the hierarchy at n = 2 n=2 : circuits in 𝒢 n ( d ) \mathcal{G}_{n}^{(d)} execute successfully, while those exceeding the Triangulum coherence budget fail as predicted. Keywords. quantum amplitude estimation; numerical integration; encoding complexity; Walsh–Hadamard transform; Sobolev regularity; encoding-circuit complexity; angle-structure hierarchy Mathematics Subject Classification (2020). 65D30, 65Y20, 68Q12, 81P68, 41A25, 42C10, 46E35 1 Introduction The complexity of numerical integration is classically governed by the interplay between regularity and sampling cost. For g\in C^{\alpha}[0,1] , an N -point quadrature rule of order p\leq\alpha satisfies |I-Q_{N}^{(p)}[g]|=\mathcal{O}(N^{-p}) [ 8 ] , while Monte Carlo estimation contributes an additional statistical error of order \mathcal{O}(M^{-1/2}) using M random samples. The total cost of achieving \varepsilon -accuracy therefore reflects two distinct mechanisms: a discretisation error controlled by the smoothness of the integrand, and a statistical error controlled by the number of function evaluations. Quantum Amplitude Estimation (QAE) [ 3 ] improves the statistical component of this balance by replacing the classical Monte Carlo rate \mathcal{O}(M^{-1/2}) with the quantum rate \mathcal{O}(M^{-1}) after M oracle calls. This observation has motivated a growing literature on quantum numerical integration [ 1 , 19 ] and quantum finance [ 31 , 27 , 9 ] . From the perspective of numerical analysis, however, the relevant question is not whether QAE improves sampling complexity in isolation, but whether this improvement survives once the cost of constructing the amplitude oracle is incorporated into the overall complexity of the method. This issue is decisive. The quantum advantage applies to the estimation stage, not automatically to the encoding stage. If the circuit that loads g into amplitudes has depth D , then the cost of one QAE run is D+\mathcal{O}(k) , where k is the amplification level. For sufficiently large k , the gain in the estimation stage may dominate; but if D grows exponentially with the number of qubits n , then the overall advantage is lost. Indeed, preparing a generic n -qubit state requires \Theta(2^{n}) gates [ 23 , 2 ] . The work of Carrera Vazquez & Woerner [ 6 ] identified practically relevant function classes admitting efficient encodings and showed how a Spin-Echo optimisation reduces the depth of repeated amplitude amplification. What remained open is the structural question that is central for the complexity of quantum numerical integration: which integrands admit low-complexity encodings, and how can they be characterised mathematically? The state-preparation bottleneck is therefore not merely a technical detail; it is a structural component of the complexity of the full numerical method. A recent survey of quantum alternatives to classical Monte Carlo [ 18 ] identifies three principal obstacles in practical QAE implementations: the construction of the amplitude oracle, the depth of the QAE circuit, and the complexity of state preparation. It also notes explicitly that the Grover–Rudolph procedure [ 13 ] may eliminate the quadratic speedup entirely for log-concave distributions [ 14 ] . At the same time, the survey establishes, through a systematic complexity comparison for Hölder and Sobolev classes, that quantum query complexity is asymptotically better than the classical randomised bound across all regularity regimes, provided that the state-preparation cost is negligible. The present paper continues the programme initiated by Novak [ 20 ] , Heinrich [ 16 ] , and Heinrich & Novak [ 17 ] of characterising the quantum complexity of numerical integration in Sobolev classes, by addressing the structural question of which integrands admit low-cost amplitude encodings. Rather than treating state preparation as a black box, we characterise, through the angle-structure hierarchy \{\mathcal{G}_{n}^{(d)}\} , the subclass of integrands for which the encoding operator remains sufficiently simple for the improved asymptotic complexity of QAE to be retained at the level of the full integration procedure. The distinction from earlier work is precise. Carrera Vazquez & Woerner [ 6 ] identified a practically relevant subclass of functions admitting low-depth encodings via a Spin-Echo optimisation, and demonstrated reduced circuit depth for repeated amplitude amplification; their analysis, however, takes the encoding cost as given and does not provide a mathematical characterisation of which integrands admit such encodings or why. Suzuki et al. [ 28 ] established the statistical convergence properties of the MLAE estimator without addressing the encoding cost at all. Heinrich [ 15 ] studied the quantum query complexity of summation and integration in L_{p}([0,1]^{d}) within the information-based complexity framework, establishing optimal convergence rates in the oracle model; in that setting the amplitude oracle is treated as a black box whose construction cost is not charged. The present paper operates in a complementary regime: we charge the circuit cost of building the oracle and ask which structural property of the integrand determines that cost. The answer — the multilinear degree of the angle map — is an invariant that has no counterpart in the oracle model, and it is this invariant that underlies both the encoding-complexity theorem and the unconditional quantum-classical separation proved here. Our starting point is the