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

Mathematical Foundations of Computing

Complexity of approximation on generalized Hölder classes

Wan Li, Peixin Ye

Published Jan 1, 2026• 0 citations
Publisher

Abstract

We study the approximation of functions from the generalized Hölder classes $ B(H_{\Omega}^{k}([0,1]^{d})) $ in the $ L_{p}([0,1]^{d}) $ metric for all $ 1\leq p\leq \infty $. We establish the exact orders of complexity for this problem in the deterministic, randomized and quantum settings. The optimal convergence rates in all three settings are $ \Omega(n^{-1/d}) $, where $ n $ is the number of function evaluations involved in the computational process. The results show that quantum and randomized algorithms yield no improvement in terms of the optimal convergence rates. Furthermore, we apply our general result to the special case $ \Omega(t) = t^{a}\left(\log_{2}\left(2+\frac{1}{t}\right)\right)^{b} $ with $ 0<a<k $ and $ b\in\mathbb{R} $, and derive the corresponding complexity orders.

DOI
10.3934/mfc.2026021

Related papers

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

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

Information-Based Complexity of Integration in the Randomized and Quantum Computation Model

Wen Gao, Duan Li, Wei Zhou +1 more

In this paper, we investigate the integration of the Hölder-Nikolskii classes in the randomized and quantum computation model. We develop randomized and quantum algorithms for integration of functions from this class and analyze their convergence rates. Comparing our result with the convergence rates in the deterministic setting, we see that quantum computing can reach an exponential speedup over deterministic classical computation and a quadratic speedup over randomized classical computation.

Advanced materials research•Nov 1, 2011•0 citations

Quantum Approximation on Some Classes of Multivarite Functions

Peixin Ye

We study the quantum query error of approximation of functions from anisotropic Sobolev class B(Wpr([0, 1]d)) and Holder-Nikolskii class B(Hpr([0, 1]d)) in the Lq([0, 1]d) norm for all 1 les p, q les infin. The results show that for the class B(Wpr([0, 1]d)) (r isin Nd) when ppr([0, 1]d)) and B(Wpr([0, 1]d)) (r isin R+d) when p ges q the optimal convergence rate is the same for all three settings.

•Jan 1, 2008•0 citations
We study the approximation of functions from the generalized Hölder classes B(HΩk([0,1]d))B(H_{\Omega}^{k}([0,1]^{d}))B(HΩk​([0,1]d)) in the Lp([0,1]d)L_{p}([0,1]^{d})Lp​([0,1]d) metric for all 1≤p≤∞1\leq p\leq \infty1≤p≤∞. We establish the exact orders of complexity for this problem in the deterministic, randomized and quantum settings. The optimal convergence rates in all three settings are Ω(n−1/d)\Omega(n^{-1/d})Ω(n−1/d), where nnn is the number of function evaluations involved in the computational process. The results show that quantum and randomized algorithms yield no improvement in terms of the optimal convergence rates. Furthermore, we apply our general result to the special case Ω(t)=ta(log⁡2(2+1t))b\Omega(t) = t^{a}\left(\log_{2}\left(2+\frac{1}{t}\right)\right)^{b}Ω(t)=ta(log2​(2+t1​))b with 0<a<k0<a<k0<a<k and b∈Rb\in\mathbb{R}b∈R, and derive the corresponding complexity orders.
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.
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 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​.
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.