On the Universal Approximability and Complexity Bounds of Deep Learning in Hybrid Quantum-Classical Computing
Authors: Weiwen Jiang
Yukun Ding
Yiyu Shi
Venue:  (2021)
Keywords: deep learning
hybrid quantum-classical computing
universal approximability

Abstract: With the continuously increasing number of quantum bits in quantum computers, there are growing interests in exploring applications that can harvest the power of them. Recently, several attempts were made to implement neural networks, known to be computationally intensive, in hybrid quantum-classical scheme computing. While encouraging results are shown, two fundamental questions need to be answered: (1) whether neural networks in hybrid quantum-classical computing can leverage quantum power and meanwhile approximate any function within a given error bound, i.e., universal approximability; (2) how do these neural networks compare with ones on a classical computer in terms of representation power? This work sheds light on these two questions from a theoretical perspective.

Under review as a conference paper at ICLR 2021
ON THE UNIVERSAL APPROXIMABILITY AND COMPLEXITY BOUNDS OF DEEP LEARNING IN HYBRID QUANTUM-CLASSICAL COMPUTING
Anonymous authors Paper under double-blind review
ABSTRACT
With the continuously increasing number of quantum bits in quantum computers, there are growing interests in exploring applications that can harvest the power of them. Recently, several attempts were made to implement neural networks, known to be computationally intensive, in hybrid crantum-classicee scheme computing. While encouraging results are shown, two fundamental questions need to be swered: (1) whether neural networks in hybrid quantum-classical computing can leverage quantum power and meanwhile approximate any function within given error bound, i.e., universal approximability; (2) how do these neural networks compare with ones classical computer terms of representation power? This work sheds light on these two questions from a theoretical perspective.
INTRODUCTION
Quantum computing has been rapidly evolving (e.g., IBM (2020) recently announced debut quan- tum computer with 1,121 quantum bits (qubits) in 2023), but the development of quantum appli- cations is far behind; in particular, it is still unclear what and how applications can take quantum advantages. Deep learning, one of the most prevalent applications, is well known to be computation- intensive and therefore their backbone task, neural networks, is regarded as an important task to potentially take quantum advantages. Recent works (Francesco et al. 2019; Tacchino et al.) 2020) Jiang al. 2020) have demonstrated that the shallow neural networks with limited functions can be directly implemented on quantum computers without interfering with classical computers, but as pointed by Brooughton et al. (2020), the near-term Noisy Intermediate-S hardly disentangle and generalize data in general applications, using quantum computers alone. This year, Google (2020) has put forward a library for hybrid quantum- classical neural networks, which attracts attention from both industry and academia accelerate quantum deep learning.
Quantum (NISQ) can
In hybrid quantum- classical computing scheme, quantum computers act as hardware accelerators, working together with classical computers, speedup the neural network computation. The incor- poration classical computers is promising to conduct operations that are hard or costly to be im- plemented on quantum computers; however, it brings high data communication costs the interface between quantum and classical computers. Therefore, instead of contiguous communication during execution, better practice is a pppologue-aceeleattio--ppp-ooo prepares data and post-processes data at prologue and epilogue, while only the quantum computer active during the acceleration process for the main computations. Without explicit explanation, "hybrid model" refers to the
scheme: the classical computer
scheme in the rest of the paper.
In classical computing scheme, the universal approximability, i.e., the ability to approximate a wide class of functions with arbitrary small error, and the complexity bounds of different types of neural networks have been well studied (Cybenko 1989 Hornik et al.) 1989 Mhaskar & Micchelli 1992 Sonoda & Murata, 2017 Yarotsky 2017 Ding et al., 2019 Wang et al.) 2019 Fan et al.) 2020 However, due to the differences in computing paradigms, not all types of neural networks can be directly implemented
quantum computers. As such, it is still unclear whether those work with hybrid quantum-clasee classical computing and still attain universal approximability. In addition, as quantum computing limits the types of computations to be handled, it is also unknown whether the

---

Under review as a conference paper at ICLR 2021
hybrid quantum-classical neural networks can take quantum advantage over the classical networks under the same accuracy. This work explores these questions from a theoretical perspective.
In this work, we first illustrate neural networks that are feasible in hybrid quantum claasssall com- puting scheme. Then we use the method of bound-y--construction to demonstrate their universal approximability for a wide class of functions and the computation bounds, including network depth, qubit cost and gate cost, under a given error bound. In addition, compared with some of the lower complexity bounds for neural networks on classical computers, our established upper bounds are of lower asymptotic complexity, showing the potential of quantum advantage.
2
RELATED WORKS AND MOTIVATION
2.1 NEURAL NETWORKS IN QUANTUM COMPUTING
Although the research on neural networks in quantum computing can trace back to the 1990s (Kak)
1995 Purushothaman & Karayiannis 1997 Ezhov & Ventura 2000), but only recently, along with actual quantum
the revolution of quantum computers, the implementation of neural networks
computer emerges (Francesco et al. 2019: Jiang et al. 2020 Bisarya et al. 2020). There are mainly three different directions to exploit the power of quantum computers: (1) applying the Quantum
Random Access Memory (QRAM) (Blencowe] 2010); (2) employing pure quantum computers; (3)
bridging different platforms for hybrid quantum classsical computing (McClean et al., 2016).
Kerenidis et al. (2019) is a typical work to implement neural networks with QRAM. Using QRAM provides the highest flexibility, such as implementing non-linear functions using lookup tables. But
QRAM itself has limitations: instead of using the widely applied superconducting qubits (Arute
2019 IBM 2016). QRAM needs the support of spin qubit (Veldhorst et al. (015)) to provide ct al.
relatively long lifetime. To make the system practical, there is still long way to go.
Alternatively, there are works which encode data to either qubits (Francesco et al. 2019) or qubit states (Jiang et al.] (020) and use superconducting-basee
quantum computers to run neural net- works. These methods also have limitations: Due to the short decoherence times in current quantum computers, the condition statement is not supported, making it hard to implement some non-linear functions such as the most commonly used Rectified Linear Unit (ReLU). But the advantages are also obvious: (1) the designs be directly evaluated actual quantum computers; (2) little com- munication is needed between quantum and classical computers, which may otherwise be expensive.
Hybrid maantmm-classicat computing tries address the limitations of QRAM and pure quantum computer based approaches. [Broughton et (2020) establishes a computing paradigm where differ- ent neurons can be implemented on either quantum or classical computers. This brings the flexibility in implementing functions (e.g.. ReLU), while at the same time, it calls for fast interfaces for massive data transfer between quantum and classical computers.
In this work, we focus on the hybrid quantum-classscal computing scheme and follow the "prologue- acceleration-epilogue" computing scheme. It offers the flexibility of implementation and at the same time requires minimal classia data transfer, as demonstrated in Figure 2
2.2 UNIVERSAL APPROXIMATION AND COMPLEXITY BOUND
Universal approximability of neural network indicates that for any given continuous function or a wide class of functions satisfying some constraints, and arbitrarily small error bound e > 0, there exists neural network model which can approximate the function with no more than error. On classical computing, different types of neural networks have been proved to have universal approx- imability: multi-layer feedforward neural networks (Cybenko) 1989. Hornik et al. 1989); ReL.U neural networks (Mhaskar Micchelli 1992; Sonoda Murata 2017] Yarotsky| (017); quantized neural networks (Ding et al.) 2019; Wang et al. [2019); and quadratic neural networks (Fan et al., 2020). In addition, many of these works also establishes complexity bounds in terms of the number of weights, number of layers, number of neurons needed for approximation with error bound c.
When it comes to quantum computing, in recent years, Delgado 2018) demonstrated quantum cir- cuit with additional trainable diagonal matrix can approximate the given functions, and Schuld jet al. (2200) shown that the Fourier-type sum- based quantum models can be universal function approximators if the quantum circuit is measured enough many times. Most recently, wit-
2

