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

International Conference on Natural Computation (ICNC)

Monte Carlo integration with small random bits

Sheng Zhang, Peixin Ye, Jingfan Long

Published Aug 1, 2010• 0 citations
Publisher

Abstract

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.
DOI
10.1109/icnc.2010.5583957

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

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

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

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