Non-asymptotic Approximation Error Bounds of Parameterized Quantum Circuits
Authors: Zhan Yu
Qiuhao Chen
Yuling Jiao
Yinan Li
Xiliang Lu
Xin Wang
Jerry Zhijian Yang
Venue: NeurIPS 2024 spotlight (2024)
Keywords: quantum machine learning
parameterized quantum circuits
expressivity
universal approximation
approximation error bound
Primary area: learning_theory

Abstract: Understanding the power of parameterized quantum circuits (PQCs) in accomplishing machine learning tasks is one of the most important questions in quantum machine learning. In this paper, we focus on the PQC expressivity for general multivariate function classes. Previously established Universal Approximation Theorems for PQCs are either nonconstructive or assisted with parameterized classical data processing, making it hard to justify whether the expressive power comes from the classical or quantum parts. We explicitly construct data re-uploading PQCs for approximating multivariate polynomials and smooth functions and establish the first non-asymptotic approximation error bounds for such functions in terms of the number of qubits, the quantum circuit depth and the number of trainable parameters of the PQCs. Notably, we show that for multivariate polynomials and multivariate smooth functions, the quantum circuit size and the number of trainable parameters of our proposed PQCs can be smaller than the deep ReLU neural networks. We further demonstrate the approximation capability of PQCs via numerical experiments. Our results pave the way for designing practical PQCs that can be implemented on near-term quantum devices with limited resources.

Non-asymptotic Approximation Error Bounds of Parameterized Quantum Circuits
Zhan Yu Qiuhao Chen Yuling Jiao Yinan Li Xiliang Lu Xin Wang' Jerry Zhijian Yang
School of Mathematics and Statistics, Wuhan University, Wuhan 430072, China
Centre for Quantum Technologies. National University Singapore. 117543, Singapore Hubei Key Laboratory of Computational Science, Wuhan 430072, China Thrust of Artificial Intelligence, Information Hub, Hong Kong University of Science and Technology (Guangzhou), Guangzhou 51 511453, China
Abstract
Parameterized quantum circuits (PQCs) have emerged as promising approach for quantum neural networks. However, understanding their expressive power in ac- complishing machine learning tasks remains a crucial question. This paper inves- tigates the expressivity of PQCs for approximating general multivariate function classes. Unlike previous Universal Approximation Theorems for PQCs, which are either nonconstructive or rely on parameterized classical data processing, we ex- plicitly construct data re-uploading PQCs for approximating multivariate polyno- mials and smooth functions. We establish the first con-asympooiic approximation error bounds for these functions in terms of the number of qubits, quantum cir- cuit depth, and number of trainable parameters. Notably, we demonstrate that for approximating functions that satisfy specific smoothness criteria, the quantum cir- cuit size and number trainable parameters of our proposed PQCs can be smaller than those of deep ReLU neural networks. We further validate the approximation capability of PQCs through numerical experiments. Our results provide theo- retical foundation for designing practical PQCs and quantum neural networks for machine learning tasks that can be implemented on near-term quantum devices, paving the way for the advancement of quantum machine learning.
Introduction
In quantum computing, one key area is to investigate if quantum computers could accelerate clas- sical machine learning tasks in data analysis and artificial intelligence, giving rise to an interdisci- plinary field known as quantum machine learning [1]. As the quantum analogs of classical neural networks, parameterized quantum circuits (PQCs) [2] have gained significant attention as a promi- nent paradigm to yield quantum advantages. PQCs offer concrete and practical way implement quantum machine learning algorithms in noisy and intermediate-scale quantum (NISQ) devices [3], rendering them well-suited for diverse array of tasks [4-11].
To establish the practical significance of quantum machine learning, an ongoing pursuit demon- strate their superiority in solving real-world learning problems compared to classical learning mod- els, including the most commonly used deep neural networks [12]. Typical supervised learning tasks, such image classification and price prediction, aim to construct a model to learn mapping
'..Y. and Q.C. contributed equally to this work
Yinan, Li www.edu.cr 'zjyang.man math @ whu.edu.cn
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

function from the input to output via training data sets. Essentially, the goal is to approximate multi- variate functions. This viewpoint leads to the celebrated Universal Approximation Theorem [13, 14), which limits what neural networks can theoretically learn. Recently, powerful tools from approxi- mation theory have been utilized to establish fruitful mathematical framework for understanding the "black magic" of deep learning by establishing non-asymptotic approximation error bounds of deep neural networks in terms of the width, depth, number of weights (neurons) and function com- plexities, see e.g. Ref'. [15-25] and references therein.
Substantial investigations have showcased the power of quantum machine learning for specific learn- ing tasks [26-33]. A fundamental question is whether the expressivity of quantum machine learning models is as powerful as, or is more powerful than, the expressivity of classical machine learning models. This can be illustrated by proving universal approximation theorems for PQCs [34-41], indicating that there exist PQCs with suitable parameter configurations to approximate target func- tions up to given approximation accuracy. This will justify the power of PQCs to solve supervised learning tasks in a mathematical way. To further investigate whether PQCs are more expressive than the classical models or not, it is natural to examine the PQC approximation performance by estab- lishing approximation error bounds for important function classes. Such quantitative error bounds are less known in the quantum setting, because the hypothesis functions generated by PQCs are more complicated than those generated by classical neural networks.
The difficulties of analyzing the PQC approximation performances can be partially overcome by allowing parameterized classical data processing. Namely, trainable parameters are allowed not only in the quantum gates in PQCs but also in the classical data pre- and post-processing. This allows one to prove approximation error bounds following classical strategies [39, 41, 40]. For instance, Goto et al. [39] proved PQC approximation error rate for Lipschitz continuous functions in terms of the number of qubits and trainable parameters by incorporating trainable parameters in the measurement post-processing phase; similar results can also be obtained by utilizing Tensor-Tras Train Network [41] or by linear transformations to preprocess the classical data.
However, utilizing parameterized classical data processing makes it hard to distinguish whether the expressive power of PQCs comes from the classical or quantum parts. In fact, parameterized classical data processing enables one to directly convert the hypothesis functions generated by the quantum models into hypothesis functions generated by classical ones and adapt expressivity results for classical machine learning models to extract the expressivity of such quantum models. As a consequence, the resulting PQCs have very simple structures and short depth. remains unknown whether one can prove approximation error bounds for PQCs without parameterized classical data processing. On the other hand, Zhao et al. [42] proved exponential lower bounds on the number of trainable parameters (in terms of the number of variables) needed for approximating bounded Lips- chitz continuous functions using PQCs without parameterized classical data processing. illustrating that using PQCs to approximate Lipschitz functions still suffers from the curse of dimensionality (CoD) met by classical deep neural networks [43]. However, this does not rule out the possibility that one can achieve the same approximation rate with PQCs of smaller size compared to classical deep neural networks.
In this paper, we explicitly construct the first PQCs without parameterized classical data process- ing for approximating multivariate polynomials and smooth funetions; a glance at these constructed PQCs is illustrated in Fig. 1. This eliminates the ambiguity regarding whether the expressivity orig- inates from classical or quantum parts. We also establish non-asymplotic PQC approximation error bounds, in the sense that the PQC approximation performances are characterized in terms of the number of qubits (width), the depth of PQCs, the number of trainable parameters/gates (parameter count), and the function complexities. These results enable to compare the approximation power of PQCs with that of classical neural networks. Notably, we show that for multivariate smooth functions, the quantum circuit size and the number of trainable parameters of our proposed PQCs demonstrate an improvement over the prior result of deep ReLU neural networks [21]. one of the most commonly used neural network family in classical deep learning theory. Our proposed PQCs not only possess the universal approximation property but also achieve parameter efficiency com- parable classical neural networks, potentially leading more efficient and scalable quantum machine learning algorithms for real-world tasks.
2

---

Linear combination unitaries
0.5
MmM
Input
0.8
-05
A,2ha
F29
(.00)
FDD
Fi?
(.00)
-05
-1.0
0.0
02
04
0.0
02
0.
0.5
100
0.5
Localization
A
0.5
12.00 (1.00
-05
-0.6
-10
0.0
02
0.4
06
1.0
RL0R
0.0
02
04
00
68
1.0
Figure I: Overview of PQCs for approximating continuous functions. (a) Flowchart illustrating the strat- egy for using PQCs approximate continuous functions via implementing Bernstein polynomials. The input data is encoded into the PQC through (zx). with the PQC (blue background) capable of representing parity- constrained polynomials up degree (as is encoded three times). The technique linear combination of unitaries (LCU) is used to aggregate these polynomials together. The output of PQC derives from measurement with a specific observable. Fine-tuning trainable parameters in Rz gates yields polynomial output depicted in the right panel. (b) Flowchart illustrating the strategy of approximation via local Taylor expansions. We first apply PQC localize the input domain into K 5 regions. For example, for input E [0.8, 1]. PQC outputs 0.8 as a fixed point. Then æ -x will be fed into new PQC for implementing the local Taylor expansions at the fixed point u'. forming a nesting architecture. Control gates with pink backgrounds implement the Taylor coefficients. Fine-tuning trainable parameters in Rx and Rz gates yields piecewise polynomial with degree 3 that approximates the target function.
2 Preliminaries
Quantum states. The basic unit of information in quantum computing is the qubit, which can exist superposition of the states 0 and 1 simultaneously, unlike classical bits that are restricted to either 0 or 1. A pure quantum state in the d-dimensional Hilbert space Cd is represented by the Dirac notation (o). 'Te conjugate transpose of (o) denoted by (ø). The inner product of two quantum states (Ø) and (&b) is written as (ńl1g). An important property is that (o) 1 for any pure state (zb). By convention, the computational basis states for single-qubit systems are written as 10) [1, 0j"" and [1] [0, 1J" where the superscript T denotes the transpose. For n-qubit systems, the computational basis states are expressed as [j) E [1)] where & denotes the tensor product operation.
Quantum gates. Quantum gates are building blocks of quantum circuits operating on quantum states. Unlike classical gates, quantum gates are reversible and described as unitary matrices. In quantum machine learning, common parameterized quantum gates include single-qubit Pauli rota- tion gates Rx(0), 00/22 Ry (0) 000/22 and Rz( e -6X/2 that rotate quantum state through angle 0 around the corresponding axis, where the three Pauli operators are defined as:
0
x
Y =
0
-
where i represents the imaginary unit. Commonly used two-qubit quantum gates include CNOT gate that flips the target qubit if and only if the the control qubit is in [1).
Quantum measurement The quantum measurement is a procedure manipulating quantum sys- tem to extract classical information. The simplest measurement is the computational basis measure- ment: For a single-qubit system (5) = a 0) + 3 [1), the outcome is either (0) with probability |a | or [1) with probability | These measurements project the quantum state onto the measured basis, collapsing the state itself. Observables, represented by Hermitian operators, correspond to measur- able quantities in quantum system like energy or position. Each observable has a set of possible outcomes (eigenvalues) and corresponding states (eigenvectors). When a measurement servable is performed, the outcome is one of the eigenvalues, and the state of the system collapses
an ob-
3

---

to the corresponding cigenvector. If we are measuring a state (&)) using observable O the expected value of outcome is (ib O (.)). This represents the average result one would expect from repeated measurements on identically prepared systems. A comprehensive introduction to the fundamental notations and concepts of quantum computation can be found in [44].
Data re-uploading PQCs. The PQCs we shall construct in this paper are of data re re-uploading type [11], i.e., consisting of interleaved data encoding circuit blocks and trainable circuit blocks. More precisely, let be the input data vector and A (0o.... 0r. be a set of trainable parameter vectors. S(x) is quantum circuit that encode a and V(0,) ) is trainable quantum circuit with trainable parameter vector 0,. An L-layer data re-uploading PQC can be then expressed as
L
Uo(x)= - V((o) II (())
(1)
j=1
Applying (a) an initial quantum state and measuring the output states provides way to express functions on æ:
(a) = (0) (a)))) 10),
where O is some Hermitian observable. The approximation capability of the PQC (o can be characterized by the classes of functions that (ar) can approximate by tuning the trainable parameter vector 0. We then turn an example of single-qubit PQCs approximating univari- ate functions. For the input x E [-,, we utilized the Pauli X basis encoding scheme [10] and defined the data encoding operator as a Pauli X rotation S(x) == e @(acccos=)) Interleav- ing the data encoding unitary S(x) with some parameterized Pauli Z rotations (2) gives the circuit of data re-uploading PQC for one variable as U2( = (2((0) II S(x) (0,) where o = -oo....,,)) 0z) RR++1 is a set of trainable parameters. Utilizing results from quantum signal processing [45-47], there exists 0 E RL++1 such that (a(r) implements polynomial transformations p(x) E R[х] p(x)= = (+)(+(x)|++ )+} for any E [-1, if and only if the degree of p(x) is at most L, the parity of p(x) is mod 4, and [o())| < 1 for all æ E [-11, 1]. Then, univariate functions that could be approximated by the specified polynomial p(z)) could also be approximated by the PQC (z). Other than the real polynomials, there are also types of single-qubit PQC with Pauli Z basis encoding that could implement complex trigonometric polynomials [37].
3 Expressivity of PQCs for multivariate continuous functions
3.1 Explicit construction of PQCs for multivariate polynomials
Although PQCs for approximate univariate functions have been constructed and analyzed, they have not yet been generally extended to the case of multivariate functions. Current proofs of universal approximation for multivariate functions are nonconstructive [34, 38] and require arbitrary circuit width, arbitrary multi-qubit global parameterized unitaries, and arbitrary observables. Goto et al. [39] proposed several constructions for approximating multivariate functions with the assistance of parameterized data pre-processing and post- post-processing, yielding a quantum -enntum-enhanced hybrid scheme rather than a purely quantum setting.
We now move to our explicit construction of PQCs for multivariate polynomials. A multivariate polynomial with d variables and degree is defined as p(æ)) == "|jaal So Ca where aa af'22" ........ x224 To implement the multivariate polynomial p(x), we first build a PQC express monomial x The construction is trivial extension of the univariate case: We simply apply the single-qubit PQC with Pauli X basis encoding on each x; to implement x. for S j S d, respectively. The coefficient Cox E E could be implemented by any of these PQCs. Thus we could construct a PQC (*) = Ø ==1 Uo, (2z) such that (+ (+ (x))+) &d = c The depth of the PQC (x)) is at most 28 + 1, the width is at most d, and the number of parameters is at most + d.
A polynomial p(r) has parity 0 if all coefficients corresponding to odd powers of x are 0, and similarly p(x) has parity 1 if all coefficients corresponding to even powers of x are 0.

---