---

Under review as a conference paper at ICLR 2021
0.000
892
0.993
033/0 (.5/3
0.599
8..90
0.960
(1997
0.496
(1994
Secord cluss
0.97
0.631 9.607
Second class
0.90
0.974
0.94
GURG
DUZAZ
0.350
9.080
0.57
0.572
0.52
0:004
00300
0.971
0.399
0.735
0.357
0.373
DJ004
DUDA
0.30
0:36
0327 D.29
0.000
0.072
0.057
0.544
2.544
0.00
2.000
0.992
0.200
0.977
0.322
0.001
0.093
0.090
USSU
UUSSI
0.59
0.301
0.500
2050
5.54
0.992
0337
03912
00990
0.39
0.999
0.00
DURD MODS 0.77L 03354 0,21 0.775 0.775
2
0.514
0.000
0.204
0.542 2.000 0.40 2085 0.20
2007
9
0.222
0.225
0.054
0.002 0.334 0.77 0.000 0202 0.72
First
First closs
First class (c) RPNN wanolooue-acceleetiiee..
(A) ReL. network in classical comp.
(b) Tree networks quantam-cllssical comp.
scheme
The test accuracy of neural networks on different computing platforms for pairwise clas- sifiers in MNIST: (a) ReLU network in classical computing; (b) tree tensor network (Huggins et al.)
Figure 1:
2019 in hybrid quantum-classical classical computing: (c) the proposed BPNN in the
epilogue computing scheme (See Appendix B for detailed experimental setup).
nessing the exponentially increasing research works to exploit the high- parallelism provided by
quantum computers to accelerate neural networks (Perdomo- et al. 2018 Huggins et al. 2019
Cong al., 2019 Kerenidis et al. 2019 Francesco et al. [2019] Bisarya et al.] 2020 Broughton
iet al., [2200] Jiang et al.j 2020 Tacchino et al.) 2020] Xia & Kais 2020). The existing works have
demonstrated that the quantum neural network can achieve state-of-the-art accuracy for some tasks.
For example, Figure I demonstrates the test accuracy comparison of different neural networks tar- geting pairwise classihers in MNIST (LeCun al. 1998)). The average accuracy gap between that in Figure [ a and Figure ()) is merely 0.5%. However, the penalty for achieving high- high-parallelism in quantum computing is the constrained computation types to be performed. As result, neural net- works designed for quantum computing has limited operations, indicating that the networks designed for classical computing may not be implemented on quantum computers. This raises a fundamental problem: whether the neural networks in quantum computing attain universal approximability?
The failure to attain universal approximability will fundamentally hinder the neural networks in quantum computing being used in practice due to the significant accuracy loss for specific functions. Therefore, it is imminent to understand the expressivity of neural networks dedicated to quantum computers. Motivated by this, we prove that the neural networks in hybrid quantum-classica computing can approximate a wide class of functions with arbitarily small error. We also establish complexity bounds, which gives practical insights in designing networks for quantum computing.
3
MAIN RESULTS
Figure iillusrrates the adopted prologue- wwteraacceeeeracccciiiieee computing scheme. It is a practical scheme with the small number of quantum-classical data transfer and the neural network designed for this scheme can achieve competitive accuracy against classical computing as demonstrated in Figure D In addition, the target computing scheme is a special case of that used in Tensorflow Quantum (Broughton et al.] 2020); therefore, if we can prove that the neural networks designed for have universal approximability, then the conclusion can be directly derived to Tensorflow Quantum. In this work, we follow the idea from Yarotskyy 2017 Ding et al. 2019) by constructing computing
a neural network (namely BPNN, see Section 4.1) in the scheme (see Section with bounded maximum error (see Section 4.3) for a wide class of functions (denoted as Fa.n. see Section 4.2). In such a proof, the fundamental function to be implemented is the Taylor polynomial. In the next, we first state the main result of the Taylor polynomial of function f E Fa, on the quantum computing (see Appendix A.5 for the formal version).
Results 3.1. For any given function ʃ E Fa.n and expansion point k its Taylor polyno- mial at point l can be implemented on the quantum computer, such that (i) the network can ex- actly implements the Taylor polynomial, (ii) the depth is O(log n), (iii) the number of gates is On log n log d), (iv) the number of qubits is O(n² log
Here, we observe that since the Taylor function can be exactly implemented by the quantum com- puter, the complexities on depth, gates, and qubits are not related to error bound e. This will be the
3

---

computing scheme follows; the formal Under review as a conference paper at ICLR 2021
Prologue
Quantum Acceleration
Epilogue
Computing platfoems:
Clamioal
Given:
espaaciin paint
finction::
J
The 1 Tylor expansion within sagment in total: polcssepillooc
evvor bound::
Co
equanion on 4s
Rosic neurai-basal finntions::
Dirt
* Outputing constant C:
Inpowr
Euld
Tox
Mullipliation fanction:
Data Prep.:
Seatling
+ Lincar function: !
* n--oter non linear function:
Unitory Mat
+ Tragenoid filtr function around expassion point kiS, [T
Scoling
KEpONOvin PAINE ON
Data x Blownng along the adge:
Figure 2: Illustration of the prologue- prologue-accel wtwpeueeaccceeeeroeeppppllllleee epilogue computing scheme used in this work.
root cause that the upper bound of neural networks in hybrid quantum-classical computing scheme can approach to the lower bound of ones on classical computing (see the comparison at the end of this section). In addition, the classical computing cannot build such a system, because there are too many inputs, reaching up to d=+1, which is infeasible for classical computing with exponentially increasing inputs. On the other hand, quantum computing can take advantage of encoding n inputs to log qubits, and therefore, it is feasible to implement such a network on quantum computer.
The above result shows the ability of BPNN to exactly implement Taylor expansion at any point. Then, combined with the classical Prologue for quantum-stale preparation and the classical Epilogue for accumulate results at all expansion points, we next state the main result of approximating a function f E Fa,n on the prolouuesccellrniion--ppplo version can be found in Appendix
Results 3.2. For any given function f E Fa.n. there is binary polynomial neural network with a fixed structure that can be implemented in the hybrid quantum-classical computing scheme, such that (i) the network can approximate f with any error c E (0, 1), (ii) the overall depth is O(1); (iit) the number of quantum gates is O ((1/)))): (iv) the number of qubits is O (11/)))) (v)
the number of weights classical computer is O (1)
From the above result, we can see that the upper bounds on the depth and the number of weight/gates of the same asymptotic complexity for both the quantum portion and classical portion in the hybrid computing system, which satisfies the constraint discussed in Section 4. to take full use of quantum computing. We further compare the complexity bounds between the BPNN on the hybrid quantum-classical computing scheme against the classical networks constructed for bound analysis.
Comparison with the upper bounds for neural networks on classical computers: To attain an approximation eтror c, Fan et al. (2020) demonstrates that the upper bound on the number of weights for unquantized quadratic network is (log(log(L/e)) x (1/e)=)), )). and Ding et al. (2019) demonstrates that the upper bound on the number of binary weights of the ReLU neural network is (llog((1/c) x (1/6) ²) On the other hand, for the BPNN on hybrid quantum-classiet computing, both the number of gates used in quantum acceleration and the weights used in classical prologue and epilogue are (((L))))). Although BPNN has similar expressive power compared with the binary ReLU network and reduced expressive power compared with the unquantized quadratic network (due to the constraints on weight selection), the obtained upper bounds are of asymptotically lower complexity, which again shows the benefits of quantum computing for neural networks.
Comparison with the lower bounds for neural networks on classical computers: We further compare the lower bound of the number of weights/gates needed to attain an error bound e on a clas- sical computer. The only established result in the literature is for unquantized ReLU network (Yarot- sky 2017), which suggests that to attain an approximation error bound of c, the number of weights needed least 2loo 2pp10g222p1100 (1/ee) x (1 (1/e)d/m) with depth constraint of O(lgg" (1/e)) where p is a constant to be chosen to determine the growth rate of depth. In this work, we demonstrate that the depth of BPNN in hybrid quantum-classical computing can be ((1) and the upper bounds on the number of weight/gates are ((1/c)d//)) (both quantum and classical computers). Apparently, our upper bounds are even approching to the lower bound of the networks on classical computers, which are unquantized and should have stronger expressive power. This clearly demonstrates the potential quantum advantage that can be attained.
4

---

Under review as a conference paper at ICLR 2021
(a)
x
(x-x+b)l
(b)
(x+c/4)2
(c)
(d)
b
d
(X-2/433
fak
Linnur Quaddratic Fun
consimicted bosic neursi-hesal functions:
350
Figure 3: Illustration of three basic neural computation used for the prologe--cceerraion--pppeuu computing scheme: (a) function fc to obtain constant c; (b) function fm for multiplication; (c)
function fe.k with four ReLU functions in terms of the expansion point k/S to act as selector; (d)
the output of function fo. in terms of input
NEURAL NETWORK IN HYBRID QUANTUM-CLASSICAL COMPUTING SCHEME AND ITS UNIVERSAL APPROXIMABILITY
4.1 NEURAL NETWORK IN M "PRLLDGUEAACCLEERTTTTPPPPCCCC SCHEME
A trivial solution for the hybrid quantum-classical computing scheme in Figure 2 is do nothing on the quantum computer during the acceleration phase and load all the computations simply on the classical computer during the prologue epilogue phases. In this case, all existing results on universal approximability and complexity bounds for classical computing can be readily applied. However, such a solution does not exploit any quantum power and thus is of little interest.
Accordingly, we add the constraint that when implementing a neural network, the computation in the quantum acceleration phase should be least of the same asymptotic complexity compared with that in the classical prologue and epilogue phases.
With full consideration of the limitations and advantages of the quantum acceleration, we apply the most basic neuron operations: the binary weighted sum and the polynomial activation function. Such network is called binary polynomial neural network (BPNN) in this paper. Let æ be the d- dimensional input, æ E [0, 1]d. We define the neuron operation in BPNN to be function O 0: x y. where y E [-1, 1], which can be formulated follows:
( = a (wTx +)
(1)
where E {-1, +1 represents vector of binary weights; b [0. is the bias; is the activation function, which can be polynomial function. Kindly note that bias can be relaxed to E IR and polynomial ReLU functions for the epilogue phase.
4.2 UNIVERSAL APPROXIMATION AND ERROR BOUND OF BPNN
The function space Fd,, considered in this work is defined as
Fan (f Wm.
wom.0o((1) (I0, 114):
max ess DD" S 11}
(2)
|| S 2e|o.1j
where Wm. ypo, 1]d) ) is the Sobolev space on [0, 1]d consisting of functions lying in L along with their weak derivatives 7 up order n. Kindly note that the weak derivative indicates that is not necessary to be differentiable and the function space Fa,n includes a wide class of functions.
In this subsection, we going show that for any target function Fa,n. there is a function f2 with a particular form that can approximate f with arbitrarily small error. This particular form of f2 will enable to realize it with BPNN and implement it with hybrid quantum-classica computing scheme precisely and efficiently, which gives the universal approximability.
We start with the construction of two basic functions in BPNN: (1) obtaining an arbitrary constant; (2) conducting multiplications. To obtain an arbitrary constant within the range [0, 1], we formulate a one-layer neuron follows.
Proposition 4.1. Let Je be a sub-nelwork of BPNN with only two weight values -1 and + An arbitrary constant can be obtained by fc, such that the approximation error e, 0.
By setting w = (+1.-1)7. x = (z, x)"" and b = c, an arbitrary constant c can be obtained, shown in Figure aa) Once the constant is obtained, we get Proposition 4.2 to carry
5

---

Under review as a conference paper at ICLR 2021
multiplication between constant and variable It can also obtain the multiplication of pair of variables x and y.
Proposition 4.2. Let fm be a sub-network of BPNN with only two weight values -I and +I. Given variable x and variable y (or constant y). the multiplication ay can be derived from f such that the approximation error Cm = 0.
Since the square function is provided in a. we can obtain 4zy based on the fact that (x+ -)2-m)=--
y)² = 4ry. According to Proposition 4.1 we can create a constant scaling factor to adjust the value from 4xy to ry. Details please see Figure 3 b) and refer to Appendix A.I
We employ function (x) to perform "selection" operation. Considering the input has one variable, we divide ft on segment 00, 1] to S segments, which provides points for the Taylor expansion. At each point, & E [0, S]. it is corresponds to one Taylor expansion, denoted as ff, as shown in Figure 2 At run time, all these functions take the inputs for execution, and at the end of the neural network, they go through "selection function" to extract the nearest expansion point in terms of inputs. For instance, if expansion point x 0.25 and the step of S segments is 0.1, only f and få may contribute to the final result. In our implementation, for around the expansion point 35 S 3k+2),, it can be approximated using f (i.e., by multiplying 1); however, it 33 or m >
E (i.e., 3k-2
33
cannot be approximated by ft" where m
3k-2
3k-2 (i.e., by multiplying 0). To enable 35
the above function, we apply the basic neuron operation to implement function h(,, 5-
k h(,,
38
5) =
2 - 3S -12
< x
(3)
35
35
0
otherwise
Extending to the case of d > for k (Ki,, kk) E {0,
S}d we have vu((x) defined as
d
k 5). [h(E
the = II
(4)
Proposition 4.3. Let Jo be a sub-network of BPNN with only two weight values -1 and +1. Given the expansion point 5. the function vx can be implemented by fo using the ReLU function and the multiplication implemented by fm-
&
As shown in Figure
3 c), we apply four ReLU functions to implement function k(r,
35 Basically,
we apply ReLU(x (x y). where y E {a, b, c, d). Specifically, for ReLU a), it creates the first turning point, then point b, it uses Lu a) LU - b)) to create the second turning point. Finally, the figure in Figure ( can be obtained. Then, scale it up h(r, }) Kindly note that segments [a, b) and Jc, in Figure
c)) will be overlapped the expansions at 1-1 and Lastly, by multiplying Mxx 8) we can obtain v/x()) (a:) in the case of 1.
k+1 S
After showing that BPNN can realize the above operations, we ready to demonstrate the uni- versal approximation property of BPNN by proving that it can implement a complex function that approximates any ʃ E Fa,n with arbitrarily small error.
Lemma 4.4. For any f E Fa,u there exists a function f2 = EkEjo,.. .ss t/k Elpolle o
2d that can be realized by BPNN and can approximate f with error 8 < m! ($) where S and Ck.v constant, E 10, n 1)d.
The proof utilizes the function approximation idea from Yarotsky (017). We partition the unity on J0, 1jd and approximate f using the Taylor polynomial of order n=11, denoted ft. Then, we prove that the approximation function can be rewritten to the given form and the approximation error can be bounded to an arbitrarily small ö. The complete proof is in Appendix A.2
In summary, we have shown that BPNN can realize a few basic functions through the propositions. Then in Lemma 4.4 we show that by using these simple functions as the building block, we are able to approximate any f by a function fa realized by a BPNN with arbitrarily small error, which gives the universal approximation property and error bound. The expansion point at K/S in Figure 2 giives an example to obtain f2 when & = and d = 1. In the figure, fo.o to fo.s represents 1/a- For k (x) in the figure represents Σ |1 <n 2k

