Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.24289

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

Francisco Chinesta, Antonio Falco, Daniela Falco-Pomares

quant-phmath.NASubmitted Apr 27, 2026• Announced Apr 28, 2026• 0 citations
v1 · Apr 27, 2026v2 · Jul 27, 2026
arXivHTMLPDF

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 $Θ_g:\{0,1\}^n\to[0,π]$ 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^α[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 $α\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 $Ω(\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.

Related papers

A Rigorous and Self--Contained Proof of the Grover--Rudolph State Preparation Algorithm

Antonio Falco, Daniela Falco-Pomares, Hermann G. Matthies

We give a rigorous and self-contained analysis of the Grover--Rudolph quantum state-preparation algorithm, which encodes a probability distribution $\{p_k\}$ as an $n$-qubit amplitude state $\sum_k\sqrt{p_k}\ket{k}$ via a hierarchy of controlled $\RY$ rotations determined by a dyadic refinement of the target. We formalize the dyadic probability tree, derive the trigonometric factorization of conditional masses, and prove by induction that the circuit prepares exactly the desired measurement law. We further prove that perturbing each rotation angle by at most $η$ changes the output distribution by at most $\min(1,nη)$ in total variation, and combine this with a Hoeffding concentration bound to obtain an explicit design rule: $b\ge\log_2(2nπ/\varepsilon)$ bits and $S\ge 2^{n+1}\log(2/δ)/\varepsilon^2$ shots suffice to achieve accuracy $\varepsilon$ with confidence $1-δ$. As a circuit-theoretic complement, we provide an ancilla-free transpilation of each stage into $\{\RY(\cdot),X,\CNOT\}$ via Gray-code ladders and a Walsh--Hadamard angle transform.

quant-pharXiv:2601.17930•Jan 27, 2026•0 citations

Comparative study of amplitude versus angle encoding in gate-based quantum machine learning

Shashank Kumar, Ashok Kumar

We investigate two fundamental data encoding strategies for gate-based quantum computers: amplitude encoding and angle encoding. In amplitude encoding, a normalized -dimensional classical vector is mapped into the probability amplitudes of a -qubit quantum state, whereas angle encoding uses one or more single-qubit rotation gates per feature to encode data as angles.[1, 2] We construct a toy binary classification dataset with four real-valued features and compare these encoding schemes using a variational quantum classifier (VQC) approach. Our results indicate that angle encoding often yields slightly higher classification accuracy (e.g. 82% vs. 75% in one experiment) at the cost of requiring more qubits, while amplitude encoding compresses features into fewer qubits (2 vs. 4) but demands deeper state-preparation circuits. These findings align with previous studies that report higher accuracy for rotation encodings (e.g. vs. in MNIST experiments [3]) and note that the encoding choice acts as a hyperparameter affecting VQC performance. [4]

International Journal of Physics and Mathematics•Jul 1, 2025•2 citations

Nearly Optimal Amplitude Estimation at any Depth

Jona Erle, Bálint Koczor

We develop a class of amplitude estimation algorithms with tunable circuit depth $M$ and circuit repetitions $N$, requiring neither ancilla qubits nor controlled Grover operations. For additive error $ε$ in the Grover angle, they attain the nearly optimal query-depth tradeoff $M^2N\in\widetilde{O}(ε^{-2})$ uniformly over $λ\in[0,π/2]$, spanning the full range from classical sampling at $M=1$ to the Heisenberg limit at $M=Θ(ε^{-1})$. While prior depth-tunable work establishes comparable angle-accuracy guarantees only away from the boundaries $λ\to0$ or $π/2$ or at discrete depth tradeoffs, our guarantee extends to both boundaries, so the quantum speedup persists there rather than degrading to classical sampling. Numerical experiments confirm the predicted uniform angle accuracy and show low overhead in practice, making them strong candidates for practical amplitude estimation in the early fault-tolerant regime, with applications such as overlap certification, trial-state verification, and Monte Carlo methods.

quant-pharXiv:2608.24434•Aug 26, 2026•0 citations

Depth-Optimal Quantum Compilation

Francisca Vasconcelos

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

quant-pharXiv:2609.34659•Sep 29, 2026•0 citations

A rigorous and self-contained proof of the Grover-Rudolph state preparation algorithm

Antonio Falcó, Departamento de Matemáticas, Física y Ciencias Tecnológicas, Universidad Cardenal Herrera-CEU, CEU Universities San Bartolomé 55, 46115 Alfara del Patriarca (Valencia), Spain, Daniela Falco-Pomares +2 more

We give a rigorous and self-contained analysis of the Grover-Rudolph quantum state-preparation algorithm, which encodes a probability distribution $ \{p_k\} $ as an $ n $-qubit amplitude state $ \sum_k\sqrt{p_k}|k\rangle $ via a hierarchy of controlled $ \mathrm{R}_y $ rotations determined by a dyadic refinement of the target. We formalize the dyadic probability tree, derive the trigonometric factorization of conditional masses, and prove by induction that the circuit prepares exactly the desired measurement law. We further prove that perturbing each rotation angle by at most $ \eta $ changes the output distribution by at most $ \min(1, n\eta) $ in total variation, and combine this with a Hoeffding concentration bound to obtain an explicit design rule: $ b\ge\log_2(2n\pi/\varepsilon) $ bits and $ S\ge 2^{n+1}\log(2/\delta)/\varepsilon^2 $ shots suffice to achieve accuracy $ \varepsilon $ with confidence $ 1-\delta $. As a circuit-theoretic complement, we provide an ancilla-free transpilation of each stage into $ \{ \mathrm{R}_y(\cdot), X, \mathrm{CNOT}\} $ via Gray-code ladders and a Walsh-Hadamard angle transform.

AIMS Mathematics•Jan 1, 2026•1 citation

Quantum amplitude estimation beyond power-of-two schedules

Farrokh Labib

Non-adaptive quantum amplitude estimation (QAE) fixes its Grover depths in advance, so every circuit can run in parallel, but it has so far needed more queries than the best adaptive methods. We show that most of this gap comes from two conventional choices: subspace-based post-processing and power-of-two depth ladders. We replace the first by the exact maximum-likelihood estimate, one matrix multiplication per batch of estimates, and the second by a geometric ladder with ratio $r \approx 1.45$. The result is a fully parallel, deterministic-schedule estimator with total query complexity $2.8$-$3.1/\varepsilon$ at 95% confidence for target errors from $3.5\times 10^{-3}$ to $10^{-6}$. This matches the average-case complexity of chebAE, the best benchmarked adaptive method, within statistical uncertainty (with the lower point estimate at every scale tested), beats its maximum-observed complexity by $1.6\times$, and needs a maximum sequential depth of only $0.21/\varepsilon$ against chebAE's $2.9/\varepsilon$. Relative to csAE, the best non-adaptive benchmark, the constants improve by 30-35% at 95% and $1.5$-$1.7\times$ at 99% confidence. The optimal ratio has a simple origin. Doubling is the fastest depth growth at which the data can still tell neighboring candidate values apart, so power-of-two ladders sit at the edge of confusion and must buy reliability with extra shots; a slightly denser ladder checks every scale redundantly. An error-probability analysis reproduces the measured failure rates and locates the optimum. The likelihood formulation extends directly to noise-aware estimation, and uniformly scaling the capped ladder covers the depth-limited regime, realizing the optimal trade-off $M N_{\mathrm{tot}} \approx (0.4$-$0.6)/\varepsilon^2$ within $\sim 1.1\times$ of the schedule's Cramér-Rao limit.

quant-pharXiv:2609.02715•Sep 3, 2026•0 citations
We study numerical integration on [0,1][0,1][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 Gn(d)\mathcal{G}_n^{(d)}Gn(d)​, defined by requiring the angle map Θg:{0,1}n→[0,π]Θ_g:\{0,1\}^n\to[0,π]Θg​:{0,1}n→[0,π] to be multilinear of degree at most ddd. Membership is classically checkable in O(n2n)O(n2^n)O(n2n) time by the Walsh--Hadamard transform. For g∈Gn(d)g\in\mathcal{G}_n^{(d)}g∈Gn(d)​, the encoding operator factorises into ∑k=0d(nk)\sum_{k=0}^d\binom{n}{k}∑k=0d​(kn​) multi-controlled RYR_YRY​ gates, interpolating between an affine O(n)O(n)O(n) regime and the generic exponential regime.
Combining this structure with classical discretisation estimates for g∈Cα[0,1]g\in C^α[0,1]g∈Cα[0,1], we obtain a depth-versus-accuracy trade-off: gate count O((log⁡(1/ε))dε−1)O((\log(1/\varepsilon))^d\varepsilon^{-1})O((log(1/ε))dε−1) suffices to achieve ε\varepsilonε-accuracy with constant probability. For d=1d=1d=1 this becomes O(ε−1log⁡(1/ε))O(\varepsilon^{-1}\log(1/\varepsilon))O(ε−1log(1/ε)), improving over classical Monte Carlo for every α≥1α\ge1α≥1. We also prove an unconditional separation: Gn(1)\mathcal{G}_n^{(1)}Gn(1)​ contains functions of Sobolev regularity s<1/2s<1/2s<1/2 for which the quantum oracle cost is O(1/ε)O(1/\varepsilon)O(1/ε), whereas classical deterministic or randomised quadrature requires Ω(ε−1/s)Ω(\varepsilon^{-1/s})Ω(ε−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=2n=2n=2: circuits inside Gn(d)\mathcal{G}_n^{(d)}Gn(d)​ run successfully, while those exceeding the Triangulum coherence budget fail as predicted.
We give a rigorous and self-contained analysis of the Grover--Rudolph quantum state-preparation algorithm, which encodes a probability distribution {pk}\{p_k\}{pk​} as an nnn-qubit amplitude state ∑kpk∣k⟩\sum_k\sqrt{p_k}\ket{k}∑k​pk​​∣k⟩ via a hierarchy of controlled $\RY$ rotations determined by a dyadic refinement of the target. We formalize the dyadic probability tree, derive the trigonometric factorization of conditional masses, and prove by induction that the circuit prepares exactly the desired measurement law. We further prove that perturbing each rotation angle by at most ηηη changes the output distribution by at most min⁡(1,nη)\min(1,nη)min(1,nη) in total variation, and combine this with a Hoeffding concentration bound to obtain an explicit design rule: b≥log⁡2(2nπ/ε)b\ge\log_2(2nπ/\varepsilon)b≥log2​(2nπ/ε) bits and S≥2n+1log⁡(2/δ)/ε2S\ge 2^{n+1}\log(2/δ)/\varepsilon^2S≥2n+1log(2/δ)/ε2 shots suffice to achieve accuracy ε\varepsilonε with confidence 1−δ1-δ1−δ. As a circuit-theoretic complement, we provide an ancilla-free transpilation of each stage into $\{\RY(\cdot),X,\CNOT\}$ via Gray-code ladders and a Walsh--Hadamard angle transform.
We investigate two fundamental data encoding strategies for gate-based quantum computers: amplitude encoding and angle encoding. In amplitude encoding, a normalized -dimensional classical vector is mapped into the probability amplitudes of a -qubit quantum state, whereas angle encoding uses one or more single-qubit rotation gates per feature to encode data as angles.[1, 2] We construct a toy binary classification dataset with four real-valued features and compare these encoding schemes using a variational quantum classifier (VQC) approach. Our results indicate that angle encoding often yields slightly higher classification accuracy (e.g. 82% vs. 75% in one experiment) at the cost of requiring more qubits, while amplitude encoding compresses features into fewer qubits (2 vs. 4) but demands deeper state-preparation circuits. These findings align with previous studies that report higher accuracy for rotation encodings (e.g. vs. in MNIST experiments [3]) and note that the encoding choice acts as a hyperparameter affecting VQC performance. [4]
We develop a class of amplitude estimation algorithms with tunable circuit depth MMM and circuit repetitions NNN, requiring neither ancilla qubits nor controlled Grover operations. For additive error εεε in the Grover angle, they attain the nearly optimal query-depth tradeoff M2N∈O~(ε−2)M^2N\in\widetilde{O}(ε^{-2})M2N∈O(ε−2) uniformly over λ∈[0,π/2]λ\in[0,π/2]λ∈[0,π/2], spanning the full range from classical sampling at M=1M=1M=1 to the Heisenberg limit at M=Θ(ε−1)M=Θ(ε^{-1})M=Θ(ε−1). While prior depth-tunable work establishes comparable angle-accuracy guarantees only away from the boundaries λ→0λ\to0λ→0 or π/2π/2π/2 or at discrete depth tradeoffs, our guarantee extends to both boundaries, so the quantum speedup persists there rather than degrading to classical sampling. Numerical experiments confirm the predicted uniform angle accuracy and show low overhead in practice, making them strong candidates for practical amplitude estimation in the early fault-tolerant regime, with applications such as overlap certification, trial-state verification, and Monte Carlo methods.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0δ>0δ>0, it ε\varepsilonε-approximates an arbitrary single-qubit gate using O(log⁡1+δ(1/ε))O(\log^{1+δ}(1/\varepsilon))O(log1+δ(1/ε)) clean ancillae, Hadamard and TTT single-qubit gates, O(log⁡(1/ε))O(\log(1/\varepsilon))O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, TTT, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(log⁡log⁡(1/ε))O(\log\log(1/\varepsilon))O(loglog(1/ε)), and we prove a matching Ω(log⁡log⁡(1/ε))Ω(\log\log(1/\varepsilon))Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(log⁡log⁡(1/ε))Θ(\log\log(1/\varepsilon))Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-ddd QAC circuit can be simulated in depth O(d)O(d)O(d) using only Hadamard, XXX, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∉\notin∈/QAC0^00 to proving a Parity lower bound against circuits consisting only of Hadamard, XXX, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
We give a rigorous and self-contained analysis of the Grover-Rudolph quantum state-preparation algorithm, which encodes a probability distribution $ \{p_k\} $ as an $ n $-qubit amplitude state $ \sum_k\sqrt{p_k}|k\rangle $ via a hierarchy of controlled $ \mathrm{R}_y $ rotations determined by a dyadic refinement of the target. We formalize the dyadic probability tree, derive the trigonometric factorization of conditional masses, and prove by induction that the circuit prepares exactly the desired measurement law. We further prove that perturbing each rotation angle by at most $ \eta $ changes the output distribution by at most $ \min(1, n\eta) $ in total variation, and combine this with a Hoeffding concentration bound to obtain an explicit design rule: $ b\ge\log_2(2n\pi/\varepsilon) $ bits and $ S\ge 2^{n+1}\log(2/\delta)/\varepsilon^2 $ shots suffice to achieve accuracy $ \varepsilon $ with confidence $ 1-\delta $. As a circuit-theoretic complement, we provide an ancilla-free transpilation of each stage into $ \{ \mathrm{R}_y(\cdot), X, \mathrm{CNOT}\} $ via Gray-code ladders and a Walsh-Hadamard angle transform.
Non-adaptive quantum amplitude estimation (QAE) fixes its Grover depths in advance, so every circuit can run in parallel, but it has so far needed more queries than the best adaptive methods. We show that most of this gap comes from two conventional choices: subspace-based post-processing and power-of-two depth ladders. We replace the first by the exact maximum-likelihood estimate, one matrix multiplication per batch of estimates, and the second by a geometric ladder with ratio r≈1.45r \approx 1.45r≈1.45. The result is a fully parallel, deterministic-schedule estimator with total query complexity 2.82.82.8-3.1/ε3.1/\varepsilon3.1/ε at 95% confidence for target errors from 3.5×10−33.5\times 10^{-3}3.5×10−3 to 10−610^{-6}10−6. This matches the average-case complexity of chebAE, the best benchmarked adaptive method, within statistical uncertainty (with the lower point estimate at every scale tested), beats its maximum-observed complexity by 1.6×1.6\times1.6×, and needs a maximum sequential depth of only 0.21/ε0.21/\varepsilon0.21/ε against chebAE's 2.9/ε2.9/\varepsilon2.9/ε. Relative to csAE, the best non-adaptive benchmark, the constants improve by 30-35% at 95% and 1.51.51.5-1.7×1.7\times1.7× at 99% confidence. The optimal ratio has a simple origin. Doubling is the fastest depth growth at which the data can still tell neighboring candidate values apart, so power-of-two ladders sit at the edge of confusion and must buy reliability with extra shots; a slightly denser ladder checks every scale redundantly. An error-probability analysis reproduces the measured failure rates and locates the optimum. The likelihood formulation extends directly to noise-aware estimation, and uniformly scaling the capped ladder covers the depth-limited regime, realizing the optimal trade-off MNtot≈(0.4M N_{\mathrm{tot}} \approx (0.4MNtot​≈(0.4-0.6)/ε20.6)/\varepsilon^20.6)/ε2 within ∼1.1×\sim 1.1\times∼1.1× of the schedule's Cramér-Rao limit.