Toward Trainability of Quantum Neural Networks
Authors: Kaining Zhang
Min-Hsiu Hsieh
Liu Liu
Dacheng Tao
Venue:  (2021)
Keywords: Near-term Quantum Algorithm
Quantum Neural Network
Trainability
Hierarchical Structure

Abstract: Quantum Neural Networks (QNNs) have been recently proposed as generalizations of classical neural networks to achieve the quantum speed-up. Despite the potential to outperform classical models, serious bottlenecks exist for training QNNs; namely, QNNs with random structures have poor trainability due to the vanishing gradient with rate exponential to the input qubit number. The vanishing gradient could seriously influence the applications of large-size QNNs. In this work, we provide the first viable solution with theoretical guarantees. Specifically, we prove that QNNs with tree tensor and step controlled architectures have gradients that vanish at most polynomially with the qubit number. Moreover, our result holds irrespective of which encoding methods are employed. We numerically demonstrate QNNs with tree tensor and step controlled structures for the application of binary classification. Simulations show faster convergent rates and better accuracy compared to QNNs with random structures.

Under review as a conference paper at ICLR 2021
TOWARD TRAINABILITY OF QUANTUM NEURAL NET- WORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Quantum Neural Networks (QNNs) have been recently proposed as generaliza- tions of classical neural networks to achieve the quantum speed-up. Despite the potential to outperform classical models, serious bottlenecks exist for training QNNs; namely, QNNs with random structures have poor trainability due the vanishing gradient with rate exponential to the input qubit number. The vanish- ing gradient could scriously influence the applications large-size QNNs. In this work, provide first viable solution with theoretical guarantees. Specifically, we prove that QNNs with tree tensor and step controlled architectures have gra- dients that vanish most polynomially with the qubit number. Moreover, result holds irrespective of which encoding methods are employed. We numer- ically demonstrate QNNs with tree tensor and step controlled structures for the application of binary classification. Simulations show faster convergent rates and better accuracy compared to QNNs with random structures.
INTRODUCTION
Neural Networks (Hecht-Nielsen, 1992) using gradient-based optimizations have dramatically ad- vanced researches in discriminative models, generative models, and reinforcement learning. To effi- ciently utilize the parameters and practically improve the trainability, neural networks with specific architectures (LeCun et al., 2015) are introduced for different tasks, including convolutional neural networks (Krizhevsky al., 2012) for image tasks, recurrent neural networks (Zaremba al., 2014) for the time series analysis, and graph neural networks (Scarselli et al., 2008) for tasks related to graph-structured data. Recently, the neural architecture search (Elsken al., 2019) is proposed to improve the performance of the networks by optimizing the neural structures.
Despite the success in many fields, the development of the neural network algorithms could be limited by the large computation resources required for the model training. In recent years, quantum computing has emerged as one solution to this problem, and has evolved into a new interdisciplinary field known the quantum machine learning (QML) (Biamonte et al., 2017; Havlfček al., 2019). Specifically, variational quantum circuits (Benedetti et al., 2019) have been explored as efficient protocols for quantum chemistry (Kandala al., 2017) and combinatorial optimizations (Zhou al., 2018). Compared to the classical circuit models, quantum circuits have shown greater expressive power (Du et al., 2020a), and demonstrated quantum advantage for the low-depth case (Bravyi al., 2018). Due to the robustness against noises, variational quantum circuits have attracted significant interest for the hope achieve the quantum supremacy on near-term quantum computers (Arute et al., 2019).
Quantum Neural Networks (QNNs) (Farhi & Neven, 2018; Schuld et al., 2020; Beer et al., 2020) are the special kind of quantum-classical hybrid algorithms that run on trainable quantum circuits. Recently, small-scale QNNs have been implemented on real quantum computers (Havlíček et al., 2019) for supervised learning tasks. The training of QNNs aims to minimize the objective function with respect to parameters 0. Inspired by the classical optimizations of neural networks, a natural strategy to train QNNs is to exploit the gradient of the loss function (Crooks, 2019). However, the recent work (McClean et al., 2018) shows that n-qubit quantum circuits with random structures and large depth L (n)) tend to be approximately unitary 2-design (Harrow & Low, 2009), and the partial derivative vanishes to zero exponentially with respect to n. The vanishing gradient problem is usually referred to the Barren Plateaus (McClean et al., 2018) 8), and could affect the

---