Having PQCs that implement monomials, the next step is to aggregate monomials to implement the multivariate polynomial. natural idea to sum the monomial PQCs together U,(2)
E || Ex (x)). However, the addition operation in quantum computing is non-trivial as the sum of unitary operators is not necessarily unitary. To overcome this issue, we utilize linear combination of unitaries (LCU) [48] to implement the operator (x) on a quantum computer. Realizing the linear combination of PQCs (x) requires applying multi-qubit control on each (x)), which could be further decomposed into linear-depth quantum circuits of CNOT gates and single-qubit rotation gates without using any ancilla qubit [49]. Then can obtain the polynomial p(z)
(x))) Sd by applying the Hadamard test on the LCU circuit. Summarizing the above, we establish the following theorem about using PQCs to implement multivariate polynomials. A formal description of such PQCs is given in Appendix B.
Theorem 1. For any multivariate polynomial p(z:) with d variables and degree such that [p(x)]
1 for [0, 1]s, there exists a PQC Wp(.r) such that
Sw, == (0) (x)) W (0) p(xr)
(3)
where 70() is the Pouli Z observable on the first qubit. The width of the PQC is O(d- s+ log d), the depth is (s22d (log s + s log d)), and the number of parameters O(dd (s + d)).
Note that the initial state in the Hadamard test is [0] @d since |+) @d could be easily prepared by
applying Hadamard gates on (0) ad Measuring the first qubit of (x(x) for ( times is needed
to estimate the value of p(æ) up to an additive error e. We could further use the amplitude estimation
algorithm [50] to reduce the overhead while increasing the circuit depth by O
3.2 PQC approximation for continuous functions
Polynomials play central role in approximation theory. The celebrated Weierstrass approximation theorem (see e.g. [51, Sec. 10.2.2l) indicates that polynomials are sufficient to approximate continu- univariate functions. For multivariate functions, their approximation can be implemented using Bernstein polynomials [52, 53]. We shall apply these results to prove PQC approximation error bounds for multivariate Lipschitz continuous functions.
For d- d-variable continuous function f [0, 1]d + R, the multivariate Bernstein polynomial with degree E N+ of is defined as
n
(x) = Σ
71
x.2) m
(4)
R1
k==0
j=l
where &- = (kI....,,kal ka) E [o.....n'' nnd. is known that Bernstein polynomials converge uniformly to f on [0, 1] as n - do [52, 53]. The PQC constructed in Theorem 1 could implement the Bernstein polynomial with proper rescaling, which implies that the PQC is universal approximator for any bounded continuous functions.
Theorem 2 (The Universal Approximation Theorem of PQC). For any continuous function f [0, 1] + [-1, given an ε >> O. there exist an n N and PQC Wo(m:) with width Odd n), depth (dn log n) and the number of trainable parameters (dda)) such that
- fw. S
(5)
for all x E [0, 1]d, where fw,(x)) = (z) WT(2) 10).
Theorem 2 serves the quantum counterpart to the universal approximation theorem of classi- cal neural networks. Moreover, the PQCs that universally approximate continuous functions are explicitly constructed without any impractical assumption, improving the previous results pre- sented in Refs. [34, 38). Moreover, for continuous functions f satisfying the Lipschitz condition, [f()) - f(y] S f||ar y|| for any æ, y. the approximation rate of Bernstein polynomials could be quantiratively characterized in terms of the degree the number of variables d and the Lipschitz constant l [53]. Thus non-asymptotic error bound for PQC approximating Lipschitz continuous functions could be obtained as follows.
5

---