---

Under review as a conference paper at ICLR 2021
4.3 APPROXIMATION PROCHDURE IN EHROLOGUE-ACCELERCEE -PIIIOUUU
In order to construct a BPNN network in the hybrid quantum-classion scheme to obtain the bounds, we need to solve the following problem: Given a function f in function space Fa,,, an error bound >> O, and set of inputs, the neural network accelerated by the quantum computer and finalized in the epilogue needs to approximate the given function f. such that the approximation error is no more than c. Based on Lemma 4.4 take Taylor polynomial as a bridge and construct BPNN hybrid quantum-classical computer to approximate the Taylor polynomial to establish the bounds. Specifically, we need to determine whether to quantum computer classical computer to imple- ment each function at the expansion point k; i.e., f As illustrated in Figure 2 the prologue phase conducts data preparation, the acceleration phase accelerates Taylor expansion all points, and the epilogue phase implements the selection function. In the following texts, we use the expansion point at & as an example to demonstrate how the hybrid computing scheme works.
the
s
Prologue phase. The classical computer conducts the data preparation: it encodes n input data (including the variable and its coefficient) into log n qubits. We apply the same data encoding method in Stravo-Prieto et al.) 2020) Jiang et al. (2000), that is, constructing an unitary matrix A, such that all inputs are normalized to the first column vector A in A. Then A is encoded to the quantum states. Limited by the data representation of qubits, we have || S. 1. If
|| < 1, we can add an additional dummy value to make sure the sum of inputs to be 1; while if || > 1, we scale all the inputs to make sure that they can be encoded to log n qubits. As pointed by Bravo-Pricto
et al.] (020). a single column in a unitary matrix A can be decomposed to the quantum circuit with gate complexity of O(log n), where log is the number of qubits. In our case, we only need to decompose the column A in the matrix A for quantum-state preparation on log n qubits.
Quantum acceleration phase. The function of Taylor polynomial is implemented on the quantum computer. Compare to the classical computer, quantum computing has limitations that restrict the operations in the neural networks.
First, non-linear functions such as ReLU needs to be implemented as classical Boolean circuit with duplicate registers, which incurs high cost.
Second, since the computation is based on the amplitude, it has the constraint that the real part of all data should range from -1 to 1.
For the non-linearity issue, it can implement the quadratic or even higher-order polynomial function by repeatedly executing the same operations on different qubits. For the data range issue, we can scale the inputs and outputs on the classical end. In addition, the quantum computer has obviously advantages over the classical counterpart. It can use log qubits to represent data and achieve massive parallelism. Section 4.4 will present a design to take full use of such an advantage.
Epilogue phase. After the computation intensive tasks completed by the quantum acceleration, the epilogue phase collects data for all expansion points, and selects the correct one in terms of the input to formulate the final result. We move the selection procedure to classical computer to take advantage of the low-cost ReLU non-linear function. Specifically, we apply 4 ReLU functions to formulate function shown in Figure Bc). c). After this, we sum up all the results. Since the selection function will prune the results if the inputs do not belong to the expansion points, the output vector has large sparsity with at most 2d (i.e.. 2 for d 1) non-zero values, among over d" S outputs. Therefore, it can be performed efficiently on the classical computer.
4.4 IMPLEMENTATION OF NETWORKS IN QUANTUM ACCELERATION
The quantum acceleration phase implements a set of sub-networks to obtain the output of Taylor polynomial all expansion points, i.e., Yk E {O..... ,S3, ft.. Since the structure of all sub- networks are the same, we focus on one sub-network net, to implement function ft.
Before introducing the detailed implementation, we first define quantum sub-system Q." to be the tth sub-system which is composed of m qbits to represent 2dd inputs at most. Then, we define notation "o"" between m and Q,n² to be the tensor product of these two quantum sub-systems. For example, for m1 = 2 and m2 = 2, we have QTa to be a sub-system with two qbits (vv))) and Qm to contain (0222). Then Q @ Qm² = (0001) @ (d2Ø3) = bdog (202)). Let A ((o01) = 100) = be the amplitude of sub-system Qr to be (00) state and Allo2(a) 100) } = 02 for Q By combining these two sub-systems, we have system Q4,2. where the amplitude for state
7

