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

Progress in Natural Science Materials International

Optimal error bound of restricted Monte Carlo integration on anisotropic Sobolev classes*

Wenhua Gao, Peixin Ye, Hui Wang

Published Jun 1, 2006• 8 citations
Publisher

Abstract

Abstract We study the restricted Monte Carlo integration error for anisotropic Sobolev classes. Results prove that with O(log2 n)random bits we have the optimal order for the n-th minimal Monte Carlo integration error with arbitrary random numbers. Supported by National Natural Science Foundation of China (Grant Nos. 10261007 and 10501026), Tianyuan Fund for Mathematics (Grant No. 10426020) and the fund for Nankai University

DOI
10.1080/10020070612330039

Related papers

Restricted Monte Carlo Integration on Some Multivariate Functions

Peixin Ye, Qing He

We study restricted Monte Carlo integration for anisotropic Holder-Nikolskii classes. The results show that with c ldr log2n random bits we have the same optimal order for the n-th minimal Monte Carlo integration error as with arbitrary random numbers.

•Jan 1, 2008•0 citations

Monte Carlo integration with small random bits

Sheng Zhang, Peixin Ye, Jingfan Long

Motivated by the recent progress on quantum integration, we study restricted Monte Carlo integration for anisotropic Hölder-Nikolskii classes. The results show that with c · log2n random bits we have the same optimal order for the n-th minimal Monte Carlo integration error as with arbitrary random numbers.

International Conference on Natural Computation (ICNC)•Aug 1, 2010•0 citations

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

Peixin Ye

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.

Scientia Sinica Mathematica•Mar 1, 2011•1 citation

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

Optimal integration error on anisotropic classes for restricted Monte Carlo and quantum algorithms

Peixin Ye, Xiaofei Hu

Journal of Approximation Theory•May 24, 2007•12 citations

On quasi-Monte Carlo methods in weighted ANOVA spaces

Peter Kritzer, Friedrich Pillichshammer, G.W. Wasilkowski

In the present paper we study quasi-Monte Carlo rules for approximating integrals over the $d$-dimensional unit cube for functions from weighted Sobolev spaces of regularity one. While the properties of these rules are well understood for anchored Sobolev spaces, this is not the case for the ANOVA spaces, which are another very important type of reference spaces for quasi-Monte Carlo rules. Using a direct approach we provide a formula for the worst case error of quasi-Monte Carlo rules for functions from weighted ANOVA spaces. As a consequence we bound the worst case error from above in terms of weighted discrepancy of the employed integration nodes. On the other hand we also obtain a general lower bound in terms of the number $n$ of used integration nodes. For the one-dimensional case our results lead to the optimal integration rule and also in the two-dimensional case we provide rules yielding optimal convergence rates.

arXiv:2001.05765•Mathematics of Computation•Nov 18, 2020•2 citations
Abstract We study the restricted Monte Carlo integration error for anisotropic Sobolev classes. Results prove that with O(log2 n)random bits we have the optimal order for the n-th minimal Monte Carlo integration error with arbitrary random numbers. Supported by National Natural Science Foundation of China (Grant Nos. 10261007 and 10501026), Tianyuan Fund for Mathematics (Grant No. 10426020) and the fund for Nankai University
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.
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.
In the present paper we study quasi-Monte Carlo rules for approximating integrals over the ddd-dimensional unit cube for functions from weighted Sobolev spaces of regularity one. While the properties of these rules are well understood for anchored Sobolev spaces, this is not the case for the ANOVA spaces, which are another very important type of reference spaces for quasi-Monte Carlo rules. Using a direct approach we provide a formula for the worst case error of quasi-Monte Carlo rules for functions from weighted ANOVA spaces. As a consequence we bound the worst case error from above in terms of weighted discrepancy of the employed integration nodes. On the other hand we also obtain a general lower bound in terms of the number nnn of used integration nodes. For the one-dimensional case our results lead to the optimal integration rule and also in the two-dimensional case we provide rules yielding optimal convergence rates.