Understanding the capacity of quantum circuits through the lens of approximation theory is essential for evaluating the complexity of quantum circuits required to solve various problems in scientific computation. We design quantum circuits capable of approximating d-dimensional functions within the Korobov function space. This is achieved by leveraging the quantum signal processing (QSP) and the linear combination of unitaries (LCU) algorithms to build quantum circuits that output Chebyshev polynomials. We also present a quantitative analysis of the approximation error rates and evaluates the computational complexity of implementing the proposed circuits. Since the Korobov function space is a subspace of the certain Sobolev spaces, our work develops a theoretical foundation for implementing a large class of functions suitable for applications on a quantum computer.Understanding the capacity of quantum circuits through the lens of approximation theory is essential for evaluating the complexity of quantum circuits required to solve various problems in scientific computation. We design quantum circuits capable of approximating d-dimensional functions within the Korobov function space. This is achieved by leveraging the quantum signal processing (QSP) and the linear combination of unitaries (LCU) algorithms to build quantum circuits that output Chebyshev polynomials. We also present a quantitative analysis of the approximation error rates and evaluates the computational complexity of implementing the proposed circuits. Since the Korobov function space is a subspace of the certain Sobolev spaces, our work develops a theoretical foundation for implementing a large class of functions suitable for applications on a quantum computer.

arXiv:2404.14570Apr 22, 20240 citations

Numerical integration in $\log$ -Korobov and $\log$ -cosine spacesNumerical integration in $\log$-Korobov and $\log$-cosine spaces

Josef Dick, Peter Kritzer, Gunther Leobacher +1 more

QMC rules are equal weight quadrature rules for approximating integrals over $[0,1]^s$ . One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on $[0,1]^s$ with square integrable partial mixed derivatives of order $α$ . Using Parseval's identity, this smoothness can be defined for all real numbers $α> 1/2$ . This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with $α$ arbitrarily close to $1/2$ . To obtain such estimates we introduce a $\log$ -scale for functions with smoothness close to $1/2$ , which we call $\log$ -Korobov spaces. We show that lattice rules can be used to obtain an integration error of order $\mathcal{O}(N^{-1/2} (\log N)^{-μ(1-λ)/2})$ for any $1/μ<λ\le 1$ , where $μ>1$ is a power in the $\log$ -scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights $(γ_j)_{j \in \mathbb{N}}$ . It is known that if $\sum_{j=1}^\infty γ_j^τ< \infty$ for some $1/(2α) < τ\le 1$ one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where $τ$ is close to $1/(2 α)$ , namely we show dimension independent error bounds under the condition that $\sum_{j=1}^\infty γ_j \max\{1, \log γ_j^{-1}\}^{μ(1-λ)} < \infty$ for some $1/μ< λ\le 1$ . The essential tool in our analysis is a $\log$ -scale Jensen's inequality. The results described above also apply to integration in $\log$ -cosine spaces using tent-transformed lattice rules.QMC rules are equal weight quadrature rules for approximating integrals over $[0,1]^s$. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on $[0,1]^s$ with square integrable partial mixed derivatives of order $α$. Using Parseval's identity, this smoothness can be defined for all real numbers $α> 1/2$. This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with $α$ arbitrarily close to $1/2$. To obtain such estimates we introduce a $\log$-scale for functions with smoothness close to $1/2$, which we call $\log$-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order $\mathcal{O}(N^{-1/2} (\log N)^{-μ(1-λ)/2})$ for any $1/μ<λ\le 1$, where $μ>1$ is a power in the $\log$-scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights $(γ_j)_{j \in \mathbb{N}}$. It is known that if $\sum_{j=1}^\infty γ_j^τ< \infty$ for some $1/(2α) < τ\le 1$ one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where $τ$ is close to $1/(2 α)$, namely we show dimension independent error bounds under the condition that $\sum_{j=1}^\infty γ_j \max\{1, \log γ_j^{-1}\}^{μ(1-λ)} < \infty$ for some $1/μ< λ\le 1$. The essential tool in our analysis is a $\log$-scale Jensen's inequality. The results described above also apply to integration in $\log$-cosine spaces using tent-transformed lattice rules.

arXiv:1411.2715Nov 11, 20140 citations

On Quantum Circuits and Back Propagation

Amitesh Kumar Singam

Jan 1, 20260 citations

A note about EC- $(s,t)$ -weak tractability of multivariate approximation with analytic Korobov kernelsA note about EC-$(s,t)$-weak tractability of multivariate approximation with analytic Korobov kernels

Heping Wang

This note is devoted to discussing multivariate approximation of continuous functions on $[0,1]^d$ with analytic Korobov kernels in the worst and average case settings. We only consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We study EC- $(s, t)$ -weak tractability under the absolute or normalized error criterion, and obtain necessary and sufficient conditions for $0<\min(s,t)<1$ and $\max(s,t)\le 1$ in the worst case setting and for $s,t>0$ in the average case setting.This note is devoted to discussing multivariate approximation of continuous functions on $[0,1]^d$ with analytic Korobov kernels in the worst and average case settings. We only consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We study EC-$(s, t)$-weak tractability under the absolute or normalized error criterion, and obtain necessary and sufficient conditions for $0<\min(s,t)<1$ and $\max(s,t)\le 1$ in the worst case setting and for $s,t>0$ in the average case setting.

arXiv:1808.01470Aug 4, 20180 citations

Numerical integration in

\log

-Korobov and

\log

-cosine spaces

QMC rules are equal weight quadrature rules for approximating integrals over

[0,1]^s

. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on

[0,1]^s

with square integrable partial mixed derivatives of order

α

. Using Parseval's identity, this smoothness can be defined for all real numbers

α> 1/2

. This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with

α

arbitrarily close to

1/2

. To obtain such estimates we introduce a

\log

-scale for functions with smoothness close to

1/2

, which we call

\log

-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order

\mathcal{O}(N^{-1/2} (\log N)^{-μ(1-λ)/2})

for any

1/μ<λ\le 1

, where

μ>1

is a power in the

\log

-scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights

(γ_j)_{j \in \mathbb{N}}

. It is known that if

\sum_{j=1}^\infty γ_j^τ< \infty

for some

1/(2α) < τ\le 1

one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where

τ

is close to

1/(2 α)

, namely we show dimension independent error bounds under the condition that

\sum_{j=1}^\infty γ_j \max\{1, \log γ_j^{-1}\}^{μ(1-λ)} < \infty

for some

1/μ< λ\le 1

. The essential tool in our analysis is a

\log

-scale Jensen's inequality. The results described above also apply to integration in

\log

-cosine spaces using tent-transformed lattice rules.

A note about EC-

(s,t)

-weak tractability of multivariate approximation with analytic Korobov kernels

This note is devoted to discussing multivariate approximation of continuous functions on

[0,1]^d

with analytic Korobov kernels in the worst and average case settings. We only consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We study EC-

(s, t)

-weak tractability under the absolute or normalized error criterion, and obtain necessary and sufficient conditions for

0<\min(s,t)<1

and

\max(s,t)\le 1

in the worst case setting and for

s,t>0

in the average case setting.