---

Under review as a conference paper at ICLR 2021
(8)
(c)
states
gbit
(x-cal
(xtr
H
H
H
Q
H
x Cg
(x-c))
Ancilla
Figure 4: Illustration of quantum implementation of l.: (a) implementing a set of parallel neuron computations with only one gate; (b) the multiplication function to achieve cpr; (c) the corre- sponding quantum circuit for egæ, with the state transitions represented in the rectangles.
(0000) is A (10011222)) the polynomial non-linear functions, since it can automatically multiply the corresponding states.
]0000)] = ai 0g. Kindly note that such combination is the base for
Basic operations. We now introduce the implementation of basic operations in BPNN on quantum computers, including (1) linear function w æ, and (2) high-order polynomial activation function a.
For a linear function w" x. it can be implemented in two steps: (1) encoding d inputs in vector x to a system with 2 foog (d+1)] states represented by [log (d + 1)] qbits, where "I" is a dummy input to guarantee the sum of squared states be 1; (2) encoding binary weights
these [log (d + 1)1 qbits using Pauli-Z gates or Controlled-2 ZZ gates. For the linear function w x + b, the bias can be encoded along with the inputs, and add an additional weight with a value of +11
Let y - : x ao+b6 b, the quadratic function, (v) y² can be implemented by using two quantum sub-systems (e.g.. Qi and Q2) and each of which implements the same function to get y. At the end of these operations, both zero states |0- (0..-0) -O) in Q1 and Q2 are y, and the |0... (0-.-0) 0) state in the combination of these two systems, Q1.2, will be y². Similar to the implementation of y², the high-order non- non-linearity (c.g.. y²"), can be implemented with m quantum sub-systems.
Based on the above designs, the neuron operations can be implemented on the quantum circuit. We next consider the implementation of fe top of these basic designs.
High-parallelism and low-cost design. An arbitrary design may not make full use of the high- parallelism of quantum computing and result in high cost in circuit depth and width. We fully exploit the parallelism of quantum operations by using the following property of BPNN.
Property 4.5. For an n-input neuron in BPNN whose activation function is polynomial linearity or non-linearity, it can be decomposed to [log2n] layers, such that each neuron has at most inputs.
A network construction can be carried out complete the transformation. We can divide inputs to [ groups, each of which contains 2 inputs, and then apply their corresponding weights in the first layer and use {+1,+1} for all the remaining layers. The linear function is applied as the activation for the intermediate layers, and the original activation is applied to the last layer. For the sub-network nety for function f%, the network itself has this property in calculating all terms in Taylor polynomial (see Figure 2 In addition, all the weights for these neuron operations are either (+1,+1} {-1,-1} (see Figure (b). This allows us to take advantage of massive parallelism provided by quantum computing to accelerate these operations.
Proposition 4.6. Let net be a layer in BPNN with 2-input neurons in total, and there are m neurons in total. Let Q² be quantum system with l qubits, and 2m inputs of net are encoded to 2 states in Q+. If all neurons have the same weights, then all m neuron compulations can be completed in 3 steps with at most 3 basic quantum logic gates.
The proof and the details of the quantum circuit constructed are included Appendix A.3 In general, this proposition indicates that quantum computer can significantly accelerate batch of neuron computations with extremely low cost. Take a further step, we have Proposition 4.7
Proposition 4.7. Let net be a layer in BPNN with 2-input neurons in total, and there are x m neurons in total, and each 2-adjacent (pair) neurons share the same inputs. Let Q² be quantum system with k qbits, and 2m inputs of net are encoded to 2 states in Q². If each pair of neurons has odd number +1 weight and all pairs of neuron have the same weights, then all 2m neuron computations can be completed in 3 steps with at most 3 basic quantum logic gates.
The proof and the details of the above proposition included in Appendix A.4 We can see that the neuron operations in sub-network nete for function J satisfy the above condition, where each pair
8

---

Under review as a conference paper at ICLR 2021
of neurons with the shared inputs has odd number (i.e., 3) +1 weights, and all pairs of neurons have the same weights. In fact, for this specific weights, all these neuron computations can be conducted in parallel with only 1 Hadamard H Gate, shown in Figure Fa).
Quantum design of sub-network for multiplication function fm. Multiplication is the core oper- ation in the sub-network net, for function f. In particular, each term of Taylor polynomial is only composed of the multiplication between "constant and variable" or "variables". We demonstrate the multiplication operation in Figure (b)- For the simplicity of presentation, we assume that the inputs v and co can be encoded into 2 states (i.e, x² + cj 1) in two quantum sub-systems (Q) and 24), otherwise, we can add dummy states using an additional qbit for the encoding. In this example, we employ two sub-systems Qi and Q2 for the quadratic function, and a CNOT gate is applied to adjust the position to make the square terms in the front of states. Then, two H gates are applied for the second-layer neuron computation. Finally, the multi-controlled not gates are applied to extract the amplitude (i.e., Co X 2)) to an Ancilla qbits for measurement.
Kindly note that since the measurement is the probabilistic domain while the computation is based on the amplitudes, a square operation will automatically conducted. To make the whole system consistent, we use the square root on each input and coefficient during the encoding. Another observation is that every term in Taylor polynomial has one state, we extract all terms at the end of the procedure, it will lead to high cost. To overcome this, observe that the results using H gates with a scale of v2 for each H gate. As a result, we only need one multi- controlled NOT gate for each quantum sub-systems.
accumulate
Proposition 4.8. If the order of term be k, its corresponding sub-network in BPNN contains [log k] layers. Then, the implementation on quartum computer involves 2k quantum sub-systems.
Without loss of generality, consider k: = 2 and m is positive integer (otherwise, we can add dummy 1s). We can apply the divide-and savide-and-conquer approach to compute pair of variables at each time. As result, the operation can be completed in m layers. For each multiplication, we need quantum sub-systems as shown in Figure (c). Therefore, involves 2k quantum sub-systems.
Based on the above design, any terms in Taylor polynomial can be implemented. Kindly note that the real number is applied in each step, and therefore, there will be no computation error for the implementation of f( on quantum computer.
CONCLUSION AND INSIGHTS
Although the implementation of neural network in quantum computing is still in its infancy, results in this work provide theoretical and practical insights for the design of neural networks for quantum computing to fully harvest the quantum power in the hybrid guantum-classical computing scheme.
Neural networks designed for hybrid quantum-classied computing, including TensorFlow Quan- tum, have the ability to approximate a wide class of functions with arbitrarily small error.
For the near-term hybrid quantum-classical neural network designs, the proposed prologue- promising computing scheme to achieve high accuracy with only two interfaces between quantum and classical portions for data conversion.
interrationeppllguue architecture
Based the depth complexity of O(1) for a hybrid quantum-classical computing scheme, it inspires us that the design of network may consider a "shallow" quantum circuit, instead of the "deep" version on classical computer. The power of shallow circuits has been demonstrated in the recent works (Benedetti et al. 2019 Cerezo et al. 2020
Putting all together, this work demonstrated the combination of machine learning and quantum computing is a promising research direction, and the results can guide future research works in the design of neural networks for quantum computing.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David Buell, al. Quantum supremacy using programmable superconducting processor. Nature, 574(7779):005-510 2019.
Marcello Benedetti, Delfina Garcia-Pintos, Oscar Perdomo, Vicente Leyton-Ortega, Yunseong Nam, and Alejandro Perdomo-Orti A generative modeling approach for benchmarking and training shallow quantum circuits. npj Quantum Information, 5(1):1-9, 2019.
Aradh Bisarya, Shubham Kumar, Walid El Maouaki, Sabyasachi Mukhopadhyay, Bikash Behera, Prasanta K Panigrahi, et al. Breast cancer detection using quantum convolutional neural networks: A demonstration on a quantum computer. medRxiv, 2020.
Miles Blencowe. Quantum ram. Nature, 468(7320)) 2010.
Carlos Pravo-Prieto, Ryan LaRose, Marco Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick Coles. Variational quantum linear solver: A hybrid algorithm for linear systems. Bulletin the American Physical Society, 65, 2020.
Michael Broughton, Guillaume Verdon, Trevor McCourt, Antonio J Martinez, Jae Hyeon Yoo, Sergei V Isakov, Philip Massey, Murphy Yuezhen Niu, Ramin Halavati, Evan Peters, al. Tensorflow quantum: A software framework for quantum machine learning. arXiv preprint arXiv:2003.02989, 2020.
Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick Coles. Cost-function- dependent barren plateaus in shallow quantum neural networks. arXiv preprint arXiv:2001.005550 2020.
Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physics, 15(12))1273-122) 1278, 2019.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Alberto Delgado. Function Approximation with Quantum Circuit. 2018.
Yukun Ding, Jinglan Liu, Jinjun Xiong, and Yiyu Shi. On the universal approximability and com- plexity bounds of quantized relu neural networks. International Conference on Learning Repre- sentations (ICLR), 2019.
Alexandr A Ezhov and Dan Ventura. Quantum neural networks. In Future directions for intelligent systems and information sciences, pp. 213-235. Springer, 2000.
Fenglei Fan, Jinjun Xiong, and Ge Wang. Universal approximation with quadratic deep networks. Neural Networks, 124:383-399 2020.
Tacchino Francesco, Macchiavello Chiara, Gerace Dario, and Bajoni Daniele. An artificial neuron implemented on actual quantum processor. NPJ Quantum Information, 5(1), 2019.
Google. Tensorflow quantum. http:://ww..eenooffooooo/amuuuua 2020. Accessed: 2020-09-30.
Kurt Homik, Maxwell Stinchcombe, Halbert White, al. Multilayer feedforward networks universal approximators. Neural networks, 2(5):359-366, 1989.
William Huggins, Piyush Patil, Bradley Mitchell, K Birgitta Whaley, and E Miles Stoudenmire. Towards quantum machine learning with tensor networks. Quantum Science and technology. (2):024001, 2019.
IBM. Ibm quantum experience. http:://qaaatttnn-ooppttttgt..gh 2016. Accessed: 2020-10-01.
roadmap for IBM. http:://ww........ooooooeereeeet http:///wwaaaaataa/////////eerne homp:///ommmmmuuutummmammmmooooo
Ibm's
scaling
quantum
technology. Accessed: 2020-
2020.
09-30.
10

