English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We study the approximation problem (or problem of optimal recovery in the$L_2$-norm) for weighted Korobov spaces with smoothnessparameter $\a$. The weights $\gamma_j$ of the Korobov spaces moderatethe behavior of periodic functions with respect to successive variables.The nonnegative smoothness parameter $\a$ measures the decayof Fourier coefficients. For $\a=0$, the Korobov space is the$L_2$ space, whereas for positive $\a$, the Korobov spaceis a space of periodic functions with some smoothness and the approximation problemcorresponds to a compact operator. The periodic functions are defined on $[0,1]^d$ and our main interest is when the dimension $d$ varies andmay be large. We consider algorithms using two different classes of information.The first class $\lall$ consists of arbitrary linear functionals.The second class $\lstd$ consists of only function valuesand this class is more realistic in practical computations.We want to know when the approximation problem istractable. Tractability means that there exists an algorithm whose erroris at most $\e$ and whose information cost is bounded by a polynomial in the dimension $d$ and in $\e^{-1}$. Strong tractability means that the bound does not depend on $d$ and is polynomial in $\e^{-1}$. In this paper we consider the worst case, randomized, and quantumsettings. In each setting, the concepts of error and cost are defineddifferently and,  therefore, tractability and strong tractability depend on the setting and on the class of information. In the worst case setting, we apply known results to provethat strong tractability and tractability in the class $\lall$ are equivalent. This holdsif and only if $\a>0$ and the sum-exponent $s_{\g}$ of weights is finite, where $s_{\g}= \inf\{s>0 : \xxsum_{j=1}^\infty\g_j^s\,<\,\infty\}$.In the worst case setting for the class $\lstd$ we must assume that $\a>1$ to guarantee thatfunctionals from $\lstd$ are continuous. The notions of strongtractability and tractability are not equivalent. In particular,strong tractability holds if and only if $\a>1$ and$\xxsum_{j=1}^\infty\g_j<\infty$.In the randomized setting, it is known that randomization does nothelp over the worst case setting in the class $\lall$. For the class$\lstd$, we prove that strong tractability and tractabilityare equivalent and this holds under the same assumptionas for the class $\lall$ in the worst case setting, that is,if and only if $\a>0$ and $s_{\g} < \infty$.In the quantum setting, we consider only upper bounds for the class$\lstd$ with $\a>1$. We prove that $s_{\g}<\infty$ implies strongtractability. Hence for $s_{\g}>1$, the randomized and quantum settingsboth break worst case intractability of approximation forthe class $\lstd$. We indicate cost bounds on algorithms with error atmost $\e$. Let $\cc(d)$ denote the cost of computing $L(f)$ for$L\in \lall$ or $L\in \lstd$, and let the cost of one arithmetic operation be taken as unity. The information cost bound in the worst case setting for the class $\lall$ is of order $\cc (d) \cdot \e^{-p}$with $p$ being roughly equal to $2\max(s_\g,\a^{-1})$.Then for the class $\lstd$in the randomized setting, we present an algorithm with error at most $\e$ and whose total cost is of order $\cc(d)\e^{-p-2} + d\e^{-2p-2}$, which for small $\e$ is roughly$$d\e^{-2p-2}.$$ In the quantum setting, we present a quantum algorithm with error at most $\e$ that uses about only  $d + \log \e^{-1}$ qubitsand whose total cost is of order$$(\cc(d) +d)   \e^{-1-3p/2}.$$ The ratio of the costs of the algorithms in the quantum setting and the randomized setting is of order$$\frac{d}{\cc(d)+d}\,\left(\frac1{\e}\right)^{1+p/2}.$$Hence, we have a polynomial speedup of order $\e^{-(1+p/2)}$.We stress that $p$ can be arbitrarily large, and in this casethe speedup is huge.

Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers