arxiv: 2604.24289 · v1 · submitted 2026-04-27 · 🪐 quant-ph · cs.NA· math.NA

Recognition: unknown

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

Francisco Chinesta , Antonio Falco , Daniela Falco-Pomares

Authors on Pith no claims yet

Pith reviewed 2026-05-08 04:00 UTC · model grok-4.3

classification 🪐 quant-ph cs.NAmath.NA

keywords quantum amplitude estimationnumerical integrationangle mapmultilinear functionsstate preparationgate complexitySobolev regularityquantum oracle cost

0 comments

The pith

Integrands with multilinear angle maps of degree at most d allow full quantum amplitude estimation to reach ε accuracy in O((log(1/ε))^d ε^{-1}) gates.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a hierarchy of grid functions G_n^{(d)} whose angle maps from the binary grid to [0,π] are multilinear of degree at most d. For members of these classes the amplitude-encoding operator factors into a sum of at most sum_{k=0}^d binom(n,k) multi-controlled R_Y rotations, yielding total gate counts O((log(1/ε))^d ε^{-1}) when combined with standard discretization bounds. In the linear case d=1 this produces an unconditional separation: certain Sobolev functions with regularity s<1/2 lie in G_n^{(1)} and admit quantum cost O(1/ε), while classical deterministic or randomized quadrature requires Ω(ε^{-1/s}) samples. Membership in each class is decidable classically by Walsh-Hadamard transform in O(n 2^n) time. The construction therefore supplies explicit integrand families for which the complete cost of QAE-based integration, including state preparation, is asymptotically superior to classical methods.

Core claim

We introduce a hierarchy of grid function classes G_n^{(d)}, defined by requiring the angle map Θ_g : {0,1}^n → [0,π] to be multilinear of degree at most d. Membership is classically checkable in O(n 2^n) time by the Walsh-Hadamard transform. For g in G_n^{(d)} the encoding operator factorises into sum_{k=0}^d binom(n,k) 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 in C^α[0,1] produces gate count O((log(1/ε))^d ε^{-1}) for ε-accuracy with constant probability. For d=1 this becomes O(ε^{-1} log(1/ε)), improving over classical Monte Carlo for every α≥1. We also

What carries the argument

The multilinear angle map Θ_g of degree ≤ d, which permits the encoding unitary to factor as a linear combination of at most sum binom(n,k) multi-controlled R_Y rotations for k≤d.

If this is right

For d=1 the total quantum cost is O(ε^{-1} log(1/ε)), which improves over classical Monte Carlo whenever the integrand has Sobolev regularity α≥1.
G_n^{(1)} contains functions of Sobolev regularity s<1/2 for which quantum oracle cost is O(1/ε) while classical deterministic or randomised quadrature requires Ω(ε^{-1/s}) evaluations.
The required gate count scales with the binomial sum up to d, giving a continuous interpolation between linear and exponential encoding complexity.
Class membership can be verified in O(n 2^n) time by a Walsh-Hadamard transform before any quantum circuit is built.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same angle-map classification may be usable to simplify state preparation in other quantum algorithms that rely on oracles for smooth functions.
Small-n hardware runs already show that circuits inside G_n^{(d)} complete within coherence limits while those outside the class fail, suggesting the hierarchy is practically relevant for near-term devices.
Extending the multilinear condition to higher-dimensional or non-uniform grids could enlarge the set of integration problems that inherit the quantum advantage.
The classical verification cost O(n 2^n) can be viewed as a one-time preprocessing step that unlocks repeated quantum speedups for the same function class.

Load-bearing premise

The integrand must belong to one of the G_n^{(d)} classes defined by its angle map being multilinear of degree at most d.

What would settle it

Exhibit a function g in G_n^{(1)} with Sobolev regularity s<1/2 for which either the quantum circuit depth needed for ε-accuracy exceeds O(1/ε) or classical quadrature achieves the same accuracy with o(ε^{-1/s}) point evaluations.

Figures

Figures reproduced from arXiv: 2604.24289 by Antonio Falco, Daniela Falco-Pomares, Francisco Chinesta.