Theorem 3. Given a Lipschitz continuous function f 10, 1] - [-1.1] with a Lipschitz con-
stant L, for any E > and n E N, there exists PQC Wo(x)) with such that fw, (x) = (0) (x) (2x) (0) satisfies
(f(z) - (w)(()) S Se+ + ++
8²
-w.
S
d2d ns²
(6)
for all x E [0, 1]s. The width of the PQC lo),, the depth is Oddn* log 1.), and the number of parameters is (ddn).
We prove these theorems in Appendix C. Although a quantitative approximation error bound is char- acterized in Theorem 3, we could find that n must be sufficiently large to obtain good precision, yielding an extremely deep PQC. This inefficiency is essentially due to the intrinsic difficulty of us- ing a single global polynomial to approximate continuous function uniformly. possible approach that may overcome the obstacle is to use local polynomials to achieve piecewise approximation, which we will discover in the next section.
3.3 PQC approximation for Hölder smooth functions
To achieve a piecewise approximation of multivariate functions, we follow the path of classical deep neural networks approximation [18, 25], which utilizes multivariate Taylor series to approximate target functions small local regions.
We focus on Hölder smooth functions. Let B = s + r > O, where r E (0, and E N+. For finite constant Bu > 0, the 3-Hölder class of functions 76 ([0, 1] BB) is defined as
100 f(x)
8 [())
H (10, 11 Bo) f: [0, - max ||00 fll>> S Bo: max sup | 1 = 1= wzy
Bo
a a
x y
(7)
where 8 = a...... 8 for a = (oi,...,, Oa) E No. We note that Hölder smooth functions are natural generalizations of various continuous functions: When B E (0, f is Hölder continuous with order 33 and Hölder constant Bo: when 3 = 1, f is Lipschitz continuous with Lipschitz constant Bo: when < N. f E C*((O, 1]d), the class of s-smooth functions whose s-th partial derivatives exist and are bounded. As shown in Petersen and Voigtlaender [18], for any 3-Hölder smooth function f E *H000, 1ja, Bo), its local Taylor expansion some fixed point æo [0, 1j satisfies
ja (x00)
f(x) Σ |
(x Io) S d' x zoll2
(8)
ad
for all x E (0, 173, where ad = an!... aal. Next, we show how to construct PQCs to implement the Taylor expansion of 3- 3-Hölder functions in the following three steps.
Localization. To utilize the Hölder smoothness, we need to first localize the entire region [0. 1]d The motivation of localization is to determine the local point zo in Eq. (8) so that the distance between and To is fairly small. An intuitive configuration is illustrated in Fig. 2, where the stars represent the local points. Given K E N and A E (0, 3k for each {0, 1. 1....... K 1]d. we define
1
(m....., na)
Q, = {xr (ZI,,... ..g.....20 xa) : 2h E TE T) A - lncck-
(9)
K
K
By the definition of 2,, the region [0, 1]d is approximately divided into small hypercubes Un Qn and some trifling region A(d, K, A) = [o, 1]d (U,, Qn), as illustrated in Fig. 2.
We construct a PQC that maps all æ E Q,, to some fixed point t,, æ in Qn, i.e., approximating the piecewise-consteee constatt function D(x) = K
if x E Qn- We describe our construction for 1, where D(x) = & if x E I k+1 A 11<k-1] for k = O...., ......K K - 1. The multivariate case K
&
could be naturally generalized by applying D(x) to each variable xy. The idea is construct polynomial that approximates the function ((x) based on the polynomial approximation to the sign function [54], which a single-qubit PQC can then implement. Generalizing to the multivariate localization, there exists PQC (x( of depth O log K and width (dd) such that the output
Swp (xr) maps x to the corresponding fixed point T. with precision e. We can obtain an estimation of n using [K fw, (z)).

---

Q. for for 3,
On 1 (0, (..1.2.3,4)
Trifling region A,1,5, A)
Triffing region A(2.
Fixed points for each
Fixed points Zap for each 1)
0.8
0.6
A
0.2
A
0.0
0.4
0.2
Figure 2: An illustration of localization. The left panel demonstrates the localization U, Q, for K = 5 and d 1. The right panel shows the of localization for K and d The "volume" of the trifling region (d, K, A) is no more than dKA.
Implementing the Taylor coefficients. Next, we use PQC to implement the Taylor coefficients Sn.a = 8 f(2n) [-1, 1] for each 77 = (m..... Ma)
1]d and a, which is essentially -pintt-fttingg problem. Then we could construct a PQC US. E., mXn @ Rx (6,,a) such that (17, 0| Us |n. 0) Sn.o. where |n) = (m) @ ... @ Iπa) and 0, = 2 arccos(En,a)) The depth of U is ((K)), the width is Oo K), and the number of parameters is O(K)). Note that the state (n) can be prepared using basis encoding on the provided r [K fww (æ)] from the localization step.
111
ad!
Implementing multivariate Taylor series. To implement the multivariate Taylor expansion of function at some fixed point Tyy, we first build PQC to represent single term in the Taylor series, which could be done by combining the PQC. which implements the Taylor coefficients and the PQC which implements monomials, i.e., constructing U/ (æ)) == U ss U (x= (()))),)
..y) The depth of U (æ) O(K" + s). the width Od K), and the number of parameters is at most K + The next step aggregate single Taylor terms together to implement the truncated Taylor expansion of the target function. We use LCU to construct the PQC (2, 2,,) == || U (x) ( so that we can
implement the Taylor expansion of the function f at point Tn as (n). (++) @d U,(2, 2,,) In, 0) @d
We construct nested PQC U, fw, such that for any input æ, the corresponding fixed point could be determined by the localization PQC. Such a PQC could be used, together with the Hadamard test, to approximate Hölder smooth functions. In particular, we prove the approximation error bound of our constructed PQC based on the error rate of Taylor expansion in Eq. (8).
Theorem 4. Given function f E H. ([0, 1]d 1) with 3 = + E (0, 1] and E N+ for any K N and A (0, 3K) there exists a PQC (x(w) such that fw, (x) = (0) W x 2() W. (0) satisfies
(f(x) - fw. S 8=+8/2
(10)
for i E Un Qn The width of the PQC O(dlog K K+log 8+ s d), the depth is O K <gogo 8 log d - dog K)) + 1 log K), and the number of parameters O(sd' (s + d + Kd) + $ log K).
The proof can found in Appendix D. Note that the PQC Theorem consists of two nested parts and its depth is counted as the sum of two PQCs for simplicity. We have established the uniform convergence property PQCs for approximating Hölder smooth function on [0, 1]d except for the trifling region A(d, K, A). The Lebesgue measure of such trifling region is more than
7

---

dKA. We can set A = K- with no influence on the size of the constructed PQC, and similar approximation error bound in the entire region [0, 1] under the L distance could be obtained.
4 Numerical experiments
This section presents numerical experiments to illustrate the expressivity of our proposed PQCs in approximating multivariate functions. We focus approximating bivariate polynomial function
(2² + y 1.5 + (x + y² + x)² + x 0.5m)²
[(x,))
over the domain (z. [0, 1J2. The approximation process involves two separate steps: (1) Learn- ing piccewise-constant function, D(x) K if x I + using single-qubit PQC, where K' E N+ determines the number of intervals for the piecewise-constant function. (2) Learning the Taylor expansion of (xx,)) y) using multi-qubit PQCs based on Theorem 4. Both learning processes Gold 6248 2.50 GHz Intel(R) Xcon(R) CPU.
implemented
We randomly sample 200 data points within the domain [0, 1] create training and test datasets for ((x). A single-qubit PQC with adjustable parameters L 764 (I. 996) is used to learn D(x) with K (K 10). Each parameter of the PQC is randomly initialized within the range 10, We use the Adam optimizer [55] with learning rate of 0.01 to minimize the Mean Squared Error (MSE) loss function during training. The training process was limited maximum of 300 iterations with batch size of 100 data points. Early termination occurred if the MSE reached below 10-4. The achieved MSE on the test data was 3.57 10-4 (K 2) and 1.04 x 10 (K = 10). The numerical results are visualized in Fig. 3.
1.0
K-10
0.8
K=2
POC output
0.6
0.4
0.2
0.0
0.2
0.4
0.6
0.8
1.0
Figure 3: Simulation results of localization. We single-qubit PQCs approximate the localization
function ((x) for = and respectively.
Similar the previous step, we randomly sampled 200 data points within the domain [0, 1]2 to create training and test datasets for f(x,, y)- A nested PQC structure was designed. It combined 12 two-qubit PQCs with depth 2, allowing the approximation of a degree-4 polynomial through combination of lower-degree ones. Additionally, Taylor coefficients were stored in separate matrix of size K2 x 12. The number of trainable parameters varied from 120 (K 2) to 1272 (K 10), each initialized randomly from [0, r]. The Adam optimizer with a learning rate of 0.01 was used to minimize the MSE loss during training. The training was limited to 500 iterations with a batch size of 100, with early termination for MSE below 10-A, The achieved MSE on the test data was 2.22 x 10-4 (K = 2) and 9.82 x 10 (K = 10). Fig. 4 visualizes the results. As K increases, the PQC demonstrates improved approximation performance, aligning with the theoretical findings.
5 Discussion
To the best of our knowledge, our results establish the first explicit PQC constructions for approx- imating Lipschitz continuous and Hölder smooth functions with quantitative approximation error bounds. These results open up the possibility of comparing the size of PQCs and the size of classi- cal deep neural networks for accomplishing the same function approximation tasks and see if there

---

K=2
K=
target function
0.70
output
0.70
PQC oulput
0.70
0.86
0.66
0.66
0.58
0.58
0.58
0.0
0.0
0.0
0.4
0.4
0.6
0.2
0.4
0.8
0.2
0.4
0.6
0.2
Figure 4: Simulation results for learning far v)- The left two panels are derived by interpolating and smoothing the output values of PQC on 100 test data points.
any quantum advantage in terms of the model size and the number of trainable parameters. Here, we mainly focus on the comparison with the results of approximation errors of classical machine learning models. classical deep learning, the deep feed-forward neural network (FNN) equipped with the rectified linear unit (ReLU) activation function is one of the most commonly used models. The quantitative approximation error bounds of ReLU FNNs for approximating continuous func- tions have been recently established, including the nearly optimal approximation error bounds of ReLU FNNs for smooth functions [21]. We briefly compare the approximation errors of PQCs and ReLU FNNs in terms of width, depth and the number of trainable parameters, Detailed comparisons can be found in Appendix E.
We consider multivariate smooth functions in (20, 1] (the unit ball of C*([O, 1] with smooth index N as the target functions in our comparison. Note that smooth functions with smooth index are exactly (s 1)-Hölder smooth functions by definition. For simplicity, we first show case of 8 2. To achieve the same approximation emor (say some constant), we need to set Ko = (d VE) for the constructed PQCs from Theorem 4 and Kc ((24/2 /V) for the constructed near-optimal ReLU FNNs from Ref. [21]. Substituting the choices of K's ' in the sizes of PQCs and ReLU FNNs, we have
Width of PQC x Depth of PQC 0(
d Kd
0
E E-//4
(1I)
Width of FNN Depth of FNN 2d+3
K
d/2
-dlog
One can obtain a similar relation for the number of required parameters in PQCs and ReLU FNNs for approximating smooth functions and extend these results to any < 8 < which holds relevance in numerous real-world applications (e.g., the input dimension d is 784 for the MNIST dataset and is 150 528 for the ImageNet dataset [56]. and empirically s S 10). Therefore, to achieve the same approximation error, the required quantum circuit size and number of parameters of PQCs exponentially smaller than the required network size and number of parameters ReLU FNNs proposed in Ref. [21]]
Aiming understand and continuously expand the range problems that can be addressed using quantum machine learning, we have demonstrated the approximation capabilities of PQC models supervised learning. We characterized the approximation error of PQCs in terms of the model size, delivering deeper understanding of the expressive power of PQCs that is beyond the univer- sal approximation propertics. With these results, we can unlock the full potential of these models results with the
and drive advancements in quantum machine learning. Notably, by comparing near-optimal approximation error bound of classical ReLU neural networks, we demonstrate an improvement over the classical models approximating high-dimensional functions that satisfy specific smoothness criteria, quantified by an improvement on the model size and the number of parameters.
Unlike many other investigations in the universal approximation properties of PQC models [26-33], our constructions of PQCs for approximating broad classes of continuous functions do not rely on any impractical assumptions. All the variables take the form of parameters within single-qubit rota- tion gates, avoiding any classical parameterized pre-processing post-processing. Ultimately, our

---

research provides valuable insights into the theoretical underpinnings of PQCs in quantum machine learning and paves the way for leveraging capabilities machine learning for both classical and quantum applications.
In this work, introduce novel nested PQC structure, which significantly improves the approxi- mation capabilities, Future work could focus on exploring more powerful PQC constructions based on our proposed idea and understanding the capabilities and limitations of PQCs more practical tasks even with real-world data. Developing efficient training strategies for PQCs, such as acceler- ated methods that achieve faster convergence rates, will also be interesting.
Acknowledgments and Disclosure of Funding
Part of this work was done when Z.Y. visiting Wuhan University. Z.Y. thanks Patrick Reben- trost for helpful discussions. The authors thank the helpful comments from the anonymous review- ers. This work is supported by the National Key Research and Development Program of China (No. 2024YFE0102500), the National Nature Science Foundation of China (No. 62302346, No. 12125103, No. 12071362, No. 12371424, No. 12371441), the Hubei Provincial Natural Science Foundation of China (No. 2024AFA045) and the "Fundamental Research Funds for the Central Universities".
References
[1] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671):195-200 September 2017. ISSN 1476-4687. doi: 10. 10.1038/aatur223444,
[2] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Science and Technology, 4(4):043001, Novem- ber 2019. ISSN 2058-9565.
doi:
[3] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2:79, August 2018. ISSN 2521-327X. doi: 20-2331/-2018-08-000 URL https:///di..ooo orrooioorg//000 10. 22331/q-2018-082
[4] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549(7671):242-244) 2017. ISSN 1476-4687. doi: 10. 10.10388/aturc23889.
[5] M. Cerezo, Kunal Sharma, Andrew Arrasmith, and Patrick Coles. Variational quantum state cigensolver. npj Quantum Information, 8(1):113, 2022. ISSN 2056-6387. doi: 10.1038/ s4 11534-022-00611-6.
[6] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik. Quantum chemistry in the age of quan- tum computing. Chemical Reviews, 119(1)):08866-100 10. we.102/acs..cemme...000ee.
2019. ISSN 0009-2665. doi:
[7] Xiaoxuan Pan, Zhide Lu, Weiting Wang, Ziyue Hua, Yifang Xu, Weikang Li, Weizhou Cai, Xuegang Li, Haiyan Wang, Yi-Pu Song, Chang-Ling Zou, Dong-Ling Deng, and Luyan Sun. Deep quantum neural networks on superconducting processor. Nature Communications, 14 (1):4006, 2023. ISSN 2041-1723, doi: (0008//41467-02-3999
[8] Wenhui Ren, Weikang Li, Shibo Xu, Ke Wang, Wenjie Jiang, Feitong Jin, Xuhao Zhu, Jiachen Chen, Zixuan Song, Pengfei Zhang, Hang Dong, Xu Zhang, Jinfeng Deng, Yu Gao, Chuanyu Zhang, Yaozu Wu, Bing Zhang, Qiujiang Guo, Hekang Li, Zhen Wang, Jacob Biamonte, Chao Song, Dong-Ling Deng, and H. Wang. Experimental quantum adversarial learning with pro- grammable superconducting qubits. Nature Computational Science, 2(11):111717,, 2022. ISSN 2662-8457. doi: 10. 00088/443588-022-003555
10

---

[9] He-Liang Huang, Yuxuan Du, Ming Gong, Youwei Zhao, Yulin Wu, Chaoyue Wang, Shaowei Li, Futian Liang, Jin Lin, Yu Xu, Rui Yang, Tongliang Liu, Min-Hsiu Hsich, Hui Deng, Hao Rong, Cheng-Zhi Peng, Chao- Yang Lu, Yu-Ao Chen, Dacheng Tao, Xiaobo Zhu, and Jian- Wei Pan. Experimental quantum generative adversarial networks for image generation. Phys. Rev. Appl., 16:024051, Aug 2021. doi: 10. 101.//hsseeeAppliiii 16..Appppee....24400000 16.024051. URL https:
//link. aps org/ wwtp////g/.ooo////////// htt..1////hhsseerpppee....d 16. 12.040551.
[10] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii. Quantum Circuit Learning. Physical Review A, 98(3):333309 September 2018. ISSN 2469-9926, 2469-9934.
doi: 10.1 10.1105/PyssRevA S.w.PPyyyReeA....322...... 98.03330.
[11] Adrián Pérez-Salinas, Alba Cervera-Lierte Elies Gil-Fuster, and José I. Latorre. Data re- uploading for universal quantum classifier. Quantum, 4:226, February 2020. doi: 10.22331/
(-2020-02-06-2266
[12] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436-
444, 2015. ISSN 1476-4687. doi: 110088/aatur114533)
[13] George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989. URL https:: feainkssprigger.co com/
article/10. 1007 /01//////...000////25557777
[14] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):399336,, January 1989. ISSN 08936080, doi:
10. 10.1016/8993-60000899992222 URL https: /et::://innnuuuu elsevier www.cooo//eeeeee coom/eeriieee// pi1/0099360888900000..
[15] A.R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930-945, May 1993. ISSN 1557-9654. doi: N0.1109/18.256670
[16] Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Net- works, 14:1031,,, 2017. ISSN 0893-6080. doi: 00.1016f..eeune22217.7..000
[17] Dmitry Yarotsky. Optimal approximation of continuous functions by very deep ReLU net- works. In Proceedings of the 31st Conference On Learning Theory, pages 539.649. PMLR, July 2018. URL htttttttts::pooeeeee http///oooceee..ee///////. mlr www.mwp........... wwwpp//e///aarosseeeeeees
html.
[18] Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep ReLU neural networks. Neural Networks, 108:296-3300 December 2018. ISSN 0893-6080. doi: ne.10/...eunee.211888.....
[19] Dmitry Yarotsky and Anton Zhevnerchuk. The phase diagram of approximation rates for deep neural networks. In Advances in Neural Information Processing Systems, volume 33, pages 13005-13015. Curran Associates, Inc., 2020. URL https: //ttpee/////ooceinggg www.ins..c..om cc/ httt//220/aaaah/9//// haaaaa/faaaaaaaa222222000..02... Abstract. wtt.sstttttttt.ll...............
[20] Zuowei Shen. Deep Network Approximationn Characterized by Number of Neurons. Communi- cations in Computational Physies, 1768 June 2020. ISSN 1815-2406, 1991-7120. doi: 10. 00.420//cip..AA-222000
[21] Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep Network Approximation for Smooth Functions. SIAM Journal on Mathematical Analysis, 53(5):5465-553 5506, January 2021. ISSN 0036- 1410. doi: 10.1137/20M134695XX URL https: siam. org/ do1/10.1137/20M133 117.11///2011445X.
[22] Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of ReLU networks in terms of width and depth. Journal de Mathématiques Pures et Appliquées, 157:101-135, January 2022. ISSN 0021-7824. doi: 10. 10.10166j.aapuur2221.77.7 https://www sciencedirect. https://ww..ciimeeddrrc. cttp://cciceeerrrrreeee////oo///
URL
[23] Weinan, Chao Ma, and Lei Wu. The barron space and the flow-induced function spaces for neural network models. Constructive Approximation, 55(1):369 2022.

---

[24] Yuling Jiao. Yanming Lai, Xiliang Lu, Fengru Wang, Jerry Zhijian Yang, and Yuanyuan Yang. Deep neural networks with Se----nn-eeeppenttte activations break eurse of dimensionality in approximation on hölder class. SIAM Journal on Mathematical Analysis, 55(4):3635-3649)
2023. doi: 10. (1137/21114431111 URL wwwphhtp////e/tt btopps://di.... .ogg//.gg...... 111.11137//1M444431..
[25] Yuling Jiao, Guohao Shen, Yuanyuan Lin, and Jian Huang. Deep nonpara- metric regression on approximate manifolds: Nonasymptotic error bounds with polynomial prefactors. The Annals of Statistics, 51(2)691-716. April 2023.
ISSN 0090-5364, 2168-8966.
doi: 10.1214/23-0052266. www.:oopprrreettr-rreeeeeeeeeeee on- approximate hot.aaooooooooooooaoottotooooooo bounds/ 10. 20.1114423-A02266.... full.
URL https:
//projecteuclid.orgg org/
[26] Vojtëch Havličck, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kan- dala, Jerry M. Chow, and Jay M. Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 267(7747):099-212, March 2019. ISSN 1476-4687. doi: 10. 10310 $41586-019-00 01986009--990-2. URL https://: http:::://www.tuu/e/e/ee/e nature. cwmc http://rtilelss.eem sate://s1116--e 010-0660--9990000000000 0980-2.
[27] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao. Expressive power of parametrized quantum circuits. Physical Review Research, 2(3):033125, July 2020. doi:
[28] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 17(9):1113-101, 2021. ISSN
doi: 10.1008//41557-021--1111
[29] Hsin- Yuan Huang, Richard Kueng, and John Preskill. cntommaiiontthorettee bounds on quan- tum advantage in machine learning. Phys. Rev. Lett., 126:15 May 2021. doi: 10.1 103// PhysRevLett. 1et.11...9990 190505. URL https: aps. org/ /tt//0.1111011/////// http://........///sseeoeetto 110s/ 1 190505.
[30] Sofiene Jerbi, Casper Gyurik, Simon Marshall, Hans Briegel, and Vedran Dunjko. Parametrized Quantum Policies for Reinforcement Learning.
Advances in Neu- ral Information Processing Systems, volume 34, pages 28362-28375. Curran Asso- ciates, Inc., 2021. URL https://prroceeding:
http://eeeiig..nnuiiiippppe neurips....... cc/ pttpppppr//221111/ /hahh// 0ec5077788888884441111466668 Awsttratttrttttteee html.
[31] Hsin-Yuan Huang. Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hart- mut Neven, and Jarrod R. McClean. Power data in quantum machine learning. Nature Com- munications, 12(1):2631, May 2021. ISSN 2041-1723. doi: 10. 0011///44467-002-222222 URL https: : /www. nature. com/ http/articlesseee s414s444447774 0771-0221223999
[32] Sofiene Jerbi, Lukas J. Fiderer, Hendrik Poulsen Nautrup, Jonas M. Kübler, Hans J. Briegel, and Vedran Dunjko. Quantum machine learning beyond kernel methods. Nature Communica- tions, 14(1):517, January 2023. ISSN 2041-1723. doi: 10.
URL
nttps://www http:://wwwww..uur.e/mmmmmmm nature........ com/ a
[33] Jonas Jäger and Roman V. Krems. Universal expressiveness of variational quantum clas- sifiers and quantum kernels for support vector machines. Nature Communications, 14(1): 576, February 2023. ISSN 2041-1723, doi: 10.0038441147--02--0044455 URL https:
// www www.re.tur.... https//e.w....aaaaaeeee////---0.
[34] Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. Effect of data encoding on the ex- pressive power of variational quantun-machine-lemmin models. Physical Review 103(3): 032430, March 2021. doi: 10. 1033/hyyseevAAA0000322.0..
[35] Francisco Javier Gil Vidal and Dirk Oliver Theis. Input Redundancy for Parameterized Quantum Circuits. Frontiers in Physics, 8, 2020. ISSN 2296-424X. URL htttps://wut frontiersin. wtwpsiirrrraaareee//.o.o.
wtt.l////ee....//////ee/ 3389/fphy.
[36] Adrián Pérez-Salinas, David López-Náñez, Artur Garefa-Sáez, P. Forn-Díaz, and José I. La- torre. One qubit as universal approximant. Physical Review A, 104(1):012405, July 2021. doi: 10.1 1...10//hyysccvA.00000....
12

---

[37] Zhan Yu, Hongshun Yao. Mujin Li. and Xin Wang. Power and limitations of single-qubit native quantum neural networks. In S. Koyejo. S. Mohamed, A. Agar- wal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Informa- tion Processing Systems, volume 35, pages 27810-27823. Curran Associates, Inc., neurips httplppperrreeaaaelelppppppaeeae httss/pppe/222//111/22
2022. URL https://proceeddie 2200e119905sds4ttadcccfeeeeeee
Sraper-Conferecce pdf.
[38] Alberto Manzano, David Dechant, Jordi Tura, and Vedran Dunjko. Parametrized Quantum Circuits and their approximation capacities in the context of quantum machine learning, July 2023.
[39] Takahiro Goto, Quoc Hoan Tran, and Kohei Nakajima. Universal Approximation Property of Quantum Machine Learning Models in Quantum-Fnnancee Feature Spaces. Physical Review Letters, 127(9))090506, August 2021. doi: 10. 101100/yssseeleeee 127.090506.
[40] Lukas Gonon and Antoine Jacquier. Universal Approximation Theorem and error bounds for quantum neural networks and quantum reservoirs, July 2023.
[41] Jun Qi, Chao-Han Huck Yang, Yu Chen, and Min-Hsiu Hsich. Theoretical error per- formance analysis for variational quantum circuit based functional regression. npj Quantum Information, 9(1):4, 2023. ISSN 2056-6387. doi: 10. 00788//45534-02--000
[42] Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C. Caro. Learning quantum states and unitaries of bounded gate complexity, 2023.
[43] Philipp Grohs and Gitta Kutyniok. Mathematical aspects of deep learning. Cambridge Uni- versity Press, 2022.
[44] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010.
[45] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. Methodology of Resonant Equian- gular Composite Quantum Gates. Physical Review X, 6(4):041067, December 2016. doi: 10.1 (ttphysseeXX.00441666.6
[46] Guang Hao Low and Isaac Chuang. Optimal Hamiltonian Simulation by Quantum Sig- nal Processing. Physical Review Letters, 118(1)001501, January 2017. doi: 10.1
[47] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value trans- formation and beyond: Exponential improvements for quantum matrix arithmetics. In Proceed- ings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193-204, June 2019. doi: 10. 10.114///313776.3336
[48] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Inf. Comput., 12(11-12)9001-99 -924, 2012. doi: 10.26421/QIC12. 11-12-1.
[49] Adenilton J. da Silva and Daniel K. Park. Linear-depth quantum circuits for multiqubit con- trolled gates. Physical Review A, 106(4):042602, October 2022. doi: 10.1103/hhyseevA.100 (426602.
[50] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum Amplitude Ampli- fication and Estimation. Contemporary Mathematics, 305:53-74, 2002. doi: 10. 1090/o///mm/ 305/05215.
[51] Kenneth Davidson and Allan P. Donsig, Real analysis with real applications. Prentice Hall, 2002. URL https://cirr mii. sii.ac.. ap.p...pppp...... httpppp//cc//111300077777766666
[52] Clemens Heitzinger. Simulation and Inverse Modeling of Semiconductor Manufacturing Pro- cesses. Thesis, Technische Universität Wien, 2002.
[53] Mama Foupouagnigni and Merlin Mouafo Wouodjié. On Multivariate Bernstein Polynomials. Mathematics, 8(9): 1397, September 2020. ISSN 2227-7390. doi: 10.33900math80913397
13

---

[54] Guang Hao Low. Quantum Signal Processing by Single-Qubit Dynamics, Thesis, Mas- sachusetts Institute of Technology, 2017. URL https:/ mit. www.handdeeeeeaaeaaaaaaaa 1/115025
[55] Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL httt::/aaxii..oo //g///b///// 111//412...00 6980.
[56] Jia Deng. Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large- scale hierarchical image database. In 2009 JEEE Conference on Computer Vision and Pattern Recognition, pages 248 258,,255,100 June 2009. doi: 10.1 2..10999CVRR.209.520060
URL https:
// //ieeexplore. ieee. . org/ /taaaabstttttteee /bcrraccc/cccumeee555266888
[57] Youle Wang, Lei Zhang, Zhan Yu, and Xin Wang. Quantum Phase Processing and its Applica- tions in Estimating Phase and Entropies, July 2023.
[58] V. N. Vapnik and A. Ya. Chervonenkis. Necessary and Sufficient Conditions for the Uniform Convergence of Means to their Expectations. Theory of Probability & Its Applications, 26(3): 532 092-553,4 January 1982. ISSN 0040-585X.
doi: 11111311126055
[59] V. M. Tikhomirov. e-Entropy and e-Capacity of Sets In Functional Spaces. In A. N. Shiryayev, editor, Selected Works of A. N. Kolmogorov: Volume III: Information Theory and the Theory of Algorithms, Mathematics and Its Applications, pages 86-170. Springer Netherlands, Dor- drecht, 1993. ISBN 978-94-017-2273-4 doi:
[60] Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of Machine Learning Research, 3(3):463, April 2003. ISSN 15324435. URL https://search: cebearccheescchhceee wwwcohost..c.o.........o........ www.coom////// cww.ottoooooooo.cocccmm www.:/oggiinniiiiee.eeree
[61] Yuxuan Du, Zhuozhuo Tu, Xiao Yuan, and Dacheng Tao. Efficient Measure for the Expres- sivity of Variational Quantum Algorithms. Physical Review Letters, 128(8);080506, February 2022. doi: 10. 1..100//hyReeveet.. 128..e000.1.0000000
[62] Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang. Statistical complexity of quantum circuits. Physical Review A, 105(6):06231, June 2022. doi: 10.1 100PPhyy/yss... 105.062431.
[63] Matthias C. Caro and Ishaun Datta. Pseudo-dimension of quantum circuits. Quantum Machine Intelligence, 2(2):14, November 2020. ISSN 4914. doi: 10.1007//42484-020 000044402200002--550
[64] Chih-Chich Chen, Masaru Sogabe, Kodai Shiba, Katsuyoshi Sakamoto, and Tomah Sogabe. General Shenik-Chrrvonenis dimension bounds for quantum circuit learning. Journal of Physics: Complexity, 3(4):045007, November 2022. ISSN 2632-072X. doi: 10.1088/
2632-072X/ac999b.
[65] Amira Abbas, David Sutter, Christa Zoufal, Aurelien Lucchi, Alessio Figalli, and Stefan Wo- erner. The power of quantum neural networks. Nature Computational Science, 1(6):403-409 June 2021. ISSN 2662-8457 doi: 10.1008//3388--22-00000
[66] Ronald A. Vore Ralph Howard, and Charles Micchelli. Optimal nonlinear approximation. manuscripta mathematica, 63(4):469-477 478. December 1989. ISSN 1432-1785, doi: 10.1007/ BF01171759.
[67] Kurt Homik. Approximation capabilities of multilayer feedforward networks. Neural net- works, 4227 1991. URL httpt:://///tt http:::://wwsssieeeiieeeeeee www.ssceieeeci..c.... wttpcccddrrect..coooeceeeeeeeeee http//ccennceeeeee article/ abs abs/pi1/093000019000
[68] Weinan E, Chao Ma, and Lei Wu. The Barron Space and the Flow-Induced Function Spaces for Neural Network Models. Constructive Approximation, 55(1):369 February 2022. ISSN 1432-0940. doi: 10. 100777/00036--021-0054999-- URL httph::/t////... tttaps://dorr 1007/ s00365- 02100011-0000100 -291-9949-y.
14

---

[69] M. H. Stone. The Generalized Weierstrass Approximation Theorem. Mathematics Magazine, 21(4):167-184 1948. ISSN 0025-570X. doi: 10.2307/3029750.
[70] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 770-778, June 2016. doi: 10.1109/VVR.2201..390
[71] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster R-CNN: Towards real- time object detection with region proposal networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL https: paper files/ httpp/paaprrrr//////// http:///hh.a...aaaeeeaaaaaaaaaa0
pttps://prccceednggga http://peeeeeeeee.eeeeeaeee newrips. cc/ .df.
[72] Zhilin Yang. Zihang Dai, Yiming Yang. Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. XLNet: Generalized Autoregressive Pretraining for Language Understand- ing. In Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL
cctppape//019////// /
Abstractttttttttteeeeeeeeeeee html.
[73] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter the Association for Computational Lin- guistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171- 4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguisties. doi: 10. 10.18653/v1/N19-144 14233. URL https: http///ccaaaallooo.o// hrg.llogooor//1199 org/ 1423.
[74] Shijun Zhang, Jianfeng Lu, and Hongkai Zhao. Deep Network Approximation: Beyond ReLU Diverse Activation Functions, September 2023. URL http://arxxi.orr/abse 06555.
[75] Ingo Gühring, Gitta Kutyniok, and Philipp Petersen. Error bounds for approximations with deep ReLU neural networks in ws.p norms. Analysis and Applications, 18(05): 803-859, 2020. doi: 10.1 (0.11422801153305144400022 $0219530519410022.
URL
wtw/o0..//10.... 1142/
[76] Johannes Schmidt- Hieber. Nonparametric regression using deep neural networks with ReLU activation function. The Annals Statistics, 48(4):1875 1897, 2020. doi: 10.1214/
19-AOS1875. URL httptttst//o..ooo orgi 1214/1211111 ADS1875.
15

---

Supplementary Material
Contents
1
Introduction
2 Preliminaries
3 Expressivity of PQCs for multivariate continuous functions
3.1 Explicit construction of PQCs for multivariate polynomials
3.2 PQC approximation for continuous functions
3.3 PQC approximation for Hölder smooth functions
Numerical experiments
5
Discussion
Preliminaries
17
A.1
Notation
17
A.2 Data re-uploading PQCs
17
A.2.1 Implementing real polynomials
17
A.2.2 Implementing trigonometric polynomials
18
A.3 Related work in PQC approximation
19
Implementing multivariate polynomials using PQCs
20
B.1 Implementing multivariate real polynomials
20
B.2 Implementing multivariate trigonometric polynomials
22
Approximating continuous functions PQCs
C.1 Established results of Bernstein polynomials approximation
23
C.2 Implement Bernstein polynomials via PQCs
25
C,3 PQC approximating continuous functions
26
Approximating smooth functions via nested PQCs
26
D.1 Localization via PQC
................................
27
D.2 Implementing the Taylor coefficients by PQC
................................
28
D.3 Implementing multivariate Taylor series PQC
28
D.4 Comparison of "global" and "local" approaches in this work ................................
Comparison with related works in classical machine learning
31
16

---

A Preliminaries
In this section, will first present some essential mathematical foundations for deriving the main results of this work. Moreover, to contextualize our work within the existing literature, we compre- hensively review relevant studies in Appendix A.3.
A.1 Notation
We unify the notations throughout the whole work. The univariate polynomial ring over a field F symbolized as F[æ]], with the variable z representing the input. The ring Laurent polynomial F[x, x []] is an extension of the polynomial ring obtained by adding inverses of x. The collection of natural numbers is represented by the symbol
2,, J. while the of non-negative integers is denoted as No- == {0} UN. The 1-norm of vector a (a1, ..,,..,, aa) is denoted by + loa).
||a||2 = |ail + 02g
A.2
Data re-uploading PQCS
In this section, we review the concept of data re-uploading PQC and define the PQC we use in this paper. The data re-uploading PQC is a quantum circuit that consists of interleaved data encoding circuit blocks and trainable circuit blocks [35, 111. More precisely, let æ be the input data vector and 0 -0o..... OL) be a set of trainable parameters. S(x) quantum circuit that encode and V(O,) is a trainable quantum circuit with trainable parameter vector 0j. An L-layer data uplladdiggg PQC can be then expressed as
L II (())) j=1
V=(x)= -
(A.1)
Applying Ue(x) to quantum state and measuring the output states provides way to express functions on æ. The expressivity of the data re-uploading PQC model can be characterized by the classes of functions that it implement. It is common to build data encoding circuits and trainable circuits using the most prevalent Pauli rotation operators,
Rx (0) = cos 8 2
i sin g
= cos
sin
0
(0)
Rx =
sin
cos 2
sin cos
e
(A.2)
Different data encoding schemes lead to different types of data re-uploading PQCs.
In some cases, trainable parameters also included both during the initial data encoding phase and the final processing of measurement outcomes. These PQCs are considered to have hybrid structures. For instance, in the models proposed by Refs. [35, 36, 40), each input data is multiplied by specific trainable parameter and subsequently subjected to Rz gates during the data encoding stage. In a similar vein, Refs. [39, 40] incorporate trainable weights into each measurement outcome generated by the constructed PQCs, aggregating these weighted outcomes to produce the final result. Such structure makes it hard judge whether the expressive power comes from the classical or quantum part.
A.2.1 Implementing real polynomials
We first introduce the data re-uploading PQC for implementing real univariate polynomials. We utilize the so-called Pauli X basis encoding [10]: The data encoding unitary is a single-qubit rotation defined as
S(x) = e arecos((1)
x
(A.3)
wi--
where x E [] 1] is the input data. Then interlaying the data encoding unitary S(x) with some parameterized Pauli Z rotations (z) gives the circuit of data re-uploading PQC for one variable as
Uo(x) = -= II ((x)
(A.4)
17

---

where 0 = 02) E R is a set of trainable parameters. The PQC in Eq. (A.4) can be used implement polynomial transformations on imput æ, as shown the following lemma. Lemma S1 ([47]). There exists 0 E RR++1 such that
P(x) iQ(x)[1=> (*)
Uo(z) iQ'(z\vi-
(A.5)
if and only if polynomials P,Q E C[a] satisfy
1. deg(P) & and deg(() S 1,
2. has parity mod 2 and Q has parity (L -1-1) mod 25,
3. Vz E 1_],, [P(x) (1 2²)10(())
As shown in the above lemma, one could implement a polynomial transformation Poly(z) such that Poly(z) = (z)))(z))00
P(z). Notice that the achievable polynomial Poly(z) implemented in this way is limited to P(z) for which there exists polynomial ((z) satisfying the conditions of Lemma $1. As the target polynomial often real in practice, we could overcome such a limitation by defining Poly(z) = (o (x))+) = R (x)) + iR((()))v - x². Then we can achieve any real polynomials with parity L mod! 2 such that dcg(Poly(z)) I L, and [Poly(z) 1 for all
x E [-.
Corollary S2 ([47)). There exists 0 RL+1 such that
p(x) (+1U6(>)1++)
(A.6)
and only if the real polynomial p(x) R[x]] satisfies
1. deg(p(æ)) < L,
2. p(z) has parity L mod 5,
3. Vz [-1,1], [pxx) < 1.
Remark S1. The results of PQC with Pauli X basis encoding presented here have been established the technique of quantum signal processing [45-47], which uses interleaving signal operators and signal processing operators to transform the input signal. The QSP circuit could be identified as a PQC in the context of quantum machine learning.
A.2.2 Implementing trigonometric polynomials
Other than the real polynomials, there are also types of single-qubit PQC with Pauli Z basis encod- ing that could implement complex trigonometric polynomials [37]. The data encoding unitary is single-qubit rotation in the Pauli Z basis
(eir/2
S(c) = Rz(x)
(A.7)
12/2
where x E IR the data. By interleaving the data encoding unitary S(x) with trainable gates Ry (0) Rø(),, the PQC is defined as
(0 = Rz(w) (0)) R2 II S())B)
(A.8)
where 0 -= (0...... 0z) R L+1 の = (do.... Ø2) R L++ and w E R. The following lemma characterizes the correspondence between PQC with 0₂ basis encoding and complex trigonometric polynomials.
For a polynomial P C[cc). P has parity if all coefficients corresponding odd powers of 0, and similarly has parity all coefficients corresponding to even powers O.
A polynomial p(x) has parity 0 if all coefficients corresponding to odd powers of are 0, and similarly p(x) has parity 1 if all coefficients corresponding
powers of O.
18

---

Lemma S3 ([37)). There exist 0, Φ E I+tl and w E R such that
U0 = P(x) -Q(x)
(A.9)
P'(x) (x)
if and only if Laurent polynomials P. E Clcie/2 , e- satisfy
1. deg(P) & L and deg(Q) - L.
2. P and Q have parity L mod 2.
3. Vz E IR, (Q(x)) =1
Note that Laurent polynomials in Cie ex//]] with parity 0 are Laurent polynomials in C[e() without parity constraints, which implies that the trigonometric QSP could implement complex trigonometric polynomials.
Corollary S4 (137, 57]). There exist 0, Φ E 12L+1 and w E R such that
t(x) (0) Uo 10)
(A.10)
if and only the complex-valued trigonometicc polynomial t(x)) E)= Geebz satisfies [t(x)] s 1 for all R.
A.3 Related work in PQC approximation
In this subsection, we review prior literature related to the approximation capabilities of PQCs, which characterizes how the architectural properties of PQC affect the resulting functions it can fit, and its ensuing performance. After a systematic comparison, we conclude that our results pro- vide precise error bounds for continuous function approximation and make no assumptions about the constructed PQCs. More importantly, all the variables in our proposal take the form of param- eters within rotation gates and remain distinct from the data encoding gates avoid any classical computational influence, thus preserving the inherent quantum property of our approach.
In theoretical machine learning, statistical complexity is notion that measures the inherent richness characterizing a given hypothesis space. There are various statistical complexity measures, includ- ing the Vapmik-Chervonenkii (VC) dimension [58], the metric entropy [59], the Gaussian complex- ity [60]. and the Rademacher complexity [60]. etc. To gauge the statistical complexity of PQCs, Du et al. [61] have explored the covering entropy of PQCs in terms of the number of quantum gates and the measurement observable. Bu et al. [62] have investigated the dependence of the Rademacher complexity of POCs the resources, width, depth, and the property of input and output registers. The assessment of PQCs has extended to encompass an array of statistical complexity measures, as delineated in Caro and Datta [63], and the VC dimension, as
including the Eseudo-Dimensing expounded upon in Chen et al. [64]. Furthermore, the evaluation of PQC expressivity has extended its purview to metrics rooted in information theory. Abbas et al. [65] have evaluated PQC expres- sivity through the prism of the effective dimension, a data-dependent metric contingent upon the Fisher information. In a parallel endeavor, Du et al. [27] have concentrated their attention on gen- erative tasks, employing entanglement entropy as a metric for quantifying PQC expressivity. It is important to underscore that, while statistical complexity metrics and cnpermation-nnspire metrics provide invaluable insights into the 'volume" of hypothesis spaces, they do not precisely delineate the functions amenable to representation by these models.
To further explore the intricacies of PQCs and their expressivity, an alternative avenue of research has emerged, as highlighted by recent studies [34, 35, 37, 36, 38]. They rewrote the PQC output, i... the inner product between an input quantum state and a variational observable, in the form of partial Fourier series. This innovative perspective introduces more nuanced toolbox for assess- ing PQC expressivity, offering fresh insights within the quantum machine learning domain, notably with respect to the universal approximation property (UAP). However, is imperative to underscore that many investigations employing Fourier expansion have been predicated upon certain imprac- tical assumptions. These assumptions encompass the demand for arbitrary parameterized global unitaries and observables, thus posing significant challenges to the practical implementation of the constructed quantum circuits. The existence proof of universal approximation also does not explic- itly give approximation error bounds of PQCs.
19

