Year: 2020

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 a 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.

heading: 1 INTRODUCTION
text: Neural Networks (Hecht-Nielsen, 1992) using gradient-based optimizations have dramatically advanced researches in discriminative models, generative models, and reinforcement learning. To efficiently 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 et al., 2012) for image tasks, recurrent neural networks (Zaremba et 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 et 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 as the quantum machine learning (QML) (Biamonte et al., 2017; Havlı́ček et al., 2019). Specifically, variational quantum circuits (Benedetti et al., 2019) have been explored as efficient protocols for quantum chemistry (Kandala et al., 2017) and combinatorial optimizations (Zhou et 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 et al., 2018). Due to the robustness against noises, variational quantum circuits have attracted significant interest for the hope to 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ı́ček et al., 2019) for supervised learning tasks. The training of QNNs aims to minimize the objective function f with respect to parameters θ. 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 = O(poly(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 as the Barren Plateaus (McClean et al., 2018), and could affect the
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 estimation of the derivatives needs an 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, we explore QNNs with special structures to gain fruitful results.
In this work, we introduce QNNs with special architectures, including the tree tensor (TT) structure (Huggins et al., 2019) referred to as TT-QNNs and the setp controlled structure referred to as SCQNNs. We prove that for TT-QNNs and SC-QNNs, the expectation of the gradient norm of the objective function is bounded.
Theorem 1.1. (Informal) Consider the n-qubit TT-QNN and the n-qubit SC-QNN defined in Figure 1-2 and corresponding objective functions fTT and fSC defined in (3-4), then we have:
1 + log n
2n · α(ρin) ≤ Eθ‖∇θfTT‖2 ≤ 2n− 1,
1 + nc 21+nc · α(ρin) ≤ Eθ‖∇θfSC‖2 ≤ 2n− 1,
where nc is the number of CNOT operations that directly link to the first qubit channel in the SCQNN, the expectation is taken for all parameters in θ with uniform distributions in [0, 2π], and α(ρin) ≥ 0 is a constant that only depends on the input state ρin ∈ C2
n×2n . Moreover, by preparing ρin using the L-layer encoding circuit in Figure 4, the expectation of α(ρin) could be further lower bounded as Eα(ρin) ≥ 2−2L.
Compared to random QNNs with 2−O(poly(n)) derivatives, the gradient norm of TT-QNNs ad SCQNNs is greater than Ω(1/n) or Ω(2−nc) that could lead to better trainability. Our contributions are summarized as follows:
• We prove Ω̃(1/n) and Ω̃(2−nc) lower bounds on the expectation of the gradient norm of TT-QNNs and SC-QNNs, respectively, that guarantees the trainability on related optimization 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 4 to prepare ρin, the expectation of term α(ρin) is lower bounded by a constant 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 bottleneck 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.

heading: 2 PRELIMINARY

heading: 2.1 NOTATIONS AND THE BASIC QUANTUM COMPUTING
text: We use [N ] to denote the set {1, 2, · · · , N}. The form ‖ · ‖ denotes the ‖ · ‖2 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 a matrixA is denoted asA†. The trace of a matrixA is denoted as Tr[A]. We denote ∇θf as the gradient of the function f with respect to the vector θ. We employ notations O and Õ to describe the standard complexity and the complexity ignoring minor terms, respectively.
Now we introduce the quantum computing. The pure state of a qubit could be written as |φ〉 = a|0〉+b|1〉, where a, b ∈ C satisfies |a|2+|b|2 = 1, and {|0〉 = (1, 0)T , |1〉 = (0, 1)T }, respectively. The n-qubit space is formed by the tensor product of n single-qubit spaces. For the vector x ∈ R2n , the amplitude encoded state |x〉 is defined as 1‖x‖ ∑2n j=1 xj |j〉. The dense matrix is defined as ρ = |x〉〈x| for the pure state, in which 〈x| = (|x〉)†. A single-qubit operation to the state behaves like the matrix-vector multiplication and can be referred to as the gate in the quantum circuit language. Specifically, single-qubit operations are often used including RX(θ) = e−iθX , RY (θ) = e−iθY , and RZ(θ) = e−iθZ :
X = ( 0 1 1 0 ) , Y = ( 0 −i i 0 ) , Z = ( 1 0 0 −1 ) .
Pauli matrices {I,X, Y, Z} will be referred to as {σ0, σ1, σ2, σ3} for the convenience. Moreover, two-qubit operations, the CNOT gate and the CZ gate, are employed for generating quantum entanglement:
CNOT = • = |0〉〈0| ⊗ σ0 + |1〉〈1| ⊗ σ1, CZ = • • = |0〉〈0| ⊗ σ0 + |1〉〈1| ⊗ σ3.
We could obtain information from the quantum system by performing measurements, for example, measuring the state |φ〉 = a|0〉+b|1〉 generates 0 and 1 with probability p(0) = |a|2 and p(1) = |b|2, respectively. Such a measurement operation could be mathematically referred to as calculating the average of the observable O = σ3 under the state |φ〉:
〈σ3〉|φ〉 ≡ 〈φ|σ3|φ〉 ≡ Tr[|φ〉〈φ| · σ3] = |a|2 − |b|2 = p(0)− p(1) = 2p(0)− 1. The average of a unitary observable under arbitrary states is bounded by [−1, 1].

heading: 2.2 RELATED WORKS
text: 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 L = O(poly(n)), the expectation of the derivative to the objective function is zero, and the variance of the derivative vanishes to zero with rate exponential 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(2−O(L)). The result implies that in the low-depth L = O(log n) case, the vanishing rate could be O( 1polyn ), 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 to an identity matrix (L = 0). Skolik et al. (2020) train parameters in subsets in each layer, so that a low-depth circuit is optimized during the training of each subset of parameters.
Since random quantum circuits tend to be approximately unitary 2-design1 as the circuit depth increases (Harrow & Low, 2009), and 2-design circuits lead to exponentially vanishing gradients (McClean 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 et al., 2019; Hayashi et al., 2019). Recently, quantum classifiers using hierarchical 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 et al., 2020). Also, the 2-design assumption in the existing theoretical analysis (McClean et al., 2018; Cerezo et al., 2020; Sharma et al., 2020) is hard to implement exactly on near-term quantum devices.

heading: 3 QUANTUM NEURAL NETWORKS
text: In this section, we discuss the quantum neural networks in detail. Specifically, the optimizing of QNNs is presented in Section 3.1. We analyze QNNs with special structures in Section 3.2. We
1We refer the readers to Appendix B for a short discussion about the unitary 2-design.
introduce an approximate quantum input model in Section 3.3 which helps for deriving further theoretical bounds.

heading: 3.1 THE OPTIMIZING OF QUANTUM NEURAL NETWORKS
text: 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 mathematically equals to a parameterized unitary matrix V (θ). The training of QNNs aims to optimize the function f defined as:
f(θ; ρin) = 1
2 +
1 2 Tr [ O · V (θ) · ρin · V (θ)† ] = 1 2 + 1 2 〈O〉V (θ),ρin , (1)
where O denotes the quantum observable and ρin denotes the density matrix of the input quantum state. Generally, we could deploy the parameters θ in a tunable quantum circuit arbitrarily. A practical tactic is to encode parameters {θj} as the phases of the single-qubit gates {e−iθjσk , k ∈ {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 algorithms (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),
∂f ∂θj = 1 2 〈O〉V (θ+),ρin − 1 2 〈O〉V (θ−),ρin = f(θ+; ρin)− f(θ−; ρin), (2)
where θ+ and θ− are different from θ only at the j-th parameter: θj → θj ± π4 . Thus, the gradient of f could be obtained by estimating quantum observables, which allows employing quantum computers for fast optimizations using stochastic gradient descents.

heading: 3.2 QUANTUM NEURAL NETWORKS WITH SPECIAL STRUCTURES
text: In this subsection, we 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 `2- norm for the TT-QNN and the SC-QNN are lower bounded by Ω̃(1/n) and Ω̃(2−nc), respectively, where nc is a 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 we discuss proposed quantum neural networks in detail. We consider the n-qubit QNN constructed by the single-qubit gate W (k)j = e
−iθ(k)j σ2 and the CNOT gate σ1 ⊗ |1〉〈1| + σ0 ⊗ |0〉〈0|. We define the k-th parameter in the j-th layer as θ(k)j . We only employ RY rotations for singlequbit 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 1 for the n = 4 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 nc = 2 case, where nc 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
fTT(θ) = 1
2 +
1 2 Tr[σ3 ⊗ I⊗(n−1)VTT(θ)ρinVTT(θ)†], (3)
fSC(θ) = 1
2 +
1 2 Tr[σ3 ⊗ I⊗(n−1)VSC(θ)ρinVSC(θ)†], (4)
where VTT(θ) and VSC(θ) denotes the parameterized quantum circuit operations for the TT-QNN and the SC-QNN, respectively. We employ the observable σ3 ⊗ I⊗(n−1) in Eq. (3-4) such that objective functions could be easily estimated by measuring the first qubit in corresponding quantum circuits.
Main results of this section are stated in Theorem 3.1, in which we prove Ω̃(1/n) and Ω̃(2−nc) lower bounds on the expectation of the square of the gradient norm for the TT-QNN and the SCQNN, respectively. By setting nc = O(log n), we could obtain the linear inverse bound for the SC-QNN as well. We provide the proof of Theorem 3.1 in Appendix D and Appendix G.
Theorem 3.1. Consider the n-qubit TT-QNN and the n-qubit SC-QNN defined in Figure 1-2 and corresponding objective functions fTT and fSC defined in Eq. (3-4), then we have:
1 + log n
2n · α(ρin) ≤ Eθ‖∇θfTT‖2 ≤ 2n− 1, (5)
1 + nc 21+nc · α(ρin) ≤ Eθ‖∇θfSC‖2 ≤ 2n− 1, (6)
where nc is the number of CNOT operations that directly link to the first qubit channel in the SC-QNN, the expectation is taken for all parameters in θ with uniform distributions in [0, 2π], ρin ∈ C2 n×2n denotes the input state, α(ρin) = Tr [ σ(1,0,··· ,0) · ρin ]2 + Tr [ σ(3,0,··· ,0) · ρin ]2 , and σ(i1,i2,··· ,in) ≡ σi1 ⊗ σi2 ⊗ · · · ⊗ σin .
From the geographic view, the value Eθ‖∇θf‖2 characterizes the global steepness of the function surface in the parameter space. Optimizing the objective function f using gradient-based methods could be hard if the norm of 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 a new theoretical framework during proving Eq. (5-6). Different from existing works (McClean et al., 2018; Grant et al., 2019; Cerezo et 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 θ varies continuously in [0, 2π]. 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 of QNN with linear depth. Our framework could be extensively employed for analyzing QNNs with other different structures as future works.

heading: 3.3 PREPARE THE QUANTUM INPUT MODEL: A VARIATIONAL CIRCUIT APPROACH
text: State preparation is an essential part of most quantum algorithms, which encodes the classical information into quantum states. Specifically, the amplitude encoding |x〉 = ∑2n i=1 xi/‖x‖|i〉 allows storing the 2n-dimensional vector in n 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(2n) using a quantum circuit with O(2n) depth, which is prohibitive for large-size data on near-term quantum computers. In fact, arbitrary quantum amplitude encoding with polynomial gate complexity remains an open problem.
Algorithm 1 Quantum Input Model
Require: The input vector xin ∈ R2 n
, the number of alternating layers L, the iteration time T , and the learning rate {η(t)}T−1t=0 .
Ensure: A parameter vector β∗ which tunes the approximate encoding circuit U(β∗). 1: Initialize {β(k)j } n,2L+1 j,k=1 randomly in [0, 2π]. Denote the parameter vector as β
(0). 2: for t ∈ {0, 1, · · · , T − 1} do 3: Run the circuit in Figure 3 classically to calculate the gradient ∇βfinput|β=β(t) using the parameter shifting rule (2), where the function finput is defined in (7). 4: Update the parameter β(t+1) = β(t) − η(t) · ∇βfinput|β=β(t) . 5: end for 6: Output the trained parameter β∗.
In this subsection, we introduce a quantum input model for approximately encoding the arbitrary vector xin ∈ R2 n
in the amplitude of the quantum state |xin〉. The main idea is to classically train an alternating layered circuit as summarized in Algorithm 1 and Figures 3-4. Now we explain the detail of the input model. Firstly, we randomly initialize the parameter β(0) in the circuit 3. Then, we train the parameter to minimize the objective function defined in (7) through the gradient descent,
finput(β) = 1
n n∑ i=1 〈Oi〉W (β)|xin〉 = 1 n n∑ i=1 1 ‖xin‖2 Tr[Oi ·W (β) · xinxTin ·W (β)†], (7)
where Oi = σ ⊗(i−1) 0 ⊗ σ3 ⊗ σ ⊗(n−i) 0 ,∀i ∈ [n], and W (β) denotes the tunable alternating layered circuit in Figure 3. Note that although the framework is given in the quantum circuit language, we actually calculate and update the gradient on classical computers by considering each quantum gate operation as the matrix multiplication. The output of Algorithm 1 is the trained parameter vector β∗ which tunes the unitary W (β∗). The corresponding encoding circuit could then be implemented as U(β∗) = W (β∗)† · X⊗n, which is low-depth and appropriate for near-term quantum computers. Structures of circuits W and U are illustrated in Figure 3 and 4, respectively. Suppose we could minimize the objective function (7) to −1. Then 〈Oi〉 = −1,∀i ∈ [n], which means the final output state in Figure 3 equals to W (β∗)|xin〉 = |1〉⊗n.2 Thus the state |xin〉 could be prepared exactly by applying the circuit U(β∗) = W (β∗)†X⊗n on the 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.
2We 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 as 1 or -1. For the former case, nothing needs to be done; for the letter case, the global phase could be introduced by adding a single qubit gate e−iπσ0 = −σ0 = −I on anyone among qubit channels.
Algorithm 2 QNNs for the Binary Classification Training
Require: Quantum input states {ρtraini }Si=1 for the dataset {(xtraini , yi)}Si=1, the quantum observable O, the parameterized quantum circuit V (θ), the iteration time T , the batch size s, and learning rates {ηθ(t)}T−1t=0 and {ηb(t)} T−1 t=0 . Ensure: The trained parameters θ∗ and b∗. 1: Initialize each parameter in θ(0) randomly in [0, 2π] and initialize b(0) = 0. 2: for t ∈ {0, 1, · · · , T − 1} do 3: Randomly sample an index subset It ⊂ [S] with size s. Calculate the gradient
∇θ`It(θ, b)|θ,b=θ(t),b(t) and ∇b`It(θ, b)|θ,b=θ(t),b(t) using the chain rule and the parameter shifting rule (2), where the function `It(θ, b) is defined in (8).
4: Update parameters θ(t+1)/b(t+1) = θ(t)/b(t) − ηθ/b(t) · ∇θ/b`It(θ, b)|θ,b=θ(t),b(t) . 5: end for 6: Output trained parameters θ∗ = θ(T ) and b∗ = b(T ).
An interesting result is that by employing the encoding circuit in Figure 4 for constructing the input state in Section 3.2 as ρin = U(β)(|0〉〈0|)⊗nU(β)†, we could bound the expectation of α(ρin) defined in Theorem 3.1 by a constant that only relies on the layer L (Theorem 3.2). Theorem 3.2. Suppose the state ρin is prepared by the L-layer encoding circuit in Figure 4, then we have, Eβα(ρin) ≥ 2−2L, where β denotes all variational parameters in the encoding circuit, and the expectation is taken for all parameters in β with uniform distributions in [0, 2π].
We provide the proof of Theorem 3.2 and more details about the input model in Appendix E. Theorem 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.

heading: 4 APPLICATION: QNNS FOR THE BINARY CLASSIFICATION

heading: 4.1 QNNS: TRAINING AND PREDICTION
text: 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 {(xtraini , yi)}Si=1 and {(xtestj , yj)} Q j=1, where yi ∈ {0, 1} denotes the label, we prepare corresponding quantum input states {ρtraini }Si=1 and {ρtestj } Q j=1 using the encoding circuit presented in Section 3.3. Then, we employ Algorithm 2 to train the parameter θ 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 is presented in the Step 3-4, which aims to minimize the loss defined in (8) for each input batch It,∀t ∈ [T ]:
`It(θ) = 1
|It| |It|∑ i=1 ( f(θ; ρtraini )− yi + b )2 . (8)
Based on the chain rule and the Eq. (2), derivatives ∂`It∂θj and ∂`It ∂b could be decomposed into products 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 θ∗ and b∗. Denote the quantum circuit V ∗ = V (θ∗). We do test for an input state ρtest by calculating the objective function f(ρtest) = 12 + 1 2Tr[O · V
∗ ρtest V ∗)†]. We classify the input ρtest as in the class 0 if f(ρtest) + b∗ < 12 , or the class 1 if f(ρ test) + b∗ > 12 .
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 circuit V (θ) as ngate and npara, respectively. Denote the number of measurements for estimating each quantum observable as ntrain and ntest for the training and test stages, respectively. Then, the time complexity to train QNNs is O(ngatenparantrainT ), and the time complexity of the test using QNNs
is O(ngatentest). We emphasize that directly comparing the time complexity of QNNs with classical 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 O(nL) gates and O(n) parameters, which lead to the training complexity O(ntrainn2LT ) and the test complexity O(ntestnL).

heading: 4.2 NUMERICAL SIMULATIONS
text: To analyze the practical performance of QNNs for binary classification tasks, we simulate the training and test of QNNs on the MNIST handwritten dataset. The 28 × 28 size image is sampled into 16× 16, 32× 32, and 64× 64 to fit QNNs for qubit number n ∈ {8, 10, 12}. We set the parameter in SC-QNNs as nc = 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 TTQNNs for general qubit numbers, we modify TT-QNNs into Deformed Tree Tensor (DTT) QNNs. The gradient norm for DTT-QNNs is lower bounded by O(1/n), which has a 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.
We construct the encoding circuits in Section 3.3 with the number of alternating layers L = 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 in 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 σ3 for all qubits in the circuit. The number of the training iteration is 100, the batch size is 20, and the decayed learning rate is adopted as {1.00, 0.75, 0.50, 0.25}. We set ntrain = 200 and ntest = 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 TTQNNs, 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 n ∈ {8, 10, 12}. The total loss is defined as the average of the single-input loss. The training loss and the test error during the training iteration are illustrated in Figures 5(a), 5(e) for the n=8 case, Figures 5(b), 5(f) for the
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 Random-QNNs 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-QNNs have better trainability and accuracy on the binary classification compared with Random-QNNs. We record the l2-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-QNN 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 α(ρin) defined in Theorem 3.1 and show the result in Figure 5(h). The average of α(ρin) is around 0.6, which is lower bounded by the theoretical result 14 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 {i, j} ⊂ {0, 1, 2, 3, 4} are provided in Table 1. The F1-0 denotes the F1-score when treats the former class to be positive, and the F1-1 denotes the F1-score for the other case. As shown in Table 1, TT-QNNs and SC-QNNs have higher test accuracy and F1-score than Random-QNNs for all class pairs in Table 1. Specifically, test accuracy of TT-QNNs and SC-QNNs exceed that of Random-QNNs 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 classification 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.

heading: 5 CONCLUSIONS
text: In this work, we analyze the vanishing gradient problem in quantum neural networks. We prove that the gradient norm of n-qubit quantum neural networks with the tree tensor structure and the step controlled structure are lower bounded by Ω( 1n ) and Ω(( 1 2 ) nc), respectively. The bound guarantees 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 neural 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.

heading: A NUMERICAL SIMULATIONS
text: In this section, we provide more experimential details about the input model and other binary classification tasks.
A.1 QUANTUM INPUT MODEL FOR THE MNIST DATASET
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 or test data with the number of alternating layers L = 1. 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 in Eq. 7 during the training of Algorithm 1 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 a 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 a few features from the input data (except the image 1 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 exact amplitude encoding, which is commonly used in existing quantum machine learning algorithms. Figure 8 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 gradient is counted in Figure 8(c), in which both the TT-QNN and the SC-QNN show larger gradient norm than the Random-QNN. 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 2. We notice that compared with QNNs using the encoding circuit, QNNs with the exact encoding tend to have better
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 in Table 3, both the training and test accuracy of TT-QNNs and SC-QNNs remain at a 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 a random guessing.
A.3 QNNS WITH DIFFERENT LABEL PAIRS
We summarize the results of training and test accuracy, along with the F1-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 F1-scores than that of Random-QNNs. Moreover, most of test accuracy of Random-QNNs drop for the same class pair when the qubit number is increased from 8 to 10, which suggest the trainability of Random-QNNs get worse as the qubit number increases.
A.4 QNNS WITH DIFFERENT ROTATION GATES
In this section, we simulate variants of TT-QNNs and SC-QNNs such that single-qubit gate operations are extended from {RY} to {RX, RY, RZ}. Results on 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.175 for the TT-QNN and the SC-QNN, respectively, and the test error converges 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 at around 0.15, and the test error 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, RZ}. Another result is provided in Table 6 which shows the difference on the training and test accuracy.
As a 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.
B NOTES ABOUT THE UNITARY 2-DESIGN
In this section, we introduce the notion of the unitary 2-design. Consider the finite gate set S = {Gi}|S|i=1 in the d-dimensional Hilbert space. We denote U(d) as the unitary gate group with the dimension d. We denote Pt,t(G) as the polynomial function which has the degree at most t on the matrix elements of G and at most t on the matrix elements of G†. Then, we could say the set S to be the unitary t-design if and only if for every function Pt,t(·), Eq. (9) holds:
1 |S| ∑ G∈S Pt,t(G) = ∫ U(d) dµ(G)Pt,t(G), (9)
where dµ(·) denotes the Haar distribution. The Haar distribution dµ(·) is defined that for any function f and any matrix K ∈ U(d),∫
U(d)
dµ(G)f(G) = ∫ U(d) dµ(G)f(KG) = ∫ U(d) dµ(G)f(GK).
The form in the right side of (9) can be viewed as the average or the expectation of the function Pt,t(G). We remark that only the parameterized gates RY = e−iθσ2 could not form a universal gate set even in the single-qubit space U(2), thus quantum circuits employing parameterized RY gates could not form the 2-design. This is only a simple introduction about the unitary 2-design, and we refer readers to Puchała & Miszczak (2011) and Cerezo et al. (2020) for more detail.

heading: C TECHNICAL LEMMAS
text: In this section we provide some technical lemmas. Lemma C.1. Let CNOT = σ0 ⊗ |0〉〈0|+ σ1 ⊗ |1〉〈1|. Then
CNOT(σj ⊗ σk)CNOT† =(δj0 + δj1)(δk0 + δk3)σj ⊗ σk + (δj0 + δj1)(δk1 + δk2)σjσ1 ⊗ σk + (δj2 + δj3)(δk0 + δk3)σj ⊗ σkσ3 − (δj2 + δj3)(δk1 + δk2)σjσ1 ⊗ σkσ3.
Further for the case σk = σ0,
CNOT(σj ⊗ σ0)CNOT† = (δj0 + δj1)σj ⊗ σ0 + (δj2 + δj3)σj ⊗ σ3.
Proof.
CNOT(σj ⊗ σk)CNOT†
= (σ0 ⊗ |0〉〈0|+ σ1 ⊗ |1〉〈1|) (σj ⊗ σk) (σ0 ⊗ |0〉〈0|+ σ1 ⊗ |1〉〈1|)
= ( σ0 ⊗
σ0 + σ3 2 + σ1 ⊗ σ0 − σ3 2
) (σj ⊗ σk) ( σ0 ⊗
σ0 + σ3 2 + σ1 ⊗ σ0 − σ3 2 ) = 1
4 (σj ⊗ σk + σ1σjσ1 ⊗ σk + σj ⊗ σ3σkσ3 + σ1σjσ1 ⊗ σ3σkσ3) + 1
4 (σjσ1 ⊗ σk + σ1σj ⊗ σk − σjσ1 ⊗ σ3σkσ3 − σ1σj ⊗ σ3σkσ3)
+ 1
4 (σj ⊗ σkσ3 + σj ⊗ σ3σk − σ1σjσ1 ⊗ σkσ3 − σ1σjσ1 ⊗ σ3σk)
+ 1
4 (σjσ1 ⊗ σ3σk − σjσ1 ⊗ σkσ3 + σ1σj ⊗ σkσ3 − σ1σj ⊗ σ3σk)
=(δj0 + δj1)(δk0 + δk3)σj ⊗ σk + (δj0 + δj1)(δk1 + δk2)σjσ1 ⊗ σk + (δj2 + δj3)(δk0 + δk3)σj ⊗ σkσ3 − (δj2 + δj3)(δk1 + δk2)σjσ1 ⊗ σkσ3.
For the case σk = σ0, we have, CNOT(σj ⊗ σ0)CNOT† = (δj0 + δj1)σj ⊗ σ0 + (δj2 + δj3)σj ⊗ σ3.
Lemma C.2. Let CZ = σ0 ⊗ |0〉〈0|+ σ3 ⊗ |1〉〈1|. Then CZ(σj ⊗ σk)CZ† =(δj0 + δj3)(δk0 + δk3)σj ⊗ σk + (δj0 + δj3)(δk1 + δk2)σjσ3 ⊗ σk
+ (δj1 + δj2)(δk0 + δk3)σj ⊗ σkσ3 − (δj1 + δj2)(δk1 + δk2)σjσ3 ⊗ σkσ3. Further for the case σk = σ0,
CZ(σj ⊗ σ0)CZ† = (δj0 + δj3)σj ⊗ σ0 + (δj1 + δj2)σj ⊗ σ3.
Proof.
CZ(σj ⊗ σk)CZ†
= (σ0 ⊗ |0〉〈0|+ σ3 ⊗ |1〉〈1|) (σj ⊗ σk) (σ0 ⊗ |0〉〈0|+ σ3 ⊗ |1〉〈1|)
= ( σ0 ⊗
σ0 + σ3 2 + σ3 ⊗ σ0 − σ3 2
) (σj ⊗ σk) ( σ0 ⊗
σ0 + σ3 2 + σ3 ⊗ σ0 − σ3 2 ) = 1
4 (σj ⊗ σk + σ3σjσ3 ⊗ σk + σj ⊗ σ3σkσ3 + σ3σjσ3 ⊗ σ3σkσ3) + 1
4 (σjσ3 ⊗ σk + σ3σj ⊗ σk − σjσ3 ⊗ σ3σkσ3 − σ3σj ⊗ σ3σkσ3)
+ 1
4 (σj ⊗ σkσ3 + σj ⊗ σ3σk − σ3σjσ3 ⊗ σkσ3 − σ3σjσ3 ⊗ σ3σk)
+ 1
4 (σjσ3 ⊗ σ3σk − σjσ3 ⊗ σkσ3 + σ3σj ⊗ σkσ3 − σ3σj ⊗ σ3σk)
=(δj0 + δj3)(δk0 + δk3)σj ⊗ σk + (δj0 + δj3)(δk1 + δk2)σjσ3 ⊗ σk + (δj1 + δj2)(δk0 + δk3)σj ⊗ σkσ3 − (δj1 + δj2)(δk1 + δk2)σjσ3 ⊗ σkσ3.
For the case σk = σ0, we have, CZ(σj ⊗ σ0)CZ† = (δj0 + δj3)σj ⊗ σ0 + (δj1 + δj2)σj ⊗ σ3.
Lemma C.3. Let θ be a variable with uniform distribution in [0, 2π]. Let A,C : H2 → H2 be arbitrary linear operators and let B = D = σj be arbitrary Pauli matrices, where j ∈ {0, 1, 2, 3}. Then
EθTr[WAW †B]Tr[WCW †D] = 1
2π ∫ 2π 0 Tr[WAW †B]Tr[WCW †D]dθ (10)
=
[ 1
2 + δj0 + δjk 2
] Tr[AB]Tr[CD] + [ −1
2 + δj0 + δjk 2
] Tr[ABσk]Tr[CDσk], (11)
where W = e−iθσk and k ∈ {1, 2, 3}.
Proof. First we simply replace the term W = e−iθσk = I cos θ − iσk sin θ. 1
2π ∫ 2π 0 dθTr[WAW †B]Tr[WCW †D]
= 1
2π ∫ 2π 0 dθTr[(I cos θ − iσk sin θ)A(I cos θ + iσk sin θ)B] · Tr[(I cos θ − iσk sin θ)C(I cos θ + iσk sin θ)D]
= 1
2π ∫ 2π 0 dθ { cos2 θTr[AB]− i sin θ cos θTr[σkAB] + i sin θ cos θTr[AσkB] + sin2 θTr[σkAσkB] }
· { cos2 θTr[CD]− i sin θ cos θTr[σkCD] + i sin θ cos θTr[CσkD] + sin2 θTr[σkCσkD] } .
We remark that: 1
2π ∫ 2π 0 dθ cos4 θ = 3 8 , (12)
1
2π ∫ 2π 0 dθ sin4 θ = 3 8 , (13)
1
2π ∫ 2π 0 dθ cos2 θ sin2 θ = 1 8 , (14)
1
2π ∫ 2π 0 dθ cos3 θ sin θ = 0, (15)
1
2π ∫ 2π 0 dθ cos θ sin3 θ = 0. (16)
Then
The integration term = 3
8 Tr[AB]Tr[CD] +
3 8 Tr[σkAσkB]Tr[σkCσkD]
+ 1
8 Tr[AB]Tr[σkCσkD] +
1 8 Tr[σkAσkB]Tr[CD]
−1 8 Tr[σkAB]Tr[σkCD]− 1 8 Tr[AσkB]Tr[CσkD] + 1
8 Tr[σkAB]Tr[CσkD] +
1 8 Tr[AσkB]Tr[σkCD]
=Tr[AB]Tr[CD] [ 1
2 + δj0 + δjk 2 ] +Tr[ABσk]Tr[CDσk] [ −1
2 + δj0 + δjk 2
] .
The last equation is derived by noticing that for B = σj , Tr[σkAσkB] = Tr[Aσkσjσk]
= [2(δj0 + δjk)− 1] · Tr[Aσj ] = [2(δj0 + δjk)− 1] · Tr[AB],
Tr[σkAB]− Tr[AσkB] = Tr[Aσjσk]− Tr[Aσkσj ] = 2(1− δj0 − δjk) · Tr[Aσjσk] = 2(1− δj0 − δjk) · Tr[ABσk],
while similar forms hold for D = σj , Tr[σkCσkD] = Tr[Cσkσjσk]
= [2(δj0 + δjk)− 1] · Tr[Cσj ] = [2(δj0 + δjk)− 1] · Tr[CD],
Tr[σkCD]− Tr[CσkD] = Tr[Cσjσk]− Tr[Cσkσj ] = 2(1− δj0 − δjk) · Tr[Cσjσk] = 2(1− δj0 − δjk) · Tr[CDσk].
Lemma C.4. Let θ be a variable with uniform distribution in [0, 2π]. Let A,C : H2 → H2 be arbitrary linear operators and let B = D = σj be arbitrary Pauli matrices, where j ∈ {0, 1, 2, 3}. Then
EθTr[GAW †B]Tr[GCW †D] = 1
2π ∫ 2π 0 Tr[GAW †B]Tr[GCW †D]dθ
=
[ 1
2 − δj0 + δjk 2
] Tr[AB]Tr[CD] + [ −1
2 − δj0 + δjk 2
] Tr[ABσk]Tr[CDσk],
where W = e−iθσk , G = ∂W∂θ and k ∈ {1, 2, 3}.
Proof. First we simply replace the term W = e−iθσk = I cos θ − iσk sin θ and G = ∂W∂θ = −I sin θ − iσk cos θ.
1
2π ∫ 2π 0 dθTr[GAW †B]Tr[GCW †D]
= 1
2π ∫ 2π 0 dθTr[(−I sin θ − iσk cos θ)A(I cos θ + iσk sin θ)B]Tr[(−I sin θ − iσk cos θ)C(I cos θ + iσk sin θ)D]
= 1
2π ∫ 2π 0 dθ { − sin θ cos θTr[AB]− i cos2 θTr[σkAB]− i sin2 θTr[AσkB] + cos θ sin θTr[σkAσkB] } · { − sin θ cos θTr[CD]− i cos2 θTr[σkCD]− i sin2 θTr[CσkD] + cos θ sin θTr[σkCσkD] } .
The integration above could be simplified using equations 12-16,
The integration term = 1
8 Tr[AB]Tr[CD] +
1 8 Tr[σkAσkB]Tr[σkCσkD]
−1 8 Tr[AB]Tr[σkCσkD]− 1 8 Tr[σkAσkB]Tr[CD] −3 8 Tr[σkAB]Tr[σkCD]− 3 8 Tr[AσkB]Tr[CσkD] −1 8 Tr[σkAB]Tr[CσkD]− 1 8 Tr[AσkB]Tr[σkCD]
=Tr[AB]Tr[CD] [ 1
2 − δj0 + δjk 2 ] +Tr[ABσk]Tr[CDσk] [ −1
2 − δj0 + δjk 2
] .
The last equation is derived by noticing that for B = σj ,
Tr[σkAσkB] = Tr[Aσkσjσk] = [2(δj0 + δjk)− 1] · Tr[Aσj ] = [2(δj0 + δjk)− 1] · Tr[AB],
Tr[σkAB] + Tr[AσkB] = Tr[Aσjσk] + Tr[Aσkσj ] = 2(δj0 + δjk) · Tr[Aσjσk] = 2(δj0 + δjk) · Tr[ABσk],
while similar forms hold for D = σj ,
Tr[σkCσkD] = Tr[Cσkσjσk] = [2(δj0 + δjk)− 1] · Tr[Cσj ] = [2(δj0 + δjk)− 1] · Tr[CD],
Tr[σkCD] + Tr[CσkD] = Tr[Cσjσk]− Tr[Cσkσj ] = 2(δj0 + δjk) · Tr[Cσjσk] = 2(δj0 + δjk) · Tr[CDσk].

heading: D THE PROOF OF THEOREM 3.1: THE TT PART
text: Now we begin the proof of Theorem 3.1.
Proof. Firstly we remark that by Lemma D.1, each partial derivative is calculated as
∂fTT
∂θ (k) j
= 1
2
( Tr[O · VTT(θ+)ρinVTT(θ+)†]− Tr[O · VTT(θ−)ρinVTT(θ−)†] ) ,
since the expectation of the quantum observable is bounded by [−1, 1], the square of the partial derivative could be easily bounded as: (
∂fTT
∂θ (k) j
)2 ≤ 1.
By summing up 2n− 1 parameters, we obtain
‖∇θfTT‖2 = ∑ j,k
( ∂fTT
∂θ (k) j
)2 ≤ 2n− 1.
On the other side, the lower bound could be derived as follows,
Eθ‖∇θfTT‖2 ≥ 1+logn∑ j=1 Eθ
( ∂fTT
∂θ (1) j
)2 (17)
= 1+logn∑ j=1 4Eθ ( fTT − 1 2 )2 (18)
≥ 1 + log n 2n
· ( Tr [ σ(1,0,··· ,0) · ρin ]2 + Tr [ σ(3,0,··· ,0) · ρin ]2) , (19)
where Eq. (18) is derived using Lemma D.2, and Eq. (19) is derived using Lemma D.3.
Now we provide the detail and the proof of Lemmas D.1, D.2, D.3.
Lemma D.1. Consider the objective function of the QNN defined as
f(θ) = 1 + 〈O〉
2 = 1 + Tr[O · V (θ)ρinV (θ)†] 2 ,
where θ encodes all parameters which participate the circuit as e−iθjσk , k ∈ 1, 2, 3, ρin denotes the input state and O is an arbitrary quantum observable. Then, the partial derivative of the function respect to the parameter θj could be calculated by
∂f ∂θj = 1 2
( Tr[O · V (θ+)ρinV (θ+)†]− Tr[O · V (θ−)ρinV (θ−)†] ) ,
where θ+ ≡ θ + π4 ej and θ− ≡ θ − π 4 ej .
Proof. First we assume that the circuit V (θ) consists of p parameters, and could be written in the sequence: V (θ) = Vp(θp) · Vp−1(θp−1) · · ·V1(θ1), such that each block Vj contains only one parameter.
Consider the observable defined as O′ = V †j+1 · · ·V †pOVp · · ·Vj+1 and the input state defined as ρ′in = Vj−1 · · ·V1ρinV † 1 · · ·V † j−1. The parameter shifting rule (Crooks, 2019) provides a gradient
calculation method for the single parameter case. For fj(θj) = Tr[O′ ·U(θj)ρ′inU(θj)†], the gradient could be calculated as
dfj dθj = fj(θj + π 4 )− fj(θj − π 4 ).
Thus, by inserting the form of O′ and ρ′in, we could obtain
∂f ∂θj = dfj dθj = fj(θj+ π 4 )−fj(θj− π 4 ) = 1 2
( Tr[O · V (θ+)ρinV (θ+)†]− Tr[O · V (θ−)ρinV (θ−)†] ) .
Lemma D.2. For the objective function fTT defined in Eq. (3), the following formula holds for every j ∈ {1, 2, · · · , 1 + log n}:
Eθ
( ∂fTT
∂θ (1) j
)2 = 4 · Eθ(fTT − 1
2 )2, (20)
where the expectation is taken for all parameters in θ with uniform distribution in [0, 2π].
Proof. First we rewrite the formulation of fTT in detail:
fTT = 1
2 +
1 2 Tr [ σ(3,0,··· ,0) · Vm+1CXm · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CX†mV † m+1 ] , (21)
where m = log n and we denote
σ(i1,i2,··· ,in) ≡ σi1 ⊗ σi2 ⊗ · · · ⊗ σin .
The operation V` consists of n·21−` single qubit rotationsW (j)` = e−iσ2θ (j) ` on the (j−1)·2`−1+1th qubit, where j = 1, 2, · · · , n · 21−`. The operation CX` consists of n · 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, 2, · · · , n · 2−`.
Now we focus on the partial derivative of the function f to the parameter θ(1)j . We have:
∂fTT
∂θ (1) j
= 1
2 Tr
[ σ(3,0,··· ,0) · Vm+1CXm · · · ∂Vj
θ (1) j
· · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † mV † m+1 ] (22)
+ 1
2 Tr
[ σ(3,0,··· ,0) · Vm+1CXm · · ·Vj · · ·CX1V1 · ρin · V †1 CX † 1 · · · ∂V †j
θ (1) j
· · ·CX†mV † m+1 ] (23)
= Tr [ σ(3,0,··· ,0) · Vm+1CXm · · · ∂Vj
θ (1) j
· · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † mV † m+1
] .
(24)
The Eq. (24) holds because both terms in (22) and (23) except ρin are real matrices, and ρin = ρ † in. The key idea to derive Eθ ( ∂fTT
∂θ (1) j
)2 = 4 · Eθ(fTT − 12 ) 2 is that for cases B = D = σj ∈ {σ1, σ3},
the term δj0+δj22 = 0, which means Lemma C.3 and Lemma C.4 collapse to the same formulation:
EθTr[WAW †B]Tr[WCW †D] = EθTr[GAW †B]Tr[GCW †D]
= 1
2 Tr[Aσ1]Tr[Cσ1] +
1 2 Tr[Aσ3]Tr[Cσ3].
Now we write the analysis in detail.
Eθ ( ∂fTT ∂θ
(1) j
)2 − 4(fTT − 1
2 )2
 (25)
=Eθ1 · · ·EθmEθ(1)m+1Tr [ σ(3,0,··· ,0) · Vm+1CXmAmCXmV †m+1 ]2 (26)
−Eθ1 · · ·EθmEθ(1)m+1Tr [ σ(3,0,··· ,0) · Vm+1CXmBmCXmV †m+1 ]2 (27)
=Eθ1 · · ·Eθm { 1 2 Tr [ σ(3,0,··· ,0,3,0,··· ,0) ·Am ]2 + 1 2 Tr [ σ(1,0,··· ,0,0,0,··· ,0) ·Am ]2} (28)
−Eθ1 · · ·Eθm { 1 2 Tr [ σ(3,0,··· ,0,3,0,··· ,0) ·Bm ]2 + 1 2 Tr [ σ(1,0,··· ,0,0,0,··· ,0) ·Bm ]2} , (29)
where
Am = VmCXm−1 · · · ∂Vj
θ (1) j
· · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † m−1V † m,
Bm = VmCXm−1 · · ·Vj · · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † m−1V † m,
and Eq. (28,29) are derived using the collapsed form of Lemma C.1:
CNOT(σ1 ⊗ σ0)CNOT† = σ1 ⊗ σ0, CNOT(σ3 ⊗ σ0)CNOT† = σ3 ⊗ σ3, and θ` denotes the vector consisted with all parameters in the `-th layer. The integration could be performed for parameters {θm,θm−1, · · · ,θj+1}. It is not hard to find that after the integration of the parameters θj+1, the term Tr[σi · Aj ]2 and Tr[σi · Bj ]2 have the opposite coefficients. Besides, the first index of each Pauli tensor product σ(i1,i2,··· ,in) could only be i1 ∈ {1, 3} because of the Lemma C.3. So we could write
Eθ ( ∂fTT ∂θ
(1) j
)2 − 4(fTT − 1
2 )2  (30) =Eθ1 · · ·Eθj
 ∑ i1∈{1,3} 3∑ i2=0 · · · 3∑ in=0 aiTr [σi ·Aj ]2 − aiTr [σi ·Bj ]2  (31)
where
Aj = ∂Vj
∂θ (1) j
CXj−1 · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CXj−1V † j
= (G (1) j ⊗ I ⊗(n−1))A /θ
(1) j
j (W (1)† j ⊗ I ⊗(n−1)),
Bj = VjCXj−1 · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CXj−1V † j
= (W (1) j ⊗ I ⊗(n−1))A /θ
(1) j
j (W (1)† j ⊗ I ⊗(n−1)),
and ai is the coefficient of the term Tr [σi ·Aj ]2. We denote G(1)j = ∂W
(1) j
∂θ (1) j
and use A /θ
(1) j
j to denote
the rest part of Aj and Bj . By Lemma C.3 and Lemma C.4, we have
E θ (1) j
[ Tr [σi ·Aj ]2 − Tr [σi ·Bj ]2 ] = 0,
since for the case i1 ∈ {1, 3}, the term δi10+δi12
2 = 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 f defined in (3), we have:
Eθ(fTT − 1
2 )2 ≥
{ Tr [ σ(1,0,··· ,0) · ρin ]}2 + { Tr [ σ(3,0,··· ,0) · ρin ]}2 8n , (32)
where we denote σ(i1,i2,··· ,in) ≡ σi1 ⊗ σi2 ⊗ · · · ⊗ σin ,
and the expectation is taken for all parameters in θ with uniform distributions in [0, 2π].
Proof. First we expand the function fTT in detail,
fTT = 1
2 +
1 2 Tr [ σ(3,0,··· ,0) · Vm+1CXm · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CX†mV † m+1 ] , (33)
where m = log n. Now we consider the expectation of (fTT − 12 ) 2 under the uniform distribution for θ(1)m+1:
E θ (1) m+1
(fTT − 1
2 )2 =
1 4 E θ (1) m+1
{ Tr [ σ(3,0,··· ,0) · Vm+1CXm · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CX†mV † m+1 ]}2 (34)
= 1
8
{ Tr [ σ(3,0,··· ,0) ·A′ ]}2 + 1
8
{ Tr [ σ(1,0,··· ,0) ·A′ ]}2 (35)
= 1
8
{ Tr [ σ(3,0,··· ,0,3,0,··· ,0) ·A ]}2 + 1
8
{ Tr [ σ(1,0,··· ,0,0,··· ,0) ·A ]}2 (36)
≥ 1 8
{ Tr [ σ(1,0,··· ,0,0,··· ,0) ·A ]}2 , (37)
where
A′ = CXmVm · · ·CX1V1 · ρin · V †1 CX † 1 · · ·VmCX†m, (38)
A = Vm · · ·CX1V1 · ρin · V †1 CX † 1 · · ·Vm, (39)
and Eq. (35) is derived using Lemma C.3, Eq. (36) is derived using the collapsed form of Lemma C.1:
CNOT(σ1 ⊗ σ0)CNOT† = σ1 ⊗ σ0, CNOT(σ3 ⊗ σ0)CNOT† = σ3 ⊗ σ3,
We remark that during the integration of the parameters {θ(j)` } in each layer ` ∈ {1, 2, · · · ,m+ 1}, the coefficient of the term {Tr[σ(1,0,··· ,0) · A]}2 only times a factor 1/2 for the case j = 1, and the coefficient remains for the cases j > 1 (check Lemma C.3 for detail). Since the formulation {Tr[σ(1,0,··· ,0) · A]}2 remains the same when merging the operation CX` with σ(1,0,··· ,0), for ` ∈ {1, 2, · · · ,m}, we could generate the following equation,
Eθ2 · · ·Eθm+1(fTT − 1 2 )2 ≥ (1 2 )m+2
{ Tr [ σ(1,0,··· ,0) · V1 · ρin · V †1 ]}2 , (40)
where θ` denotes the vector consisted with all parameters in the `-th layer.
Finally by using Lemma C.3, we could integrate the parameters {θ(j)1 }nj=1 in (40):
Eθ(fTT − 1
2 )2 = Eθ1 · · ·Eθm+1(fTT −
1 2 )2 (41)
≥ { Tr [ σ(1,0,··· ,0) · ρin ]}2 + { Tr [ σ(3,0,··· ,0) · ρin ]}2 2m+3
(42)
=
{ Tr [ σ(1,0,··· ,0) · ρin ]}2 + { Tr [ σ(3,0,··· ,0) · ρin ]}2 8n . (43)

heading: E THE QUANTUM INPUT MODEL
text: For the convenience of the analysis, we consider the encoding model that the number of alternating layers is L. The model begins with the inital state |0〉⊗n, where n is the number of the qubit. Then we employ the X gate to each qubit which transform the state into |1〉⊗n. Next we employ L alternating layer operations, each of which contains four parts: a single qubit rotation layer denoted as V2i−1, a CZ gate layer denoted as CZ2, again a single qubit rotation layer denoted as V2i, and another CZ gate layer with alternating structures denoted as CZ1, for i ∈ {1, 2, · · · , L}. Each single qubit gate contains a parameter encoded in the phase: W (k)j = e
−iσ2β(k)j , and each single qubit rotation layer could be written as
Vj = Vj(βj) = W (1) j ⊗W (2) j ⊗ · · · ⊗W (n) j .
Finally, we could mathematically define the encoding model:
U(ρin) = V2L+1ULUL−1 · · ·U1X⊗n,
where Uj = CZ1V2jCZ2V2j−1 is the j-th alternating layer.
By employing the encoding model illustrated in Figure 10 for the state preparation, we find that the expectation of the term α(ρin) defined in Theorem 1.1 has the lower bound independent from the qubit number.
Theorem E.1. Suppose the input state ρin(θ) is prepared by the L-layer encoding model illustrated in Figure 10. Then,
Eβα(ρin) = Eβ ( Tr [ σ(1,0,··· ,0) · ρin ]2 + Tr [ σ(3,0,··· ,0) · ρin ]2) ≥ 2−2L, where β denotes all variational parameters in the encoding circuit, and the expectation is taken for all parameters in β with uniform distribution in [0, 2π].
Proof. Define ρj = UjUj−1 · · ·U1X⊗n|0〉⊗n〈0|⊗nX⊗nU†1 · · ·U † j−1U † j , for j ∈ {0, 1, · · · , L}. We have:
Eβ ( Tr [ σ(1,0,··· ,0) · ρin ]2 + Tr [ σ(3,0,··· ,0) · ρin ]2) (44)
= Eβ1 · · ·Eβ2L+1 ( Tr [ σ(1,0,··· ,0) · V2L+1ρLV †2L+1 ]2 + Tr [ σ(3,0,··· ,0) · V2L+1ρLV †2L+1 ]2) (45)
= Eβ1 · · ·Eβ2L ( Tr [ σ(1,0,··· ,0) · ρL ]2 + Tr [ σ(3,0,··· ,0) · ρL ]2) . (46)
≥ 2−2L ( Tr [ σ(1,0,··· ,0) · ρ0 ]2 + Tr [ σ(3,0,··· ,0) · ρ0 ]2) (47)
= 2−2L · (02 + (−1)2) = 2−2L, (48)
where Eq. (45) is derived from the definition of ρL. Eq. (46) is derived using Lemma C.3. Eq. (47) is derived by noticing that for each j ∈ {0, 1, · · · , L− 1}, the following equations holds,
Eβ1 · · ·Eβ2j+2 ( Tr [ σ(1,0,··· ,0) · ρj+1 ]2 + Tr [ σ(3,0,··· ,0) · ρj+1 ]2) (49)
= Eβ1 · · ·Eβ2j+2 ( Tr [ σ(1,0,··· ,0) · Uj+1ρjU†j+1 ]2 + Tr [ σ(3,0,··· ,0) · Uj+1ρjU†j+1 ]2) (50)
= Eβ1 · · ·Eβ2j+2Tr [ σ(1,0,··· ,0) · CZ1V2j+2CZ2V2j+1ρjV †2j+1CZ2V † 2j+2CZ1 ]2 (51)
+ Eβ1 · · ·Eβ2j+2Tr [ σ(3,0,··· ,0) · CZ1V2j+2CZ2V2j+1ρjV †2j+1CZ2V † 2j+2CZ1 ]2 (52)
= Eβ1 · · ·Eβ2j+2Tr [ σ(1,3,0,··· ,0) · V2j+2CZ2V2j+1ρjV †2j+1CZ2V † 2j+2 ]2 (53)
+ Eβ1 · · ·Eβ2j+2Tr [ σ(3,0,··· ,0) · V2j+2CZ2V2j+1ρjV †2j+1CZ2V † 2j+2 ]2 (54)
≥ Eβ1 · · ·Eβ2j+2Tr [ σ(3,0,··· ,0) · V2j+2CZ2V2j+1ρjV †2j+1CZ2V † 2j+2 ]2 (55)
= Eβ1 · · ·Eβ2j+1 ( 1 2 Tr [ σ(1,0,··· ,0) · CZ2V2j+1ρjV †2j+1CZ2 ]2 + 1 2 Tr [ σ(3,0,··· ,0) · CZ2V2j+1ρjV †2j+1CZ2 ]2) (56)
= Eβ1 · · ·Eβ2j+1 ( 1 2 Tr [ σ(1,0,··· ,0,3) · V2j+1ρjV †2j+1 ]2 + 1 2 Tr [ σ(3,0,··· ,0) · V2j+1ρjV †2j+1 ]2) (57)
≥ Eβ1 · · ·Eβ2j+1 1 2 Tr [ σ(3,0,··· ,0) · V2j+1ρjV †2j+1 ]2 (58) = Eβ1 · · ·Eβ2j 1
4
( Tr [ σ(1,0,··· ,0) · ρj ]2 + Tr [ σ(3,0,··· ,0) · ρj ]2) , (59)
where Eq. (50) is derived from the definition of ρj+1. Eq. (51-52) are derived from the definition of Uj+1. Eq. (53-54) and Eq. (57) are derived using Lemma C.1. Eq. (56) and Eq. (59) are derived using Lemma C.3.

heading: F THE DEFORMED TREE TENSOR QNN
text: Similar to the TT-QNN case, the objective function for the Deformed Tree Tensor (DTT) QNN is given in the form:
fDTT(θ) = 1
2 +
1 2 Tr[σ3 ⊗ I⊗(n−1)VDTT(θ)ρinVDTT(θ)†], (60)
where VDTT 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 in Theorem F.1.
Theorem F.1. Consider the n-qubit DTT-QNN defined in Figure 11 and the corresponding objective function fDTT defined in (60), then we have:
1 + log n
4n · α(ρin) ≤ Eθ‖∇θfDTT‖2 ≤ 2n− 1, (61)
where the expectation is taken for all parameters in θ with uniform distributions in [0, 2π], ρin ∈ C2 n×2n denotes the input state, α(ρin) = Tr [ σ(1,0,··· ,0) · ρin ]2 + Tr [ σ(3,0,··· ,0) · ρin ]2 , and σ(i1,i2,··· ,in) ≡ σi1 ⊗ σi2 ⊗ · · · ⊗ σin .
Proof. Firstly we remark that by Lemma D.1, each partial derivative is calculated as
∂fDTT
∂θ (k) j
= 1
2
( Tr[O · VDTT(θ+)ρinVDTT(θ+)†]− Tr[O · VDTT(θ−)ρinVDTT(θ−)†] ) ,
since the expectation of the quantum observable is bounded by [−1, 1], the square of the partial derivative could be easily bounded as: (
∂fDTT
∂θ (k) j
)2 ≤ 1.
By summing up 2n− 1 parameters, we obtain
‖∇θfDTT‖2 = ∑ j,k
( ∂fDTT
∂θ (k) j
)2 ≤ 2n− 1.
On the other side, the lower bound could be derived as follows,
Eθ‖∇θfDTT‖2 ≥ 1+dlogne∑ j=1 Eθ
( ∂fDTT
∂θ (1) j
)2 (62)
= 1+dlogne∑ j=1 4Eθ ( fDTT − 1 2 )2 (63)
≥ 1 + log n 4n
· ( Tr [ σ(1,0,··· ,0) · ρin ]2 + Tr [ σ(3,0,··· ,0) · ρin ]2) , (64)
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 fDTT defined in Eq. (60), the following formula holds for every j ∈ {1, 2, · · · , 1 + dlog ne}:
Eθ
( ∂fDTT
∂θ (1) j
)2 = 4 · Eθ(fDTT − 1
2 )2, (65)
where the expectation is taken for all parameters in θ with uniform distribution in [0, 2π].
Proof. The proof has a very similar formulation compare to the original tree tensor case. First we rewrite the formulation of fDTT in detail:
fDTT = 1
2 +
1 2 Tr [ σ(3,0,··· ,0) · Vm+1CXm · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CX†mV † m+1 ] , (66)
where m = dlog ne and we denote
σ(i1,i2,··· ,in) ≡ σi1 ⊗ σi2 ⊗ · · · ⊗ σin .
The operation V` consists of bn · 21−`c single qubit rotations W (j)` = e−iσ2θ (j) ` on the (j − 1) · 2`−1 + 1-th qubit, where j = 1, 2, · · · , bn · 21−`c. The operation CX` consists of bn · 2−`c 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, 2, · · · , bn · 2−`c.
Now we focus on the partial derivative of the function f to the parameter θ(1)j . We have:
∂fDTT
∂θ (1) j
= 1
2 Tr
[ σ(3,0,··· ,0) · Vm+1CXm · · · ∂Vj
θ (1) j
· · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † mV † m+1 ] (67)
+ 1
2 Tr
[ σ(3,0,··· ,0) · Vm+1CXm · · ·Vj · · ·CX1V1 · ρin · V †1 CX † 1 · · · ∂V †j
θ (1) j
· · ·CX†mV † m+1 ] (68)
= Tr [ σ(3,0,··· ,0) · Vm+1CXm · · · ∂Vj
θ (1) j
· · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † mV † m+1
] .
(69)
The Eq. (69) holds because both terms in (67) and (68) except ρin are real matrices, and ρin = ρ † in. Similar to the tree tensor case, the key idea to derive Eθ ( ∂fDTT
∂θ (1) j
)2 = 4 · Eθ(fDTT − 12 ) 2 is that for
cases B = D = σj ∈ {σ1, σ3}, the term δj0+δj22 = 0, which means Lemma C.3 and Lemma C.4 collapse to the same formulation:
EθTr[WAW †B]Tr[WCW †D] = EθTr[GAW †B]Tr[GCW †D]
= 1
2 Tr[Aσ1]Tr[Cσ1] +
1 2 Tr[Aσ3]Tr[Cσ3].
Now we write the analysis in detail.
Eθ (∂fDTT ∂θ
(1) j
)2 − 4(fDTT − 1
2 )2  (70) =Eθ1 · · ·EθmEθ(1)m+1Tr [ σ(3,0,··· ,0) · Vm+1CXmAmCXmV †m+1 ]2 (71)
−Eθ1 · · ·EθmEθ(1)m+1Tr [ σ(3,0,··· ,0) · Vm+1CXmBmCXmV †m+1 ]2 (72)
=Eθ1 · · ·Eθm { 1 2 Tr [ σ(3,0,··· ,0,3,0,··· ,0) ·Am ]2 + 1 2 Tr [ σ(1,0,··· ,0,0,0,··· ,0) ·Am ]2} (73)
−Eθ1 · · ·Eθm { 1 2 Tr [ σ(3,0,··· ,0,3,0,··· ,0) ·Bm ]2 + 1 2 Tr [ σ(1,0,··· ,0,0,0,··· ,0) ·Bm ]2} , (74)
where
Am = VmCXm−1 · · · ∂Vj
θ (1) j
· · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † m−1V † m,
Bm = VmCXm−1 · · ·Vj · · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † m−1V † m.
Eq. (73) and Eq. (74) are derived using the collapsed form of Lemma C.1:
CNOT(σ1 ⊗ σ0)CNOT† = σ1 ⊗ σ0, CNOT(σ3 ⊗ σ0)CNOT† = σ3 ⊗ σ3, and θ` denotes the vector consisted with all parameters in the `-th layer. The integration could be performed for parameters {θm,θm−1, · · · ,θj+1}. It is not hard to find that after the integration of the parameters θj+1, the term Tr[σi · Aj ]2 and Tr[σi · Bj ]2 have the opposite coefficients. Besides, the first index of each Pauli tensor product σ(i1,i2,··· ,in) could only be i1 ∈ {1, 3} because of the Lemma C.3. So we could write
Eθ (∂fDTT ∂θ
(1) j
)2 − 4(fDTT − 1
2 )2  (75) =Eθ1 · · ·Eθj
 ∑ i1∈{1,3} 3∑ i2=0 · · · 3∑ in=0 aiTr [σi ·Aj ]2 − aiTr [σi ·Bj ]2  (76)
where
Aj = ∂Vj
∂θ (1) j
CXj−1 · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CXj−1V † j
= (G (1) j ⊗ I ⊗(n−1))A /θ
(1) j
j (W (1)† j ⊗ I ⊗(n−1)),
Bj = VjCXj−1 · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CXj−1V † j
= (W (1) j ⊗ I ⊗(n−1))A /θ
(1) j
j (W (1)† j ⊗ I ⊗(n−1)),
and ai is the coefficient of the term Tr [σi ·Aj ]2. We denote G(1)j = ∂W
(1) j
∂θ (1) j
and use A /θ
(1) j
j to denote
the rest part of Aj and Bj . By Lemma C.3 and Lemma C.4, we have
E θ (1) j
[ Tr [σi ·Aj ]2 − Tr [σi ·Bj ]2 ] = 0,
since for the case i1 ∈ {1, 3}, the term δi10+δi12
2 = 0, which means Lemma C.3 and Lemma C.4 have the same formulation. Then, we derive the Eq. (65).
Lemma F.2. For the loss function fDTT defined in (60), we have:
Eθ(fDTT − 1
2 )2 ≥
{ Tr [ σ(1,0,··· ,0) · ρin ]}2 + { Tr [ σ(3,0,··· ,0) · ρin ]}2 16n , (77)
where we denote σ(i1,i2,··· ,in) ≡ σi1 ⊗ σi2 ⊗ · · · ⊗ σin ,
and the expectation is taken for all parameters in θ with uniform distributions in [0, 2π].
Proof. First we expand the function fDTT in detail,
fTT = 1
2 +
1 2 Tr [ σ(3,0,··· ,0) · Vm+1CXm · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CX†mV † m+1 ] , (78)
wherem = dlog ne. Now we consider the expectation of (fDTT− 12 ) 2 under the uniform distribution for θ(1)m+1:
E θ (1) m+1
(fDTT − 1
2 )2 =
1 4 E θ (1) m+1
{ Tr [ σ(3,0,··· ,0) · Vm+1CXm · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CX†mV † m+1 ]}2 (79)
= 1
8
{ Tr [ σ(3,0,··· ,0) ·A′ ]}2 + 1
8
{ Tr [ σ(1,0,··· ,0) ·A′ ]}2 (80)
= 1
8
{ Tr [ σ(3,0,··· ,0,3,0,··· ,0) ·A ]}2 + 1
8
{ Tr [ σ(1,0,··· ,0,0,··· ,0) ·A ]}2 (81)
≥ 1 8
{ Tr [ σ(1,0,··· ,0,0,··· ,0) ·A ]}2 , (82)
where
A′ = CXmVm · · ·CX1V1 · ρin · V †1 CX † 1 · · ·VmCX†m, (83)
A = Vm · · ·CX1V1 · ρin · V †1 CX † 1 · · ·Vm. (84)
Eq. (80) is derived using Lemma C.3, and Eq. (81) is derived using the collapsed form of Lemma C.1:
CNOT(σ1 ⊗ σ0)CNOT† = σ1 ⊗ σ0, CNOT(σ3 ⊗ σ0)CNOT† = σ3 ⊗ σ3,
We remark that during the integration of the parameters {θ(j)` } in each layer ` ∈ {1, 2, · · · ,m+ 1}, the coefficient of the term {Tr[σ(1,0,··· ,0) · A]}2 only times a factor 1/2 for the case j = 1, and the coefficient remains for the cases j > 1 (check Lemma C.3 for detail). Since the formulation {Tr[σ(1,0,··· ,0) · A]}2 remains the same when merging the operation CX` with σ(1,0,··· ,0), for ` ∈ {1, 2, · · · ,m}, we could generate the following equation,
Eθ2 · · ·Eθm+1(fDTT − 1 2 )2 ≥ (1 2 )m+2
{ Tr [ σ(1,0,··· ,0) · V1 · ρin · V †1 ]}2 , (85)
where θ` denotes the vector consisted with all parameters in the `-th layer.
Finally by using Lemma C.3, we could integrate the parameters {θ(j)1 }nj=1 in (85):
Eθ(fDTT − 1
2 )2 = Eθ1 · · ·Eθm+1(fDTT −
1 2 )2 (86)
≥ { Tr [ σ(1,0,··· ,0) · ρin ]}2 + { Tr [ σ(3,0,··· ,0) · ρin ]}2 2m+3
(87) ≥ { Tr [ σ(1,0,··· ,0) · ρin ]}2 + { Tr [ σ(3,0,··· ,0) · ρin ]}2 16n . (88)

heading: G THE PROOF OF THEOREM 3.1: THE SC PART
text: 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 + nc 21+nc · α(ρin) ≤ Eθ‖∇θfSC‖2 ≤ 2n− 1, (89)
where nc is the number of the control operation CNOT that directly links to the first qubit channel, and the expectation is taken for all parameters in θ with uniform distributions in [0, 2π], ρin ∈ C2 n×2n denotes the input state, α(ρin) = Tr [ σ(1,0,··· ,0) · ρin ]2 + Tr [ σ(3,0,··· ,0) · ρin ]2 , and σ(i1,i2,··· ,in) ≡ σi1 ⊗ σi2 ⊗ · · · ⊗ σin .
Proof. Firstly we remark that by Lemma D.1, each partial derivative is calculated as
∂fSC
∂θ (k) j
= 1
2
( Tr[O · VSC(θ+)ρinVSC(θ+)†]− Tr[O · VSC(θ−)ρinVSC(θ−)†] ) ,
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) j
)2 ≤ 1.
By summing up 2n− 1 parameters, we obtain
‖∇θfSC‖2 = ∑ j,k
( ∂fSC
∂θ (k) j
)2 ≤ 2n− 1.
On the other side, the lower bound could be derived as follows,
Eθ‖∇θfSC‖2 ≥ Eθ
( ∂fSC
∂θ (1) 1
)2 +
n∑ j=n−nc+1 Eθ
( ∂fSC
∂θ (1) j
)2 (90)
= (1 + nc) · 4 · Eθ ( fSC − 1
2
)2 (91)
≥ 1 + nc 21+nc
· ( Tr [ σ(1,0,··· ,0) · ρin ]2 + Tr [ σ(3,0,··· ,0) · ρin ]2) , (92)
where Eq. (91) is derived using Lemma G.1, 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 θ(1)j tunes the single qubit gate on the first qubit channel:
Eθ
( ∂fSC
∂θ (1) j
)2 = 4 · Eθ ( fSC − 1
2
)2 , (93)
where the expectation is taken for all parameters in θ with uniform distribution in [0, 2π].
Proof. First we write the formulation of fSC in detail:
fSC = 1
2 +
1 2 Tr [ σ(3,0,··· ,0) · VnCXn−1 · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CX † n−1V † n ] , (94)
where we denote σ(i1,i2,··· ,in) ≡ σi1 ⊗ σi2 ⊗ · · · ⊗ σin . The operation CX` is defined as,
CX` = { CNOT operation on qubits pair (n+ 1− `, n− `) (1 ≤ ` ≤ n− 1− nc), CNOT operation on qubits pair (n+ 1− `, 1) (n− nc ≤ ` ≤ n− 1).
The operation V` is defined as,
V` =  W (1) 1 ⊗W (2) 1 ⊗ · · · ⊗W (n) 1 (` = 1),
I⊗(n−`) ⊗W (1)` ⊗ I⊗(`−1) (1 ≤ ` ≤ n− 1− nc), W
(1) ` ⊗ I ⊗ I ⊗ · · · ⊗ I (n− nc ≤ ` ≤ n).
Now we focus on the partial derivative of the function fSC to the parameter θ (1) j . We have:
∂fSC
∂θ (1) j
= 1
2 Tr
[ σ(3,0,··· ,0) · VnCXn−1 · · · ∂Vj
θ (1) j
· · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † n−1V † n ] (95)
+ 1
2 Tr
[ σ(3,0,··· ,0) · VnCXn−1 · · ·Vj · · ·CX1V1 · ρin · V †1 CX † 1 · · · ∂V †j
θ (1) j
· · ·CX†n−1V †n ] (96)
= Tr [ σ(3,0,··· ,0) · VnCXn−1 · · · ∂Vj
θ (1) j
· · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † n−1V † n
] .
(97)
The Eq. (97) holds because both terms in (95) and (96) except ρin are real matrices, and ρin = ρ † in. The key idea to derive Eθ ( ∂fSC
∂θ (1) j
)2 = 4 ·Eθ(fSC− 12 ) 2 is that for cases B = D = σj ∈ {σ1, σ3} in
Lemma C.3 and Lemma C.4, the term δj0+δj22 = 0, which means both lemma collapse to the same formulation:
EθTr[WAW †B]Tr[WCW †D] = EθTr[GAW †B]Tr[GCW †D]
= 1
2 Tr[Aσ1]Tr[Cσ1] +
1 2 Tr[Aσ3]Tr[Cσ3].
Now we write the analysis in detail.
Eθ ( ∂fSC ∂θ
(1) j
)2 − 4 ( fSC − 1
2 )2 (98) =Eθ1 · · ·Eθn−1EθnTr [ σ(3,0,··· ,0) · VnCXn−1An−1CXn−1V †n ]2 (99)
−Eθ1 · · ·Eθn−1EθnTr [ σ(3,0,··· ,0) · VnCXn−1Bn−1CXn−1V †n ]2 (100)
=Eθ1 · · ·Eθn−1 { 1 2 Tr [ σ(3,3,0,··· ,0) ·An−1 ]2 + 1 2 Tr [ σ(1,0,0,··· ,0) ·An−1 ]2} (101)
−Eθ1 · · ·Eθn−1 { 1 2 Tr [ σ(3,3,0,··· ,0) ·Bn−1 ]2 + 1 2 Tr [ σ(1,0,0,··· ,0) ·Bn−1 ]2} , (102)
where
An−1 = Vn−1CXn−2 · · · ∂Vj
θ (1) j
· · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † n−2V † n−1,
Bn−1 = Vn−1CXn−2 · · ·Vj · · ·CX1V1 · ρin · V †1 CX † 1 · · ·V † j · · ·CX † n−2V † n−1.
Eq. (101) and Eq. (102) are derived using Lemma C.3 and the collapsed form of Lemma C.1:
CNOT(σ1 ⊗ σ0)CNOT† = σ1 ⊗ σ0, CNOT(σ3 ⊗ σ0)CNOT† = σ3 ⊗ σ3,
and θ` denotes the vector consisted with all parameters in the `-th layer. The integration (99)- (102) could be performed similarly for parameters {θn−1,θn−2, · · · ,θj+1}. It is not hard to find that after the integration of the parameters θj+1, the term Tr[σi · Aj ]2 and Tr[σi · Bj ]2 have the opposite coefficients. Besides, the first index of each Pauli tensor product σ(i1,i2,··· ,in) could only be i1 ∈ {1, 3} because of the Lemma C.3. So we could write
Eθ ( ∂fSC ∂θ
(1) j
)2 − 4 ( fSC − 1
2 )2 (103) =Eθ1 · · ·Eθj
 ∑ i1∈{1,3} 3∑ i2=0 · · · 3∑ in=0 aiTr [σi ·Aj ]2 − aiTr [σi ·Bj ]2  , (104)
where
Aj = ∂Vj
∂θ (1) j
CXj−1 · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CXj−1V † j
= (G (1) j ⊗ I ⊗(n−1))A /θ
(1) j
j (W (1)† j ⊗ I ⊗(n−1)),
Bj = VjCXj−1 · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CXj−1V † j
= (W (1) j ⊗ I ⊗(n−1))A /θ
(1) j
j (W (1)† j ⊗ I ⊗(n−1)),
and ±ai are coefficients of the term Tr [σi ·Aj ]2, Tr [σi ·Bj ]2, respectively. We denote G(1)j = ∂W
(1) j
∂θ (1) j
and useA /θ
(1) j
j to denote the rest part ofAj andBj . By Lemma C.3 and Lemma C.4, we have
E θ (1) j
[ Tr [σi ·Aj ]2 − Tr [σi ·Bj ]2 ] = 0,
since for the case i1 ∈ {1, 3}, the term δi10+δi12
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:
Eθ ( fSC − 1
2
)2 ≥ { Tr [ σ(1,0,··· ,0) · ρin ]}2 + { Tr [ σ(3,0,··· ,0) · ρin ]}2 23+nc , (105)
where we denote σ(i1,i2,··· ,in) ≡ σi1 ⊗ σi2 ⊗ · · · ⊗ σin ,
and the expectation is taken for all parameters in θ with uniform distributions in [0, 2π].
Proof. We expand the function fSC in detail,
fSC = 1
2 +
1 2 Tr [ σ(3,0,··· ,0) · VnCXn−1 · · ·CX1V1 · ρin · V †1 CX † 1 · · ·CX † n−1V † n ] = 1
2 +
1 2 Tr [ σ3,0,··· ,0 · ρ(n) ] ,
where ρ(j) = VjCXj−1 · · ·CX1V1ρin · V †1 CX † 1 · · ·CX † j−1V † j , ∀j ∈ [n]. (106)
Now we focus on the expectation of (fSC − 12 ) 2:
Eθ ( fSC − 1
2
)2 = Eθ1Eθ2 · · ·Eθn 1 4 Tr [ σ3,0,··· ,0 · ρ(n) ]2 (107)
≥ Eθ1Eθ2 · · ·Eθn−1 1 8 Tr [ σ1,0,··· ,0 · ρ(n−1) ]2 (108)
≥ Eθ1Eθ2 · · ·Eθn−nc 1 22+nc Tr [ σ1,0,··· ,0 · ρ(n−nc) ]2 (109)
= Eθ1Eθ2 · · ·Eθn−nc−1 1 22+nc Tr [ σ1,0,··· ,0 · ρ(n−nc−1) ]2 (110)
= Eθ1 1 22+nc Tr [ σ1,0,··· ,0 · ρ(1) ]2 (111) = 1
23+nc
( Tr [σ1,0,··· ,0 · ρin]2 + Tr [σ3,0,··· ,0 · ρin]2 ) , (112)
where Eq. (112) is derived from Lemma C.3. We derive Eqs. (108-109) by noticing that following equations hold for n− nc + 1 ≤ j ≤ n and i ∈ {1, 3},
Eθj Tr [ σi,0,··· ,0 · ρ(j) ]2 = Eθj Tr [ σi,0,··· ,0 · VjCXj−1ρ(j−1)CX†j−1V † j ]2 (113)
= 1 2 Tr [ σ1,0,··· ,0 · CXj−1ρ(j−1)CX†j−1 ]2 (114)
+ 1 2 Tr [ σ3,0,··· ,0 · CXj−1ρ(j−1)CX†j−1 ]2 (115)
≥ 1 2
Tr [ σ1,0,··· ,0 · CXj−1ρ(j−1)CX†j−1 ]2 (116)
= 1 2 Tr [ σ1,0,··· ,0 · ρ(j−1) ]2 , (117)
where Eq. (113) is derived based on the definition of ρ(j) in Eq. (106), Eqs. (114-115) are derived based on Lemma C.3, and Eq. (117) is derived based on Lemma C.1.
We derive Eq. (110-111) by noticing that following equations hold for 2 ≤ j ≤ n− nc, Eθj Tr [ σ1,0,··· ,0 · ρ(j) ]2 = Eθj Tr [ σ1,0,··· ,0 · VjCXj−1ρ(j−1)CX†j−1V † j ]2 (118)
= Tr [ σ1,0,··· ,0 · CXj−1ρ(j−1)CX†j−1 ]2 (119)
= Tr [ σ1,0,··· ,0 · ρ(j−1) ]2 , (120)
where Eq. (118) is based on the definition of ρ(j) in Eq. (106), Eq. (119) is based on Lemma C.3, and Eq. (120) is based on Lemma C.1.

Review summaries:
The 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.