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 encoding 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• Revised Jul 27, 2026 (v2)
v1 · Apr 27, 2026v2 · Jul 27, 2026
arXivHTMLPDF

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

Comments
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

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

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

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

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

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

Novel oracle constructions for quantum random access memory

Ákos Nagy, Cindy Zhang

We present new designs for quantum random access memory. More precisely, for each function, $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^d$, we construct oracles, $\mathcal{O}_f$, with the property \begin{equation} \mathcal{O}_f \left| x \right\rangle_n \left| 0 \right\rangle_d = \left| x \right\rangle_n \left| f(x) \right\rangle_d. \end{equation} Our methods are based on the Walsh-Hadamard Transform of $f$, viewed as an integer valued function. In general, the complexity of our method scales with the sparsity of the Walsh-Hadamard Transform and not the sparsity of $f$, yielding more favorable constructions in cases such as binary optimization problems and function with low-degree Walsh-Hadamard Transforms. Furthermore, our design comes with a tuneable amount of ancillas that can trade depth for size. In the ancilla-free design, these oracles can be $ε$-approximated so that the Clifford + $T$ depth is $O \left( \left( n + \log_2 \left( \tfrac{d}ε \right) \right) \mathcal{W}_f \right)$, where $\mathcal{W}_f$ is the number of nonzero components in the Walsh-Hadamard Transform. The depth of the shallowest version is $O \left( n + \log_2 \left( \tfrac{d}ε \right) \right)$, using $n + d \mathcal{W}_f$ qubit. The connectivity of these circuits is also only logarithmic in $\mathcal{W}_f$. As an application, we show that for boolean functions with low approximate degrees (as in the case of read-once formulas) the complexities of the corresponding QRAM oracles scale only as $2^{\widetilde{O} \left( \sqrt{n} \log_2 \left( n \right) \right)}$.

arXiv:2405.20225•May 30, 2024•0 citations
We study numerical integration on [0,1][0,1][0,1] by quantum amplitude estimation (QAE), with emphasis on the cost of constructing the amplitude oracle. We introduce a hierarchy of grid functions Gn(d)\mathcal{G}_n^{(d)}Gn(d)​ whose angle map Θg:{0,1}n→[0,π]Θ_g:\{0,1\}^n\to[0,π]Θg​:{0,1}n→[0,π] is multilinear of degree at most ddd. Membership is classically checkable in O(n2n)O(n2^n)O(n2n) time by the Walsh--Hadamard transform, and each g∈Gn(d)g\in\mathcal{G}_n^{(d)}g∈Gn(d)​ admits a canonical encoding circuit with ∑k=0d(nk)\sum_{k=0}^d\binom{n}{k}∑k=0d​(kn​) multi-controlled RYR_YRY​ gates. Combining this circuit bound with classical discretisation estimates, we obtain a depth-versus-accuracy trade-off: for g∈Cα[0,1]g\in C^α[0,1]g∈Cα[0,1], total gate count O((log⁡(1/ε))dε−1)O((\log(1/\varepsilon))^d\varepsilon^{-1})O((log(1/ε))dε−1) suffices for ε\varepsilonε-accuracy with constant probability; in the affine case d=1d=1d=1 this is O(ε−1log⁡(1/ε))O(\varepsilon^{-1}\log(1/\varepsilon))O(ε−1log(1/ε)) at fixed discretisation. We also show that encoding degree and Sobolev smoothness are independent: for every s∈(0,1/2)s\in(0,1/2)s∈(0,1/2), Gn(1)\mathcal{G}_n^{(1)}Gn(1)​ contains restrictions of functions in Ws′,2(0,1)W^{s',2}(0,1)Ws′,2(0,1) for all s′<ss'<ss′<s but not in Ws,2(0,1)W^{s,2}(0,1)Ws,2(0,1). Experiments on the SpinQ Triangulum (NMR) and IBM Kingston (superconducting) processors at n=2n=2n=2 validate the predicted hierarchy: affine encodings run reliably on both platforms, while quadratic encodings exceed the Triangulum coherence budget but execute on Kingston.
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 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 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.
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.
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.
We present new designs for quantum random access memory. More precisely, for each function, f:F2n→F2df : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^df:F2n​→F2d​, we construct oracles, Of\mathcal{O}_fOf​, with the property \begin{equation} \mathcal{O}_f \left| x \right\rangle_n \left| 0 \right\rangle_d = \left| x \right\rangle_n \left| f(x) \right\rangle_d. \end{equation} Our methods are based on the Walsh-Hadamard Transform of fff, viewed as an integer valued function. In general, the complexity of our method scales with the sparsity of the Walsh-Hadamard Transform and not the sparsity of fff, yielding more favorable constructions in cases such as binary optimization problems and function with low-degree Walsh-Hadamard Transforms. Furthermore, our design comes with a tuneable amount of ancillas that can trade depth for size. In the ancilla-free design, these oracles can be εεε-approximated so that the Clifford + TTT depth is O((n+log⁡2(dε))Wf)O \left( \left( n + \log_2 \left( \tfrac{d}ε \right) \right) \mathcal{W}_f \right)O((n+log2​(εd​))Wf​), where Wf\mathcal{W}_fWf​ is the number of nonzero components in the Walsh-Hadamard Transform. The depth of the shallowest version is O(n+log⁡2(dε))O \left( n + \log_2 \left( \tfrac{d}ε \right) \right)O(n+log2​(εd​)), using n+dWfn + d \mathcal{W}_fn+dWf​ qubit. The connectivity of these circuits is also only logarithmic in Wf\mathcal{W}_fWf​. As an application, we show that for boolean functions with low approximate degrees (as in the case of read-once formulas) the complexities of the corresponding QRAM oracles scale only as 2O~(nlog⁡2(n))2^{\widetilde{O} \left( \sqrt{n} \log_2 \left( n \right) \right)}2O(n​log2​(n)).