---

A very general approach to expressiveness in the context of approximation is the method of nonlin- ear widths by De Vore al. [66] that concerns the upproximation of family of functions under the assumption of continuous dependence of the model on the approximated function. Pérez-Salinas et [36] have proved that single-qubit data re-uploading PQCs are universal function approxi- mators, inheriting the famous universal approximation theorem for neural networks [13, 67]. In quantum-enhanced context, Goto et al. [39] have constructed PQCs to approximate any continuous function guided by the Stone- Weierstrass theorem. Qi et al. [41] have studied the approximation error of PQCs enhanced by lensor-train networks. Their investigation focused on smooth functions, considering factors such the number of qubits and quantum measurement counts. Furthermore, Gonon and Jacquier [40] have defined a specific hypothesis space consisting of non-oscillating func- tions, drawing inspiration from Barron [15] and devised PQCs for approximating such functions without encountering the curse of dimensionality (CoD). Notably, the mitigation of Col) arises from their specific hypothesis space definition and is also observed within the domain of classical neural network [68]. It is essential to acknowledge that these works unveil a hybrid nature, blurring the boundaries between classical and quantum domains in circuit construction. The hybrid structure manifests in the data encoding phase and becomes evident in the weighted summation of outputs from foundational quantum circuits. Consequently, whether the powerful expressivity comes from the classical part or the quantum part of hybrid models is unclear.
In our present work, make assumptions in the construction of the PQCs. In PQC model, all variables take the form of parameters within rotation gates. Besides, these trainable parameters remain distinct from the data encoding gates to avoid any classical computational influence. These properties ensure that our constructed PQCs retain practicality and remain firmly rooted within the quantum domain.
B Implementing multivariate polynomials using PQCs
B.1 Implementing multivariate real polynomials
A multivariate polynomial with d variables and degree 8 E N is defined as
p(x) = Σ
ca
(B.11)
||c||
where x (#1...., xd) E Rd, a (ai.....
ad) E No, Ca E R and x" = 0d To implement the multivariate polynomial p(z), we first build PQC to express monomial x
222 x where I < 1 for æ E [0, and ||a]]] I s. We apply the single-qubit PQC with Pauli X basis encoding defined in Eq. (A.4) on each æz for S S d, respectively.
Ca 01
Lemma S5. Given monomial x = C Ing I222.... ... va
.. such that 1 < 1 all a E [0,
1jd
and ||a]|] for E N, there exists PQC U (x)) such that
( (x))+))8 ca
(B.12)
The width of the PQC is at most d, the depth is most 2s 1, and the number of parameters is at most s + d.
Proof. By Corollary S2, there exist d single-qubit PQCs Ug (z1), Ug2 (I2),....... Un (x.) such that
(+|U (21)++) = ca2
(+|Ug) (22)l+) = x22 a0
(z)) ad
where the number of layers of each PQC is L3 = =a for 1 < < d. We then define a d-qubit PQC
as
d
(
U (xz),
(B.
j=1
20

---

For convenience, we rewrite the normalized target operator with a being an indexed variable as which gives
(+) bo U (-))+))
Rd = II (+UV (zy)++) = Ca
(B.14)
==1
Since |a]|| = E oj S 8, we can conclude that the depth of (x:) at most 2s and the number of parameters in U (x) is at most 8 + d.
The next step to combine monomials together implement the multivariate polynomial. Specifi- cally, we would like to implement the following (unnormalized) operator
(p(3)) = Σ U²(2))
(B.15)
a SS
so that we can implement an (unnormalized) polynomial as
(+)0)((()))+))))
Σ (+)))((()))+)))
Σ
Co = =((x).
(B.16)
|a|ISa
We denote T the number of termss in the summation and observe that it can be bounded as
T= Σ 1
S (s 1)d".
(B.17)
|ol|
j=0 aa ر|=j
j=0
T
= Σ
(x).
(B.18)
However, the addition operation quantum computing is non-trivial as the sum of unitary opera- tors is not necessarily unitary. To sum the monomials together, we utilize the technique of linear combination of unitaries (LCU) [48] to implement the operator U2( in Eq. (B. 18) on quantum computer. We first construct unitary operator F such that
F F
VT M 1))
(B.19)
The unitary F could be simply implemented by Hadamard gates. Next, we construct controlled unitary
Uc(x) Σ 16Xil & Ua (x)
(B.20)
j=1
Note that each liXi| s ( (a)) could be constructed using (log quuibt controlled Pauli rotation gates, as ( (x) consisting of single-qubir Pauli rotation gates. The (log -uuqubit controlled gates could be further decomposed into quantum circuits of CNOT gates and single-qubit rotation gates in
Ollog 7') circuit depth without using any ancilla qubit. We refer to the detailed implementation of
these muult--controllcr gates to da Silva and Park [49]. Then the unitary Wicu = (F* & [FU.(F @ I) satisfies that
Wica (0) |+) 0d = 10) (p(x) 1+) sd +11),
(B.21)
where ((0) @ 1]) Notice that
(0) (+1 Wten 10) |+) = (+1 3d Up(2)) | p(x).
(B.22)
To obtain the polynomial p(æ), we could estimate (0) (+| Wien 10) |+) using the Hadamard test.
Theorem 1. For any multivariate polynomial p(æ) with d variables and degree such that [p(x) S
1 for x [0, 1]d, there exists a PQC W Wp(x) (x) such that
fw_(w) == (0) W
(x) [
W, 10) = p(x)
(B.23)
where 7(0) the Pauli Z observable on the first qubit. The width of the PQC is O(d log 8 log d), the depth is O(s² d' (log + log d)), and the number of parameters is ( (s d)).
21

---

Proof. We apply the Hadamard test on Wie.. giving the quantum circuit Wo (x)x) as follows.
[0]
H
H
(0)
W Lou
(0)
Had
Measuring the first qubit of (ær), we have
fw, = (0) w (z) ( w>))) 10)= (+) (+1 Wicu 10) (4) 04 p(x))
(B.24)
The controlled unitary used in LCU,
U2(x)) Σ Lilil & U (x),
(B.25)
f=1
could be implemented by at most OTTs) (log -ubbit controlled gates. (log qubbit controlled gate could be implemented by quantum circuit consisting of CNOT gates and single-qubit gates with depth (loog T) [49]. Thus U,(Z) could be implemented by quantum circuit with depth
OsT log I' and width O(d log T). Then the depth and width of ica (F @ (F @ I) are in the same order of (x) since F is simply tensor of Hadamard gates. Therefore the entire depth of the circuit Wp is (sTlogg + d), and the width of Wp O + log 7). As < (s + 1)d". Note that the number of parameters in the PQC equals the number of parameters in U,( which ( + d)).
Note that measuring the first qubit of (x(x)) for ( times is needed to estimate the value of p(æ)) up additive error We could further use the amplitude estimation algorithm [50] to reduce the overhead while increasing the circuit depth by 0
B.2 Implementing multivariate trigonometric polynomials
We extend the PQCs with Rz encoding to implement multivariate trigonometric polynomials. A multivariate trigonometric polynomials with d variables and degree is defined as
t(x) Σ |
(B.26)
where on E C, x
(21...., va) E Rd, v (aI..... ad) E Zd, and e in
amnmige ... e.. en Consider trigonometric monomial On en e ... en..o such that | < for all æ E
d and ||a||| I 8, we could apply the single-qubit PQC with Rz encoding defined in Eq. (A.8) on each z, for S < d respectively.
Lemma 86. Given a trigonometric monomial on in
On ene ... ginaaa such that e < for all x E IR and ||||| there exists PQC (*)))) such that
(0 Sd irew
(B.27)
The width of the PQC is at most d, the depth is at most 6s 3, and the number of parameters is at most 4s + 3d.
Proof. By Corollary
S4, U d. (ma) such that
could
construct d
single-qubit
PQCs
Tm 0, (x1), U 02 (x2)....
(0)um) 0 (zI)
Cn in
(2 d2 (xz)10) in2z2
U 04. (zz)10) = ianva
22