**Figure 1.** Figure 1: Depth-accuracy trade-off: total gate count (quantum) or evaluation count (clas view at source ↗

**Figure 2.** Figure 2: Quantum-classical separation for the family view at source ↗

**Figure 3.** Figure 3: Amplitude-encoding circuits Gg for n = 2 qubits, k = 0. (a) g1|X2 ∈ G(1) 2 (d = 1, 3 gates, (57)): one unconditional rotation RY (Θˆ ∅) on the ancilla q2, one Cq0 -RY (Θˆ {0}), and one Cq1 -RY (Θˆ {1}). Circuit depth ≤ 4 layers. (b) g2|X2 ∈ G(2) 2 \ G(1) 2 (d = 2, 4 gates, (58)): the d = 1 part (left brace) is followed by the degree-2 correction C {0,1}RY (Θˆ {0,1}) (orange brace), decomposed into 2 CNOTs … view at source ↗

read the original 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 $\mathcal{G}_n^{(d)}$, defined by requiring the angle map $\Theta_g:\{0,1\}^n\to[0,\pi]$ to be multilinear of degree at most $d$. Membership is classically checkable in $O(n2^n)$ time by the Walsh--Hadamard transform. For $g\in\mathcal{G}_n^{(d)}$, the encoding operator factorises into $\sum_{k=0}^d\binom{n}{k}$ 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\in C^\alpha[0,1]$, we obtain a depth-versus-accuracy trade-off: gate count $O((\log(1/\varepsilon))^d\varepsilon^{-1})$ suffices to achieve $\varepsilon$-accuracy with constant probability. For $d=1$ this becomes $O(\varepsilon^{-1}\log(1/\varepsilon))$, improving over classical Monte Carlo for every $\alpha\ge1$. We also prove an unconditional separation: $\mathcal{G}_n^{(1)}$ contains functions of Sobolev regularity $s<1/2$ for which the quantum oracle cost is $O(1/\varepsilon)$, whereas classical deterministic or randomised quadrature requires $\Omega(\varepsilon^{-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 $\mathcal{G}_n^{(d)}$ run successfully, while those exceeding the Triangulum coherence budget fail as predicted.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines explicit grid-function classes based on low-degree multilinear angle maps that let the QAE oracle be built with few multi-controlled gates, yielding full-cost separations against classical quadrature for certain low-regularity cases.

read the letter

The main point is that this work pins down concrete classes of integrands where the quantum amplitude estimation oracle can be built with polynomially many gates in n, leading to an overall quantum cost that scales better than classical methods even when you include state preparation. They define G_n^{(d)} by the angle map being multilinear of degree at most d. This lets the encoding operator decompose into a sum of binom(n,k) multi-controlled RY gates for k up to d. Combined with standard discretization, they get gate counts O((log 1/ε)^d / ε) for accuracy ε. For d=1 that's O(ε^{-1} log(1/ε)), which improves on Monte Carlo for smooth enough functions, and they show an unconditional separation against classical quadrature for functions with Sobolev regularity below 1/2 that still sit in G_n^{(1)} by construction. The new part is this angle-structure characterization and its direct circuit realization. The proofs seem to follow from the multilinear property and Walsh-Hadamard for checking. The hardware runs at n=2 are a nice touch to show the hierarchy works in practice. The soft spots are minor but worth noting. The membership test is O(n 2^n), so for large grids it's not practical to check if a random function fits, but the separation results use constructed examples so that's not an issue. The experiments are limited to very small n, and the paper doesn't claim the classes cover most interesting integrands. The classical comparison uses deterministic or randomized quadrature, which is fair. This paper is for people working on quantum algorithms for numerical integration who want to move beyond query complexity to full gate counts. It shows clear engagement with the literature on QAE and discretization. The math looks solid with no obvious circularity. I would send it to peer review. The contribution is specific but useful for clarifying when quantum integration can be advantageous in full.

Referee Report

2 major / 3 minor

Summary. The paper introduces a hierarchy of grid function classes G_n^{(d)} defined by the condition that the angle map Θ_g is multilinear of degree at most d, shows that this allows the amplitude encoding oracle to be implemented with O(n^d) multi-controlled R_Y gates, derives a total gate complexity O((log(1/ε))^d ε^{-1}) for ε-accurate integration by combining with classical discretization bounds, proves an unconditional separation showing that G_n^{(1)} contains Sobolev-s<1/2 functions where quantum cost is O(1/ε) versus classical Ω(ε^{-1/s}), and validates the hierarchy on small-scale quantum hardware.

Significance. If the derivations hold, the results identify explicit, checkable integrand classes (via Walsh-Hadamard transform) where the full QAE pipeline including state preparation is asymptotically superior to classical quadrature, with a concrete separation for low-regularity functions. The by-construction examples and hardware experiments at n=2 are strengths that make the contribution concrete and falsifiable.

major comments (2)

[separation result] The separation result (abstract and associated section): the claim that G_n^{(1)} contains functions whose continuous extensions have Sobolev regularity s<1/2 requires an explicit construction of at least one such function together with a direct calculation or bound on its Sobolev norm; without this, the Ω(ε^{-1/s}) classical lower bound cannot be rigorously attached to the quantum O(1/ε) cost.
[complexity trade-off] Trade-off derivation (abstract and complexity section): the combination of the O(1/ε) QAE query complexity with the classical discretization error that forces n = O(log(1/ε)) must include a complete error-propagation argument (including success probability and the precise dependence on the C^α norm) to confirm that the stated O((log(1/ε))^d ε^{-1}) gate count is achieved with constant probability.

minor comments (3)

[introduction] The definition of the angle map Θ_g and the precise meaning of 'multilinear of degree at most d' should be restated in the main text before the complexity claims, rather than only in the abstract.
[experiments] Hardware experiments at n=2: the figure or table should report the exact gate counts, depths, and coherence budgets for the G_n^{(d)} circuits versus the failing ones to make the 'as predicted' statement verifiable.
[oracle construction] Notation consistency: ensure that the binomial sum for the number of multi-controlled gates is written with the same symbols in the text and any displayed equation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and recommendation for minor revision. The two major comments identify places where the manuscript can be strengthened with additional explicit details. We address each point below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [separation result] The separation result (abstract and associated section): the claim that G_n^{(1)} contains functions whose continuous extensions have Sobolev regularity s<1/2 requires an explicit construction of at least one such function together with a direct calculation or bound on its Sobolev norm; without this, the Ω(ε^{-1/s}) classical lower bound cannot be rigorously attached to the quantum O(1/ε) cost.

Authors: We agree that an explicit construction would make the separation more concrete and directly verifiable. In the revised version we will add a specific example of a function g ∈ G_n^{(1)} (with affine angle map) whose continuous extension on [0,1] has Sobolev regularity s < 1/2, together with an explicit upper bound on its Sobolev norm that justifies attaching the classical lower bound Ω(ε^{-1/s}). revision: yes
Referee: [complexity trade-off] Trade-off derivation (abstract and complexity section): the combination of the O(1/ε) QAE query complexity with the classical discretization error that forces n = O(log(1/ε)) must include a complete error-propagation argument (including success probability and the precise dependence on the C^α norm) to confirm that the stated O((log(1/ε))^d ε^{-1}) gate count is achieved with constant probability.

Authors: We thank the referee for this observation. We will expand the complexity section with a complete error-propagation argument that tracks the discretization error for g ∈ C^α[0,1], the resulting choice n = O(log(1/ε)), the dependence on the C^α norm, the success probability of QAE, and the overall gate count, confirming that O((log(1/ε))^d ε^{-1}) gates suffice with constant probability. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper defines the classes G_n^{(d)} independently via the multilinear degree-d condition on the angle map Θ_g (checkable by Walsh-Hadamard transform in O(n 2^n) time). The factorization of the encoding operator into O(n^d) multi-controlled R_Y gates follows directly from the monomial expansion of a degree-d multilinear function, which is an algebraic identity independent of the target complexity bounds. Quantum cost then applies standard QAE query complexity O(1/ε) plus classical discretization to fix n = O(log(1/ε)), yielding the stated gate count. The Sobolev separation is obtained by explicit construction of grid functions inside G_n^{(1)} whose continuous extensions have s < 1/2; membership is by design, not by fitting. No load-bearing step reduces to a fitted parameter, self-citation chain, or redefinition of its own output. The hierarchy and bounds are externally verifiable against standard QAE and Sobolev theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on the definition of the angle map being multilinear of bounded degree and on standard approximation theory for C^α functions; no explicit free parameters are fitted in the abstract, but d is a discrete choice parameterizing the classes.

axioms (2)

domain assumption The angle map Θ_g : {0,1}^n → [0,π] can be checked for multilinearity degree ≤d via Walsh-Hadamard transform in O(n 2^n) time.
Invoked to establish membership in G_n^{(d)}.
standard math Classical discretisation error estimates hold for g ∈ C^α[0,1].
Used to combine with quantum oracle cost to obtain overall ε-accuracy.

invented entities (1)

Grid function class G_n^{(d)} no independent evidence
purpose: To classify integrands whose angle maps have bounded multilinearity degree, enabling factorised quantum encoding.
Newly introduced hierarchy that interpolates between affine and generic cases.

pith-pipeline@v0.9.0 · 5687 in / 1654 out tokens · 31766 ms · 2026-05-08T04:00:56.437906+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

32 extracted references · 12 canonical work pages

[1]

D. S. Abrams and C. P. Williams. Fast quantum algorithms for numerical integrals and stochastic processes.arXiv preprint quant-ph/9908083, 1999

work page arXiv 1999
[2]

Barenco, C

A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter. Elementary gates for quantum compu- tation.Physical Review A, 52(5):3457–3467, 1995

1995
[3]

Brassard, P

G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation.Contemporary Mathematics, 305:53–74, 2002

2002
[4]

Carlet and S

C. Carlet and S. Mesnager. On the supports of the Walsh transforms of Boolean functions.Cryptology ePrint Archive, Paper 2004/256, 2004. https://eprint.iacr.org/2004/256

2004
[5]

Carlet, U

C. Carlet, U. Pastor-Díaz, and J. M. Tornero. On the Walsh and Fourier–Hadamard supports of Boolean functions from a quantum viewpoint. In S. Petkova-Nikova and D. Panario (eds.),Arithmetic of Finite Fields — WAIFI 2024, Lecture Notes in Computer Science, vol. 15176. Springer, Cham, 2025. doi:10.1007/978-3-031-81824- 0_14

work page doi:10.1007/978-3-031-81824- 2024
[6]

Carrera Vazquez and S

A. Carrera Vazquez and S. Woerner. Efficient state preparation for quantum amplitude estimation.Phys. Rev. Applied15(2021), 034027. doi:10.1103/PhysRevApplied.15.034027

work page doi:10.1103/physrevapplied.15.034027 2021
[7]

H. K. Cummins and J. A. Jones. Use of composite rotations to correct system- atic errors in NMR quantum computation.New Journal of Physics2(2000), 6. doi:10.1088/1367-2630/2/1/306

work page doi:10.1088/1367-2630/2/1/306 2000
[8]

P. J. Davis and P. Rabinowitz.Methods of Numerical Integration. Academic Press, 2nd edition, 1984

1984
[9]

D. J. Egger, R. G. Gutiérrez, J. C. Mestre, and S. Woerner. Credit risk analysis using quantum computers.arXiv:1907.03044, 2019. 35

work page arXiv 1907
[10]

Falcó, D

A. Falcó, D. Falcó-Pomares, and H. G. Matthies. A rigorous and self-contained proof of the Grover–Rudolph state preparation algorithm. Preprint submitted toAIMS Mathematics, January 2026.arXiv:2601.17930 [quant-ph]

work page arXiv 2026
[11]

Falcó and H

A. Falcó and H. G. Matthies. Vistas of algebraic probability, quantum computation and information. Preprint,arXiv:2602.04351 [quant-ph], 2026

work page arXiv 2026
[12]

A. Falcó. SpinQit QAE Triangulum.https://github.com/afalco/ spinqit-qae-triangulum, 2025. (Accessed March 2026.)

2025
[13]

L. K. Grover and T. Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. Preprint,arXiv:quant-ph/0208112, 2002

work page Pith review arXiv 2002
[14]

S. Herbert. Quantum Monte Carlo integration: the full advantage in minimal circuit depth.PRX Quantum, 3:020361, 2022

2022
[15]

Heinrich

S. Heinrich. Quantum summation with an application to integration.Journal of Complexity, 18(1):1–50, 2002

2002
[16]

Heinrich

S. Heinrich. Quantum integration in Sobolev classes.Journal of Complexity, 19(1):19–42, 2003

2003
[17]

Heinrich and E

S. Heinrich and E. Novak. On a problem in quantum summation.Journal of Com- plexity, 19(1):1–18, 2003

2003
[18]

Intallura, G

P. Intallura, G. Korpas, S. Chakraborty, V. Kungurtsev, R. Lawrence, A. Wodecki, and J. Marecek. A survey of quantum alternatives to randomized algorithms: Monte Carlo sampling and beyond. Preprint,arXiv:2303.04945v2 [quant-ph], 2026

work page arXiv 2026
[19]

Montanaro

A. Montanaro. Quantum speedup of Monte Carlo methods.Proceedings of the Royal Society A, 471:20150301, 2015

2015
[20]

E. Novak. Quantum complexity of integration.Journal of Complexity, 17(1):2–16, 2001

2001
[21]

Novak and H

E. Novak and H. Woźniakowski.Tractability of Multivariate Problems, vol. 1. Euro- pean Mathematical Society, Zürich, 2008

2008
[22]

O’Donnell.Analysis of Boolean Functions

R. O’Donnell.Analysis of Boolean Functions. Cambridge University Press, 2014

2014
[23]

V. V. Shende, S. S. Bullock, and I. L. Markov. Synthesis of quantum-logic circuits. IEEE Transactions on Computer-Aided Design, 25(6):1000–1010, 2006

2006
[24]

SpinQ Triangulum: a desktop 3-qubit NMR quantum computer.https://www.spinq.cn, 2021

SpinQ Technology Co., Ltd. SpinQ Triangulum: a desktop 3-qubit NMR quantum computer.https://www.spinq.cn, 2021

2021
[25]

SpinQit: quantum software framework

SpinQ Technology Co., Ltd. SpinQit: quantum software framework. https://github.com/SpinQTech/SpinQit, 2022

2022
[26]

IBM Quantum Platform.https://quantum.ibm.com, 2024

IBM Quantum. IBM Quantum Platform.https://quantum.ibm.com, 2024

2024
[27]

Stamatopoulos, D

N. Stamatopoulos, D. J. Egger, Y. Sun, C. Zoufal, R. Iten, N. Shen, and S. Woerner. Option pricing using quantum computers.arXiv:1905.02666, 2019. 36

work page arXiv 1905
[28]

Suzuki, S

Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto. Amplitude estimation without phase estimation.Quantum Information Process- ing19(2020), Article 75. doi:10.1007/s11128-019-2565-2. Preprint available at arXiv:1904.10246 [quant-ph]

work page doi:10.1007/s11128-019-2565-2 2020
[29]

Triebel.Theory of Function Spaces

H. Triebel.Theory of Function Spaces. Birkhäuser, Basel, 1983

1983
[30]

L. M. K. Vandersypen and I. L. Chuang. NMR techniques for quantum control and computation.Reviews of Modern Physics76(2005), 1037–1069. doi:10.1103/RevModPhys.76.1037

work page doi:10.1103/revmodphys.76.1037 2005
[31]

Woerner and D

S. Woerner and D. J. Egger. Quantum risk analysis.npj Quantum Information, 5:15, 2019

2019
[32]

Zygmund.Trigonometric Series, vols

A. Zygmund.Trigonometric Series, vols. I & II, 3rd ed. Cambridge University Press, 2002. 37

2002