---

Under review as a conference paper at ICLR 2021
Weiwen Jiang, Jinjun Xiong, and Yiyu Shi. A co-design framework of neural networks and quantum circuits towards quantum advantage. arXiv preprint arXiv:2006.148)) 2020.
Subhash C Kak. Quantum neural computing. In Advances in imaging and electron physics, vol- ume 94, pp. 259-313. Elsevier, 1995.
lordanis Kerenidis, Jonas Landman, and Anupam Prakash, Quantum algorithms for deep convolu- tional neural networks. arXiv preprint /rXiv: 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228--2524, 1998.
Jarrod McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik, The theory of vari- ational hybrid quantum-classical algorithms. New Journal of Physics, 18(2):023033, 2016.
Hrushikesh N Mhaskar and Charles A Micchelli. Approximation by superposition of sigmoidal and radial basis functions. Advances in Applied mathematics, (3(3):350-377) 1992.
Alejandro Perdomo-Ortiz Marcello Benedetti, John Realpe-Gómez, and Rupak Biswas. Oppor- tunities and challenges for quantum-assisted machine learning near-term quantum computers. Quantum Science and Technology, 3(3):030502, 2018.
Gopathy Purushothaman and Nicolaos B Karayiannis. Quantum neural networks (qnns): inherently fuzzy feedforward neural networks. IEEE Transactions on neural networks, 8(3):679-693, 1997.
Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. The effect of data encoding on the expres- sive power of variational quantum machine learning models. arXiv preprint arXiv:2008.0880 08605, 2020.
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions is universal approximator. Applied and Computational Harmonic Analysis, 43(2):233-268, 2017.
Francesco Tacchino, Panagiotis Barkoutsos, Chiara Macchiavello, Ivano Tavernelli, Dario Gerace, and Daniele Bajoni. Quantum implementation of artificial feed-forward neural network. Quan- tum Science and Technology, 2020.
Menno Veldhorst, CH Yang, JCC Hwang, W Huang, JP Dehollain, JT Muhonen, S Simmons, A Laucht, FE Hudson, Kohei M Itoh, et al. two-qubit logic gate in silicon. Nature, 526 (7573):410-414, 2015.
Yanzhi Wang, Zheng Zhan, Liang Zhao, Jian Tang, Siyue Wang, Jiayu Li, Bo Yuan, Wujie Wen, and Xue Lin. Universal approximation property and equivalence of stochastic computing-bes based neural networks and binary neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 5369-5376, 2019.
Rongxin Xia and Sabre Kais. Hybrid Quantum-Classical Neural Network for Calculating Ground State Energies of Molecules. Entropy, 22(8))828, 2020.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.