---

where the number of layers of each PQC is L, = ny for j j S d. We then define d-qubit PQC
U x =
U
0g.dy (zz))
(B.28)
j=l
which gives
(0 2d U U* (x)10) 04 = II (0 (z₂) = c
(B.29)
Since ||a||a = Eラ= S s, we can conclude that the depth of U (²x(x) at most 6s + 3 and the number parameters U (~) is at most 4s + 3d.
Then we could apply the technique of LCU the PQCs U* (a) implement the operator
U,(z)=
Σ (²))).
(B.30)
so that we can implement the multivariate trigonometric polynomial as
UZ,))
+) +d
Σ
(=))))(()))))
Σ
(B.31)
||
Note that the number of terms in the summation is
Σ 1
2s S 1)
(B.32)
1=0
||>|||=
1=0
Then, we have the following proposition.
Proposition S7. For any multivariate trigonometric polynomial t(x) with variables and degree such that [tx)] 1 for Rd., there exists PQC (1) such that
fw... = (0) (x.,(()))) (2) W (eri(x) 10) = t(x)
(B.33)
where Z(0) is the Pauli Z observable on the first qubit. The width of the PQC is (d- log 8 s log d), the depth is de sloodeloo s log d)), and the number of parameters is O(sd2s (s + d)).
The proof similar to Theorem 1. This result demonstrates the universal approximation property of PQC in the perspective of multivariate Fourier series, which yields similar results in Schuld et al. [34]. Notably, the PQC in Proposition S7 has an explicit construction without any assumption, improving the implicit PQCs proposed in Schuld et al. [34] in terms of circuit size. For instance, to implement the d-variable Fourier series with degree 8, the PQC with parallel structure in Schuld al. [34] requires width (ds) and potentially exponential depth O(4ss).
C Approximating continuous functions via PQCs
We have constructively shown in the previous section that PQCs could implement multivariate poly- nomials. To study the approximation capabilities of PQC, natural strategy involves aggregating multiple polynomials to approximate the continuous function, drawing on well-established princi- ples from classical approximation theory. In the context of univariate functions, this endeavor is guided by the Stone-Weierstrass Theorem [69]. For the multivariate case, we accomplish this task by employing PQCs implement Bernstein polynomials, followed by the established result on the approximation error bound of Bernstein polynomials [52, 53].
C.1 Established results of Bernstein polynomials approximation
For d-variable continuous function f d H, the multivariate Bernstein polynomial with degree n E of ff is defined as
(xi =
(1
xz nks,
(C.34)
kig
k==0) =D
j=1
23

---

and k (k1....,kkl ka) E {O....,.) n2.d. Then, we have the following lemma on the approximation error bound of the Bernstein polynomial.
Lemma S8 (Bernstein polynomials approximation for Lipschitz functions [53). Given a Lipschitz continuous function f [o. 1] - R with Lipschitz constant E, which is defined as [f() f(y) S fllæ: yl Let f be bounded by r. The approximation error of the n-degree Bernstein polynomial
of f scales
C 4NE?
(11+
l2
1 -1)
[f(z) Bn(f= SE 21
Σ
S s
2r
(C.35)
4nE²
where & is an arbitrarily small quantity.
Proof. Drawing inspiration from the Lipschitz continuity of the target function f. we define 5 = e/l. Consequently, for any two points (I1,- .......,2.) ".ti,...>> ,,dz) and y (W),.... :Ma) such that | yil
for all i E {I....,a} ... it follows that [f(xx) f3y) S E. The target function can be written as
f(x)
((xi....,Ed))
d
f "
F4
zi (1 - =x2)" n
his
R1
ka=0
f (01
Fa)
II
ki (1 (1=z))) ==:)
(C.36)
hi
===0
i=1
Let us consider the set E' I1 {0, 1....,,,,,, n.. and for 1, 2, .., d, we define the sets
22 -Kk E (0, 10.,,..., ki =zy1 z,1 5) and F E (94 x Ωa)-
(C.37)
Then,
F Uk
Fk. with Fk = {II Daaul E : ax E (0, 1), Σd Ois = k... where
2/oul ik
Ω
if ask =1 and 5i = E (0, ,n. 1 2, 2 67. For A =
if au =
I glaaa
Fk, k 1,..., let us detine also I fie (I, ,d] au 1} (that means card (IA.) = 1: 2 1). We have
|f (I1, ... , ra)) - Bn (fi21, ... x2a)
(II,
Id)
n
ks (1 - I:;) Iz)" n-k
ki
An 0
hz=0
==1
hid
d
n
ki (1 - - (1-x;)"" =k
ki
n
k 0
Rd 0
i=1
1
[0)1
xxa)
hi
hi
n
1 (1 x;} )
k;
71
n
(C.38)
hi
ka
f (I11...,,00 xxa) -
x (1 ==:n~
ki
k;
4 0
k==0
f (x11 ... .xa) -f (1
ki
hi
n
x (1 - xzi 2z2n nk
k;
0
f (01, - ( (
ka
Σ
n
xx (1 - xzi) 1z:" m
k;
n
24

---

Using the fact that f is continuous and bounded, we get
If (
Fa)
Bn (f:311''' sra)
z (1 - xz n-k + 21
n2
xz (1 xz,) m=)=m²k
21
Ba i=1
Se + 21
II
xz)" =; Kg x.t (1 (1=x;)"'
AFEF i=1
(C.39)
SE + 21
Σ
4nd
1=1 AiEFi
=s = + 21
Σ
4 (Anoeys < 21
(1++
82
-1)
4ne
This completes the proof. A more detailed expansion of Eq. (C.39) can seen in Theorem 2 in Foupouagnigni and Mouafo Wouodjié [53].
0
Remark S2. Here, it is important to observe that for a continuous target function, denoted as f (xx), there exists value of 8 such that:
4no2 ((1+11=--11))
If (I1,-.. ... ,z)) , - Bn
S 2r
This expression signifies the convergence rate of the Bernstein polynomial for general continuous functions.
C.2 Implement Bernstein polynomials via PQCs
In Lemma S8, we have defined the Bernstein polynomial and its approximation error towards the Lipschitz continuous function. Guided by Theorem 1, we can construct PQC to implement such Bernstein polynomial.
Lemma S9. For any d-variable Bernstein polynomial with degree n E N defined in Eq. (C.34) such that B, (f: S for a E [0, 1]a there exist a PQC Ws(x) satisfying
fw. == (0) W (a: Wo(x) (0) = B, The width of the PQC is llgnn,,, the depth is (dn log and the number of parameters is Odn").
(C.40)
Proof. We undertake a two-step process in the proof of Lemma $9, Initially, we construct PQCs to provide exact representation of ((#) I[ (x)=,, (1==z))=k;, for all & E [0] Sub- sequently, we employ LCU aggregate these PQCs for the purpose of approximating the Bernstein polynomial described in Eq. (C.34).
The univariate polynomial x² (1 x)--* can be represented by PQC. The depth of this PQC is less than 2n + 1, the width is 2, and the number of parameters is n + 2. The multivariate polynomial (( I (1)x R3 (1 > can be exactly represented by the product of the univariate poly-
nomial 1²(1 x²) > The same routine has been employed in Lemma S5. The depth of this PQC less than 2n + 1. the width is 2d, and the number of parameters is d(n 2).
The number of terms in the summation in Eq. (C.34) is (n + 1)d, We can employ the same routine in Theorem 1 to construct the PQC Wz) The depth of W, scales as
((d(n 11d+1 11d+1 log (n + (1+ +d);
the width is 2d dog (n + 1), and the number of parameters is (n + 1)d 2)d. The results presented in Lemma S9 can be obtained after simplification.
25

---

C.3 PQC approximating continuous functions
We have successfully derived results regarding the approximation error between PQCs and Bemn- stein polynomials and between Bernstein polynomials and continuous functions. Leveraging these established findings, we can now formulate a rigorous assertion regarding the universal approxima- tion theorem and the error bound of PQCs, employing the well-established principles of triangle inequality.
Theorem 2 (The Universal Approximation Theorem of PQC). For any continuous function f [0, 1]d + [-1,1], given an E >> O, there exist an n E N and a PQC Wo(x) with width Od n)), depth O log n) and the number of trainable parameters (dn such that
- (w) S
(C.41)
for all a E [0, 1js, where fw, = (0) W (2)) 10).
Proof. Remark S2 has established the uniform convergence of the Bernstein polynomial towards any continuous function within the cubic domain [0. 1]. denoted as (,; with the property that xf + f(x as n + +oc. Building on Lemma S9, we can effectively implement this Bernstein polynomial (f:(aa)) a)) using (w,( The depth of the PQC (x( is O Odn" log n). the width is (dloogn) n), and the number of parameters is ((dn"). This completes the proof.
Theorem 3. Given a Lipschitz continuous function f : [o, 1]d - [-1,1] with a Lipschitz con- stant E, for any e > and n E N, there exists PQC Wo(w:) with such that fw,(2), = (0)
10) satisfies
lf(z) - fwo fm) SE+2
-1) SE
6 ( nE²
-1)
d2d
6
(C.42)
me²
for all [0, 174. The width of the PQC Ogd n), the depth is O Odn" log n). and the number of parameters is (dr)))
Proof. Lemma S8 has established the uniform convergence rate of the Bernstein polynomial towards any Lipschitz continuous function within the cubic domain [o, 1]d We know that for any Lipschitz continuous function fax) with Lipschitz constant L, there exists Bernstein polynomial (f) satisfying
29))
82 (()) 4
@2 ((1+ 4ne²
)
-11
(s()) - Bx(;a)) S 2r
Σ
Se+
1
Building on Lemma S9, we can effectively implement this Bernstein polynomial B, x) using Sw, (z)) The depth the PQC Wx(w) is O(dr (ddn I). the width Old n), and the number of parameters is (d This completes the proof.
D Approximating smooth functions via nested PQCs
Other than using a Bernstein polynomial to approximate continuous function globally, could also utilize local polynomials to achieve a piecewise approximation. To do this, we follow the path of classical deep neural networks [18, 21, 25], using multivariate Taylor series expansion to approximate a multivariate smooth function f in some small local region. Let 3 = 8 + > 0, r = (0, 1] and s = [Ø] E N, for finite constant Bo 0, the 3-Hölder class of functions 3 ([0, 1]s, Bo) is defined as H. ((0, 11 Bb) = {s { 1] + R, max 1 f flloo & Bo, max sup ||
| f(z) 80 f(y)
< Bo
||a]| # æşy |
y
(D.43)
(a1, (ai,...,aal aa) E Nd. By definition, for function f H. 1]d, Bo), when B E (0. 1), is Hölder continuous function with order 3 and Hölder constant Bo: when 3 1, f is Lipschitz function with Lipschitz constant Bg: when G > 1. belongs to the C class of functions whose s-th partial derivatives exist and are bounded.
where 80 = g..... ... for
26

---

We utilize the following lemma on the Taylor expansion of 3-Höller functions as mathematical tool for constructing and analyzing the PQC approximation.
Lemma S10 (118)), Given a function E (10, 100, with 3 = 8, (0, and s E N+ for any æ, zo E [0, 1] we have
(x x0)a s d zoll2. 0a ((00))
f(x))
(D.44)
at!
S
where a!! aa!...aa
Next, we show how to construct PQCs to implement the Taylor expansion of ß-Hölder functions.
D.1 Localization via PQC
As shown in Eq. (D.44), the Taylor expansion of multivariate smooth function only converges in a fairly small local region. So, we need first to localize the entire region [o, 1] Given K E and
A E (0, 3R) for each r = (71....., na) E {0, 1............... K 13d, we define
Qn = {xr = (Z), xa) : 24 E
T
T -
A -L
(D.45)
K
K
By the definition of 1p the region [0, 11 is approximately divided into small hypercubes Un Qu and some trifling region A(d, K, A) [o. 1j (U,,, Qn), (n), illustrated in Fig. 2 in the main text. Then we need to construct PQC that maps any x E Qn to some fixed point on к if x E Qn where
n Qn. i.c. approximating the piecewise-constan function D(x) = 2 We consider the case of 1, where the localization function
K
K
h D(z)
k k
K' i
1 for k
K-
(D.46)
K
K
The multivariate case could be easily generalized by applying D(x) each variable zj. The idea is to find polynomial that approximates the sign function
1,
if x c,
sgn x - 0)
0,
if x = C
(D.47)
1, if < c
as shown in the following lemma. Lemma S11 (Polynomial approximation the sign function sgn(æ: - c) [54]). Vc [-1,111 0, E (0, 1). there exists an odd polynomial PA.e (z) of degree n = 0 log 2 that satisfies
1. PA.e c)1 < for all x E [-1,],
2. sggn( c) (r c)1 S : for all E [-11,1]] (c- 4)
Note that we could also approximate the step function defined stp(r c) 1 sgn(x c) + by the polynomial P/,e (x c) P that (x c)] S for all æ [-1.]] and |stp( [-1, (c A 2,c ). Note that the polynomial ( e) does not have definite parity and thus cannot be directly implemented by PQC shown Corollary $2. Since only the domain [o, 1] is relevant to I, for e E (0, 1). we could define an even polynomial
c) + 1 of degree 0 log ) which satisfies
(2. - c) S _ for all
1
peven
(xr)
(Pa,e c) (- (
(D.48)
1+ 2
such that |eeenn (z) < 1 for all e [-1,1] and |stp(z - c) peven (x) S 1/ for all
[o, 1] (c 2 c + ). The piecewise-constant function D(x) can be written as a combination of step functions,
K-1 D(x)
Σ k=1
k stp(p
A
(D.49)
K
Then could find even polynomials P. Combining those polynomials together in Eq. (D.49), we have the following lemma.
(I) that approximate stp( t +) for each k.
27

---

Lemma S12. Given K E N and A E (0, 3k), there exists an even polynomial (2.)()) of degree
O( log K that satisfies
1. PA.e (x)) < 1 for x I 1-1,1|
2. (xx) - (a))( for all x UK-I k+1
1kck-1]-
K
K
Note that we could shift the polynomial (z.)(z) such that Pa,e(x) ( - D(x) E (0, without chang- ing the degree. It follows that we construct PQC implement the polynomial (a.e()) by Corollary S2.
Corollary S13. Given E, A (0, of depth O 1 log () that satisfies
1) and E (0, t). there exists a single-qubil PQC Up()) 3K
k
k k +1
(+|UD(I))+)-
E (0,E) if K
A LLck-1 for k 0, K - (D.50)
K K
Note that E has be bounded by 1. which is the length the localized region. We could further implement such localization procedure for x = (#1...., Tt) on the region [0, 1] by applying the PQC for each zj. as stated in the following corollary.
Lemma S14 (Localization via PQC). Given K N. N. (0, (0, and e (0, k) there exists PQC WD (xz) of width (dd and depth O log K implementing a localization function (w) Rd + IRd such that
0 I Swp (a)
Se
if E Qm
(D.51)
K
where 0 (O.....0) 0) and (E) are d-dimensional vectors.
Proof. We construct d-qubit PQC WD(#) = 0 UD(zz) where the single-qubit PQC (a) constructed in Corollary S13. Then we apply the Hadamard test each (n(z;) obtain JUp (xy) = (+|Un(zy)1+)) Let Swp (x)) = (Stp ( (ra)), which implements the lo- calization function required.
D.2 Implementing the Taylor coefficients by PQC
Next, we use PQC to implement the Taylor coefficients, which is essentially point-fitting problem. 8
For each 7) (m .......: 7a) (0. 1,.... K -13d and a, we denote E,,ox Then we could construct the following PQC.
E [-1, 1].
U Σ "
mnnll @ Rx (0,.))
(D.52)
where (n)) (m)) & Ina) and 0 arccos((E,.)) It gives the following lemma.
Lemma S15. Given a 3-Hölder smooth function [0, 1]d + [-1, for any a E N and
n (0, 10,1....,,A 13d, there exists a PQC U such that
(n, 0| U 'n, En.ax
(D.53)
The width of the PQC is Od K), and the depth is ((Kd).
We note that the state (n)) can be prepared using basis encoding according to the results of localiza- tion in Lemma S14.
D.3 Implementing multivariate Taylor series by PQC
To implement the multivariate Taylor expansion function, we first build a PQC to represent a single term in the Taylor series, which could be done by combining the monomial implementation in Lemma $5 and the Taylor coefficient implementation Lemma S15. Thus, we have the following corollary.
28

---

Corollary S16. For any B-Hölder smooth function f. given an a E N' with ||a]] S s for E N and an vy E (0, 1...., K 13,, there exists a PQC (x) such that
8a (( (n (+1 0d (x) In. 0)1+)
7
(x
(D.54)
ad!
K
The width of the PQC is O(dlog K), the depth is O(K + s), and the number of parameters is at most Kd + + d.
Proof. Let (z) Uh @ U (z: X where U% is defined in Lemma S15 and U R defined in Lemma with changing input from i to a K Then the corollary directly follows from Lemma S5 and Lemma $15.
The next step is to combine single Taylor terms together to implement the truncated Taylor expansion of the target function. The method is in the same spirit what is utilized in Theorem 1, i... using LCU to achieve the following (unnormalized) operator,
Uz(x))
Σ (z).
(D.55)
Then we implement the Taylor expansion of the function ʃ point K
in. [+| 04 Uz(2)) nn 0)|+}
8
(
x
7 K
(D.56)
ad!
||
Hence we have the following lemma.
Lemma S17. Given a function f H 1]4, 1) with B = r s, E (0, and 8 E EN+, for any
n (0...., K 7--1 134, there exists a PQC Wa( B such that Sw. (z) = (0) W (=) 7(0 (0) implements the truncated Taylor expansion at point R.
80
fw.(x)= = Σ
x
7
(D.57)
ad!
K
The depth of the PQC is O(s²d' tt K (log s + s log d + d log K)), the width is Ol K + log s + s log d), and the number of parameters (sdd (s + + kd))
Proof. The idea of constructing the PQC (x, 7) is similar the construction of W, in Theorem 1. The only difference is that here apply LCU on unitaries UN (x) = U U x ? instead of (x)). Thus, the controlled unitary is
T Σ j=1
Uc(x,
7 R K
Mall @ U (x)
(D.58)
and the unitary Wten(w, 7) (F & l2U,( (F @ I) satisfies that
yo ad!
(n [++ Wien (x, K
10) (/lln.0)++ 0)
x
7
j
(D.59)
K
We then apply the Hadamard test on Wicu (x, R
giving the quantum circuit W. R
as below
(0)
H
10)
10)
(n))
Wica
10)
(0)
Hod
29

---

where the unitary Un) takes as imput and maps (0) to In). Note that the controlled uni- tary Uz(æ, )) could be implemented by O(T(s + 1)) number of (log -qubit controlled gates and O(TK*) number of (log'T + dllog K) -uubit controlled gates. An n-qubit controlled gate could be implemented by quantum circuit consisting of CNOT gates and single-qubit gates with depth (m)) [49]. Thus U2(x) could be implemented by a quantum circuit with depth O((s + 1)7 T + TKo + d dog K)) and width O(d + log T + d log K). Then the depth and width of W Wacu( x)
(Ft @ [2, 2) @ I) are in the same order of Ua(æ, x) since F is simply tensor of Hadamard gates. Therefore the entire depth of the circuit W. is O(ssTlog + (1ogl + d log K))) and the width O(d+ T + dloog K). As T S (s+1)dd we have the depth and width of PQC shown in Lemma S17. Note that the number of parameters in the PQC equals the number of parameters in (2),, which is ( + d K))).
Finally, we combine the steps of localization and the Taylor series implementation to achieve a local Taylor expansion for the target function. The PQC in nested structure consisting of a PQC for localization and PQC for Taylor series; see the detailed construction in the following theorem.
Theorem 4. Given a function f E 7º ([0, 1J4,1) with 3 r + 8, E (0, 1] and 8 E N+ for any K E N and A E (0, 3K there exists a PQC (xx) such that fw, (x)) = (0) (x) z W (x)) 10)
satisfies
If(x) ( (x)) S 00+8//3
(D.60)
for i E U, On The width of the PQC is Od K K+log 8+8 log d), the depth is Os2 K
s log d + d'log K)) + 2 log K), and the number of parameters O(sd (s + d + Kd) + log K).
Proof. By Lemma S10, we have the following error bound for Qn-
f( ad!
[(x)) Σ
-
x
o
x
7 K ll S d
(D.61)
|
Motivated by this, we first construct localization PQC (xx as in Lemma S14 such that
"
1
0 S fw, (z)
S
if x E Qn,
(D.62)
K
2K
2K
The depth of (x) is O log K). We then construct a PQC
(i(x)= = Wz fw)(
(D.63)
where We is the PQC proposed in Lemma S17. Note that the state (n) in Lemma S17 could be prepared by rounding Swp (77) K, i.e., 7 = Líw (n) In other words, the PQC (x(x) has a nested structure consisting of PQC for localization and a PQC for Taylor series implementation.
Then we show that fw. (x) (0) W/ (ax W.: 10) can approximate 3-Hölder smooth function f on U., Qn- By the triangle inequality and Eq. (D.61), we have
0 f (x)) (a fwo + d fwo (x)
[f(x) - fw. S [x) - Σ
ad!
I
(D.64)
80 [[Jwo (2)) (x (wo( +0
$ (w)) Σ
(D.65)
ac!
S d 1/+111--2
(D.66)
The second inequality comes from the fact that || /wo(w))l S 1 for E Qn This completes the proof.
Note that the PQC in Theorem 4 is nesting of two PQCs, while its depth is counted the sum of two PQCs for simplicity. We have established the uniform convergence property of PQCs for approximating Hölder smooth function that the Lebesgue measure of such trifling region is no more than dK A. We can set A K-d with no influence on the size of the constructed PQC Theorem 4. Since v absolutely continuous with respect to the Lebesgue measure, we have the following corollary.
[0, 1]d except for the trifling region A(d, K, A). Note
30

---

Table S1: Approximation errors of PQCs and ReLU FNNS
Approach
Target
Width
Depth
Number of parameters
Approximation
PQC
d-var, deg.ss momomial ((d)
O(s)
O(d
0
ReLU (21]
d-var, deg -s monomial
O(N +
((P
O( + M)
Nosted PQC
C] 17")
Oldlog K + a log d)
d(K"d")
o(K"d'11)
O(f-KT")
FNN [21]
O(s*+IN)
O()²M)
O( K)
0(8"8"K7))
Satisfying NM @(K4/2).
Corollary S18. Given a function f E ([0, 11 with 3= = rr (0, 1] and s E , any
K E N and A E (0, 3k) there exists a PQC (x) such that fw. (x) = (0) W7 (x) (z) (0)
1
satisfies
- S..1 fiw
[f(x)) - fw. (x) =
(D.67)
(f(x) - fw: (2)))
(D.68)
(UnGUUMaK. I (d D/2 9- 4dK1-d.
(D.69)
The width of the PQC is Odd K + log + slog d), the depth Oss2 Kd (logs s d
dlog K)) + 2/ log K), and the number of parameters ((sd' d + Kd) + log K).
D.4 Comparison of "global" and "local" approaches in this work
We note that we have presented two distinct methodologies for constructing PQC models with UAP properties aimed at approximating continuous functions. In Theorem 3 and Theorem 4, establish PQC models, guided by the multivariate Bernstein polynomials and the Taylor expansion of multi- variate continuous functions, respectively. We categorize these approaches as "local" and "global". We proceed to conduct a comprehensive comparative analysis of these two strategies in the context of approximating Lipschitz continuous functions. For the subsequent analysis, set B 1, thus s = in Theorem 4, in accordance with the Lipschitz continuous property exhibited by the target function.
The approximation error associated with the global approach can be bounded as (24d6))/(n=") + By selecting n (2/", we ensure an approximation error of 2s. Concurrently, the corre- sponding number of trainable parameters scale as O22d gd+1 gad /="d). In contrast, the local ap- Setting K = vd/z ensures 2e approximation error, with the number of trainable parameters scaling O (d"/ These find- ings highlight the advantage of the local approach for approximating continuous functions. More importantly, the approximation error proposed by the local method approaches the optimal conver- gence rate established in Shen et al. [22]. A formal comparison between PQCs and classical deep neural networks is stated in the next section.
proach exhibits an approximation error scaling as vdk-I
E Comparison with related works in classical machine learning
In this subsection, we conduct comparative exploration of PQCs and classical deep neural net- works, focusing on critical aspects, including model size, the number of trainable parameters, and approximation error. To establish a meaningful benchmark, we turn our attention to deep feed- forward neural networks (FNNs) distinguished by the incorporation of rectified linear unit (ReLU) activation functions. FNNs represent the foundational class of neural networks, characterized by unidirectional flow of information, commencing from the input layer and traversing through one or more hidden layers before culminating at the output layer. This architectural design ensures the ab- sence of cyclic dependencies or loops among nodes within each layer. The ReLU activation function, mathematically defined as ReLU(z)) == max x., 0). has gained prominence across diverse domains, including but not limited to image recognition [70, 71] and natural language processing [72, 73). Its popularity in feed-forward networks stems from its efficacy in facilitating the convergence of function approximation during network training. Additionally, a recent study [74] has affirmed that classical neural networks employing commonly utilized activation functions can be effectively
31

---

approximated by ReLU-activated networks while maintaining a mild increment in network size. Readers are also referred some other excellent works related ReLU networks [16, 75, 76].
In particular, Shen et al. [22] have proposed the optimal approximation error to approximate any Lipschitz function. Lu et al. [21] have provided nearly optimal approximation error to approxi- mate any smooth function using ReLU FNNs. For clarity, the comparison of our results with theirs summarized in Table. S1. It is pertinent to observe that, in the majority of practical instances, the smoothness coefficient s of the target function tends to be modest since most functions to be approximated is not very smooth. Additionally, within practical scenarios, particularly in domains like image recognition and natural language processing, the dimensionality d of input data is sub- stantially large. Consequently, within this context, we identify terms that solely rely on the variable s as constants and d > s within Table S1.
We extend our investigation by quantifying the performance of PQCs and FNNs in terms of the model size and the number of parameters for approximating s-smooth functions C ([0, 1]a). No- tably, discover that in cases where the target function adheres to certain norms of smoothness, PQCs exhibit a notable improvement in approximating this function in terms of the model size and the number of parameters.
Model size. In particular, we explore the comparison of PQC and FNN model sizes when they yield the same approximation error (say some constant). Here, product of width and depth, to gauge the model size. By setting approximation error as E, the size of PQC and FNN scale as ((K)rt2) and O(K2² kd/2 (d+3), respectively, where Kę O /et///////
straightforward measure, the
and Ko = ((s4/s /E2/x).
Remarkably, when 2 S s < d, an intriguing observation emerges: the ratio of model sizes between PQCs and FNNs [21] exhibits scaling behavior of O O(e-d/(2)) /gdd / log, d). Our comprehensive analysis concludes that in situations where the smoothness threshold is satisfied, PQCs boast a sig- nificantly smaller model size compared to FNNs.
Number of trainable parameters. In the present investigation, we delve into the comparative analysis of the number of trainable parameters of PQC and FNN under the premise of yielding comparable approximation errors. From the perspective of approximation theory, the count of pa- rameters serves as standard metric for assessing model degrees of freedom and expressing model expressiveness. By setting approximation error as s, the number trainable parameters of PQC and FNN scale as O +)) and ( (1+))///22 22444), respectively. Here, the hyperparameter Ao E (0, 1) signifies FNN's 's width.
Remarkably, through our analysis, have uncovered that when 2 < d, the relationship between the number of trainable parameters of PQCs and FNNs [21] demonstrates a scaling pattern characterized by D(==((1A))d/(22) / (1g) o -olg,, 4). As a consequence, the number of trainable parameters of PQCs significantly reduces compared to that of FNNs.
Approximating monomial. Here, we conduct a comparative performance analysis of PQC and FNN in approximating monomial functions of degree 8. Within this specialized target function space, PQCs exhibit distinct advantages in terms of width, depth, model size, and the number of trainable parameters. Notably, PQCs possess the unique capability to capture the dynamics of mono- mial functions precisely, eliminating the need for approximation and thereby offering a compelling advantage. These advantages position PQCs as promising candidates for outperforming FNNs when addressing more complex target function spaces.
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have clearly summarized the main contribution and scope of our work in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The authors have discussed the specific type of functions that PQCs can ap- proximate with quantitative error bound and the specific case where PQCs would have improvement over the classical neural networks. The pros and cons of global and local approximation are also discussed in the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
33

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Complete proofs are provided in the supplementary materials. The authors also discuss the sketch proof ideas in the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We have clearly stated all information and detailed settings of our experi-
ments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- reasonable avenue for reproducibility, which may depend
missions to provide on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibiliiy. In the case of closed-source models, it may be that access to the model is limited in
34

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have provided the complete code in the supplementary materials that is necessary reproduce the experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: (https://nips) https:://ippccooo cc/
htgii//gguides/oooeusuassssssss ioi for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. wwublic/guides/Caee
ssi onPolicyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:[Yee
Justification: We have provided the necessary experimental settings in the main text, such as the model configurations, the optimizer, the training and test data generation, etc. The full details can be found in code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
Justification: As our work mainly focuses on the theoretical approximation capability of PQCs, the numerical experiments are provided verify the theoretical results on the non- asymptotic approximation emoor bound. In this case, we did not include error bars nor other information about the statistical significance of the experiments, which would be irrelevant to the expressivity of the model.
35

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: In the main text, we have provided the detailed hardware information needed to reproduce the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurian
The research conducted the paper conform with the NeurIPS Code of Answer: [Yes]
Justification:
Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
36

---

Answer:
[NA]
Justification:
There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications,
authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The paper poses no such risks since the authors focus on the theoretical as- pect of quantum machine learning models, particularly approximation capability and expressivity.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
37

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcom thcodehooee.... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmoel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
38

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research
with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "KPpFinjVwI", "reviewer": "Reviewer_xe2x", "summary": "This paper studies the expressiveness of parameterized circuits to perform multivariate function approximation. This serves as a quantum counterpart to the theoretical results of classical machine learning, namely the universal approximation theorem. Theoretical results provide bounds on the approximation error of parameterized circuits with bounds on the quantum resources required. Finally, numerical experiments are provided, showing that parameterized quantum circuits are able to approximate multivariate functions with improved accuracy as the number of parameters increases.", "questions": "- In the second paragraph of Sec 3.1, why is the number of parameters $s+d$, rather than simply $s$? If $d>s$, then only $s$ variables are relevant.\n- In Sec 3.2, why were Bernstein polynomials chosen over other polynomial approximations, such as truncated Taylor series expansions? Are there other ways, and if so, what are the drawbacks?\n- In Theorem 2, how does $n$ depend on $\\epsilon$? I think it would make more sense to express the resource costs in terms of $1/\\epsilon$.\n- In Theorem 3, why does $n$ no longer depend on $\\epsilon$? Does it mean that both $\n\\epsilon$ and $n$ could be simultaneously chosen to be arbitrarily small?\n- I am curious about how the PQCs were implemented for the numerical experiments. I assume analytical formulas for the approximating polynomial were used, rather than full circuit implementations with the overhead of LCU, right?", "limitations": "There are no major negative societal impacts of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper uses ideas from quantum signal processing to study the expressivity of parameterized quantum circuits, thereby serving as a first step for bridging the gap between quantum algorithms for matrix functions and quantum machine learning. This is a very natural idea, and is better motivated than many other ansatz used in variational quantum algorithms. Generally speaking, I think it is valuable for works in (quantum) machine learning to be guided by results with theoretical guarantees as this typically leads to better algorithm design.\n- The overall paper is well-written and clear to understand.\n- The numerical experiments appear promising and supplement the theoretical results well, although the parameter counts are fairly large even for the small test-cases presented.", "weaknesses": "- The use of ideas from quantum signal processing is a bit of a double-edged sword. While Theorem 3 provides a non-asymptotic error bound, the quantum resources (circuit width and depth) are only asymptotic bounds. Presumably, the resources required for performing the LCU circuit are not very practical for NISQ devices, and it is likely that there are significant improvements to be made.\n- It would be nice to include code for the numerical experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the appreciation of the paper and inspiring feedback. Here we respond to the insightful comments and questions.\n\n> 1. The use of ideas from quantum signal processing is a bit of a double-edged sword. While Theorem 3 provides a non-asymptotic error bound, the quantum resources (circuit width and depth) are only asymptotic bounds. Presumably, the resources required for performing the LCU circuit are not very practical for NISQ devices, and it is likely that there are significant improvements to be made.\n\nReply 1: For the construction of our PQCs, the error bound and quantum circuit size are typically non-asymptotic, except in the step of decomposing multi-qubit gates into one- and two-qubit gates. Specifically, in the LCU procedure, constructing a larger-scale unitary block that encodes the summation of multiple unitary matrices requires applying multi-qubit control to each unitary matrix. To achieve this on a quantum computer, we utilize techniques from Ref. [1] to decompose the multi-qubit control gate into a linear-depth quantum circuit composed of CNOT gates and single-qubit rotation gates without using any ancilla qubit. The quantum resources are asymptotic in this multi-qubit control gate decomposition. These asymptotic quantum resources merely conceal constant or trivial terms, which do not impact the feasibility of our construction on quantum devices. Furthermore, decomposing multi-qubit gates to one- and two-qubit gates facilitates fair comparisons with classical neural networks in terms of network width and depth.\n\n[1] A. J. da Silva and D. K. Park, Linear-depth quantum circuits for multiqubit controlled gates, Physical Review A 106.4 (2022).\n\n> 2. It would be nice to include code for the numerical experiments.\n\nReply 2: Thanks for asking, actually all the code has been uploaded to the Supplementary Material accompanying this work, along with instructions on how to run the code.\n\n> 3. In the second paragraph of Sec 3.1, why is the number of parameters $s+d$, rather than simply $s$? If $d>s$, then only $s$ variables are relevant.\n\nReply 3: Thanks for pointing it out. Here, in Sec 3.1, we do not have any assumption about $d>s$ as we aim to have a general analysis of PQC construction. Quantum signal processing (QSP) indicates that expressing an $s$-degree polynomial requires $s+1$ parameters. Therefore, when $s>d$, expressing an $s$-degree $d$-variable polynomial, with each variable having a non-zero degree, necessitates $s+d$ parameters. Conversely, when $d>s$, at most $2s$ parameters are needed to express an $s$-degree $d$-variable polynomial. Overall, at most $s+d$ parameters are required to express an $s$-degree $d$-variable polynomial.\n\n> 4. In Sec 3.2, why were Bernstein polynomials chosen over other polynomial approximations, such as truncated Taylor series expansions? Are there other ways, and if so, what are the drawbacks?\n\nReply 4: In Sec 3.3, we do utilize truncated Taylor expansions for polynomial approximations, as presented in Theorem 4. We selected the Bernstein polynomial due to its ease of implementation and comprehensive theoretical results. Bernstein polynomials are considered \"global\" polynomials because they approximate functions over an entire interval without focusing on specific local behavior, which facilitates implementation through QSP. However, a drawback of global polynomials is their relatively poor approximation error, as illustrated in Figure 1. In contrast, Taylor series expansions are \"local\" polynomials that approximate functions based on local information at specific points. The approximation process involves identifying local points for expansion and using these points to construct polynomials. This locality allows for more precise approximations, as illustrated in Figure 1, making them a central approach in classical machine learning approximation theory.  Based on these principles, we designed the PQC with a nested architecture. PQCs implementing local Taylor expansions yield better approximation errors, demonstrating an advantage even over near-optimal classical neural networks, as shown in our discussion part.\n\n> 5. In Theorem 2, how does $n$ depend on $\\epsilon$? I think it would make more sense to express the resource costs in terms of $1/\\epsilon$.\n\nReply 5: In Theorem 2, we present a universal approximation theorem (UAT) for PQCs, highlighting the existence of a PQC capable of approximating any continuous function, but we do not explore the relationship between $n$ and $\\epsilon$. Similarly, in classical learning theory (as in [13]), the UAT simply guarantees the existence of a neural network for approximating any continuous function within arbitrary error but does not imply the relationship between the network size and approximation error. All non-asymptotic results are detailed in Theorems 3 and 4, which go beyond UAT by providing quantitative error bound in terms of circuit size.\n\n> 6. In Theorem 3, why does $n$ no longer depend on $\\epsilon$? Does it mean that both $\\epsilon$ and $n$ could be simultaneously chosen to be arbitrarily small?\n\nReply 6: In Theorem 3, epsilon does not represent the approximation error. As shown in Equation (6), the approximation error $\\epsilon+d2^d\\frac{\\ell^2}{n\\epsilon^2}$ is determined by both $\\epsilon$ and $n$. Choosing both $\\epsilon$ and $n$ to be small may result in a large approximation error.\n\n> 7. I am curious about how the PQCs were implemented for the numerical experiments. I assume analytical formulas for the approximating polynomial were used, rather than full circuit implementations with the overhead of LCU, right?\n\nReply 7: Yes, we did not implement the heavy LCU procedure in our experiments. There is no difference between adding monomials together and implementing the linear combination of monomial PQCs when we conduct numerical simulations, so we go for an easier way.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6L1yCjqols", "reviewer": "Reviewer_joax", "summary": "In this work, the authors aim to build a theoretical understanding of parameterized quantum circuits via non-asymptotic approximation error performance analysis. In particular, they demonstrate the advantages of PQCs over classical ones if specific smoothness criteria can be satisfied. The simulation results can further corroborate their theoretical understanding.", "questions": "1. how can the authors generalize the proposed theory to those cases if the target function is non-smooth and non-continuous? \n\n2. What is the most significant advantage of the non-asymptotical analysis on PQCs compared to the universal approximation theory? \n\n3. Is there a different or new discovery of the PQC's setup if using the authors' new theoretical perspective?", "limitations": "1. The proposed theorems rely on continuous or smooth target functions, which hinders their application to broader use cases. \n\n2. The numerical simulations cannot corroborate the specific smooth and continuous functions.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a different theoretical perspective of understanding PQCs using a non-asymptotic viewpoint in addition to the universal approximation theory. \n\n2. Their established non-asymptotic PQC approximation error bounds are technically correct\n\n3. The simulation results can corroborate the theoretical results.", "weaknesses": "1. The authors' theoretical analysis of PQCs relies on the assumption of continuous or smooth target functions, which hinders the theoretical usage from a broader case of non-smooth and non-continuous target functions. \n\n2. The numerical simulation is less convincing than practical machine learning datasets, so the actual machine learning applications are expected to validate the proposed theory. \n\n3. the experimental validation could be designed to corroborate the theoretical results, e.g., the target function relying on Holder's discussions on smooth and continuous functions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and valuable comments. We would like to provide a detailed response to the questions raised by the reviewer.\n\n> 1. The authors' theoretical analysis of PQCs relies on the assumption of continuous or smooth target functions, which hinders the theoretical usage from a broader case of non-smooth and non-continuous target functions. How can the authors generalize the proposed theory to those cases if the target function is non-smooth and non-continuous?\n\nReply 1:  First, we would like to point out that continuous functions are typical classes of target functions in the study of learning theory. For example, the most celebrated universal approximation theorems for neural networks involve approximating continuous functions. This is because machine learning data points in practical scenarios are discrete and can often be fitted into continuous functions. Second, the Hölder smooth functions considered in our work constitute a large class of continuous functions, but they are not necessarily **infinitely smooth**. By the definition in Eq. (7) and the following explanation, the smoothness index of the Hölder class can vary in the range $(0, \\infty)$. From a theoretical perspective, it is certainly of great interest to study the approximation of non-continuous functions, as the reviewer suggested. One possible way to generalize would be to first use continuous functions to approximate non-continuous functions, followed by the analysis in our work. Additionally, in the appendix, we introduce the construction of PQCs that implement multivariate trigonometric polynomials, which can be used to approximate any square-integrable functions (not necessarily continuous). However, to the best of our knowledge, deriving a quantitative error bound for approximating general non-continuous functions is highly non-trivial and thus requires further investigation.\n\n> 2. The numerical simulation is less convincing than practical machine learning datasets, so the actual machine learning applications are expected to validate the proposed theory.\n\nReply 2: We would like to emphasize that the main contribution of our work lies in the theoretical aspect of PQC approximation performance. The numerical simulation in our work is used to validate our theoretical results, which is about using PQC to approximate continuous and smooth functions. For practical machine learning datasets, there is no such target function well defined but only discrete data points, so it is not intuitive to use such \"datasets\" to numerically validate our theory of \"function\" approximation. Additionally, the dimensions of real datasets are typically very large, making it impossible to train such a huge PQC model on our computers.\n\n> 3. The experimental validation could be designed to corroborate the theoretical results, e.g., the target function relying on Hölder's discussions on smooth and continuous functions.\n\nReply 3: As we explained above, we designed the numerical experiment to validate our theorem. Thus, we chose a target function from the class of Hölder smooth functions that we study in the theory.\n\n> 4. What is the most significant advantage of the non-asymptotical analysis on PQCs compared to the universal approximation theory?\n\nReply 4: The universal approximation theorem only demonstrates the existence of PQCs that can approximate the target function within some arbitrary error. However, it does not provide the construction of the circuit and its size as a function of the error and, therefore, cannot quantify the approximation performance. The non-asymptotic analysis of PQCs for QML in our work gives the explicit construction of PQCs and quantitative approximation error bound of PQCs, which characterizes the approximation performance of PQCs in terms of circuit size and the number of parameters. More importantly, such non-asymptotic analysis of PQCs makes it possible to compare their performance with that of classical neural networks, potentially revealing quantum advantages.\n\n> 5. Is there a different or new discovery of the PQC's setup if using the authors' new theoretical perspective?\n\nReply 5: Yes, one of the novel contributions of our work is the setup of PQCs using quantum signal processing circuits and linear combination of unitaries circuits, which are first utilized in PQC constructions. Also, in Section 3.3 of PQC approximation for Hölder smooth functions, we propose a new construction called \"nested PQC\" that feeds the results of the first PQC to the second PQC. This new structure provides better approximation performance than traditional constructions and is therefore worth further study.\n\nOverall, we would like to clarify that our main contribution is the theoretical analysis of PQC approximation performance for a wide class of functions that are typically studied in learning theory and approximation theory. We intend to use a simple toy example in the numerical experiment to validate and better illustrate our theoretical results, which is not our main focus in this work. We thank the reviewer again for pointing out the other possible classes of functions, like non-continuous functions, that are worth further investigation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cl4T8rHvfM", "reviewer": "Reviewer_VAJH", "summary": "The authors explore the power and limitations of parameterized quantum circuits (PQCs).\nThey show that a large class of multivariate polynomials and smooth functions can be efficiently (approximately) represented by PQCs.\nMore importantly, they show that the requirements of such PQCs compare favorably to their classical counterparts (deep ReLu nets, etc.)", "questions": "Page 1:\nMaybe you can early on present a figure depicting some PQC (and a deep ReLu net, for comparison)?\nThis could help the reader relate to the subject matter.\n\nPage 2:\nCan PQCs trivially simulate classical deep learning nets?\n\nPage 3:\nShould you define mixed states for comparison with the pure states?\n\nShould you emphasize that the chosen basis is complete?\n\nPage 4:\nHow is Equation (1) derived?\nEquation (2) captures your notion of expressibility, right?\n\nPage 5:\nCan you please add some more discussion about Theorem 2?\n\nPage 6:\nCan you please elaborate on Lines 220 -- 221?\n\nPage 7:\nPlease elaborate on the caption of Figure 2.\n\nLine 263:\nWhy is such an $f$ interesting?\n\nPage 8:\nFigure 3:\nPlease elaborate on the caption.\n\nFigure 4:\nWhat is the moral regarding K? The higher the better? :)\n\nPage 9:\nDiscussion is good.\nPlease add some more future work/next steps.\n\nPlease do not wait until the end of the paper to state that your work is (???) the first of its kind :)\n\nWhat is the relationship of your work to (classical or quantum) computational complexity, and Turing machines? Please provide some discussion about how your work connects to the theory of computation.", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The main strength of the paper is that it addresses an important problem of practical and theoretical interest regarding the power and limitations of parameterized quantum circuits.\nThe results are novel, and the highlighted open problems are of great interest.", "weaknesses": "See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the contributions and novelty of our work! Here we respond to the insightful comments and questions raised by the reviewer.\n\n> 1. Page 1: Maybe you can early on present a figure depicting some PQC (and a deep ReLu net, for comparison)? This could help the reader relate to the subject matter.\n\nReply 1: Thank you for your kind suggestion. We will consider including a figure as suggested in the revised version.\n\n> 2. Page 2: Can PQCs trivially simulate classical deep learning nets?\n\nReply 2: Thanks for this insightful question! We believe that PQCs cannot trivially simulate classical deep neural networks. Using PQCs to simulate a classical neural network requires efficiently encoding classical data and implementing non-linear activation functions. Specifically, costly amplitude encoding techniques, such as QRAM, are necessary to encode classical data. Additionally, while our PQCs can properly approximate the non-linear activation function, applying this PQC element-wise to a pure quantum state is computationally challenging. In this work, we design novel PQCs to approximate functions with non-asymptotic error bounds by implementing various polynomials rather than directly simulating classical deep neural networks.\n\n> 3. Page 3: Should you define mixed states for comparison with the pure states? Should you emphasize that the chosen basis is complete?\n\nReply 3: Since mixed states are not used in our technical discussion, we did not define this concept. We will consider adding the definitions as suggested in the revised version.\n\n> 4. Page 4: How is Equation (1) derived? Equation (2) captures your notion of expressibility, right?\n\nReply 4: Equation (1) defines a PQC with data re-uploading structures as shown in [11], consisting of interleaved data-encoding circuit blocks and trainable circuit blocks. A formal definition and introduction to such data re-uploading PQCs can be found in the Appendix (Sec A.2). Equation (2) encapsulates our notion of expressibility. Formally, expressibility is captured by the class of functions that Equation (2) can approximate by adjusting its trainable parameters.\n\n> 5. Page 5: Can you please add some more discussion about Theorem 2?\n\nReply 5: Theorem 2 essentially characterizes the universal approximation property of PQCs, corresponding to the celebrated universal approximation theorem of classical neural networks. We will add several sentences in line 187: \"Theorem 2 serves as the quantum counterpart to the universal approximation theorem of classical neural networks. Moreover, the PQCs in Theorem 2 are explicitly constructed without any impractical assumptions...\"\n\n> 6. Page 6: Can you please elaborate on Lines 220 -- 221?\n\nReply 6: To elaborate on Lines 220-221, we will add the following sentence in Line 218: \"The motivation of localization is to determine the local point, i.e., $x_0$, in Equation (8). An intuitive configuration is illustrated in Figure 2, where the stars represent the local points. To implement this localization process, a straightforward method is to realize a step function $D'(x)=\\frac{k}{K}$ if $x\\in[\\frac{k}{K}, \\frac{k+1}{K}]$ for $k=0, 1, \\dots, K-1$. To approximate this discontinuous step function with polynomials, we exclude the $\\Delta$-neighborhood of the discontinuous points and approximate the remaining parts by polynomials.\"\n\n> 7. Page 7: Please elaborate on the caption of Figure 2.\n\nReply 7: After clarifying the motivation for the localization step, we believe that Figure 2 will be more comprehensible..\n\n> 8. Line 263: Why is such an $f$ interesting?\n\nReply 8: We emphasize that this work investigates the approximation capability of PQCs from a theoretical aspect, and the purpose of the numerical results is to support the theoretical findings. We select a bivariate polynomial function as the target function because it belongs to the function space studied in this context and is also easier to visualize, as shown in Figure 4. Also, there are situations where, despite the PQC's powerful expressibility, an imperfect optimization algorithm results in poor learning performance. Therefore, to reduce the impact of optimization imperfections on the final error, we choose a relatively simple polynomial function as our target for approximation.\n\n> 9. Page 8: Figure 3: Please elaborate on the caption.\n\nReply 9: We will add the following sentence to the caption of Figure 3:  \"The single-qubit PQCs trained to approximate the target localization function $D(x)$ for $K=2$ and $K=10$\".\n\n> 10. Figure 4: What is the moral regarding K? The higher the better? :)\n\nReply 10: Yes, with increasing $K$, the PQC exhibits a smaller approximation error as expected, which is consistent with our theoretical findings. We will add relevant discussion in the revised version.\n\n> 11. Page 9: Discussion is good. Please add some more future work/next steps. Please do not wait until the end of the paper to state that your work is (???) the first of its kind :)\n\nReply 11: Thanks for your comments. We will make corresponding changes in the revised version according to your suggestions.\n\n> 12. What is the relationship of your work to (classical or quantum) computational complexity, and Turing machines? Please provide some discussion about how your work connects to the theory of computation.\n\nReply 12: Thanks for this interesting question! The complexity theory primarily addresses computational problems, whereas our work is centered on approximation problems. Although our results demonstrate that the size of PQCs is smaller than that required by some neural networks when approximating certain types of functions, we cannot draw definitive conclusions about the complexity of classical or quantum computing based on our findings. This is because both neural networks and PQCs are specific learning models that cannot fully characterize the computational power of classical and quantum computers.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "z5R6cx7bSt", "reviewer": "Reviewer_5eFM", "summary": "This is a solid paper for approximating Hölder smooth functions using parameterized Quantum Circuits (PQC). The results show that using PQC for approximation can achieve better results than those in Lu's paper, especially when $K$, the length of the local region of Taylor expansion, is not large and the dimension $d$ is large.", "questions": "Mentioned in the Weaknesses.", "limitations": "All right.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Finding the approximation rate for different structures in deep learning is an important task to understand deep learning. The author presents approximation results for PQC, and I find this result interesting.", "weaknesses": "1. For continuous and Lipschitz continuous functions, the author only establishes the Universal Approximation Theory. Can the author improve the result to find the approximation rate based on [22] cited in the paper?\n\n2. The author's result is better than Lu's paper since they consider the approximation by $L^\\infty$-norm. In [22], it is shown that for the $L^p$ norm, the coefficient in Lu's paper can also not exponentially depend on $d$. In this case, is the result in this paper still better than Lu's paper?\n\n3. Based on my knowledge, in Lu's paper, they obtain a better rate of $K$ than the author's paper due to the use of the bit extraction technique, achieved by ReLU FNN, but the parameters in this technique need to be very large. Therefore, can your paper provide the bound of parameters? If so, this would be a significant benefit of your paper.\n\n4. The structure of the neural network is hard to train since it is not wide but deep when $K$ is large. Can you make the neural network shallower and wider?\n\n5. I think some tables and comments in the appendix can be shown on the main page such as Table S1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and valuable comments. We would like to provide a detailed response to the insightful questions raised by the reviewer.\n\n> 1. For continuous and Lipschitz continuous functions, the author only establishes the Universal Approximation Theory. Can the author improve the result to find the approximation rate based on [22] cited in the paper?\n\nReply 1: In fact, we do prove the approximation rate for Lipschitz continuous functions, for both the Bernstein polynomial approximation and the local Taylor expansion method. For the PQC approximation error bound using Bernstein polynomials, please refer to Theorem 3. For PQC approximation error bound using local Taylor expansion, please refer to Theorem 4. We would like to remind that the class of Hölder smooth functions considered in Theorem 4 includes Hölder continuous functions and Lipschitz continuous functions. Details can be referred to the definition of Hölder smooth functions in Lines 208–214.\n\n> 2. The author's result is better than Lu's paper since they consider the approximation by $L^\\infty$-norm. In [22], it is shown that for the $L^p$-norm, the coefficient in Lu's paper can also not exponentially depend on $d$. In this case, is the result in this paper still better than Lu's paper?\n\nReply 2: We would like to thank the reviewer for the insightful question. We believe that PQC function approximation under the $L^p$ norm is certainly worth further investigation, which would require careful calculations and proofs. For now we cannot say whether our PQCs would have better performance than Lu's paper for approximation under the $L^p$-norm, however, we believe that using the technique in [22] could aid in studying PQC approximation performance under the $L^p$ norm, and we will certainly pursue this in a later stage.\n\n> 3. Based on my knowledge, in Lu's paper, they obtain a better rate of $K$ than the author's paper due to the use of the bit extraction technique, achieved by ReLU FNN, but the parameters in this technique need to be very large. Therefore, can your paper provide the bound of parameters? If so, this would be a significant benefit of your paper.\n\nReply 3: Yes, as the reviewer pointed out, Lu's paper achieves a better dependence on $K$ due to the bit extraction technique, although the parameters could be extremely large. However, in the quantum strategy presented in our work, we do not use the technique of bit extraction but implement a quantum circuit to achieve the Taylor coefficients with parameters ranging between $0$ and $2\\pi$ since they represent angles for parameterized rotation gates.\n\n> 4. The structure of the neural network is hard to train since it is not wide but deep when $K$ is large. Can you make the neural network shallower and wider?\n\nReply 4: We thank the reviewer for highlighting this issue. Our PQC structure does not involve a tradeoff between width and depth like deep neural networks, and thus we cannot easily make PQCs shallower and wider. However, there is a fundamental difference between PQC and classical neural networks, i.e., wider PQCs are harder to train from the perspective of gradients because of the Barren Plateaus phenomenon [1]. For classical deep neural networks, the gradient can vanish exponentially with the number of layers (depth), while for quantum neural networks, the gradient decreases exponentially with the number of qubits (width). Therefore, we believe it is unnecessary to make our PQCs shallower and wider from the perspective of gradients.\n\n[1] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren Plateaus in Quantum Neural Network Training Landscapes, Nat Commun 9, 4812 (2018).\n\n> 5. I think some tables and comments in the appendix can be shown on the main page such as Table S1.\n\nReply 5: Thank you for the suggestion. We will consider moving some of the content from the appendix to the main text in the revised version, as the reviewer suggested.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This submission aims to build a theoretical understanding of parameterized quantum circuits via non-asymptotic approximation error performance analysis. It conducts a comprehensive investigation of the expressiveness of parameterized quantum circuits (PQCs) in the context of multivariate function approximation. Furthermore, they demonstrate PQCs have more favorable expressiveness than their classical counterparts (deep ReLu nets, etc.). The reviewers are all unanimously positive about the submission. We suggest the authors further revise the submission based on the feedback.
Decision: Accept (spotlight)