Under review as a conference paper at ICLR 2021
trainability of QNNs in two folds. Firstly, simply using the gradient- based method like Stochastic Gradient Descent (SGD) to train the QNN takes a large number of iterations. Secondly, the esti- mation of the derivatives needs extremely large number of samples from the quantum output to guarantee a relatively accurate update direction (Chen et al., 2018). To avoid the Barren Plateaus phenomenon, explore QNNs with special structures gain fruitful results.
In this work, we introduce QNNs with special architectures, including the tree tensor (TT) structure (Huggins al., 2019) referred as TT-QNNs and the setp controlled structure referred as SC- QNNs. We prove that for TT-QNNs and SC-QNNs, the expectation of the gradient norm of the objective function bounded.
Theorem 1.1. (Informal) Consider the n-qubit TT-QNN and the n-qubit SC- SC-QNN defined in Fig- ure 1 1-2 and corresponding objective functions fir and fsc defined in (3-4), then we have:
1 + log n
-a(pi)) S Vefmi11 2m
2n
+ The
aa(pi)) Eolsell 2n 1n
21+
where ne is the number of CNOT operations that directly link to the first qubit chunnel in the SC- QNN, the expectation is taken for all parameters in O with uniform distributions in [0, 2ml, and (pp)) 2 a constant that only depends on the input state per E C2" x2" Moreover, by preparing Pin using the L-layer encoding circuit in Figure 4, the expectation of alpi)) could be further lower bounded as (m()p)) 2 2-1.
Compared to random QNNs with 2 2-O(poly(m) derivatives, the gradient norm of TT-QNNs ad SC- QNNs greater than S2 (21/n) or 22(2- that could lead to better trainability. Our contributions are summarized as follows:
We prove (11/n) and f1(2"=)) lower bounds on the expectation of the gradient norm of TT-QNNs and SC-QNNs, respectively, that guarantees the trainability on related optimiza- tion problems. Our theorem does not require the unitary 2-design assumption in existing works and is more realistic to near-term quantum computers.
We prove that by employing the encoding circuit in Figure to prepare Pin. the expectation of term (Pm) lower bounded by constant 2 2-2L Thus, we further lower bounded the expectation of the gradient norm to the term independent from the input state.
We simulate the performance of TT-QNNs, SC-QNNs, and random structure QNNs on the binary classification task. All results verify proposed theorems. Both TT-QNNs and SC-QNNs show better trainability and accuracy than random QNNs.
Our proof strategy could be adopted for analyzing QNNs with other architectures as future works. With the proven assurance on the trainability of TT-QNNs and SC-QNNs, we eliminate one bottle- neck in front of the application of large-size Quantum Neural Networks.
The rest parts of this paper are organized as follows. We address the preliminary including the definitions, the basic quantum computing knowledge and related works in Section 2. The QNNs with special structures and the corresponding results are presented in Section 3. We implement the binary classification using QNNs with the results shown in Section 4. We make conclusions in Section 5.
2 PRELIMINARY
2.1 NOTATIONS AND THE BASIC QUANTUM COMPUTING
We use [N] denote the set 21, ,J. The form denotes the || norm for vectors. We denote aj as the j-th component of the vector a. The tensor product operation is denoted as "Ø" The conjugate transpose of matrix A is denoted as At, The trace of a matrix is denoted as Tr[A]. We denote Vøʃ as the gradient of the function with respect to the vector 0. We employ notations O and Ô to describe the standard complexity and the complexity ignoring minor terms, respectively.
2

---

Under review as a conference paper at ICLR 2021
Now introduce the quantum computing. The pure state of qubit could be written as (ø) al0) +b11), where a, b E C satisfies |a " 1b|2 = 1, and {10) = (1,0)", .11 = (0, 1)"), respectively. The n--uuit space formed by the tensor product of single-qubit spaces. For the vector x E I2"",
the amplitude encoded state (>) is defined as
a= -==1,155: The dense matrix is defined as -= |z) (ar) for the pure state, in which (a) = (x) r. A single-qubit operation to the state behaves like the matrix- multiplication and can be referred to the gate - in the quantum circuit
1
language. Specifically, single-qubit operations are often used including Rx (0) = e -80 Ry (0)
BY and (z) = =02
X ( 0) v
2 6 9)
Pauli matrices X1 Y, 3} will be referred as {oo, σ1, 02, d3} for the convenience. Moreover, two-qubit operations, the CNOT gate and the CZ gate, are employed for generating quantum entan- glement:
CNOT
10) & o [1) & o1, CZ 1 10] da [1) @ 03.
O
We could obtain information from the quantum system by performing measurements, for example,
measuring the state (o) = al0) +b(1) generates 0 and with probability p(0) = |a 2 and p( ) = |b/2 respectively. Such a measurement operation could be mathematically referred to as calculating the average of the observable O 03 under the state (Ø):
(0a)10) = ( = Tr([o) (Ø) 0g) = |a|² - 1b|2 p(0) - p(1) 2p(0) 1.
The average of a unitary observable under arbitrary states is bounded by [-1,
2.2 RELATED WORKS
The barren plateaus phenomenon in QNNs is first noticed by McClean et al. (2018). They prove that for n-qubit random quantum circuits with depth I, = (ppol((n) the expectation of the derivative to the objective function is zero, and the variance of the derivative vanishes to zero with rate expo- nential in the number of qubits n. Later, Cerezo et al. (2020) prove that for L-depth quantum circuits consisting of 2-design gates, the gradient with local observables vanishes with the rate O -(1)). The result implies that in the low-depth L = Ollog n) case, the vanishing rate could be O polyn ) which is better than previous exponential results. Recently, some techniques have been proposed to address the barren plateaus problem, including the special initialization strategy (Grant et al., 2019) and the layerwise training method (Skolik et al., 2020). We remark that these techniques rely on the assumption of low-depth quantum circuits. Specifically, Grant et al. (2019) initialize parameters such that the initial quantum circuit is equivalent an identity matrix (L = 0). Skolik et al. (2020) train parameters in subsets in each layer, so that low-depth circuit is optimized during the training of each subset of parameters.
Since random quantum circuits tend to be approximately unitary 2-design' as the circuit depth in- creases (Harrow & Low, 2009), and 2-design circuits lead to exponentially vanishing gradients (Mc- Clean et al., 2018), the natural idea is to consider circuits with special structures. On the other hand, tensor networks with hierarchical structures have been shown an inherent relationship with classical neural networks (Liu al., 2019; Hayashi et al., 2019). Recently, quantum classifiers using hierar- chical structure QNNs have been explored (Grant et al., 2018), including the tree tensor network and the multi-scale entanglement renormalization ansatz. Besides, QNNs with dissipative layers have shown the ability to avoid the barren plateaus (Beer et al., 2020). However, theoretical analysis of the trainability of QNNs with certain layer structures has been little explored (Sharma al., 2020). Also, the 2-design assumption in the existing theoretical analysis (McClean et al., 2018; Cerezo al., 2020; Sharma al., 2020) is hard to implement exactly on near-term quantum devices.
QUANTUM NEURAL NETWORKS
In this section, we discuss the quantum neural networks in detail. Specifically, the optimizing of QNNs is presented Section 3.1. We analyze QNNs with special structures Section 3.2. We
We refer the readers to Appendix B for short discussion about the unitary 2-design.
3

---

Under review as a conference paper at ICLR 2021
introduce approximate quantum input model in Section 3.3 which helps for deriving further theoretical bounds.
3.1 THE OPTIMIZING OF QUANTUM NEURAL NETWORKS
In this subsection, we introduce the gradient- based strategy for optimizing QNNs. Like the weight matrix in classical neural networks, the QNN involves a parameterized quantum circuit that math- ematically equals to a parameterized unitary matrix V(0). The training of QNNs aims to optimize the function f defined as:
1 [r V(0) Pm v(0)|= 1 (O)
f(0: Pm)) 2 +
where O denotes the quantum observable and Pmn denotes the density matrix of the input quan- tum state. Generally, we could deploy the parameters 0 in tunable quantum circuit arbi- trarily. practical tactic is to encode parameters (0z} as the phases of the single-qubit gates {e- te=19yox,k E [1,2,3} while employing two-qubit gates {CNOT, CZ) among them to generate quantum entanglement. This strategy has been frequently used in existing quantum circuit algo- rithms (Schuld et al., 2020; Benedetti et al., 2019; Du et al.. 2020b) since the model suits the noisy near-term quantum computers. Under the single-qubit phase encoding case, the partial derivative of the function f could be calculated using the parameter shifting rule (Crooks, 2019).
af 1 (O)v10)).p. -2( (O)v(o_)).m f(0+: f(0=; 00;
where 0+ and 0_ are different from 0 only the j-th parameter: 0, + 0, + -. Thus, the gradi- ent of f could be obtained by estimating quantum observables, which allows employing quantum computers for fast optimizations using stochastic gradient descents.
3.2 QUANTUM NEURAL NETWORKS WITH SPECIAL STRUCTURES
In this subsection, introduce quantum neural networks with tree tensor (TT) (Grant et al., 2018) and step controlled (SC) architectures. We prove that the expectation of the square of gradient b2- norm for the TT-QNN and the SC-QNN are lower bounded by ((1/n) and (²(2- respectively, where n. is parameter in the SC-QNN that is independent from the qubit number n. Moreover, the corresponding theoretical analysis does not rely on 2-design assumptions for quantum circuits.
Now discuss proposed quantum neural networks in detail. We consider the n-qubit QNN con- structed by the single-qubit gate wr(k) = - 02 and the CNOT gate σs @ [1)(1) + ao & 10) (0)-
We define the k-th parameter in the j-th layer as g(A) We only employ Ry rotations for single- qubit gates, due to the fact that the real world data lie in the real space, while applying Rx and Rz
rotations would introduce imaginary term to the quantum state.
We demonstrate the TT-QNN in Figure I for the n = case, which employs CNOT gates in the binary tree form to achieve the quantum entanglement. The circuit of the SC-QNN could be divided into two parts: in the first part, CNOT operations are performed between adjacent qubit channels; in the second part, CNOT operations are performed between different qubit channels and the first qubit channel. An illustration of the SC-QNN is shown in Figure 2 for the n = 4 and n. = 2 case, where n. denotes the number of CNOT operations that directly link to the first qubit channel. The number of parameters in both the TT-QNN and the SC-QNN are 2n 1. We consider correspond objective functions that are defined as
1
fri
2 Trios @
(3)
(sc(0) = + Tr(as 3 Vsc
(4)
2
where Vrr(@) and Voc(0) denotes the parameterized quantum circuit operations for the TT-QNN and the SC-QNN, respectively. We employ the observable d3 @ I@(=-)) in Eq. (3-4) such that objective functions could be easily estimated by measuring the first qubit in corresponding quantum circuits.
4

---

Under review as a conference paper at ICLR 2021
Main results of this section stated in Theorem 3.1, in which prove (1(1/n) and n.) lower bounds on the expectation of the square of the gradient norm for the TT-QNN and the SC- QNN. respectively. By setting n. (log n),, could obtain the linear inverse bound for the SC-QNN as well. We provide the proof Theorem 3.1 in Appendix D and Appendix G.
(0)
W22
(0]
W
W1
((wa)
((uu)
(0)
W
W/(0))
W
(0)
(((4)
(0)
w.(4)
Quantum Neural Network with the Tree Tensor structure (n = 4).
Figure 1:
Figure 2: Quantum Neural Network with the Step Controlled structure (n = 4, nh 2).
Theorem 3.1. Consider the n--ubii TT-QNN and the n--ubii SC-QNN defined in Figure 1-2 and corresponding objective functions frr and fsc defined in Eq. (3-4), then have:
1 + log
a(pm) S Eo Vofrr 2n
(5)
2n
+ nee a(pi)) S Es Vefsel? 2n
(6)
21+m.
where nee is the number of CNOT operations that directly link to the first qubit channel in the SC-QNN, the expectation taken for all parameters in with uniform distributions in [0. 2T),
Pin x2"x2" x2" denotes the input state, a(pm) Tr [o 00 pmm] 22 Tr [o(3,,... 0) Pin and
-2
(ii.fa, (n) = oii 8 oig 8 .... 8 Jin.
From the geographic view, the value Eo /o characterizes the global steepness of the function surface in the parameter space. Optimizing the objective function f using gradient-basee methods could be hard if the norm the gradient vanishes to zero. Thus, lower bounds in Eq. (5-6) provide a theoretical guarantee on optimizing corresponding functions, which then ensures the trainability of QNNs on related machine learning tasks.
From the technical view, we provide new theoretical framework during proving Eq. (5-6). Different from existing works (McClean al., 2018; Grant al., 2019; Cerezo al., 2020) that define the expectation as the average of the finite unitary 2-design group, we consider the uniform distribution in which each parameter in f varies continuously in [0, 2x| Our assumption suits the quantum circuits that encode the parameters in the phase of single-qubit rotations. Moreover, the result in Eq. (6) gives the first proven guarantee on the trainability QNN with linear depth. Our framework could be extensively employed for analyzing QNNs with other different structures future works.
3.3 PREPARE THE QUANTUM INPUT MODEL: A VARIATIONAL CIRCUIT APPROACH
State preparation an essential part of most quantum algorithms, which encodes the classical in- formation into quantum states. Specifically, the amplitude encoding x)) = - 2z/ /r/l|///ll allows storing the 2n di-diennsoonal vector qubits. Due to the dense encoding nature and the similarity to the original vector, the amplitude encoding is preferred as the state preparation by many QML algorithms (Harrow et al., 2009; Rebentrost et al., 2014; Kerenidis et al., 2019). Despite the wide application in quantum algorithms, efficient amplitude encoding remains little explored. Existing work (Park et al., 2019) could prepare the amplitude encoding state in time O(2") using quantum circuit with O(2") depth, which is prohibitive for large-size size data near-term quantum computers. In fact, arbitrary quantum amplitude encoding with polynomial gate complexity remains an open problem.
5

---

Under review as a conference paper at ICLR 2021
Algorithm Quantuu Input Model
Require:
The input vector Vin E I22", the number of alternating layers L, the iteration time T, and the learning rate (n(t)]==1
Ensure: A parameter vector 3 which tunes the approximate encoding circuit ('33).
1: Initialize (B(() 2
jik=1 randomly in [0, 2m.. Denote the parameter vector as g0))
2: for E {0.1,-.. . 1 do
3: Run the circuit in Figure classically calculate the gradient V Vas/inputss using the parameter shifting rule (2), where the function Simpun is defined in (7).
4: Update the parameter ((++1) 3(0) - rt() V VaJimull B=
5: end for
6: Output the trained parameter 3r.
(
(e(t)
W(())
(0]
X
W-ta)
10)
(x(3)
(=(3)
(0]
W(4)
W
(0]
20
W(
W:(0)
W
A
(0)
(((0)
w-(0)
W
A
(0]
w.(?)
w:(?)
(0]
(x(
w-(a)
Wais
(0]
Alternating Layer
U(3")
Figure 3: The parameterized alternating layered circuit ((3) (n = 8, T, = 1) for training the corresponding encoding circuit of the input Zin-
Figure 4: The encoding circuit U(O*),
where W(3") the trained parameter- ized circuit in Figure 3.
In this subsection, we introduce a quantum input model for approximately encoding the arbitrary vector Fin E _² in the amplitude of the quantum state |ainn. The main idea classically train an alternating layered circuit as summarized in Algorithm I and Figures 3-4. Now we explain the detail of the input model. Firstly, we randomly initialize the parameter (3(0) in the circuit 3. Then, we train the parameter minimize the objective function defined in (7) through the gradient descent,
Simpar (B)
Σ (0,) ()))w()))))))
Tr(O, W(B) Din W(3)),
Min
where O, = 0 10-i 2 0g & 0 (nn-1) Vi E [n]. and W(3) denotes the tunable alternating layered circuit in Figure Note that although the framework is given in the quantum circuit language, actually calculate and update the gradient on classical computers by considering each quantum gate operation the matrix multiplication. The output of Algorithm is the trained parameter vector 3 which tunes the unitary W (B+).. The corresponding encoding circuit could then be implemented as U(B*) W(G*)* x0n which is low-depth and appropriate for near-term quantum computers. Structures of circuits W and U are illustrated in Figure and 4, respectively. Suppose we could minimize the objective function (7) to -1. Then (O,) 11, E [r]]. which means the final output state in Figure 3 equals to (( (Z..) by applying the circuit U(3*) = W(B*) X Sn on state [0) @n However we could not always optimize the loss in Eq. (7) to 1, which means the framework could only prepare the amplitude encoding state approximately.
[1)@
Thus the state (ærin) could be prepared exactly
We ignore the global phase on the quantum state. Based on the assumptions of this paper, all quantum states that encode input data lie in the real space, which then limit the global phase I or -1. For the former case, nothing needs to be done; for the letter case, the global phase could be introduced by adding single qubit gate Fo anyone among qubit channels.

---

Under review as a conference paper at ICLR 2021
Algorithm 2 QNNs for the Binary Classification Training
Require: Quantum input states { _ k=1 for the dataset [(artai, 1/)) y=))==1- the quantum observable
O the parameterized quantum circuit (0),, the iteration time T, the batch size and learning
rates {t) and (t))
Ensure: The trained parameters 0" and b".
1: Initialize each parameter in ((0) randomly [0, 2x] and initialize ((0)
2: for E 10 . 1 do
3: Randomly sample an index subset 4 C [S] with size s. Calculate the gradient
Vgli, (0, b)le b gey and Voli, (0, b)le, 000),,0)) pae) using the chain rule and the parameter shifting rule (2), where the function fr, (0, b) is defined in (8).
4: Update parameters (((+1) /bit+1) /b(+1)/((++) = ((t) /b()) Te/b(() Voyoes, 00,0)0,00000000000
5: end for
6: Output trained parameters 0 ===00 ( and b- B(T).
An interesting result that by employing the encoding circuit in Figure 4 for constructing the input state in Section 3.2 as Pm (00)(()))))) ((B", we could bound the expectation of a(pa) defined in Theorem 3.1 by a constant that only relies on the layer L (Theorem 3.2).
((B)
Theorem 3.2. Suppose the state Piu is prepared by the L-layer encoding circuit in Figure then we have,
(pm)) 22-21,
where (3 denotes all variational parameters in the encoding circuit, and the expectation is taken for all parameters in B with uniform distributions in [0, 2m.
We provide the proof of Theorem 3.2 and more details about the input model in Appendix E. The- orem 3.2 can be employed with Theorem 3.1 to derive Theorem 1.1, in which the lower bound for the expectation of the gradient norm is independent from the input state.
APPLICATION: QNNs FOR THE BINARY CLASSIFICATION
4.1 QNNS: TRAINING AND PREDICTION
In this section, we show how to train QNNs for the binary classification in quantum computers. First of all, for the training and test data denoted as {(a:!rinn 1=))]=1 and {( ز where yi E {0. 1) denotes the label, we prepare corresponding quantum input states { Ji=1 and { Q using the encoding circuit presented in Section 3.3. Then, we employ Algorithm to train the parameter 0 and the bia b via the stochastic gradient descent method for the given parameterized circuit V and the quantum observable O. The parameter updating in each iteration presented in the Step 3-4, which aims to minimize the loss defined in (8) for each input batch 4, Vt E [Z']:
Jz=1
1
l,. (0)
Σ T.
((
yi +b
88,, and Based on the chain rule and the Eq. (2), derivatives Dæ, D6 of objective functions f with different variables, which could be estimated efficiently by counting quantum outputs. In practice, we calculate the value of the objective function by measuring the output state of the QNN for several times and averaging quantum outputs. After the training iteration we obtain the trained parameters 6* and d". Denote the quantum circuit V = (V))). We do test for an input state poe by calculating the objective function f(ptst 1 + ]TT( V p V*
at,, could be decomposed into products
We classify the input glest as in the class if f(p)")) + b" < 2. or the class 1 if f( + 1
The time complexity of the QNN training and test could be easily derived by counting resources for estimating all quantum observables. Denote the number of gates and parameters in the quantum cir- cuit V (()) Ngaaee and Πpaaa respectively. Denote the number of measurements for estimating each quantum observable as Thrain and Reese for the training and test stages, respectively. Then, the time complexity to train QNNs is O Para Muain Prain 7), and the time complexity of the test using QNNs
7

---

Under review as a conference paper at ICLR 2021
(b)
(c)
(d)
(c)
(f)
g
(h)
Figure 5: Simulations on the MNIST binary classification between (0, 20. The training loss and the test error during the training iteration are illustrated in Figures 5(a), 5(e) for the n=8 case, Fig- ures 5(b), 5(f) for the n=10 case, and Figures S(c), 5(g) for the n=12 case. The gradient norm of objective functions and the term (((m) during the training are shown in Figures 5(d) and 5(h), respectively for the n=8 case.
(eganeeesss We emphasize that directly comparing the time complexity of QNNs with classi- cal NNs is unfair due to different parameter strategies. However, the complexity of QNNs indeed shows a polylogarithmic dependence on the dimension of the input data if the number of gates and parameters are polynomial to the number of qubits. Specifically, both the TT-QNN and the SC-QNN equipped with the L-layer encoding circuit in this work have (nL)) gates and O(n) parameters, which lead to the training complexity ( LT)) and the test complexity O (mtssTL))
4.2 NUMERICAL SIMULATIONS
To analyze the practical performance of QNNs for binary classification tasks, we simulate the train- ing and test of QNNs on the MNIST handwritten dataset. The 28 x size image is sampled into 16 x 16, 32 x 32, and 64 x 64 to fit QNNs for qubit number in SC-QNNs as nhe = 4 for all qubit number settings. Note that the based on the tree structure, the qubit number of original TT-QNNs is limited to the power of 2. To analysis the behavior of TT- QNNs for general qubit numbers, we modify TT-QNNs into Deformed Tree Tensor (DTT) QNNs. The gradient norm for DTT-QNNs is lower bounded by (11/n), which has similar form of that for TT-QNNS. We provide more details of DTT-QNNS in Appendix F and denote DTT-QNNS as TT-QNNs in simulation parts (Section 4.2 and Appendix A) for the convenience.
{8, 10, 12). We set the parameter
We construct the encoding circuits in Section 3.3 with the number of alternating layers T, = 1 for 400 training samples and 400 test samples in each class. The TT-QNN and the SC-QNN is compared to the QNN with the random structure. To make a fair comparison, we set the numbers of RY and CNOT gates the random QNN to be the same with the TT-QNN and the SC-QNN. The objective function of the random QNN is defined as the average of the expectation of the observable d3 for all qubits in the circuit. The number of the training iteration 100, the batch size 20, and the decayed learning rate is adopted as (1.00, 0.75, 0.50, 0.25). We set Plrain 200 and Theat 1000 as numbers of measurements for estimating quantum observables during the training and test stages, respectively. All experiments are simulated through the PennyLane Python package (Bergholm et al., 2020).
Firstly, we explain our results about QNNs with different qubit numbers in Figure 5. We train TT- QNNs, SC-QNNs, and Random-QNNs with the stochastic gradient descent method described in Algorithm 2 for images in the class (0, 2) and the qubit number E {8, 10, 12). The total loss defined as the average of the single-input loss. The training loss and the test error during the training iteration illustrated in Figures 5(a), 5(e) for the n=8 case, Figures 5(b), 5(f) for the
8

---

Under review as a conference paper at ICLR 2021
TT-QNN
SC-QNN
Random-O -NNN
Class pair
test (F1-0, F1-1)
test (F1-0, F1-1)
test (F1-0, F1-1)
0-1
0.959 (0.958, 0.960)
0.979 (0.979, 0.979)
0.920 (0.915, 0.925)
0-2
0.844 (0.852, 0.834)
0.859 (0.859, 0.858)
0.738 (0.751, 0.722)
0-3
0.835 (0.810, 0.854)
0.859 (0.857, 0.860)
0.659 (0.680, 0.635)
0-4
0.938 (0.938, 0.938)
0.925 (0.925, 0,925)
0.779 (0.796, 0.759)
1-2
0,929 (0.930, 0.927)
0.965 (0.965, 0.965)
0.700 (0.728, 0.666)
1-3
0.938 (0.941, 0.934)
0.881 (0.87),
0.765 (0.773, 0.756)
144
0,821 (0.837, 0.802)
0.871 (0.879,0.86)
0.705 (0.737, 0.664)
2-3
0.814 (0.791, 0.832)
0.820 (0.810, 0.829)
0.709 (0.743, 0.664)
2-4
0,931 (0.928, 0.934)
0.935 (0.933,, 0.937)
0.645 (0.728, 0.487)
3-4
0.931 (0.930, 0.933)
0.944 (0.943, 0.945)
0.819 (0.839, 0.793)
Table 1: The test accuracy and Fi-scores for different class pairs (qubit number = 10).
n=10 case, and Figures 5(c). 5(g) for the n=12 case. The test error of the TT-QNN, the SC-QNN and the Random-QNN converge to around 0.2 for the n=8 case. As the qubit number increases, the converged test error of both TT-QNNs and SC-QNNs remains lower than 0.2, while that of Candom-QNNy increases to 0.26 and 0.50 for n=10 and n=12 case, respectively. The training loss of both TT-QNNs and SC-QNNs converges to around 0.15 for all qubit number settings, while that of Random-QNNs remains higher than 0.22. Both the training loss and the test error results show that TT-QNNs and SC-QNN- have better trainability and accuracy on the binary classification compared with Random-QNNY We record the 2e-norm of the gradient during the training for the n=8 case in Figure 5(d). The gradient norm for the TT-QNN and the SC-QNN is mostly distributed in [0.4, 1.4), which is significantly larger than the gradient norm for the Random- MNNN that is mostly distributed in [0.1, 0.2]. As shown in Figure 5(d), the gradient norm verifies the lower bounds in the Theorem 3.1. Moreover, we calculate the term a (Pin) defined in Theorem 3.1 and show the result in Figure 5()). The average of ((p)) is around 0.6, which is lower bounded by the theoretical result in Theorem 3.2 (L 1).
Secondly, we explain our results about QNNs on the binary classification with different class pairs. We conduct the binary classification with the same super parameters mentioned before for 10-qubit QNNs, and the test accuracy and F1-scores for all class pairs { C {0, 1, 2, 3, 4) are provided in Table The F1-0 denotes the Fi-score when treats the former class to be positive, and the F1-1 denotes the Fl-score for the other case. As shown in Table 1, TT-QNNs and SC-QNNs have higher test accuracy and Fl-score than Random-QNNs for all class pairs in Table 1. Specifically, test accuracy of TT-QNN: and SC-QNNs exceed that of Random- ONNs by more than 10% for all class pairs except the (0, 1) which is relatively easy to classify.
In conclusion, both TT-QNNs and SC-QNNs show better trainability and accuracy on binary classifi- cation tasks compared with the random structure QNN, and all theorems are verified by experiments. We provide more experimental details and results about the input model and other classification tasks in Appendix A.
5 CONCLUSIONS
In this work, we analyze the vanishing gradient problem in quantum neural networks. We prove that the gradient norm of n--ubbit quantum neural networks with the tree tensor structure and the step controlled structure are lower bounded by 2(-) and ()) respectively. The bound guaran- tees the trainability of TT-QNNs and SC-QNNs on related machine learning tasks. Our theoretical framework requires fewer assumptions than previous works and meets constraints on quantum neu- ral networks for near-term quantum computers. Compared with the random structure QNN which is known to be suffered from the barren plateaus problem, both TT-QNNs and SC-QNNs show better trainability and accuracy on the binary classification task. We hope the paper could inspire future works on the trainability of QNNs with different architectures and other quantum machine learning algorithms.

---

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 A Bucll, al. Quantum supremacy using programmable superconducting processor. Nature, 574(7779):505-510, 2019.
Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias J Osborne, Robert Salzmann, Daniel Scheiermann, and Ramona Wolf. Training deep quantum neural networks. Nature communi- cations, 1-1);1-6, 2020.
Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum cir- cuits as machine learning models. Quantum Science and Technology, 4(4):043001, 2019.
Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, M. Sohaib Alam, Shahnawaz Ahmed, Juan Miguel Arrazola, Carsten Blank, Alain Delgado, Soran Jahangiri, Keri McKiernan, Jo- hannes Jakob Meyer. Zeyue Niu, Antal Száva, and Nathan Killoran. Pennylane: Automatic differentiation of hybrid quantum-classied computations, 2020.
Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 1:9 2017.
Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308-3) 2018.
M Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. Cost-function-deeendeett barren plateaus in shallow quantum neural networks. arXiv preprint arXiv:2001.005500, 2020.
Zhao Chen, Vijay Badrinarayanan, Chen- Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks. In International Conference on Machine Learning, pp. 794-803. PMLR, 2018.
Gavin E Crooks. Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition. arXiv preprint arXiv: /905. 13311, 2019.
Yuxuan Du, Min-Hsiu Hsich, Tongliang Liu, and Dacheng Tao. Expressive power of parametrized quantum circuits. Physical Review Research, 2(3), Jul 2020a.
Yuxuan Du, Min-Hsiu Hsich, Tongliang Liu, Shan You, and Dacheng Tao. On the learnability of quantum neural networks. arXiv preprint arXiv:2007. 12369, 2020b.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey.
Journal of Machine Learning Research, 20:1-21, 2019.
Edward Farhi and Hartmut Neven. Classification with quantum neural networks term pro- cessors. arXiv preprint arXiv: 1.Xi::1802.00002. 2018.
Edward Grant, Marcello Benedetti, Shuxiang Cao, Andrew Hallam, Joshua Lockhart, Vid Stoje- vic, Andrew G. Green, and Simone Severini. Hierarchical quantum classifiers. upj Quantum
Information, 4(1), Dec 2018.
Edward Grant, Leonard Wossnig, Mateusz Ostaszewski, and Marcello Benedetti. An initialization strategy for addressing barren plateaus parametrized quantum circuits. Quantum, 3:214, 2019.
Aram W Harrow and Richard A Low. Random quantum circuits are approximate 2-designs. Com- munications in Mathematical Physics, (1:(527773,,,, 2009.
Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):15050. 2009.
Vojtëch Havlfčck, Antonio D Córcoles, Kristan Temme, et al. Supervised learning with quantum- enhanced feature spaces. Nature, 567(7777): 2019.
Kohei Hayashi, Taiki Yamaguchi, Yohei Sugawara, and Shin-ichi Maeda. Exploring unexplored tensor network decompositions for convolutional neural networks. In Advances in Neural Infor- mation Processing Systems, pp. 5552-5562, 2019.
10

---

Under review as a conference paper at ICLR 2021
Robert Hecht-Nielsen. Theory of the backpropagation neural network. In Neural networks for perception, pp. 65-93.--- Elsevier, 1992.
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.
Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. Hardware-efficte variational quantum eigensolver for small molecules and quantum magnets. Nature, 549(7671):242-22) 2017.
lordanis Kerenidis, Jonas Landman, and Anupam Prakash. Quantum algorithms for deep convolu- 2019.
tional neural networks. arXiv preprint
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):336-444 2015.
Ding Liu, Shi-Ju Ran, Peter Wittek, Cheng Peng, Raul Blázquez García, Gang Su, and Maciej Lewenstein. Machine learning by unitary tensor network of hierarchical tree structure. New Journal of Physics, 21(7):073059 Jul 2019.
Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Bar- ren plateaus quantum neural network training landscapes. Nature communications, 9(1):166, 2018.
Daniel K Park, Francesco Petruccione, and June-Koo Kevin Rhee. Circuit-based quantum random access memory for classical data. Scientific reports, 911):188, 2019.
Zhigniew Puchata and Jarostaw Adam Miszczak. Symbolic integration with respect to the haar measure the unitary group. arXiv preprint arXiv: 2011.
Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical review letters, 113((3))130503 2014.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008
Maria Schuld, Alex Bocharov, Krysta M Svore, and Nathan Wiebe. Circuit-centric quantum classi- fiers. Physical Review A, 101(3)003238, 2020.
Kunal Sharma, Marco Cerezo, Lukasz Cincio, and Patrick Coles. Trainability of dissipative perceptron-based quantum neural networks. arXiv preprint 2205: 2020.
Andrea Skolik, Jarrod R McClean, Masoud Mohseni, Patrick van der Smagt, and Martin Leib. Lay- erwise learning for quantum neural networks. arXiv preprint arXiv:2006. 14904, 2020.
Wojeiech Zaremba, llya Sutskever, and Oriol Vinyals. Recurrent neural network regularization. arXiv preprint arXiv: 4409.3329 2014.
Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term 2018.
devices. arXiv preprint
11

---

Under review as a conference paper at ICLR 2021
The Appendix of this paper is organized as follows. We shortly introduce the notion of unitary 2-designs in Appendix B. Some useful technical lemmas are provided and proved in Appendix C. We prove the Theorem 3.1 in Appendix D and Appendix G. The Appendix C. Appendix D, and Appendix G form the theoretical framework for analyzing the gradient norm of QNNs. We provide the proof of Theorem 3.2 in the main text and more detail about the proposed encoding model in Appendix E. All experimental details are provided in Appendix A.
A NUMERICAL SIMULATIONS
In this section, we provide more experimential details about the input model and other binary clas- sification tasks.
A.1 QUANTUM INPUT MODEL FOR THE MNIST DATASET
1
(b)
(c)
(d)
Figure 6: The training loss of the input model for MNIST images in class (0, 1,2,3..
O
2
2
3
(b)
(C)
(e)
Figure 7: The visualization of the encoding circuit for MNIST images in class {0, 2, 4).
In this section, we discuss the training of the input model (Algorithm 1) in detail. We construct the encoding circuits in Section 3.3 for each training test data with the number of alternating layers = The number of the training iteration is 100. We adopt the decayed learning rate as {0.100, 0.075, 0.050, 0.025). We illustrate the loss function defined Eq. 7 during the training of Algorithm for label in {0, 1, 2, 3} for the n=8 case in Figure 6, in which we show the training of the input model for one image per sub-figure. All shown loss functions converge to around -0.6 after 60 iterations.
For better understanding to the input model, we provide the visualization of the encoding circuit in Figure 7. We notice that the encoding circuit could only catch few features from the input data (except the image which shows good results). Despite this, we obtain relatively good results on binary classification tasks which employ the mentioned encoding circuit.
Apart from the binary classification tasks using QNNs equipped with the encoding circuit provided in Section 3.3, we perform some experiments such that the encoding circuit is replaced by the ex- act amplitude encoding, which commonly used in existing quantum machine learning algorithms. Figure demonstrates the simulation on MNIST classifications between images (0, 2), which shows the convergence of training loss (Figure 8(a)) and the test error (Figure 8(b)). The norm of the gradi- ent is counted in Figure 8(c), in which both the TT-QNN and the SC-QNN show larger gradient norm than the Random- -NNN. Thus, the trainability of TT-QNNs and SC-QNNs remains when replace the encoding circuit with the exact amplitude encoding.
The training and test accuracy for other class pairs are summarized in Table We notice that compared with QNNs using the encoding circuit, QNNs with the exact encoding tend to have better
12

---

Under review as a conference paper at ICLR 2021
(a)
(b)
(c)
Figure 8: The training of binary classification task on the MNIST image bettwen classes (0, 2) using 8-qubit QNNs with the exact amplitude encoding. The training loss and the test error during the training iteration are illustrated in Figures 8(a), 8(b), respectively. The gradient norm of objective functions during the training is shown in Figures 8(c).
TT-QNN training, test
TT-QNN (exact encoding)
SC-QNN training, test
SC-QNN (exact encoding) training, test
Class pair
training, test
0-1
0.959, 0.981
0.980, 0.988
0.958, 0.969
0.986, 0.988
0-2
0.850, 0.812
0.902, 0.869
0.840, 0.850
0.881, 0.850
1-2
0.896, 0.909
0.924, 0.925
0.932, 0.943
0.919, 0.910
Table The training and test accuracy of TT-QNNs and SC-QNNs for different encoding strategies and different class pairs.
performance on the accuracy, which is reasonable since the exact amplitude encoding remains all information of the input data.
A.2 QNNS WITH DIFFERENT QUBIT SIZES
We summarize the results of training and test accuracy for different qubit numbers in Table 3, which corresponds to the main results presented in Figure 5 in Section 4.2. As shown Table 3, both the training and test accuracy of TT-QNNs and SC-QNNs remain high level for all qubit number settings, while the training and test accuracy of Random-QNNs decrease to around 0.5 for the 12- qubit case, which means the Random QNN cannot classify better than random guessing.
TT-QNN
SC-QNN training, test
Random-QNN training, test
Qubit number
training, test
8
0.850, 0.812
0.840, 0.850
0.741, 0.765
10
0.865, 0.844
0.871, 0.859
0.804, 0.738
12
0.884, 0.884
0.844, 0.814
0.497, 0.495
Table 3: The training and test accuracy for different qubit numbers {8, 10, 12} on the classification between (0, 2) classes.
A.3 QNNs WITH DIFFERENT LABEL PAIRS
We summarize the results training and test accuracy, along with the Fl-score, for QNNs on the classification between different label pairs in Table 4 and Table 5, for qubit number 8 and 10, respectively. For all label pairs, TT-QNNs and SC-QNNs show higher performance of the training accuracy, the test accuracy, and the Fi-scores than that of Random- ONots. Moreover, most of test accuracy of Random- -NNs drop for the same class pair when the qubit number is increased from to 10, which suggest the trainability of Random-Que ONNss get worse the qubit number increases.
13

---

Under review as a conference paper at ICLR 2021
TT-QNN
SC-QNN
Random-QNN training, test (F1-0, F1-1)
Class pair
training, test (F1-0, F1-1)
training, test (F1-0, F1-1)
0-1
0.959, 0.981 (0.981, 0.981)
0.958, 0.969 (0.969, 0.969)
0.954, 0.927 (0.923, 0.932)
0-2
0.850, 0.812 (0.820, 0.804)
0.840, 0.850 (0.847, 0.853)
0.741, 0.765 (0.790, 0.734)
0-3
0,871, 0.856 (0.845, 0.866)
0.870, 0.861 (0.853, 0.869)
0.722, 0.728 (0.734, 0.721)
0-4
0.919, 0.894 (0.891, 0.896)
0.934, 0.910 (0.907, 0.913)
0.831, 0.766 (0.773, 0.759)
1-2
0.896, 0.909 (0.914, 0.903)
0,932, 0.943 (0.943, 0.942)
0.627, 0.601 (0.704, 0.390)
1-3
0.940, 0.940 (0.943, 0.937)
0.922. 0.905 (0.912, 0.896)
0.802, 0.794 (0.826, 0.747)
1-4
0,891, 0.938 (0.938, 0.937)
0,885, 0.915 (0.917, 0.912)
0.850, 0.871 (0.881, 0.860)
2-3
0.805, 0.771 (0.750, 0.789)
0.824, 0.790 (0.761, 0.813)
0.684, 0.666 (0.694, 0.633)
2-4
0,810, 0.871 (0.873, 0.869)
0.845, 0.901 (0.899, 0.904)
0.738, 0.733 (0.752, 0.710)
3-4
0.920, 0.926 (0.922, 0.930)
0.939, 0.901 (0.898, 0.904)
0.695, 0.701 (0.751, 0.627)
Table 4: The classification accuracy for different class pairs (n=8).
TT-QNN
SC-QNN
Random-QNe QNNN
Class pair
training, test (F1-0, F1-1)
training, test (F1-0, F1-1)
training, test (F1-0, F1-1)
0-1
0,965, 0.959 (0.958, 0.960)
0,959, 0.979 (0.979, 0.979)
0.922, 0.920 (0.915 0.925)
0-2
0,865, 0.844 (0.852, 0.834)
0.871, 0.859 (0.859, 0.858)
0.804, 0.738 (0.751, 0.722)
0-3
0.870, 0.835 (0.810, 0.854)
0.871, 0.859 (0.857, 0.860)
0.654, 0.659 (0.680, 0.635)
0-4
0,945, 0.938 (0.938, 0,938)
0,938, 0.925 (0.925, 0.925)
0.839, 0.779 (0. (0.796, 0.759)
1-2
0.915, 0.929 (0.930, 0.927)
0.930, 0.965 (0.965, 0.965)
0.693, 0.700 (0. 728, 0.666)
1-3
0.944, 0.938 (0.941, 0.934)
0.899, 0.881 (0.879, 0.884)
0.759, 0.765 (0.773, 0.756)
144
0,844, 0.821 (0.837, 0.802)
0,854, 0.871 (0.879,
0.726, 0.705 (0. 0.664)
2-3
0,829, 0.814 (0.791, 0.832)
0,855, 0.820 (0.810, 0.829)
0.754, 0.709 (0.743, 0.664)
24
0.875, 0.931 (0.928, 0.934)
0.889, 0.935 (0.933, 0.937)
0.649, 0.645 (0. 728, 0.487)
34
0.940, 0.931 (0.930, 0.933)
0.944, 0.944 (0.943, 0.945)
0.876, 0.819 (0.839, 0.793)
Table 5: The classification accuracy for different class pairs (n=10).
A.4 QNNS WITH DIFFERENT ROTATION GATES
In this section, we simulate variants of TI-QNNs and SC-QNNs such that single-qubit gate op- erations are extended from {RY) (RX, RY, RZ). Results the binary classification between MNIST image (0, 2) using 8-qubit QNNs are provided in Figure 9. The training loss converges to around 0.23 and 0.5 for the TT-QNN and the SC-QNN, respectively, and the test error con- verges to around 0.3 for both the TT-QNN and the SC-QNN. We remark that based on results in Figures 5(a) and Figure 5(e), the training loss of original TT-QNN and SC-QNN converge around 0.15, and the test eтrоr converge at around 0.20 and 0.15, respectively. Thus, both the TT-QNN and the SC-QNN show the worse performance than original QNNs when employing the extended gate set (RX, RY, RZJ. Another result is provided in Table 6 which shows the difference on the training and test accuracy.
As conclusion, employing gate set (RX, RY, RZ) could worse the performance of the QNNs on real-world problems, which may due to the fact that real-world data lie in the real space, while operations (RX, RZ} introduce the imaginary term to the state.
TT-QNN ((RY)) TT-QNN (RRX, RY, RZ)) SC-QNN ((RY)) SC-QNN ((RX, RY, RZ)) training, test
Class pair
training, test
training, test
training, test
0-2
0.850, 0.812
0.656. 0.699
0.840, 0.850
0.785, 0.731
Table 6: The training and test accuracy of TT-QNNs and SC-QNNs for different single-qubit gate settings.
14

---

Under review as a conference paper at ICLR 2021
ONN
64
0.2
0.2
test eerror
6.
0.2
64-
0.18
00
training iteration
training iteration
(a)
(b)
Figure 9: The training of binary classification task the MNIST image bettwen classes (0, 2) using 8-qubit QNNs with the extended gate operation {RX, RY, RZ]. The training loss and the test error during the training iteration illustrated in Figures (a), 9(b), respectively.
B NOTES ABOUT THE UNITARY 2-DESIGN
In this section, we introduce the notion of the unitary 2-design. Consider the finite gate (G.) in the d-dimensional Hilbert space. We denote (d) as the unitary gate group with the dimension d. We denote (G) the polynomial function which has the degree at most i on the matrix elements of G and at most the matrix elements of Gt, Then, could say the set S to be the unitary (-design and only if for every function Pr,((). Eq. (9) holds:
Σ Pt.(G) = S Pr.(G).
S
GES
where dp(-)) denotes the Haar distribution. The Haar distribution du(-)) is defined that for any func- tion f and any matrix K E (d).
Se BuG])(G)) Im dK())[(K)= Suco du(G))(GK).
The form in the right side of (9) can be viewed as the average or the expectation of the function (G). We remark that only the parameterized gates RY -1902 could not form a universal gate set even in the single-qubit space (2), thus quantum circuits employing parameterized RY gates could not form the 2-design. This only a simple introduction about unitary 2-design, and we refer readers to Puchata & Miszczak (201) I) and Cerezo et al. (2020) for more detail.
C TECHNICAL LEMMAS
In this section we provide some technical lemmas. Lemma C.1. Ler CNOT = oo & (0)(0) + & [1] Then
CNOT(O, & CNort =6600 + (820 + 6 Bax + (6,0 + 6,1) + 6x2)a,0 &
+ (ō,2 + 6,3) + óua)o o403 (6,2 (5k) + 812)a,0 @0.03.
Further for the case dg.
CNOT(a; @ or) oN) (6,0 + d @ oa (5,z + 55a)o @ 03.
Proof.
CNOT(a, & o CNoTt
(ao [0) + (1)( (ay @ σx) (an & 10)(0) (1)
15

---

Under review as a conference paper at ICLR 2021
00 K
do 03
+ 8
00 03
03
(0, 2 on)
0x)
00
do
+ 03
+
00
03
2
2
1 2 ok 010 80
03010s +00,0 8030403)
4 (0001 00 100
010 k30k)))
+
(0 o403 00
000
-0000-1100011 @ 030kk)
4
(0j01 ② 030k - 8013000011000000000000
010, @ d30%)
4
(6,0 + 6,1 (0 + 653) oh (0,0 + 022 @ ok
+ (6 + (ō + ) @ o4ds - (ر,2 ( + 022 @ 00033
For the case o% ou. we have,
CNOT(a; @ oo) = (ōjo + dni)a, 8o + (6.z + 633)03 03.
Lemma C.2. Ler CZ do 10]00| @ [1] Then
CAaa @ 0x) CZ =6,0 + 653) (6xo + 6kz)a 80 or + (650 + 653) (ōkr + 6 00 oz
+ (ō,1 + ( + dealo 0003 (6,) + 652)(6n1 + 612)0,03 @ 0zd3.
Further for the case o = ou.
CZ 2 0 oo) Cz = (6,0 -5z)o, 0oo + (6 + 652), 03.
Proof.
CZia, 8 0h CZi
(ao @ (0) + @ (1)) (o, 0 (00 8 10)(0) + @ (1)
0o 03 +
do 03
Oo
+ 03
do 03
0g
(0, mk)
00 2
+
8
2
2
2
(oy 2 σk 030 0o + 030 030 1 030303)
4
1
(0j0s 030
0003
03 J30 0 030h03)
(0, @ 0303 8 000
030 k30k)
4
+ (0,03 2 030k 0,03
o 030 030k)
4
16 + ( + 8E3 o o (6 + 63 (6 + 6 0
(8,1 + ) (RRo duz)a 0503 (6,1 ( + 622)0,03 0a
For the case 0 = oo. we have,
CZ(a, 2 Cz (8,0 + 853) 80 (6,1 6/2) 003
Lemma C.3. Let be a variable with uniform distribution in [0, 2n). Let A,C H2 + H2 be arbitrary linear operators and let B D o. be arbitrary Pauli matrices, where j (0,1, Then
2x
BJTWW///
TriW WIWWWWBBTWWWWTTL
(10)
2T
E40 + 85
5,0 + 6yk
TH|BB[HCCD] +
Tr(ABoodTHCDDal
(11)
2
2
where W -100 and k (1,2,3)
16

---

Under review as a conference paper at ICLR 2021
Proof.
First simply replace the term W e e-ide I cos 0 io sin 8.
1
2m
d0Tr(W (WW
2m
1
d0Tr[(] cos - i sin AI cos + io sin Tr[(1 cos io sin O)C cos 0 + in sin 0)
Jo
2m
1
Jo
d0 {cos² @Tr[AB] - sin 0 cos OT + isn cos [T + sin (T
2T
{ coos (Tr[CD] i sin 0 cos (Trro isin cos (T Oiiaa
We remark that:
1
2m
3
d0 cos
(12)
2M
0
8"
2m
3
d0 sin
(13)
Jo
8'
1
2x
d9 cos 2 sin 1
(14)
2n
8'
d0 cos sin = 0,
(15)
2T
2x
d0 cos 0 sin 0 O.
(16)
2T
Jo
Then
The integration term
Tr|AB[TCCD] Tio,,Ao,
THABBTHooCoo,D1 Troo
Tr BTTCCo)
AB
+ Tr B
650 + 6jk
-TR[AB]TCCD]
2
550 + 8sk
+Tr(ABon)T((CDor
2 +
The last equation derived by noticing that for = =0
To
TT[AAO
[2(050 + ds.)) - 1] Tr(AAo
[2(0ç0 dze) - 1] Tr(AB],
Tr Tr(AA,,
Tr[Agjou] Tr[AoHof]
2(1 650 55k) Tr(AojØR]
2(1 - 650 55x) Tr(A [[A))
while similar forms hold for D oj,
Tr(o
Tr(Cota,ok) [2(0,0 dΙx) - 1| Tr(Co,
[2(0,0 +jp) - 1] TT(CD),
Tr Dr|Co,D]
Tr[Co,ox] Tr(Cogo,)
2(1 - 6,0 6,K) T[(Co
2(1 6,0 5,²) Tr(D)
17

---

Under review as a conference paper at ICLR 2021
Lemma C.A. Let O be variable with uniform distribution in [0, 2x). Let A,C H2 - H2 be arbitrary linear operators and let B == Jj be arbitrary Pauli matrices, where j E (0,1,2.3 Then
2
EATrGAW BJTAGCWI BAYGGWWBBHGGWWW D] = 2π
(GGAWBBIT/GCCT Did0
60 + 85
8,0 +
5zk 2
Tr Tr|AB[T[CD]]
[
Tr T/ABoN)TT(CDo
2
where W = = --iime, G = aw and k E (1,2.3}.
Proof. First we simply replace the term W e-doz I coss 8 -I sin 0 io cos 0.
i sin 0 and G
oW
1
(UTGGAWTBJT[(CWWT
2m
1
d0Tr[(- [ir[(-Isii) ssn 0 i cos A) cos io sin [] sin 0 io cos () cos 1 + io sin D)
2T
Jo
1
2st
d9 { sin cos [Tr[AB]]] cos [Tr isin [Tr[Ao, si oTo
2m
sin f [T[[CD] - cos (T isin [Tr[Co, + cos sin o
The integration above could be simplified using equations 12-16.
The integration term
TT(BBTHCCD] Trio, Ao
B
Tr|Ao, B BTrr
AB
Tr Ar CDD
630 + 652
-T[[AB]T(CD]
2
650 + 65k
+TH[ABos
2
The last equation derived by noticing that for = -j
Trto TT(AAT
= [2(8,0 + 85k) 1] Tr(Ao
[2(6ç0 + 65k) 1] - (AA)
Tr(aaAB] Tr|Aox B] = Tr[AAa + Tr[AAroj]
2(0,0 5nx) Tr[AO,oR]
= 2(0,0 + 5zk) Tr(ABo
while similar forms hold for D oj
Tr(oxCouD] Tr[Conooook]
[2(0,0 + dÿz) 1] Tr(Co,]
12(0,0 dnz) 1| Tr(D),
Tr(oyCD] + Tr[Co D]
Tr[Cojou]- - Tr[Co
2(050 + d/2) Tr(Co,ok)
26800 + 6n²) Tr(CDot)
18

---

Under review as a conference paper at ICLR 2021
D THE PROOF OF THEOREM 3.1: THE TT PART
Now we begin the proof of Theorem 3.1.
Proof. Firstly remark that by Lemma D.1, each partial derivative is calculated
ffr 1 (Tr(O (k) 2
Tr(O Vir((=))pn
since the expectation of the quantum observable is bounded by [-1, 1], the square of the partial derivative could be easily bounded
fr a0!h)
1.
By summing up 2n parameters, obtain
O 00(N)
|oorrl| =2 =E
< 2n 1.
J.K
On the other side, the lower bound could be derived as follows,
1+log
fTT [0(1]
VofT
Ep
(17)
1+og
1
Σ
4Eg
frr
(18)
2
1 + log n
Tr (1,00,..... .0 Pm]] + Tr (a,,0,... _0 Pin] p'm]").
(19)
2n
where Eq. (18) derived using Lemma D.2, and Eq. (19) is derived using Lemma D.3.
Now provide the detail and the proof of Lemmas D.I, D.2, D.3. Lemma D.1. Consider the objective function of the QNN defined as
f(0) 1 + (0) 1 + Tr V pm (()))
2
where 0 encodes all parameters which participate the circuit e 10, k E 1,2,3, Pin denotes the input state and O an arbitrary quantum observable. Then, the partial derivative of the function respect to the parameter Oj could be calculated by
0ʃ 1 (THO ((o+))..v THO V(0-)paa 00,
where 0+ e, and 0_ 1- ee.
Proof. First we assume that the circuit V(0) consists of parameters, and could be written in the sequence:
( (0,) V)-1 (01),
such that each block V, contains only parameter.
Consider the observable defined as O' VIn ... vtoV, Vz-1 and the input state defined as P/n V.-na..VippaV V--1- The parameter shifting rule (Crooks, 2019) provides gradient
19

---

Under review as a conference paper at ICLR 2021
calculation method for the single parameter case. For fy(0,) could be calculated as
the gradient
df, [03 + f 4
"
d0,
Thus, by inserting the form of O' and Vn could obtain
05 = 4/1 d0, 00;
f10,
" 7) (Tr(O- ((0+))m((04)1) - v(0-)
Lemma D.2. For the functionn for defined in Eq. (3), the following formula holds for every
j E (1,2, logn):
OfT a
1 = 4 Eo(fr
Ee
2
(20)
where the expectation is taken,fo for all parameters in 0 with uniform distribution in [0, 2m..
Proof. First we rewrite the formulation of fIT in detail:
1 + 2-1 [3........0) o) VI+ICXm CXiVi Pmn Vicx]. .......xttte Cxtvv vt v fIr 2
(21)
where = log n and we denote
(ii bn) = oi @ 0i & O..
The operation V2 consists of n 21 single qubit rotations W e 0 on the (j-1)-2f-1+1
th qubit, where 1, ... 21- The operation C.X. consists of 2- CNOT gates, where each them acts on (j 1) 2 + 1-th and - (.50 2 + 1-th qubit, for j = 1,2,...,h 2
Now we focus the partial derivative of the function f to the parameter 0."). We have:
0fm 0002)
1 Tr (3.0,---.00) 0) Wm+1CX ... 0v, ...CVVV Am V/cx VJ CX Ci m-
2
00))
(22)
033,0,...00) Vm++CCm ... C...V Am v/cx ... ovt
Tr
Cxt
0
m+1
(23)
0v, Tr (300... .0 V
CC,VV Pmn vfcxf.... vj. ....cttu vt
σ()
m+11
(24)
The Eq. (24) holds because both terms in (22) and (23) except Pin are real matrices, and Pin Pmn
2
The key idea to derive Eg
0/T 00!!!
Eo(FT 1)² is that for cases = oy (01,033)
the term 22 = O. which means Lemma C.3 and Lemma C.4 collapse to the same formulation:
E Tr AwW BIr
E,
Tr|Ao 1
TT[AAo]]T(Coos)
Now we write the analysis detail.
2
Öfu 00/'1
1 ) 4(fTT -
Ee
(25)
2
20

---

Under review as a conference paper at ICLR 2021
1
-Eg
Eg... B
pay m+1
Tr (3.0.... V Am CX Vi m+1
(26)
-Eo, Eo.. 1
oa
Tr (3.00--0)) V CX B C'X Vit
m+11
(27)
m+1
-Eg,
Eam
Tr 0,3,0, .0 Am Tr (1,0, 0,0.0 .0) Am]
(28)
-Eo,
Eo..
033,0....0000....00
0,3,0, 0) Bm Tr (1.0,... 0.00....0 Bm
(29)
2
where
0V;
Am Cm m-1
....... C..VV Pin vfcxi ........... v7. CX - 0
... m- V and Eq. (28,29) are derived using the collapsed form of Lemma C.I:
Bm = Cm ".... ......XVV v/x Vÿ ... ...
CNOT CN) 01 on, CNOT(a3 & co)CNOTT
& 03
and 0₂ denotes the vector consisted with all parameters in the &-th layer. The integration could be performed for parameters {0m. 6 0m- 0 It is not hard to find that after the integration of the parameters fj+1, the term Tr(a; A and Tr(a B,]² have the opposite coefficients. Besides, the first index of each Pauli tensor product (b1,8a, in) could only be {1, 3} because of the Lemma C.3. So we could write
2
fT 0000)
1 } 4(5TT -
Eg
(30)
=Eg,
Σ
arTr fo; A,I² arTr lo; B,}²
(31)
hE i==0
where
0v, CX j-1 CXiV C..V Pin .xcxx...cx,...
Aj
08 1)
(G 10(n-1)) 1 10 (w. @ 10(n-1)).
B, V,CX,-1 -1 CXIVi Pin V/cx CX
(w(") 1((- A 10th (W
13(-11))
and o; is the coefficient of the term Tr (a: A, We denote ((3)
ow(1)
00fi
and use 1/00
to denote
rest part of A, and By. By Lemma C.3 and Lemma C.4, we have
Egg Tr A, Tr B₁}² 00
since for the case i E (1, the term t, 0, which means Lemma C.3 and Lemma C.4 have the same formulation. Then, we derive the Eq. (20).
Lemma D.3. For the loss function J defined in (3), we have:
1 Eo(fn 2
{Tr [a....... .0 pm + {Tr [o .0) pmm]
(32)
8n
where we denote
(b3 S.) os, @ oiy & T
and the expectation taken for all parameters with uniform distributions in [0. 2m.
21

---

Under review as a conference paper at ICLR 2021
Proof. First expand the function frr in detail,
fIr 2 + Tr [.........) 1m+1CX, ... C.C.VVVV Pm vicxf ... v v
(33)
2
where m log n. Now we consider the expectation of (frr 2) under the uniform distribution
for m+1
E B0o m+1
(frr
5)2
1
1
B m+1
TTr (0..0....00 .0
V ... C.CVVV Pin V/Cx] ... -xt vt
1 2
4
m m+1
(34)
1
Tr (3,0, .0 AA]} [rr (1.0.-0 .) (0 -A]]²
1
(35)
8
8
1
TT (.., 0,3.0 .) ]] + Tr o0,,, a,0, o) A]}
(36)
Tr [0 0.000.0...00...... 0.0,- 0) ... A]]?
(37)
8
where
A' CX CX1V1 Pm Vfcxf- Vn Cx
(38)
A Vm ... CXiVi Pin Vy ... Vm
(39)
and Eq. (35) is derived using Lemma C.3, Eq. (36) is derived using the collapsed form of Lemma C.I: CNOT(O1 o.)CNOT' on ou, CNOT(O3 @ Co)CCTOT' 03 @ 03.
We remark that during the integration of the parameters {0(2) } in each layer E 21, m 1}, the coefficient of the term (Tr(o .) AA} only times factor 1/2 for the case j 1, and the coefficient remains for the cases > (check Lemma C.3 for detail), Since the formulation
(1,, .0 A remains the same when merging the operation CX2, with (1,0,- .0), for E E (1,2, ... m we could generate the following equation,
Eo, Rom+. (STT ) 2 (
1 mm2 { [ou.0.-.0) 0) Vi Pm vi]}} ?
(40)
where O2 denotes the vector consisted with all parameters in the l-th layer.
Finally by using Lemma C.3, we could integrate the parameters (0()) }グ= in (40):
Ee(frr 2 = Es. ... Ee... 11 (frT )
(41)
2
Tr [1.0,... .0 Min]
+ {Tr (3.0,... .0) Pmm] pm]]
(42)
2m+3
Tr [o 0) pmn)
+ (Tr (8,0, .0) pm])
(43)
8n
E THE QUANTUM INPUT MODEL
For the convenience of the analysis, consider the encoding model that the number of alternating layers is T.. The model begins with the inital state @n, where n is the number of the qubit. Then we employ the X gate each qubit which transform the state into [1) 0n Next we employ L alternating layer operations, each of which contains four parts: single qubit rotation layer denoted V2 a CZ gate layer denoted as CZ2, again single qubit rotation layer denoted V2, and another CZ gate layer with alternating structures denoted as C'2, for i E {1,2, ... L}. Each
single qubit gate contains a parameter encoded in the phase: w((k) e - and each single qubit rotation layer could be written as
V, V2(B) w & w.!2) s0 w(()
22

---

Under review as a conference paper at ICLR 2021
(0)
X
(
W
W3
W
W
10)
x
W
(x (2)
W
2
(0)
x
W
W
W
10)
x
W
(4)
(((4)
W (4)
W
(0)
x
W
(5)
w
W
W (5)
W
(0)
X
(
(
(2(6)
W
(0)
X
w
W
W
W177)
W
(0)
X
(
W:(5)
((())
W
W/(8)
Figure 10: An example of the variational encoding model (L case).
Finally, we could mathematically define the encoding model:
(pm) = U.
where = C2,,,,,,, the j-th alternating layer.
By employing the encoding model illustrated in Figure 10 for the state preparation, find that the expectation of the term a(Pm) defined in Theorem 1.1 has the lower bound independent from the qubit number.
Theorem E.1. Suppose the input state Pin (f) is prepared by the L-layer encoding model illustrated in Figure 10. Then,
Ega(pm) = EB (Tr [T oy pm]? + Tr [T3.0.---.)) Pin] pmm²)) 22 21.
pm]²
where B denotes all variational parameters in the encoding circuit, and the expectation is taken for all parameters in B with uniform distribution [0,2mt] 2m).
Proof. Define P3 -.. 100 cnn x ... ..UU/JUJ, for j (0, LJ. We have:
--
Eg
Trr [o .) pin] + Tr lo(s.u,..... pin mmn)))
(44)
EEg ... EBI1 ( (Tr(ocaa...0)) V21+1Pr Vt
2 + Tr 013,0,--.00 VPL+ )
=
21.41
(45)
= =Ep, ... EB2 (T( pL] + Tr (0(3,0,...00) pLl²).
(46)
2 2-2 Tr [0(1.0....0) [o]2+TT Tr [o -
pp]] pu]²)
(47)
2- (02 (-11))
(48)
where Eq. (45) is derived from the definition of PL. Eq. (46) is derived using Lemma C.3. Eq. (47) derived by noticing that for each j (0, 1,,11.... .... 1}, the following equations holds,
Eg, ... Eppy+o
(Th [or.o... . P + Tr [013.......)) pstal?)
(49)
Trr (rroa......) 0) - (0100--000UU11100UJ}11 Tr [[(...0....))) UU UU-10; 1²)
= Eg ... E Epsst2
(50)
23

---

Under review as a conference paper at ICLR 2021
2
=Ep, ... Bast Tr
(1.0.....)) -
(51)
+ Rg ... R po Tr
(3.0,-- -CVV 2/+2
(52)
= -Eg, ... E Bay+ Tr
(1,3,0,, o) 12
(53)
2/42
+ Eg,
R Boyz Tr
(3.0....00 V2)+2 2j+1 C72V
C 2j+2
(54)
2 Ep. E pay+a Tr
(3.0... 0) V2 2 CZ2V
(55)
21+2
Epp
E1
2
Tr -1.....
2 012.v...222222335 2011 C22
+
Tr (330, C 122224+110 12 13
(56)
-Eg ... E3
2
123+ 2j+1 01.00,-
1
+ Tr (3.0,-- .)) 122++ Vs
1 2
2/+1 }²)
(57)
1
2 1
2 EEg ... E B2g4+ 2
Tr (3..0.-..00) .0 V2 12
(58)
EEg, Ep, 1
Tr (1.a......))) 0) -)] Tr [o.0......)) 0) -p))))
(59)
where Eq. (50) is derived from the definition Pý+1- Eq. (51-52) are derived from the definition of Us+1. Eq. (53-54) and Eq. (57) derived using Lemma C.I. Eq. (56) and Eq. (59) are derived using Lemma C.3.
THE DEFORMED TREE TENSOR QNN
Similar to the TT-QNN case, the objective function for Deformed Tree Tensor (DTT) QNN given in the form:
1
(D) - 2 Tr(a3 @ 1 (On
(60)
where VOrT denotes the circuit operation of DTT-QNN which is illustrated in Figure 11. The lower bound result for the gradient norm of DTT-QNNs is provided Theorem F.1.
Theorem F.1. Consider the n-qubit DTT-QNN defined Figure 11 and the corresponding objective function JDit defined in (60), then we have:
1 + log n a(pi)) < Vofurll' < 2n-14 -
(61)
4n
where the expectation is taken for all parameters in 0 with uniform distributions in [0, 2m Pin E x2" denotes the inpul state, a(p)) = Tr [0 00 Pmn] + Tr [3,00.... .0) Pin and ((iddamm)))) = oo & oi, 8 T..-
Proof. Firstly we remark that by Lemma D.1, each partial derivative calculated as
Øbrr (Tr(O- Vor Vorr pm Vor (0) Tr(O Virr(0-))ta Von (k 2
since the expectation of the quantum observable is bounded by [-1, 1), the square of the partial derivative could be easily bounded as:
2
fort (
$ 1.
24

---

Under review as a conference paper at ICLR 2021
10)
W(1)
W2
W (1)
W (1)
W
10)
W12)
10)
W
O
W
10)
W(4)
(0)
W(5)
W
W
10)
(pin)
(0)
W
W24
(0)
W(
10)
(()
W
W (2)
10)
((0)
(0)
W(T7)
W(4))
10)
W/(8)
Figure 11:
Quantum Neural Network with the Deformed Tree Tensor structure (qubit number 12).
By summing up 2n parameters, we obtain
f 00/h)
Σ 3.k
< 2n - 1.
On the other side, the lower bound could be derived as follows,
1+ nl
2
fvrr (0
EellVoSome
Eg
(62)
j=1
1+ ++oogg m
1 2
Σ
(63)
j=1
+ log n
(Tr [T .0) Mm]] p *TTh Tr [a(3.0.... 00 Mm ]²]
2
(64)
4n
where Eq. (63) is derived using Lemma F.1. and Eq. (64) is derived using Lemma F.2.
Lemma F.1. For the objective function forr defined in Eq. (60), the following formula holds for
every j (1,2, ,1, [log
2
1 )
Eo
4. EooSDr
(65)
where the expectation is taken for all parameters in 0 with uniform distribution in [0, 2m].
25

---

Under review as a conference paper at ICLR 2021
Proof. The proof has very similar formulation compare the original tree tensor case. First rewrite the formulation forr in detail:
1 Tr (3.00 o) V CXm ... C.XVV M.C.I....CX. kitti] +
fDIT 2 2
(66)
where m = [log n and we denote
(11 (n)) oi X o2 @
0..
The operation V/ consists of In 21-² single qubit rotations w 1020l on the (j 1) 2 1-th qubit, where j = 1,2, ... In- 22-((] The operation C.x, consists of In 2- CNOT
gates, where each of them acts on the (j 1) 2 1-th and (j 0.5) 2 + 1-th qubit, for j = 1, .. [n ".
Now we focus on the partial derivative of the function f to the parameter 0/4). We have:
f 5
033.0.-...00 .) Vm 0v, ...CCVV Pm V/cx.... ...I. VV. --..Ctt Vt
Tr
0
(67)
(3.0.....) Vm+1CX, ......V....................... "....yVV, Pm v/cx| ovt
1 + -Tr Tr
ext
vt
2
000)
m+11
(68)
0v, V CXm
CX,Vi Pm vfcxi ... .y. ... .xt yt
Tr (3.0,-..0)
m+1
(69)
The Eq. (69) holds because both terms in (67) and (68) except Pin real matrices, and Pmn Pur
= 4 Ee 1 is that for Similar to the tree tensor case, the key idea to derive Eeg
aum a0
cases D oj {3) the term fo 0. which means Lemma C.3 and Lemma C.4 collapse to the same formulation:
Tr (ITWWW//B//WWWWW
ETT
I TTAoos]Ti(oo) 1 TT[Aos]TT(Cos)
Now we write the analysis in detail.
2
0fr
IEg
4(fDIT
(70)
2
-Eo ... Eo E oan Tr (0......))) .0 Vm Min+ CX, Vt
(71)
m+1
-Eo ... Eo E gan
Tr (33.0,...0)) .0 V Cx B CX2,
vt_ m m+
(72)
Tr 03.00,,...0033.. 033.0,.- .0 Am + Tr [0,,, 0.0.0.---00 .0) Am] 12]
-IE,, Ea...
(73)
2
1
-Ee
Eo...
Tr (3,0, 0,3,0, .0 Bm + Tr 00,00, 0.000.0000 .0) Bml]
(74)
2
where
0v, (()
Am CX
C.CVV Pm v/cx.... vj... .fft.. vi
m-1
26

---

Under review as a conference paper at ICLR 2021
Bm Cn V.......y.............. Pm -Vcc ... vy... vf Vi
Eq. (73) and Eq. (74) are derived using the collapsed form Lemma C.I:
Co on) di do. CNOT(a33 & oo) = 03 2 03.
and O, denotes the vector consisted with all parameters in the &-th layer. The integration could be performed for parameters (0.: i. 0++1) It is not hard to find that after the integration of the parameters f+ the term Tr A,]² and Tr(o: By]² have the opposite coefficients. Besides, the first index of each Pauli tensor product (in, (in) could only be i (1.3) because of the Lemma C.3. So we could write
2
furt 50000
4(DVT 3
Eg
(75)
2
Eo,
Σ
Σ
TTrro A,l² arTr lo: B,1²
(76)
(1.31 i2=0
where
0v,
Aj
(Xj-1--.-CXpp Pin [.Cx]_..cxxj-.. 0
(G))) (0(n-1)) 11 /0000 (W s 10(n-1)),
B₁ V,CX,- -- CXiVi Pmn V/cx ... CX
(w 18(n-1)) 4 100 (w & 13(n-1)).
and 0₃ the coefficient of the term (az A, We denote G
aw(1) (1) oب
and use A 10
to denote
the rest part of A, and By. By Lemma C.3 and Lemma C.4, we have
E Bggss
[T A,}² Tr [r B,} 0,
since for the case i, E [1,3). the term ,,,t = 0, which means Lemma C.3 and Lemma C.4 have the same formulation. Then, derive the Eq. (65).
2
Lemma F22 For the loss function fort defined (60), we have:
Eo(for }
Trr [o(1,,,...,))
pm + (Tr [o,,0, .0) pm]]
(77)
2
16n
where we denote
(bs.8a oi 2 Oig @ T...
and the expectation taken for all parameters with uniform distributions in [0, 2T).
Proof. First expand the function fDIT in detail,
1 + Tr [o13.0.--.0) Vn+i CX,, CX.V. Pin ViCx cxt cxt Vt fTT 2
m+1
(78)
2
where m [log n]. Now we consider the expectation of (Jorr ) under the uniform distribution
for of m+1:
1 }/² =
1 E Bon { (3.0.... .0 Vm+1 CXm ... ..C.VVVV Pm Vlcxl ... C.x vl
1
E (0o (forr
4
mts
m+1
(79)
(Tr 10.0.... .0) AA]} _ [Tr (1........ .0) : A
(80)
8
27

---

Under review as a conference paper at ICLR 2021
1 [Tr 01,0,- 000000000 - A
Tr (3,0, 0.3.0.-.. .0 } +
(81)
(T [0.00, 0.0, -
(82)
where
A' CX CXiV3 Pm VICXI. V.
(83)
ma
A = Vn ......CC CX1V1 Pm C/Cx| ... V.
(84)
Eq. (80) is derived using Lemma C.3, and Eq. (81) is derived using the collapsed form of Lemma C.I:
CNOT(O, @ o.)CNoT' = on @ CNOT(Os & cNoT = 2 03.
We remark that during the integration of the parameters (0(²) } each layer E {1, , 1}. the coefficient the term (Tr .0) A]}² only times factor 1/2 for the case j and the coefficient remains for the cases >> (check Lemma C.3 for detail). Since the formulation
(Tr. .0 A]}² remains the same when merging the operation CX2, with (1.0... .), for {1,2, m), we could generate the following equation.
1 ) (
{Tr [ocLo,--00) 0) V1 Pin vi]}}²
Eo, Be (JDIT
(85)
2
where Og denotes the vector consisted with all parameters in the f-th layer.
Finally by using Lemma C.3, could integrate the parameters (0 in (85):
EJ(JDT ) Es, Eo... (JDTT )
(86)
Tr (1.0.... .0 Pmn /
Tr (3.0. .0) Pin] pmm]]
(87)
2m+3
Tr [o.1..... .0) .Pal
+ [Tr 13,0.... .0 .Pul)
(88)
16n
G THE PROOF OF THEOREM 3.1: THE SC PART
Theorem G.1. Consider the n-qubit SC-QNN defined in Figure 2 and the corresponding objective function fsc defined in (4), then we have:
1 Th 21+n.
a(pa)) S Eol Volsc|l < 2n 1,
where The is the number of the control operation CNOT that directly links to the first qubit chan- nel, and the expectation is taken for all parameters in 0 with uniform distributions in [0, 2T),
Pin x2"x2" denotes the input state, a(p)) Tr [o(.,,,.. .0 Pin] + Tr [0 Pin and -2
(la dn)) oi & Fig 8 ..... di..
Proof. Firstly we remark that by Lemma D.1, each partial derivative calculated as
assc 1 a0 2 (Tr( Vsc(O,) )mm Vse (0,) (+) Tr(O (S 1o Vsc (sc())))))
since the expectation of the quantum observable is bounded by [-1, 1], the square of the partial derivative could be easily bounded as:
fsc (k
< 1.
28

---

Under review as a conference paper at ICLR 2021
By summing up 2n parameters, obtain
Ossc 80(A)
|ee/scll =
Σ
S 2n - 1.
J.K
On the other side, the lower bound could be derived as follows,
Ossc 2
Ossc a0(t))
EØ VoSscll 2 Eg
Σ
E
(90)
00
J=n +c+1
1)²
= (1 + no) 4. Eo
isc
(91)
2
+ The
(Tr [o110000-00 .y Pin] 2 Tr [0 pin pmn)))
2 21+n.
(92)
where Eq. (91) derived using Lemma G.I, and Eq. (92) is derived using Lemma G.2.
Lemma G.1. For the objective function fsc defined in Eq. (60), the following formula holds for every j such that 0 tunes the single qubil gate on the first qubit channel:
Ofsc 0
1 2)²
Eg
E. fsc
(93)
where the expectation taken for all parameters with uniform distribution [0, 2m).
Proof. First we write the formulation of fsc in detail:
1 2 fsc 2
2 (3,0,...0))
V2,C. CXiVi Pm .xcx|x..ccx,....
(94)
where we denote (in (.)) = oi, 8 01
X oi, The operation CX2, defined as,
CX. - {
CNOT operation qubits pair (n + () 6) (1 f 1 ne).
CNOT operation on qubits pair (n + 1, (n n. S l 5 1 1).
The operation V is defined as,
w(11) & w. 10(n-1) & WT (1) @ 10(-1))
(2) @ ... @ m
(E = 1),
V
(1 n ne)) (n - no S e n).
w(t) 81018 ... 01
Now we focus on the partial derivative of the function fsc to the parameter )()) We have:
Sssc
03.0.-- 0) VVCCX 0v,
Tr
V...C Pmn vicxi... ... .o.i......Vv...... .g....l!_ V
CX.V
00
2
00)
(95)
(3.0.....)) V,CCX=1 v........V.......... V..V..VVVV.. vlxt ... ovj ... ....tt n- Vt
1
+
Tr
2
) ((
(96)
0v, (3300,.. 00 V2COX-11
Tr
C..C..V Am vicxt.... ... ...oxt n v [1)
(97)
29

---

Under review as a conference paper at ICLR 2021
The Eq. (97) holds because both terms in (95) and (96) except Pin real matrices, and Pmn Pin The key idea to derive E
ffcc a0
4 14EE (fsc - ) 2 that for cases B D = o, E for 0z) in
Lemma C.3 and Lemma C.4, the term و 0, which means both lemma collapse to the same formulation:
Eg Tr AW BIT
Eg (TTGAW/BB)(GCW"
Tr(Aos]Tr(Cos] ; + [T[[Ass|TT(Cos)
Now write the analysis in detail.
Jsc 1 2]
OSsc)
Eo
000"1
(98)
2
=Fo ... Eo, Eo, Tr [0(300,-...0 0) V. 1/1²2
(99)
-Ea ... Eo._, Eo, Tr [3.00..-.. VV.Cxn-11 1 CC 1V.1
(100)
-Eg. ... Ea.-1
Tr [(33000. 00 An 1² +
-
Tr (1.0.0,. .0) . Ann11]
(101)
2
2
-Eo. ... Ea.
Tr 0(33......... 0) B, 1²
+
1
Tr 01.0.00 .) Bn Bn-1 2
(102)
2
where
0V, C..CV Pm V/Cxj ... V/. ......................... ((1)
cX -.. 2
=
Bn-1= V Vg CX.V Am Vlcx| ........ ... ...c. -
Eq. (101) and Eq. (102) are derived using Lemma C.3 and the collapsed form of Lemma C.I:
CNOT(a) @ cn)
@ oo. CNOT(a3 & oo)CNOTt
0 03
and 0₂ denotes the vector consisted with all parameters in the é-th layer. The integration (99)- (102) could be performed similarly for parameters (0,-1,5 0n- ... 0j+1). It is not hard to find
that after the integration of the parameters 0,+1, the term Trio, A and Trio, B,1 have the opposite coefficients. Besides, the first index of each Pauli tensor product (br (.)) could only
be i E (1,3} because of the Lemma C.3. So we could write
(clsee
0ssc 000!))
Eg
- 4 fsc
2)
(103)
3
EEo ... ...E;;;
Σ
Σ
TrTr(a A,}² - arTr a;Tr(au B,}²
(104)
(1.3333) 1==
1,=0
where
0v,
Pin vfcxi...cxx
00
1)
10(0) (w @ 18(n-1)),
(G @ 10(n 18(n-11) 11 )
B, = V,CX,-1 ... ......VV1 .m vicx ... CX
(W/)" 8 11(-11) ()())
(w & 18(n1)),,
30

---

Under review as a conference paper at ICLR 2021
and La; are coefficients of the term Tr (ox Az]² Trr loy ByI² respectively. We denote C3))) aw and use A ;
ao())
denote the rest part of A, and By. By Lemma C.3 and Lemma C.4, we have
E Bgg
Tr A,i² - To BB}² =0,
-
since for the case i E (1,3), the term 1,0+,,2 = 0 in Lemma C.3 and Lemma C.4, which means both lemmas have the same formulation. Then, we derive the Eq. (93).
Lemma G.2. For the loss function fsc defined in (4), we have:
[sc 2 1)
Tr [o........ .0) Pm)] }² + (Tr [o........ .0) pm]]²
Eg
(105)
23+
where denote
(br (.))
oi C 022 8 0'.
and the expectation is taken for all parameters in with uniform distributions in [0, 2x).
Proof. We expand the function fsc in detail,
fsc = + Tr (3.0, 00 Vn V.C.In--.-..Ccip Pla VíCx ... ....
2
2
O,U,,-. pmm)
-
2
where
0 V,CX,-1 ... 1XXVVPm
vj e [n].
(106)
Now focus the expectation of (fsc 2)²
1 1)² Eo, Eo, Eo, Tr /o.,,... 10,0.,.00 o plu)]
Eg [scc
(107)
2
2 Eo, Eo, Bo 1
Tr 110,0-. o mnn
(108)
8
Tr 01.0.... . pp(p
2 Es, Eo, ... Ee, 22tne
(109)
Tr oi.u.... o 1mn-
Eo, Eo, ... Eg.-n -1 22tn.
(110)
1
Tr 01.00....00 0 (1)
Eo, 22+no
(111)
(r (Tr(01,0,... .0 Amn Tr 03.00..... .0 pmn)3)
(112)
23+n
where Eq. (112) derived from Lemma C.3. We derive Eqs. (108-109) by noticing that following equations hold for n. - + S S n and i E (1,3).
Eo, Tr [oi0.... . pppb] = Eo, Tr Tin...... V,CX,-1P cxt v
(113)
2 00.0... CX 1p 1Cx ,-1
Tr
-
(114)
03, o CX cx 1²
Tr
(115)
pp! - 12
Tr 010 0 CX
(116)
01,0... . p أ
Tr
(117)
31

---

Under review as a conference paper at ICLR 2021
where Eq. (113) is derived based on the definition of p in Eq. (106), Eqs. (114-115) are derived based on Lemma C.3, and Eq. (117) is derived based on Lemma C.I.
We derive Eq. (110-111) by noticing that following equations hold for 2 S j S
ne.
Eø, Tr 01.0,... . pb0)² Eo, Tr 0I...... VjCX -
CX V
(118)
Tr 01.00-00 CX, cX -x
1
(119)
=Tr [0 ( 1)
(120)
where Eq. (118) based on the definition of pb) in Eq. (106), Eq. (119) is based on Lemma C.3, and Eq. (120) is based Lemma C.I.
32


Reviews:
[{"review_id": "qwBIf9-abT", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Traditional Quantum Neural Networks suffer from poor trainability and one biggest reason is that the gradient vanishes exponentially with the input qubit number. \n\nThe paper proposes Tensor Tree(TT) Circuits based Quantum Neural Network to avoid such problems, a sufficient theoretical analysis was provided.\n\nIt proved a training guaranteed lower bound of $\\mathcal{O}(1/n)$  on the expectation of the gradient norm on TT and further proved a lower bound for  the expectation of the gradient norm that is independent from the input state.\n\nA binary MNIST experiment was also conducted.\n\nAdvantages:\nA.\tClarity: The paper is well written and easy to be extended. \n\nB.\tOriginality: The theoretical analysis is sufficient. This paper proposed a framework which can be employed for analyzing QNNs with other different structures in the future.\n\nDisadvantage: \n\nA. Experiment: Although theoretical analysis is sufficient and convincing, the experiment does not convince me very much: \n1. In figure 4d, the blue lines showed that the training error is 10% larger than testing error. This should be analyzed. Does it mean that the chosen test data is not very sufficient to represent the performance of the model?\n2. The classification accuracy is not a very good criterion to evaluate the binary classification performance, F1 score would be much appropriate.\n3. Only 0-1 classification experiment was conducted, the results of some other pairs should also be provided.\n4. I suggest that other tensor network Quantum circuits could also be compared.\n\nB. Limitation: I believe that TT-QNN has better trainability and can solve the gradient vanishing.  This paper only discussed an example structure and it is doubtable to generalize to other structures.\n\nC. This paper (with 20 pages) exceeds the maximum size of ICLR which is 8 pages. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Rluy1d94eyc", "reviewer": "AnonReviewer2", "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": "##########################################################################\n\nSummary:\n\n \nThe design of a useful generalization of neural networks on quantum computers has been challenging because the gradient signal will decay exponentially with respect to the depth of the quantum circuit (saturating to exponentially small in system size after the depth is linear in system size). This work provides a detailed analysis of quantum neural networks with a tree structure that uses only a depth logarithmic in the system size. The authors show that the gradient signal will only be polynomially small with respect to the system size. The authors also provide empirical verification of the theoretical analysis showing a much larger gradient norm. However, the improvement in prediction accuracy (under early stopping) when using tree-structure quantum neural networks is not very significant. This is likely because the considered system size (8 qubits) is too small to fully demonstrate the exponential decay and the inability to train random quantum neural networks.\n\n##########################################################################\n\nReasons for score: \n\nI think the theoretical analysis of the tree-structure quantum neural networks is nice. It provides a rigorous result for training a promising class of quantum neural networks. The proven result can be derived in a straightforward manner if we know that the gradient signal decays exponentially in the depth (which is not what was originally stated in the barren plateau paper [1], the result in [1] only shows an exponential decay in the system size after a depth linear in the system size). This is because a quantum neural network with a tree structure only has a log(n) depth, so the gradient norm would be 2^{-log(n)} = 1/n. However, I don't think this intuition that gradient signal decays exponentially in circuit depth is widely known, so this work still provides a novel contribution from a theoretical aspect.\n \n##########################################################################Pros: \n\nPros:\n\n1. The barren plateau problem has been a challenge that the quantum machine learning community has to overcome. This work provides a promising class of quantum neural networks that do not suffer from the barren plateau problem.\n \n2. The authors provide rigorous support for the proposed class of quantum neural networks.\n \n3. A good set of numerical experiments supplement their theoretical analysis.\n\n \n##########################################################################\n\nCons: \n\n \n1. The proven result can be derived in a straightforward manner if we know that the gradient signal decays exponentially in the depth.\n\n2.  We do not see a large improvement in prediction accuracy when the random quantum neural network employs early stopping. For example, in fig. 4(a), we can stop at iteration 50~60 and the prediction error of the random quantum neural network would be fairly small.\n \n\n \n##########################################################################\n\nQuestions and comments during rebuttal period: \n\n1. Lower bound should be $\\Omega(\\cdots)$ rather than $\\mathcal{O}(\\cdots)$.\n\n\n2. The proposed TT-QNN will have a limited expressibility due to the logarithmic depth. Do you know any application where the target function can be represented using a TT-QNN?\n\n\n3. I would strongly encourage the authors to run experiments with a larger system size (e.g., 12 to 15 qubits). Experiments with 8 qubits are too small and a gradient norm of 0.2 (for random QNN) is quite large. This is likely the cause of the lack of a large prediction advantage when using TT-QNN. Random QNN is just completely untrainable in large system sizes. Numerical experiments with a large system size will likely make the paper much stronger from an empirical perspective (if we can see a larger improvement in prediction error).\n\n\n[1] McClean, Jarrod R., et al. \"Barren plateaus in quantum neural network training landscapes.\" Nature communications 9.1 (2018): 1-6.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4_9pkYzKrH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 authors propose a new analysis of a certain type of trainable quantum circuits, namely Tree Tensor Quantum Neural Networks (TT-QNNs), that gives new and positive guarantees of its learning abilities. Using their methods, that include a specific encoding circuit and a specific loss function, the gradient of each parameter vanishes less badly compared to the usual Random QNNs. The authors demonstrate a lower bound on the (expectation value of the) norm of the overall gradient, which is also observed numerically. This could ensure a better trainability of these quantum circuits, which is of great interest. Their methodology could be used in other circuit designs. The article is well written and quantum computing concepts are well introduced, at least for an accustomed audience.\n\nHowever, some remarks could cloud the main results. \n\nMajor Remarks [concerning the encoding circuit] : \n- The encoding circuit seems poorly efficient: it has to be trained for each sample of the dataset. For each sample, the circuit has to be changed n times to scan all measurement configurations. For each configuration, multiple measurements are needed to estimate the gradient of one parameter among the 3xLxn ones (?). And then this has to be repeated through many iterations to reach convergence. Is this procedure realistic? Maybe it is considering that the circuit itself is shallow but repeated many times. A comment from the authors would be useful. \n- Worsening the case of the previous question, it seems that each time the encoding circuit is run, it is needed to have the quantum state |x_in>, the amplitude encoding of the sample, as input. How is it done in practice during the training part of each encoding circuit, since the authors themselves say that it seems unplausible to obtain such  states with near term quantum computers? \n- p.5 it is said that the simulation has been done \"classically\" on this part, why? No numerical simulation is shown to see how well the training happened. Is it efficient? Is the input state created close to the amplitude encoding objective?\n- Finally, if the encoding circuit proposed in this work was not to be used, and if one would use a random encoding instead, what could be said on the bounds of alpha(ro_in)? Could this kill the benefit claimed and lead to a similar vanishing gradient as Random QNNs? \n\nOther Remarks : \n- In the complexity analysis of Algorithm 2, it would have been more informative to provide the runtime O(n_gate n_para n_train T) in terms of n, m, L, s, and other circuit parameters. This makes more sense to grasp the difficulty of the proposed method. And maybe to compare it to the Random QNN Complexity Analysis? At least in the Appendix. \n- The choice of the form of the objective function f in (2), and the loss function in (7) should be better explained. Has it been chosen to suit the binary classification set up? and/or to ensure the bound necessary during the proof of Thm.3.1?\n- Same question for the choice of Pauli-Z based measurements in both encoding and classifier circuits. \n- Similarly, the authors should explain in the main paper the choice of using only RY rotations in the main circuit. It seems from reading the Appendix that it is for avoiding to have a unitary 2-design, is it? Could this restrain the applications, compare to what we see in a lot a (random) QNNs with the mixture of the three types of Rotations?\n\nMinor remarks : \n- extra parenthesis in the qubit at the top of p.3\n- p.7, is n_test renamed n_teXt and then n_infer? It is hard to follow. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces two new quantum neural networks with specific structures: TT-QNNs and SC-QNNs. The main contribution of this work is to show a theoretical lower bound that the gradient of the two neural networks (at random initialization) with respect to certain training objectives is well lower bounded by 2^{-2 L}, where L is the number of layers in the network. Previously, the known work only manage to prove this lower bound with less-realistic QNNs with 2-design, or prove an 2^{-poly(n)} lower bounds for random QNNs, where the input of the neural network is an n-qubit. This paper makes a first step towards solving the vanishing gradient problem of QNNs at random initialization. 



The major concern of the paper is the usefulness of these QNNs with proposed architectures: The proposed QNNs might be theoretically easier to train, but what if they can only learn a significantly smaller class of functions? In classical world, such phenomenons are very common: Linear classifiers (or even linear functions over prescribed feature mappings) are much easier to train and have much better theoretical properties, but they fail short in terms of representation power comparing to real neural networks.



In this paper, on the theory side, there is no argument about the representation power of these QNNs: It is unclear which set of functions they can represent efficiently, which limits their theoretical interests to machine learning committee. On the empirical side, the reviewers all agree that the empirical results are weak at this point: The proposed new QNNs did not show significant advantages over random QNNs (especially with early stopping), and other types of QNNs were not compared. Moreover, there seems to be some efficiency issue regarding implementing these QNNs -- More convincing empirical evidence or theoretical evidence about the power of these QNNs need to be addressed.  
Decision: Reject