---

Under review as a conference paper at ICLR 2021
A PROOFS
A.1 PROOF OF PROPOSITION 4.2
Proposition 4.2 Let fm be a sub-network of BPNN with only two weight values -I and +1. Given variable a and variable y (or constant y), the multiplication zy can be derived from fms such that the approximation error Cm
Proof. We show the correctness of the proposition by constructing 2-layer neuron network using the basic neuron operations for both multiplications between "variable and constant" and "vari- ables".
First, we construct the multiplication of x x between variable and a constant e (i.e., W. As shown in Figure b), we first using Proposition 4.1 to form constant 1. Let x: (I, 4)² be 2-dimension input and z be the output; and let w. big and Ts.j be the weights, bias, and activation function the jth output neuron at the 7th layer, respectively. We set W1,1 = [+1,+ +1}, W1,2 = W2,1 = (+1.-1}. b1.1 b 12, 0, I1,1 and 01,2 be the quadratic function, and 02 be the linear function. Then, we can represent x z using two layers the neuron operations: 01, #1j 1 x (wT,, and 0221 x x (w o b2,1), where
(01,1.01,2)
Second, the multiplication of ry between two variables can be constructed in a similar way. The only difference is that we need additional multiplication scale the results of 4xy to ry. Specifically, we can initialize two inputs as 4ry and T6
A.2 PROOF OF LEMMA 4.4
Lemma 4.4 For any f E Fa.m there exists function f2 = Eke (0.....9a the Elplll> <n v
that can be realized by BPNN and can approximate f with error 5 S nt (5)) where S and Ck constant, E {0, 10,1.....
2a
1)d.
Proof. We define the approximation to as
S2
Σ
whe Ph.R.
(5)
(0......
where (m) is the order n - Taylor polynomial at S. Specifically, we have
k
D
k
Pa(ar) = Σ
x
(6)
n!
S
||m| I<n
where (nI..... na) E (0,1....,11 1 The approximation enror to f can bounded by Equation
If(x) f2(x))
Σ the (f(( Ps (=))
< 2d
max
1f(z) - Px(x)]
k:|0,
2 d
1
max ess sup 10th f(x)
n!
$
|n|=n
2d
<
n!
$
The second step is based the fact that any x E [0, 1jd is on the support of at most 2d 4/ functions. In the third step, we use the Lagrange's form of the Taylor reminder and lastly we use maxn:/n/=x css sup D f(x) <
The first line follows Eke (0....... v2((x)
Using the binomial theorem, can be rewritten
12

---

Under review as a conference paper at ICLR 2021
12
Σ tK Σ
Σ
Σ
Ck. n.
[elll vienn
(8)
V
C
RE (0...
1/ <n
dd. Kindly For the implementation of each term in BPNN, it involves the multiplication of a constant and an input variable with the nh order non-linear function, which can be implemented using the basic neural operations in Figure B with a constant number of weights (i..., 2 for constant generation and 6 for multiplication). Then, all the terms will be sum up using a linear activation function, and the number of weights is the same as the number of terms. As result, the complexity of the corresponding neural network is d(Sdd=1))
where v = (01,..., Ud) E {0, 1,..,,,, 1]d and v & n means oi S ny for i E (1....,,)}
note that the number of terms Ck, " in f2 is [k] | S (S 1) Σi= E d: (S ())
Given Proposition
and
we can conclude that f2 can be realized by BPNN.
A.3 PROOF OF PROPOSITION 4.6
Proposition 4.6, Let net be a layer in BPNN with 2- 2-input neurons in total, and there are m neurons total. Let Qa be a quantum system with & qbits, and 2 m inputs of net are encoded to 2 states in Qt. If all neurons have the same weights, then all m neuron compulations can be completed in 3 steps with at most 3 basic quantum logic gates.
Proof. First, the 2-input neurons have possible (+1,,+),,+1, (+1, (-1, (1), (-1,-1))
pairs of weights: Let's first consider Q', where we have introduced the following texts Then, the gate applied on the qbit
(z1, x2) which will conduct the matrix and vector multiplication. Therefore, we can regard each row in the matrix representation of gates to be the weight pairs.
[
1
First, know that the matrix representation of H is
contains weights pairs
/2
-1
(+1, and (+1, -1).
1
1
0
-1 = - =
Second, we can use Zxxx
get ZxXxH 2
V2
0
-1
x
X
Now, we have the weight pair (-1, -1).
Third, we can apply H x X to get matrix which contains weight pair (-1,1). We have H x X
0
1
1
-1
V2
1 1
0
The above results demonstrate that at most 3 quantum gates (the second case) are needed to cover all weight pairs.
Next, we demonstrate that no additional gates are needed for computing multiple neurons with the same weights. To demonstrate this, let's first consider the tensor product operator, which is
applied to obtain the matrix of parallel gate, For instance, & v
x
1
1
-1
0
0
The observation here is that by tensor product of the gate and identity gate
0
0
0
1
-1
I, the weights for each pair of inputs are the same. Kindly note that identity gate indicates that no gate is placed and no gate cost all.
Therefore, we can conudct x m operations at the same time with at most 3 gates to cover the weight pair.
13

---

Under review as a conference paper at ICLR 2021
A.4 PROOF OF PROPOSITION 4.7
Proposition 4.7, Let net be layer in BPNN with 2-input neurons in total, and there are 2 x m. neurons in total, and each 2-adjacent (pair) neurons share the same inputs. Let Q be a quantum system with k qubits, and 2 inputs of net are encoded to 2 states in Q². If each pair of neurons has odd number of +1 weight and all pairs of neuron have the same weights, then all 2 x m neuron computations can be completed in 3 steps with most 3 basic quantum logic gates.
The proof of this proposition is similar to Proposition 4.6 From the proof procedure in Proposition 4.6 it is clear to see that one gate can perform neuron computation at the same time, meanwhile the values of weights are different. In addition, due to the matrix representation of gate need to be unitary, we cannot engagement the same weights in one gate operation. It is equivalent to that the number of both weight +1 and weight - needs to be an odd number.
A.5 PROOF OF RESULT 3.1
Results 3.1 For any given function f E Fd.n and an expansion point k, its Taylor polyno- mial at point can be implemented on the quantum computer, such that (i) the network can ex- actly implements the Taylor polynomial, (ii) the depth is Ollogn,, (fii) the number of gates is O( log n log d), (iv) the number of qbits O(n² log d).
Proof. The cost quantum circuit comes from 4 parts. Figure 4 c) demonstrates the first parts: computation (i.e.. H gate), state position adjustment (i.e., CN gate), and state extraction (i.e., multi-controlled NOT gate). In addition, as stated, we apply H gate in each sub-system to sum up results of the tt order term.
In our design, the gate complexity for H is On log n), since each layer of each sub-system needs H gate, and there are log layers (see Proposition 4.8) and sub-systems.
For CNOT, for each layer at each sub-system, the number of CNOT is half of the number of qbits, which is (n 1) log(d) (d). There are log layers and sub-systems, and therefore, the complexity is (n² log n log d).
Next, for the H gates used for summation, the usage is related to the number of terms to be summed up. For the 2th order term, it involves d' addition, while we can use H gate as a adder tree, which will involve log(d") = i log gates. Therefore, the upper bound O(n logn).
Finally, for multi-controlled NOT gate, each sub-system needs one multi-controlled NOT gate, where the number of control ports is the same as the number of qbits. A k-controlled NOT gate can be broken down to poly(k) standard Toffoli gates. Therefore, for n sub-systems and each sub- system with On log d' gbits, the cost complexity for the multi-comtrolledd NOT gate O(n" log d).
Overall, the cost bound of the quantum implementation for f. is O log n log d).
A.6 PROOF OF RESULT 3.2
Results 3.2, For any given function f E Fd.., there is a binary polynomial neural network with a fixed structure that can be implemented in the hybrid guantun-classical computing scheme, such that (i) the network can approximate I with any error e E (0,1), (ii) the overall depth is 0(1);
(tit) the number of quantum gates O ((1/c)= &
(iv) the number of qbits ((1/))²) (v) the
number of weights on classical computer is O (L.
Proof. In Lemma 4.4 we have already proved that a BPNN fz can approximate the given function
f. whose approximation error If f2l -
2d To satisfy the given error c, we have:
n.
5
2d
d
Sc
(9)
S
2d
1
S 2 d x
x
-
(10)
n
c
14

---

Under review as a conference paper at ICLR 2021
On the other hand, according to Lemma 3.1 we have the gate number used for implementing Taylor polynomial at one expansion point is O log n log d),,, and the number of qbits to be O(n log n). For the whole system, there are d variables in total, and each of which is partitioned into S seg- ments. Therefore, there are 5d possible expansion points for the Taylor polynomial. Overall, the quantum gate number used in approximating the given function f is On log n log d x St)), which is O (1/e)") similarly, the number of qbits used for approximation is O( log S*), which
is O (1/e)*) For depth, from Lemma 3.1 have the depth of (log In the epilogue phase on classical computer, the depth is 2 (see Figure 3 (a)). Therefore, the depth of the whole neural network is (() in terms of the error bound
Finally, the weight cost on classical computer is proportional to the number of expansion points, because take the output at each expansion point where ReLU is operated. Therefore, the weight
cost on classical computer is (SS"), which is O ((1/e)*).
B EXPERIMENTAL SETUP
We use pairwise classifiers in MNIST for the test the accuracy of different neural networks on different platforms, including (1) ReLU network in classical computing in FigureTTa),, (2) tree tensor network in hybrid guantum-classica computing in Figure [b), and (3) the BPNN in the prologue- acceleration-epilogue computing scheme Figure [c). The results of the tree tensor network are obtained from Huggins et al. (2019). The result of the ReLU network in classical computing is conducted by constructing a ReLU neural network, where the input resolution 28 28 pixels, the hidden layer has 16 neurons, and the output layer has 2 neurons for the classification. Then, we train network using the learning rate of 0.01 on the Adam optimizer, the epoch 10, the batch size of 16, and the input data to be normalized to make the sum of the square to be 1. The BPNN has the same structure as the ReLU neural network, except that the activation function of the hidden layer is the quadratic function.
Now, we introduce how we test the BPNN on the prolouu-aaceeleration--ee Let denote C1 for prologue, C2 for epilogue and Q for acceleration portion. In C1,, we conduct the data prepossessing for quantum state- tiate--reprration Then in Q, we apply the neural computation and the corresponding quantum circuit design in (Francesco al. 2019 Jiang et al.] 2020). Finally, in C2, we translate the output from the quantum data to classical data and then perform fully connected layer for the final classification.
computing scheme.
Next, the training of BPNN carried out on a classical computer. Since all operations on Q have the equivalent neural computation on classical computing, it is possible for to train the network on a classical computer, which has the same training setup as the ReLU network.
Finally, we conduct the training and testing procedure for each pair of two classifiers in MNIST and obtain the results demonstrated in Figure
15


Reviews:
[{"review_id": "eQVq6oD4lBl", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The problem studied in this work is of interest in the quantum machine learning community, as the power of small and noisy quantum computers for machine learning problems is far from being understood. Therefore, it is important to study the expressivity of quantum neural networks as function approximators. This work uses the model introduced by Tensorflow Quantum, where different neurons can be implemented on either quantum or classical computers.\n\nHowever, it is unclear how this result applies to current topologies of QNN/variational circuits used in current literature. From my knowledge of quantum variational circuits, the architecture proposed is different. To my understanding, this work addresses specifically the model proposed for TensorFlow quantum, and this should probably be made more explicit, as it's somehow different from current literature, where quantum neural network architectures are the sole computational node, and no classical computation is performed classically (besides the optimization of the parameters of the variational circuit). The model described in this work is called the \"prologue, acceleration, epilogue\".\n\nIf I understood the work properly, the role of quantum computers is to evaluate on a quantum computer the \"binary\" part of a Binary Polynomial Neural Network (this is what the authors call the acceleration phase), after in a prologue part the data is loaded as initial quantum state with a log-depth circuit.Then, in the epilogue phase, a nonlinearity, like a a ReLU function is applied classically,\n \nIt is really interesting the comparison with the approximation function of neural networks in classical computers. Perhaps more (recent) literature review on quantum expressiveness of other variational circuits can be added.\n \nI checked some of the proofs in the manuscript, and they are correct. The paper is nicely written, but perhaps might benefit some more clarity, especially in the proofs in the appendix.\n\nOverall, the submission would have benefited from experiments, showing that a QNN built with the architecture proposed in this work can achieve high accuracy in classification/regression tasks. This can be either done on small quantum computers, or even simulated in GPUs or large classical computers. Also, it would have been beneficial to write more clearly section 3.3, perhaps with an example, on how the classical optimizer is meant to choose the parameters of this circuit in a machine learning problem, i.e. how this architecture is meant to be used in practice.\n\nOther remarks are the following:\n- Please use a consistent notation for multiplication. If my understanding is correct, In proposition 3.2 and the subsequent lines, you use the notation $x \\times y$, $xy$, and $x \\dot y$ to denote the same operation.\n\n-  In section 4.1 it's not clear to me what this sentence means:\n At the end of these operations, both zero states $\\ket{0}$ in $Q_1$ and $Q_2$ are y, and the $\\ket{0..}$ state in the combination of these two systems, $Q_{1,2}$ will be $y^2$. How can the zero register be $y^2$?\n \n-  What is the $p$ in the Discussion section, when discussing the result of Yarotsky?\n\n- I think in some parts of the paper the authors use $n$ for the number of qubits, and then $\\log n$.\n\n- Figure 1 could be split into two figures (left and right), and the notation in the figure could be better explained as the figure is referenced many times in the paper.\n\n- Is written in the section where the  prologue phase is described \"As pointed by Bravo-Prietoet al. (2020), unitary matrix A can be decomposed to the quantum circuit with gate complexity ofO(logn), where logn is the number of qbits.\" This is only true if the matrix $A$ is of the kind specified before, i.e. it's just one single column.\n\n- The fact that the depth of BPNN in hybrid quantum-classical computing can be of $O(1)$ is a strong result that perhaps should be compared more with the literature on the power of quantum shallow circuits or constant depth circuits.  \n\nAlso, I think the work should conform to the widespread and standard notation of using qubits and not qbits.\n\n Some typos:\n - Proof Proposition 4.2. \"the Of\" should be \"the of\".\n - After lemma 3.3 \"which is introduced in the following texts\" -> which is introduced next (or in the following section).\n - \"To take the advantages of high-parallel in quantum computing, we made an observation on the network structure of BPNN as described in the following Property.\" Might be improved. It might be changed into \"high-parallelism\" and rephrased the whole sentence.\n -Section 4.2\n \"d input variables and f has weak derivative\" should be derivativeS.\n - . This brings flexibility in implementing functions (e.g., ReLU), while at the same calls for interface for massive data transfer between quantum and classical computers. Perhaps you wanted to say \"at the same time calls for fast interfaces\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "IPcJ3lSTNE", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the expressivity and approximation properties of machine learning models where a parameterized quantum circuit is used to 'accelerate' a classical neural network. The results consider a model with a date encoder, a quantum circuit, and then a classical feedforward neural net for post-processing. To make the results non-trivial only models with asymptotically similar classical and quantum complexity are considered.\n\nUsing a technique best on Taylor polynomial approximations, the paper finds that a large class of smooth functions can be approximated using O(log(1/\\epsilon)^(n/d)) quantum gates, qubits,  and classical width. This is slightly (logarithmic factors of  1/\\epsilon) smaller than the best known upper bounds with ReLU or unconstrained quadratic networks.\n\nPros:\n\nThe paper shows how some techniques used to obtain classical approximation theorems can be extended to quantum gates. The slight improvement from the addition of a quantum element raises the possibility of showing a stronger separation in the future.\n\nCons:\nThe results in their current form do not really show any benefit (from the point of view of approximation) for quantum neural networks, since the bounds are only logarithmicallly better than classical bounds. \n\nThe technique used seems to be to use quantum units to mimic subfunctions in a manner quite similar to classical units, and does not provide much insight into why we should expect a 'quantum improvement' here.", "extra_scores": {}, "extra_text": {}}, {"review_id": "DyMreCdsikF", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides new approximation theorems for a family of functions representable by hybrid quantum-classical circuits. \n\n\nSpecifically, the paper looks at neural nets that can be evaluated quickly by a three-stage circuit, where the second stage is quantum and the first and third phases are classical. The paper shows that neural networks in such a class allow for more efficient approximation of certain functions than (a) was previously known and (b) is possible using a related class of networks that can be implemented using an entirely classical circuit. \n\n\n\nOverall, I found the paper’s significance hard to evaluate. Here are a few questions I had a hard Time finding answers to in the text of the paper: \n\n- Why is this problem important to begin with? Is the bottleneck with neural nets their evaluation, or their training? Is the hope that by using quantum computers to evaluate complex NN’s we can allow for learning more complex functions? How would one train such networks?  I felt like the big picture was missing. I know my way around quantum computing and algorithms but still found the paper hard to read and understand. I think a typical ICLR audience-member would be entirely lost.\n\n- The comparison with known bounds for classical circuits in Section 5 was quite hard to understand. Taking it at face value, the gains in complexity from moving to the quantum model seem limited: gains of $poly\\log(1/\\epsilon)$ in depth and circuit size? Is it clear that no better classical circuits are known for approximating the functions of interest? \n\nSome specific comments and suggestions: \n\n- Equation 1: What does it mean that y is bounded when sigma is a polynomial? Does sigma have to be such that it’s value is bounded on the range of possible inputs (something like $-(d+1)$ to $(d_1)$)?\n- Expand the notation in the definition of equation (2). I interpreted it to mean that derivatives of up to order n are defined almost everywhere, and bounded. But the comment after that (when n=1 and f is not differentiable) confused me. \n- Lemma 3.3: how complex is the network as a function of delta? I had trouble mapping the form of $f_2$ into the form of the network. I guess it has something like depth 3 and a number of neurons equal to the number of possible $\\mathbf{ k, v}$ pairs?\n- I felt like what was missing at the end of Section 3.2 was a self-contained recap statement. \n- Moving the main Theorem statements (4.5 and 4.6) earlier to the introduction (along with the comparison to bounds for classical circuits) would help. (That is, explaining the result top-down, rather than bottom-up.) The effort to keep everything in mind until I got to final statements exceeded my stack depth. I like to think that I would have had no trouble understanding a more self-contained exposition of the main results.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides approximation results for functions that can be represented by hybrid quantum-classical circuits. It is felt that venues such as QIP would be a more suitable venue, and perhaps some experiments/simulations could be added.
Decision: Reject