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

Restricted Monte Carlo Integration on Some Multivariate Functions

Peixin Ye, Qing He

Published Jan 1, 2008• 0 citations
Publisher

Abstract

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.
DOI
10.1109/csse.2008.570

Related papers

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

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

Wenhua Gao, Peixin Ye, Hui Wang

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

Progress in Natural Science Materials International•Jun 1, 2006•8 citations

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•7 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

Optimal restricted Monte Carlo integration on generalized Hölder classes

Li Wan, Man Lu, Peixin Ye

Journal of Applied Mathematics and Computing•Jan 21, 2025•1 citation

When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?

Ian H. Sloan, Henryk Woźniakowski

Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.

Journal of Complexity•Mar 1, 1998•613 citations
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.
Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.