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

Journal of Computational Mathematics

Quantum Complexity of the Integration Problem for Anisotropic Classes

Xiao-Fei Hu, Pei-Xin Ye

Published Jun 2, 2005• 0 citations
Publisher

Abstract

We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes $W_{\infty}^{\bf r}([0,1]^d)$ and Hölder Nikolskii classes $H_{\infty}^{\bf r}([0,1]^d)$. It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor $n^{-1}$ and over randomized classical methods due to factor $n^{-1/2}$. Moreover, we give an estimation for optimal query complexity in the class $H_{\infty}^{\Lambda}(D)$ whose smoothness index is the boundary of some complete set in $\mathbb{Z}_+^d$.

DOI
10.4208/jcm.v23.n3.p233

Related papers

QUANTUM COMPLEXITY OF THE INTEGRATION PROBLEM FOR ANISOTROPIC CLASSES

Xiao-feiHu, Pei-xinYe

We obtain the optimal order of high-dimensional integration complexity in the quantumcomputation model in anisotropic Sobolev classes W∞^r ([0, 1]^d) and Hǒlder Nikolskii classes H∞^r([0, 1]^d). It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor n^-1 and over randomized classical methods due to factor n^-1/2. Moreover, we give an estimation for optimal query complexity in the class H∞^∧ (D) whose smoothness index is the boundary of some complete set in Z+^d.

Journal of Computational Mathematics•Jan 1, 2005•7 citations

QUANTUM APPROXIMATION ON ANISOTROPIC SOBOLEV AND HÖLDER-NIKOLSKII CLASSES

Peixin Ye

We estimate the quantum query error of approximation to functions from the anisotropic Sobolev class ${\cal B}(W_p^{\bf r}([0,1]^d))$ and the Hölder-Nikolskii class ${\cal B}(H_p^{\bf r}([0,1]^d))$ in the $L_q([0,1]^d)$ norm for all $1 \leq p,q \leq \infty$. It turns out that for the class ${\cal B}(W_p^{\bf r}([0,1]^d))$ $({\bf r}\in {\mathbb{N}^d})$, when $p \lt q$, the quantum algorithms can essentially improve the rate of convergence of classical deterministic and randomized algorithms; while for the class ${\cal B}(H_p^{\bf r}([0,1]^d))$ and ${\cal B}(W_p^{\bf r}([0,1]^d))$ $({\bf r}\in {\mathbb{R}_+^d})$, when $p \geq q$, the optimal convergence rate is the same for all three settings.

Taiwanese Journal of Mathematics•Jan 1, 2012•1 citation

Quantum Complexity of the Approximation on the Classes B(Wrp([0, 1]d)) and B(Hrp([0, 1]d))

Peixin Ye

The optimal order of complexity of the approximation of the imbedding from anisotropic Sobolev classes B(Wpr([0, 1]d)) and Holder Nikolskii classes B(Hpr([0, 1]d)) into the Lq([0, 1]d) with q les p quantum computation model is obtained up to logarithmic factors. It shows that the quantum algorithms are not significantly better than the classical ones for this type of problems.

International Conference on Natural Computation (ICNC)•Jan 1, 2008•0 citations

Lower Bound for Quantum Integration Error on Some Sobolev Classes

Peixin Ye

We study the approximation of the integration of multivariate functions in the quantum model of computation. Using a new reduction approach we obtain a lower bound of the n-th minimal query error on anisotropic Sobolev classes B(Wpr([0, 1]d)), (r isin R+d). Then combining our previous results we determine the optimal bound of nth minimal query error for anisotropic Holder-Nikolskii class B(Hinfinr([0, 1]d)), (r isin R+d) and Sobolev class B(Wpr([0, 1]d)) (r isin Nd). The results show the quantum algorithms give speed up over classical algorithms.

International Conference on Natural Computation (ICNC)•Jan 1, 2008•0 citations

Complexity for the approximation of Sobolev imbeddings in the quantum computation model

Jingfan Long, Peixin Ye, Xiuhua Yuan

Using a new and elegant reduction approach we derive a lower bound of quantum complexity for the approximation of imbeddings from anisotropic Sobolev classes B(W p r([0, 1]d)) to anisotropic Sobolev space W p s([0, 1]d) for all 1 ≤ p, q ≤ ∞. When p ≥ q this bound is optimal. In this case the quantum algorithms are not significantly better than the classical deterministic or randomized algorithms. When p ≥ q we conjecture that quantum algorithms bring speed-up over the classical deterministic and randomized ones. This conjecture was confirmed in the situation s = 0.

Chinese Control Conference (CCC)•Jan 1, 2011•0 citations

Complexity of quantum integration on generalized Hölder classes

Wan Li, Peixin Ye

