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)

Convergence rate of quantum algorithm for multivariate approximation

Jingfan Long, Sheng Zhang, Peixin Ye

Published Aug 1, 2010• 0 citations
Publisher

Abstract

We estimate the convergence rate of quantum algorithm for approximation from some smooth functions in the Lq([0, 1]d) norm for 1 ≤ q ≤ ∞. It turns out that for the Sobolev class B(Wpr([0, 1]d)) (r ∈ ℕd), when p <; q, the quantum algorithms can bring speedup over classical deterministic and randomized algorithms.
DOI
10.1109/icnc.2010.5582913

Related papers

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

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

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

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

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