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

Scientia Sinica Mathematica

Complexity of Sobolev imbeddings and integration in the deterministic and randomized settings

Peixin Ye

Published Mar 1, 2011• 1 citation
Publisher

Abstract

This paper reformulates the problems of approximation of imbedding and integration from anisotropic Sobolev classes B(Wrp([0, 1]d)) in the deterministic, randomized and average case settings, and obtains the exact orders of the n-th minimal error of these problems in all three settings. The results show that in the case of B(Wrp([0, 1]d)) being not imbedded into the space of continuous functions C([0, 1]d), the randomized and average case error are essential smaller than the deterministic ones. Quantitatively, this maximal gain for imbedding problem amounts to the factor n-1+ε for any ε > 0, and for integration problem the gain is up to factor n-1 which is also the maximal speedup over the deterministic algorithms observed so far in natural numerical problems.

DOI
10.1360/012010-569

Related papers

Complexity of deterministic and randomized methods for multivariate integration problems for the class HpΛ(Id)

Fang Gensun, Peixin Ye

We introduce a new class of multivariate functions HpΛ(Id), which includes some classical sets of functions such as isotropic and anisotropic Sobolev and Hölder–Nikolskii as special cases or as a subclass in the sense of continuous imbedding. Then we prove that when p > 1 the ε-complexity of the integration problem in the randomized setting as well as in the average case setting is significantly smaller than that in the worst case deterministic setting.

IMA Journal of Numerical Analysis•Feb 7, 2005•6 citations

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

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

Quantum Approximation Error on Some Sobolev Classes

Peixin Ye

We study the approximation of functions from anisotropic and generalized Sobolev classes under Lq([0, 1]d) norm in the quantum model of computation. Based on the quantum algorithm for approximation of finite imbedding from LNPto LiNQ, we develop a quantum algorithm for approximating the imbedding from anisotropic Sobolev classes B(Wpr(|0, 1|d)) to Lq(|0, 1|d) space for all 1 les q,p les infin and prove their optimality. Our results show that for p < q the quantum model of computation can bring a speedup of roughly squaring the rate of classical deterministic and randomized settings.

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

Sobolev Approximation in the Quantum Computation Model

Peixin Ye, Yuan Xiuhua

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(Wpr([0,1]d)) to anisotropic Sobolev space (Wps([0,1]d) for all 1 ≥ p, q ≤ ∞ . When p≥q we show this bound is optimal by deriving the matching upper bound. In this case the quantum algorithms are not significantly better than the classical deterministic or randomized algorithms.

International Conference on Intelligent Computation Technology and Automation•Mar 1, 2011•0 citations

Quantum Complexity of the Integration Problem for Anisotropic Classes

Xiao-Fei Hu, Pei-Xin Ye

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$.

Journal of Computational Mathematics•Jun 2, 2005•0 citations
This paper reformulates the problems of approximation of imbedding and integration from anisotropic Sobolev classes B(Wrp([0, 1]d)) in the deterministic, randomized and average case settings, and obtains the exact orders of the n-th minimal error of these problems in all three settings. The results show that in the case of B(Wrp([0, 1]d)) being not imbedded into the space of continuous functions C([0, 1]d), the randomized and average case error are essential smaller than the deterministic ones. Quantitatively, this maximal gain for imbedding problem amounts to the factor n-1+ε for any ε > 0, and for integration problem the gain is up to factor n-1 which is also the maximal speedup over the deterministic algorithms observed so far in natural numerical problems.
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.
We study the approximation of functions from anisotropic and generalized Sobolev classes under Lq([0, 1]d) norm in the quantum model of computation. Based on the quantum algorithm for approximation of finite imbedding from LNPto LiNQ, we develop a quantum algorithm for approximating the imbedding from anisotropic Sobolev classes B(Wpr(|0, 1|d)) to Lq(|0, 1|d) space for all 1 les q,p les infin and prove their optimality. Our results show that for p < q the quantum model of computation can bring a speedup of roughly squaring the rate of classical deterministic and randomized settings.
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​.