In this paper, we study the numerical integration problem of functions from the generalized Hölder class [Formula: see text], which is determined by a generalized modulus of smoothness [Formula: see text], in the quantum model of computation. We obtain the exact order of complexity of this problem. The results show that quantum algorithms have faster convergence rates than those of deterministic and randomized ones. Quantitatively, the improvement amounts to the factors [Formula: see text] for the deterministic case and [Formula: see text] for the randomized case, where [Formula: see text] is the number of function evaluations involved in the computational process. Furthermore, we apply our general results to the case [Formula: see text] with [Formula: see text] and [Formula: see text] and obtain the corresponding complexity.

Analysis and Applications•Feb 27, 2026•0 citations
We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes W∞r([0,1]d)W_{\infty}^{\bf r}([0,1]^d)W∞r​([0,1]d) and Hölder Nikolskii classes H∞r([0,1]d)H_{\infty}^{\bf r}([0,1]^d)H∞r​([0,1]d). It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor n−1n^{-1}n−1 and over randomized classical methods due to factor n−1/2n^{-1/2}n−1/2. Moreover, we give an estimation for optimal query complexity in the class H∞Λ(D)H_{\infty}^{\Lambda}(D)H∞Λ​(D) whose smoothness index is the boundary of some complete set in Z+d\mathbb{Z}_+^dZ+d​.
We obtain the optimal order of high-dimensional integration complexity in the quantumcomputation model in anisotropic Sobolev classes W∞^r ([0, 1]^d) and Hǒlder Nikolskii classes H∞^r([0, 1]^d). It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor n^-1 and over randomized classical methods due to factor n^-1/2. Moreover, we give an estimation for optimal query complexity in the class H∞^∧ (D) whose smoothness index is the boundary of some complete set in Z+^d.
We estimate the quantum query error of approximation to functions from the anisotropic Sobolev class B(Wpr([0,1]d)){\cal B}(W_p^{\bf r}([0,1]^d))B(Wpr​([0,1]d)) and the Hölder-Nikolskii class B(Hpr([0,1]d)){\cal B}(H_p^{\bf r}([0,1]^d))B(Hpr​([0,1]d)) in the Lq([0,1]d)L_q([0,1]^d)Lq​([0,1]d) norm for all 1≤p,q≤∞1 \leq p,q \leq \infty1≤p,q≤∞. It turns out that for the class B(Wpr([0,1]d)){\cal B}(W_p^{\bf r}([0,1]^d))B(Wpr​([0,1]d)) (r∈Nd)({\bf r}\in {\mathbb{N}^d})(r∈Nd), when p<qp \lt qp<q, the quantum algorithms can essentially improve the rate of convergence of classical deterministic and randomized algorithms; while for the class B(Hpr([0,1]d)){\cal B}(H_p^{\bf r}([0,1]^d))B(Hpr​([0,1]d)) and B(Wpr([0,1]d)){\cal B}(W_p^{\bf r}([0,1]^d))B(Wpr​([0,1]d)) (r∈R+d)({\bf r}\in {\mathbb{R}_+^d})(r∈R+d​), when p≥qp \geq qp≥q, the optimal convergence rate is the same for all three settings.
We study the approximation of the integration of multivariate functions in the quantum model of computation. Using a new reduction approach we obtain a lower bound of the n-th minimal query error on anisotropic Sobolev classes B(Wpr([0, 1]d)), (r isin R+d). Then combining our previous results we determine the optimal bound of nth minimal query error for anisotropic Holder-Nikolskii class B(Hinfinr([0, 1]d)), (r isin R+d) and Sobolev class B(Wpr([0, 1]d)) (r isin Nd). The results show the quantum algorithms give speed up over classical algorithms.
Using a new and elegant reduction approach we derive a lower bound of quantum complexity for the approximation of imbeddings from anisotropic Sobolev classes B(W p r([0, 1]d)) to anisotropic Sobolev space W p s([0, 1]d) for all 1 ≤ p, q ≤ ∞. When p ≥ q this bound is optimal. In this case the quantum algorithms are not significantly better than the classical deterministic or randomized algorithms. When p ≥ q we conjecture that quantum algorithms bring speed-up over the classical deterministic and randomized ones. This conjecture was confirmed in the situation s = 0.
In this paper, we study the numerical integration problem of functions from the generalized Hölder class [Formula: see text], which is determined by a generalized modulus of smoothness [Formula: see text], in the quantum model of computation. We obtain the exact order of complexity of this problem. The results show that quantum algorithms have faster convergence rates than those of deterministic and randomized ones. Quantitatively, the improvement amounts to the factors [Formula: see text] for the deterministic case and [Formula: see text] for the randomized case, where [Formula: see text] is the number of function evaluations involved in the computational process. Furthermore, we apply our general results to the case [Formula: see text] with [Formula: see text] and [Formula: see text] and obtain the corresponding complexity.