Statistical Analysis of Quantum State Learning Process in Quantum Neural Networks
Authors: Hao-Kai Zhang
Chenghong Zhu
Mingrui Jing
Xin Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: quantum neural networks
quantum state learning
quantum computing
quantum machine learning
quantum optimization

Abstract: Quantum neural networks (QNNs) have been a promising framework in pursuing near-term quantum advantage in various fields, where many applications can be viewed as learning a quantum state that encodes useful data. As a quantum analog of probability distribution learning, quantum state learning is theoretically and practically essential in quantum machine learning. In this paper, we develop a no-go theorem for learning an unknown quantum state with QNNs even starting from a high-fidelity initial state. We prove that when the loss value is lower than a critical threshold, the probability of avoiding local minima vanishes exponentially with the qubit count, while only grows polynomially with the circuit depth. The curvature of local minima is concentrated to the quantum Fisher information times a loss-dependent constant, which characterizes the sensibility of the output state with respect to parameters in QNNs. These results hold for any circuit structures, initialization strategies, and work for both fixed ansatzes and adaptive methods. Extensive numerical simulations are performed to validate our theoretical results. Our findings place generic limits on good initial guesses and adaptive methods for improving the learnability and scalability of QNNs, and deepen the understanding of prior information's role in QNNs.

Statistical Analysis of Quantum State Learning Process in Quantum Neural Networks
Hao-kai Zhang Chenghong Zhu Mingrui Jing?.?, Xin Wang2.3*
Institute for Advanced Study, Tsinghua University, Beijing 100084, China Thrust of Artificial Intelligence, Information Hub, Hong Kong University of Science and Technology (Guangzhou), China 3 Institute for Quantum Computing, Baidu Research, Beijing, China
Abstract
Quantum neural networks (QNNs) have been a promising framework in pursuing near-term quantum advantage in various fields, where many applications can be viewed as learning quantum state that encodes useful data. As a quantum analog of probability distribution learning, quantum state learning
theoretically and practically essential in guantum machine learning. In this paper, we develop no-go theorem for learning an unknown quantum state with QNNs even starting from high-fidelity initial state. We prove that when the loss value is lower than a critical threshold, the probability of avoiding local minima vanishes exponentially with the qubit count, while only grows polynomially with the cireuit depth. The curvature of local minima is concentrated to the quantum Fisher information times loss-depents doss-dependent constant, which characterizes the sensibility of the output state with respect to parameters in QNNs. These results hold for any circuit structures, initialization strategies, and work for both fixed ansatzes and adaptive methods. Extensive numerical simulations are performed to validate our theoretical results. Our findings place generic limits on good initial guesses and adaptive methods for improving the lcarnability and scalability of QNNs, and deepen the understanding of prior information's 's role in QNNs.
Introduction
Recent experimental progress towards realizing quantum information processors [1-3] has fostered the thriving development of the emerging field of quantum machine learning (QML) [4-18], pursuing quantum advantages artificial intelligence. Different QML algorithms have been proposed for various topics, e.g., quantum simulations [19-23], chemistry [24-28], quantum data compression [29, 30), generative learning [31, 32] and reinforcement learning [33], where quantum neural networks (QNNs) become a leading framework due to the hardware restriction from noisy intermediate scale quantum (NISQ) [34] devices. As quantum analogs of artificial neural networks, QNNs typically refer to parameterized quantum circuits which are trainable based on quantum measurement results.
However, QNNs face severe scalability barrier which might prevent the realization of potential quantum advantages. A notorious example is the barren plateau phenomenon [35] which shows that the gradient of the loss function vanishes exponentially in the system size with high probability for randomly initialized deep QNNs, giving rise to an exponential training cost. To address this issue, a variety of training strategies has been proposed, such as local loss functions [36], correlated
parameters [37], structured architectures [38 48), good initial guesses [41, 42], initialization heuristics near the identity [43-46], adaptive methods [27] and layerwise training [47], etc. Nevertheless, there
felixxinwang @ hkustt @wkusttgz.edu..rr gz.edu.cn
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a)
Circuit depth
Easy
C' > Ce
C' < Le
(b)
H
10
Hard
10y
Qubit count
Figure 1: Sketches our work characterizing the statistical performance of QNNs on quantum state learning tasks. (a) indicates the existence of critical loss value L. 1 2- below which the local minima start to become severe to trap the training process. (b) depicts the setup of quantum state learning tasks where QNN is used to learn an unknown target state encoding practical data. All target states with a constant distance to the output state (ı6*) form our ensemble T, depicted by the contour the Bloch sphere. (c) shows typical loss curves for different qubit counts of N 6, 10 and circuit depths of D = 1,3 3, 5. The intensity of the background colors represents the magnitude of our theoretical bound on the probability
encountering local minimum, which hence signifies the hardness of optimization. One can find that the theoretical bound appropriately reflects the hardness encountered by the practical loss curves.
lack of scalability analyses for these strategies guarantee their effectiveness. Especially, since the identity initialization and adaptive or layerwise training methods do not require uniformly random initialization of deep QNNs, they are out of the scope of barren plateaus and urgently need comprchensive theoretical analysis to ascertain their performance under general conditions.
In this work, analyze the learnability of QNNs from statistical perspective considering the information of loss values. Specifically, given certain loss value during the training process, we investigate the statistical properties of surrounding training landscapes. Here we mainly focus on quantum state learning tasks [48, 49], which can be seen as a quantum analog of probability distribution learning and play a central role in QML. To summarize, our contributions include:
We prove no-go theorem stating that during the process of learning unknown quantum state with QNNs, the probability avoiding local minima is order O(N22 D2 long the loss value is lower than eritical threshold (cf. Fig. 1). The bound vanishes exponentially in the qubit count while only increases polynomially with the circuit depth D. The curvature of local minima concentrated to the quantum Fisher information times a loss-dependent constant. The proof is mainly based on the technique of "subspace Haar integration" developed in Appendix A. generalized version for the local loss function is provided in Appendix C.
We conduct extensive numerical experiments to verify theoretical findings. We first compare our bound with practical loss curves to show the prediction ability on the statistical behavior of the actual training process. Then sample landscape profiles to visualize the existence of asymptotic local minima. Finally, we compute the gradients and diagonalize the Hessian matrices to directly verify the correctness of our bound.
Our results place general limits on the learnability of QNNs, especially for the training strategies beyond the scope of barren plateaus, including high-fidelity initial guesses, initial- ization heuristics near the identity, and adaptive and layerwise training methods. Moreover, our results provide theoretical basis for the necessity of introducing prior information into QNN designs and hence draw a guideline for future QNN developments.

---

1.1
Related works
The barren plateau phenomenon was first discovered by [35], which proves that the variance of the gradient vanishes exponentially with the system size if the randomly initialized QNN forms a unitary 2-design. Thereafter, [36] finds the dependence of barren plateaus on the circuit depth for loss functions with local observables. [50] proves that training QNNs is in general NP-hard. [51] introduces barren plateaus from uncertainty which precludes learning scramblers. [51, 52] establish connections among the expressibility, generalizability and trainability of QNNs. [53] and [54] show that apart from barren plateaus, QNNs also suffer from local minima in certain cases.
On the other hand, many training strategies have been proposed to address barren plateaus. Here we only list small part relevant to our work. [43-46] suggest that initializing the QNN near the identity could reduce the randomness and hence escape from barren plateaus. [27] and [47] propose adaptive and layerwise training methods which avoid using randomly initialized QNNs in order to avoid barren plateaus, whereas [55] finds counterexamples where the circuit training terminates close to the identity and remains near to the identity for subsequently added layers without effective progress.
2 Quantum computing basics and notations
We use || Ilp to denote the I,p fn-norm for vectors and the Schatten-p norm for matrices. At is the conjugate transpose of matrix A. Lr A represent the trace of A. The 5-th component of the vector is denoted as 0n and the derivative with respect to 8y is simply denoted as 0 2 We employ O as the asymptotic notation of upper bounds.
a0,
In quantum computing, the basic unit of quantum information is a quantum bit or qubit. A single-qubi pure state is described by unit vector in the Hilbert space C2, which is commonly written in Dirac notation (&)) = ax(0) + 3 11). with [0; = (1, 0)", [1) = (0, 1)T a, 3 e C subject to |a|² + |3]
The complex conjugate of (w)) is denoted as (eb) = (t)). The Hilbert space of N qubits is formed by the tensor product "ø" of N single-qubit spaces with dimension d = 2% We denote the inner product of two states (ω) and (4b) as (ølv) and the overlap is defined as Kol(>), General mixed quantum states are represented by the density matrix, which a positive semidefinite matrix p E Cd subject to tr p 1. Quantum gates are unitary matrices, which transform quantum states via the matrix-vector multiplication. Common single-qubit rotation gates include Ry =e- - (0) 001/2
(+) e i07/22 which are in the matrix exponential form of Pauli matrices
x = 0 1
d))
0 (
1 0 0 -1)
Y
z=
(1)
Common two-qubit gates include controlled-X gate CNOT = =T@ X (+ is the direct sum) and controlled-Z gate C7 I Z, which can generate quantum entanglement among qubits.
2.1 Framework of Quantum Neural Networks
Quantum neural networks (QNNs) typically refer to parameterized quantum circuits U(O) where the parameters 0 are trainable based on the feedback from quantum measurement results using classical optimizer. By assigning some loss function (()), QNNs can be used to accomplish various tasks just like artificial neural networks. A general form of QNNs reads U(0) = II W,)) u., where Up (0w) - is parameterized gate such as single-qubit rotations with R. being a Hermitian generator. Wい is a non-nonnannn coo-paammeterized gate such as CNOT and CZ. The product I is by default in the increasing order from the right to the left. M denotes the number of trainable parameters. Note that QNNs with intermediate classical controls [56] can also be included in this general form theoretically. Commonly used templates of QNNs include the hardware efficient ansatz [26], the alternating-layene ansatz (ALT) [57] and the tensor-network-baeee ansatz [36, 58), which are usually composed of repeated layers. The number of repeated layers is called the depth of the QNN, denoted as D. Fig. 2 depicts an example of the ALT circuit. The gradients of loss functions of certain QNNs are evaluated by the parameter-shiff rule [59-61] on real quantum devices. Hence we can train QNNs efficiently with gradient-based optimizers [62].
Here we focus on quantum state learning tasks, the objective of which is to learn a given target state (d) encoding practical data via minimizing the distance between the target state (o) and the output
3

---

x
Ry(O1)
R₂ (6s)
(00)
(=18)))
Ry (0))
R₂ (06)
(f10)
R3 (+14)
(yy(11)
R₂ (019)
(9s)
RS (07)
(011)
R₂ (215)
Ry(01s)
Rs (020)
(04)
Rs (0s)
(112)
R2
Figure 2: The quantum eircuit of the alternating- Ry layer and a Rg layer, followed by D repeated layers, where each layer contains alternating 2-qubit unit blocks of CZ gate, two Ry gates and two R. gates.
ansatz on qubits. The circuit starts with
state from the QNN (0)) ((0)00) The corresponding loss function usually chosen as the fidelity distance
(( Ko)
which can be efficiently calculated on quantum computers using the swap test [63]. An important quantity we used below characterizing the sensitivity of the QNN output state (O)) regarding its parameters 0, the quantum Fisher information (QFI) matrix Fuu [64], which is defined as the Riemannian metric induced from the fidelity distance (ef. Appendix A.4)
( = 2 Re [10 (0.+))))))))))))))))) - (1)
If the QFI is not full-rank, we say (b)) is wer-parameterized [65, 66] meaning that there redundant degrees of freedom in the parameters over the manifold dimension of the state.
Statistical characterization of quantum state learning in QNNs
In this section, develop no-go theorem characterizing the limitation of quantum neural networks in state learning tasks from a statistical perspective. In short, we prove that the probability of avoiding local minima during the process of learning unknown quantum state with QNN is of order O(2-N N22 M2/²2,, where N is the number qubits, M is the number of trainable parameters and c represents the typical precision of measurements. The detailed upper bound also depends the overlap between the value of the loss function and the QFI of the QNN. Our bounds significantly improve existing results of the trainability analysis of QNNs. which mainly foeus on the randomness from the initialization and neglect the information of the loss function value. We will first introduce ensemble setting in Section 3.1, then present main theorem on local minima in Section 3.2 and finally show some results beyond local minima in Section 3.4.
3.1 Ensemble of the unknown target state
We first introduce the probability measure used in this work. The randomness studied by most of the previous work on the trainability analyzes QNNs originates from the random initialization of trainable parameters [35], which usually depends the circuit depth, specifie choices of the QNN architecture and initialization strategies [44]. Mcanwhile, the randomness can also come from the lack of prior information, such learning unknown quantum state unknown scrambler like a black hole [67]. We focus on the latter in the present work.
The usage of adaptive methods is usually not covered by common trainability analyses, however, the training process often tends to stagnate. With the aim of investigating the trainability at a specific loss function value, the ensemble is constructed by uniform measure of overall pure states that have the same overlap with the current output state of the QNN. Specifically, suppose is the current value of the trainable parameters. The overlap, or fidelity, between the output state jbb*) (v²))))
and the target state (o) equals to | = Thus, the target state can decomposed as
(Ø) = pl p/u* / pz ")
(4)
where ( represents the unknown component the target state (d) orthogonal to the learnt component (b*). ). If no more prior information is known about the target state (ø) except for the overlap

---

in the spirit of Bayesian statistics, 1/5 !) is supposed to be a random state uniformly distributed in the orthogonal complement of [ denoted as H-- Such a Haar-random state can induce an ensemble of the unknown target state via Eq. (4), which we denote as = {lø) (x-) is Haar-random 7 Graphically, T can be understood as contour the Bloch sphere of an N-qubit system with constant distance to (el") as shown in Fig. 1(b). We remark that 0 can be interpreted as either an
initial guess or intermediate value during the training process so that our following results can be applied to the entire process of learning a quantum state. See Appendix A. for more details on the ensemble setting.
3.2 Exponentially likely local minima
We now investigate the statistical properties of the gradient C and the Hessian matrix He of the loss function C(0") at the parameter point 0 = 0" regarding the ensemble T, and hence derive an upper bound of the probability that 0* not local minimum. For simplicity of notation, we represent the value of a certain function at f = 0 by appending the superscript "*", e.g., Vile=o- as V and Hc -ele- as H2- We define that l is local minimum up fixed precision c c (2) and only if each of the gradient components is not larger than 6 and the minimal eigenvalue of the
Hessian matrix is not smaller than -22, i.e.,
M
LocalMin(O OO" .e) = n {0,,0 n (H2 > -e21}.
(5)
If é1 and E2 both take zero, Eq. (5) is reduced back to the common exact definition of the local minimum. However, noises and uncertainties from measurements on real quantum devices give rise to a non-zero e, where the estimation cost scales as (1/c²) for some power a [68]. Specially, ()(())) approaches the true target state (o) such that L - O, say 0 is global minimum. That is to say, here "local minima" are claimed with respect to the entire Hilbert space instead of training landscapes created by different ansatzes. The expectation and variance of the first and second-order derivatives of the loss function are calculated and summarized in Lemma 1, with the detailed proof in Appendix B utilizing the technique we dubbed "subspace Haar integration" in Appendix A.I.
Lemma 1 The expectation and variance of the gradient V L and Hessian matrix He of the fidelity loss function ((0)= -1 (()) 0 0* with respect to the target state ensemble T satisfy
Er [ [*] = 0, Varr = (p(,d)F pm
(6)
dp²
Er [H2] d 1 F", 1a & f2 d0),d 11
where F. denote the OFI matrix in Eq. (3) and S2 is the generator of the gate (p(()). fi and fa are functions of the overlap p and the Hilbert space dimension d, i.e.
p²(1 p²) f( f(bad)== d-1
felp.)) 32(1 - p²) 12 + d
2(1 (p)p
(8)
d-1
The exponentially vanishing variances in Lemma imply that the gradient and Hessian matrix concentrate to their expectations exponentially in the number of qubits N due to d = 2 for a N -uqubit system. Thus the gradient concentrates to zero and the Hessian matrix concentrates to the QFI F times non-vanishing coefficient proportional to (1² 1/d). Since the QFI is always positive semidefinite, the expectation of the Hessian matrix is either positive semidefinite L =-=1-pp p² 1 1/d, or negative semidefinite if L > 1 1/d, illustrated in Fig. ((a). The critical point C. = 1 1 1/d coincides with the average fidelity distance of two Haar maar- pure states, which means that as long as (Ø*)) has higher fidelity than the average level of all states, the expectation of the Hessian matrix would be positive semidefinite.
Using Lemma 1, we establish an exponentially small upper bound on the probability that 0' is not a local minimum in the following Theorem 2, where the generator norm vector is defined as = (I|9, |l,,, [S ||
5

---

Theorem 2 If the fidelity loss function satisfies _()") < <1- - <1-1/d, the probability that 6" is not local minimum of C up to a fixed precision = 62) with respect to the target state ensemble T is upper bounded by
Prr Prrl-LocaMMin(0 ,e]] S (P, d) d|
f2(p. d) 1101
$f
[ ex + +22
where ex denotes the minimal eigenvalue of the QFI matrix at 0 = 0" S and f2 are defined in Eq. (8) which vanish at least of order 1 1/d.
A sketch version of the proof is as follows, with the details in Appendix B. By definition in Eq. (5), the left-hand side of Eq. (9) can be upper bounded by the sum of two terms: the probability that one gradient component is larger than e1, and the probability that the Hessian matrix is not positive definite up to 62. The first term can be bounded by Lemma and Chebyshev's inequality, i.e.,
M
M Varr(o,f(]
fi(p,d) &
Prr
U
ir
(10)
111 G
where the QFI diagonal element is bounded as Fu I 21 12x by definition and thus tr F < 2|
After assuming p² > 1/d, the second term can be upper bounded by perturbing [r[H2] to obtain a sufficient condition of positive definiteness (see Appendix A.2), and then utilizing Lemma with the generalized Chebyshev's 's inequality for matrices (see Appendix A.3).
M
Varr O20 S f2(p. d) [Wll
Prt [H2
* =22
S
Σ 1MK=1
(11)
dp d-1
ex + +
dgg-te" + +
2'
Combining the bounds regarding the gradient and hessian matrix, one arrives at Eq. (9).
Theorem 2 directly points out that if the loss function takes value lower than the critical threshold L. = - -1/d, then the surrounding landscape would be a local minimum for almost all of the target states, the proportion of which is exponentially close to 1 as the qubit count N = logg d grows. Note that || = Ene ||s2,u11e scales linearly with the number of parameters M and at most polynomially with the qubit count N. Because practically the operator norm || Ic constant such as the generators of Pauli rotations ||X]|>> = || system size such as the layer with globally correlated parameters [56] and the global evolution in analog quantum computing [69]. Here focus the former and conclude that the upper bound in Theorem 2 is of order ((2 N ) implying the exponential training cost. The conclusion also holds for noisy quantum states (see Appendix B). A similar result for the so-called local loss function, like the energy expectation used in variational quantum eigensolvers, is provided in Appendix C.
= || 1, or grows pol polynomially with the
In principle, if one could explore the whole Hilbert space with exponentially many parameters, 0" was a saddle point most instead of a local minimum since there must exist a unitary connecting the learnt state [x**) and the target state (o). This also consistent with our bound by taking M (222/22 to cancel the 2 factor such that the bound is no more exponentially small. However, the number of parameters one can control always scales polynomially with the qubit count due to the memory constraint. This fact indicates that if the QNN is not designed specially for the target state using some prior knowledge so that the "correct" direction towards the target state is contained in the accessible tangent space, the QNN will have the same complexity as the normal quantum state tomography.
Dependence on the loss value L. The dependence of the bound in Theorem 2 on the overlap p vI- L shows that, as the loss function value becomes lower, the local minima becomes denser so that the training proceeds harder. This agrees with the experience that the loss curves usually decay fast at the beginning of training process and slow down till the convergence. If e * 0, the second term in Eq. (9) becomes larger as p² + 1/d, suggesting that the local minima away from the critical point Le is more severe than that near Le. Moreover, if c2 O. the bound diverges the QFI minimal eigenvalue e* vanishes, which reflects the fact that over wer-parameterized QNNs have many equivalent local minima connected by the redundant degrees of freedom of parameters.
By contrast, L* > Ler the results could be established similarly by slightly modifying the proof yet with respect to local maxima, depicted in Fig. 1(a). However, the critical point L. 1 1- 2 2-N

---

moves to 1 exponentially fast as N increases, i.e., the range of L without severe local minima shrink exponentially. Hence for large-scale systems, even with a polynomially small fidelity, one would encounter a local minimum almost definitely if no more prior knowledge can be used.
3.3 Implication on the learnability of QNNs
In practical cases, if the QNN is composed of D repeated layers with Z trainable parameters for each layer and each qubit, then the total number of trainable parameters becomes M = N and hence the probability of avoiding local minima is of order (N D2 /2))), which increases quadratically as the QNN becomes deeper. This seems contrary to the conclusion from barren plateaus [35] where deep QNNs lead to poor trainability. But in fact, they are complementary to each other. The reason is that the ensemble here originates from the unknown target state instead of the random initialization. Similar to classical neural networks, a deeper QNN has stronger expressibility, which creates a larger accessible manifold to approach the unknown state and may turn local minimum into saddle point with the increased dimensions. But on the other hand, a deeper QNN with randomly initialized parameters leads to barren plateaus [36]. In short, the local minima here arise due to the limited expressibility together with a non-vanishing fidelity while barren plateaus stem from the strong expressibility together with the random initialization.
To solve this dilemma, our results suggest that a well-designed QNN structure taking advantage of prior knowledge of the target state is vitally necessary. Otherwise, a good initial guess (i.e., an initial state with high fidelity) solely hard to play its role. An example of prior knowledge from quantum many-body physics is the tensor network states [70] satisfying the entanglement area law, which lives only in a polynomially large space but generally can not be solved in two and higher spatial dimensions by classical computers. Other examples include the UCCSD ansatz [71] in quantum chemistry and the QAOA ansatz [72] in combinatorial optimization, which all attempt to utilize the prior knowledge of the target states.
Finally, we remark that our results also place general theoretical limits for adaptive [27] or layer- wise training methods [47]. Relevant phenomena are observed previously in special examples [55]. Adaptive methods append new training layers incrementally during the optimization instead of placing a randomly initialized determinate ansatz at the beginning, which is hence beyond the scope of barren plateaus [35]. Nevertheless, our results imply that for moderately large systems with L Lee, every time a new training layer is appended, the learnt state (n)") would be a local minimum of the newly created landscape so that the training process starting near (4*)) would go back to the original state (5b) without any effective progress more than applying an identity. Note that in adaptive methods, one usually initializes the new appended layer near the identity to preserve the historical learnt outcomes. Similar phenomena are also expected to occur in the initialization strategies where the circuit begins near the identity [43, 44, 46]. We emphasize that our results do not imply the ineffectiveness of all adaptive methods. Instead, they only suggest that simplistic frute-force adaptive methods provide no significant benefit in terms of enhancing lcarnability on average.
3.4 Concentration of training landscapes
Theorem 2 analyses the statistical properties of the vicinity of a certain point 0", i.e., the probability distributions of the gradient and Hessian matrix of 0*. To characterize the training landscape beyond the vicinity, a pointwise result is established in Proposition 3 with the proof in Appendix B.
The expectation and variance of the fidelity loss fanction C with respect to the target state ensemble T can be exactly calculated as
Proposition 3
+ dp 1
Er [C(0)] = 1 p2
d d-1 (()),
(12)
1 12 (())
122² (d (d-29 2)(1 -1²) d(d-1)
Varr [C(0)]
4p²
g(0)
d
where g(0) = 1 (=
Since the factor g0) takes its global minimum at 0" by definition, the exponentially small variance in Proposition 3 implies that the entire landscape concentrates exponentially in the qubit count to
7

---

Quhiisd
Quliibed Qubitt=111
0.7
# Quiiis10
100
0.5
0.7
0.7
000
0.3
Quliilsm4
(4)
# Quhits-10
(6)
(
00- 12
|10 0'11a
|0
Figure 3: Samples of training landscapes along randomly chosen directions as a function of the distance 0 0*1 for random target states from T with the sample size 200, the qubit count N = 4 and N 10 and the overlap (a) p = 0.2 and (b) p = 0.8, respectively. The setup in (c) is the same as in (b) but fixes the target state and only samples the directions. A clear convex shape is present in the samples from N = 10 but absent in the samples from N This phenomenon intuitively shows that the training landscapes from the ensemble T are concentrated to a local minimum around 0 as the qubit count increases.
the expectation Er [C(0)] with pointwise convergence (not necessarily uniform convergence), which takes its global minimum at 0 with respect to the training landscape as long as p² > 1/d. For QNNs satisfying the parameter-shift rule, the factor g(0) along the Cartesian axis corresponding to 8, passing through 6 will take the form of a trigonometric function 2. sin sin"(O,,.
8%)). which is elaborated in Appendix B. Other points apart from 0" is allowed to have a non-vanishing gradient expectation in setup, which leads to prominent local minima instead of plateaus [35].
Numerical experiments
Previous sections theoretically characterize the limitation of QNNs in state learning tasks considering the information of the loss value L In this section, verify these results by conducting numerical experiments on the platform Paddle Quantum [73] and Tensorcircuit [74] from the following three perspectives. The codes for numerical experiments can be found in [75].
Comparison with loss curves. Firstly, we show the prediction ability of Theorem by direct comparison with experimental loss curves in Fig. 1(c). We create 9 ALT circuits for qubit counts of 2, 6, 10 and circuit depth of 1,3,5 with randomly initialized parameters, denoted as 0". For each circuit, we sample 10 target states from the ensemble T with p 0.2 and then generate 10 corresponding loss curves using the Adam optimizer with a learning rate 0.01. We exploit the background color intensity to represent the corresponding bounds from Theorem 2 by assigning e* = 0.1 and é = E2 = 0.05. One can find that the loss curves decay fast at the beginning and then slow down till convergence, in accordance with the conclusion that the probability of encountering local minima is larger near the bottom. The convergent loss value becomes higher as the qubit count grows and can be partially reduced by increasing the circuit depth, which is also consistent with Theorem 2.
Landscape profile sampling. We visualize the existence of asymptotic local minima by sampling training landscape profiles in Fig. 3. Similar to the setup above, we create an ALT circuit with randomly initialized parameters 0", sample 200 target states from the ensemble T and compute the loss values near 0*, Figs. 3(a) and (b) are obtained by randomly choosing a direction for each landscape sample, while Fig. 3(c) is obtained by randomly sampling 200 directions for one fixed landscape sample. There is no indication of local minimum in the case of few qubits and small fidelity shown by the blue curves in Fig. 3(a). However, as the qubit number grows, the landscape profiles concentrate into a clear convex shape centered at 0" for both p = 0.2 and p = 0.8, where the curvature for p 0.8 is larger due to the factor (p² 1/d) in Eq. (7). Fig. 3(c) further demonstrates that beyond the convexity along a specific direction, 0* is a highly probable local minimum in the case of large qubit counts.
Probability evaluation. Finally, we compute the gradients and diagonalize the Hessian matrices to directly verify the exponentially likely local minima proposed by Theorem 2 in Fig. 4. Similar to
8

---

Pesstoe Pusseter 2
J Spihe
8 Q
Prsssttres 3
8 Quitest
Pry PrylLovabten d)
Pre Baaoe Ma +
Prssetev
Pry Manaaaaaaai
# Quicss
22 Quiats
Figure 4: Numerical evaluation for the probability that 0 is a local minimum up to fixed precision c, i... Prr [LocalMin .c)] for different qubit count, the number of trainable parameters and the overlap p. with the error bar representing the statistical uncertainty in experiments. (a) shows that the probability converges to rapidly with the increasing qubit count. (b) shows that the probability is reduced by increasing the number of parameters, implying the local minimum phenomenon is mitigated. (c) illustrates that the probability of encountering local minima always converges to 1 for any fixed overlap p. p 0.8 for both (a) and (b) and the number of parameters in (c) is 6.
the setup above, we create ALT circuits for qubit count from N sample 200 target states from T for each circuit. After specifying certain subset of parameters to be differentiated, we estimate the probability that 0 local minimum by the proportion of samples satisfying the condition LocalMin(O" <), where we assign
with depth D 5 and
f2 0.05. One can find that the probability of encountering local minima saturates to 1 very fast as the qubit count increases for arbitrary given values of p, and at the same time, it can be reduced by increasing the number of trainable parameters, which is consistent with the theoretical findings Theorem 2.
5 Conclusion and outlook
In this paper, prove that during the process of learning unknown quantum state with QNNs, the probability of avoiding local minima is of order ONN D2/22) which is exponentially small in the qubit count N while increases polynomially with the circuit depth D. The curvature of local constant which is positive be regarded a quantum version of the no-free-lunch
minima is concentrated to the QFI matrix times a fidelit--dependee n² 1/d. In practice, our results (NFL) theorem suggesting that no single QNN is universally the best-performing model for learning all target quantum states. We remark that compared previous works, findings first establish quantitative limits on good initial guesses and adaptive training methods for improving the learnability and scalability of QNNs.
In the technical part of our work, our ensemble arises from the unknown target state. Alternatively, the QNN is sufficiently deep form subspace 2-design (ef. Appendix A.1) replacing the ensemble we used here, a different interpretation could be established with the same calculations: there are exponentially large proportion of local minima with a constant loss function value. However, it remains an open question what the scaling of the QNN depth is constitute such subspace 2-design, given that a local random quantum eircuit of polynomially depth forms an approximate unitary L-design [76]. We would like to note that the case where the output and target states are mixed states is not covered due the quantum nature of the hard-to-defining orthogonal ensemble of mixed states, which may be left for future research.
cross sections of the training landscape
Future progress will necessitate more structured QNN architectures and optimization tools, where insights from the field of deep learning may prove beneficial. Our findings suggest that the unique characteristics and prior information of quantum systems must be thoughtfully encoded in the QNN in order to learn the state successfully, such as the low entanglement structure in the ground state [70], the local interactions in Hamiltonians [71, 77] and the adiabatic evolution from product states [72].
Acknowledgement. We would like to thank the helpful comments from the anonymous reviewers. Part of this work was done when H. Z., C. Z., M. J., and X. W. were at Baidu Research.

---

References
[1] Thaddeus Ladd, Fedor Jelezko, Raymond Laflamme, Yasunobu Nakamura, Christopher Monroe, and Jeremy Lloyd O'Brien. Quantum computers. nature, 464(7285):45-53 2010.
[2] Christopher Monroe and Jungsang Kim. Scaling the ion trap quantum processor. Science, 33966124):111441116,, 2013.
[3] Michel H Devoret and Robert Schoelkopf. Superconducting circuits for quantum information: 11116112):::66111111 an outlook. Science, 339(6124): 169-1669911111 1174, 2013.
[4] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(767 (1077671):199) 1):19)999222 sep 2017.
[5] Xuchen You, Shouvanik Chakrabarti, Boyang Chen, and Xiaodi Wu. Analyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernels. arXiv preprint arXiv:2303.14844 2023.
[6] Yehui Tang and Junchi Yan. GraphQNTK: Quantum Neural Tangent Kernel for Graph Data. Advances in Neural Information Processing Systems, 35:6104-611 2022.
[7] Junyu Liu, Francesco Tacchino, Jennifer R Glick, Liang Jiang, and Antonio Mezzacapo. Repre- sentation learning via quantum neural tangent kernels. PRX Quantum, 333:30032, 2022.
[8] Matthias C Caro, Hsin- Yuan Huang, Marco Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J Coles. Generalization in quantum machine learning from few training data. Nature communications, 13(1);4919, 2022.
[9] M Cerezo, Guillaume Verdon, Hsin- Yuan Huang, Lukasz Cincio, and Patrick Coles. Chal- lenges and opportunities in quantum machine learning. Nature Computational Science, 2(9):567- 576, 2022.
[10] Hsin- Yuan Huang, Richard Kueng, Giacomo Torlai, Victor V Albert, and John Preskill. Provably efficient machine learning for quantum many-body problems. Science, 377(6613)xeabk333) 2022.
[11] Yang Qian, Xinbiao Wang, Yuxuan Du, Xingyao Wu, and Dacheng Tao. The dilemma of quantum neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[12] Zhan Yu, Hongshun Yao, Mujin Li, and Xin Wang. Power and limitations of single-qubit native quantum neural networks. In 36th Conference on Neural Information Processing Systems (NeurIPS 2022), 2022.
[13] Jinkai Tian, Xiaoyu Sun, Yuxuan Du, Shanshan Zhao, Qing Liu, Kaining Zhang, Wei Yi. Wan- rong Huang, Chaoyue Wang, and Xingyao Wu. Recent advances for quantum neural networks in generative learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
[14] Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear quantum algorithms for training linear and hernel-based classifiers. In International Conference on Machine Learning. pages 3815-3824. PMLR, 2019.
[15] Guangxi Li, Ruilin Ye, Xuanqiang Zhao, and Xin Wang. Concentration of Data Encoding in Parameterized Quantum Circuits. In 36th Conference on Neural Information Processing Systems (NeurIPS 2022). 2022.
[16] Sofiene Jerbi, Lukas Fiderer, Hendrik Poulsen Nautrup, Jonas M. Kübler, Hans J. Briegel, and Vedran Dunjko. Quantum machine learning beyond kernel methods. Nature Communications, 14(1):517, jan 2023.
[17] Weikang Li and Dong-Ling Deng. Recent advances for quantum classifiers. Science China Physics, Mechanics & Astronomy, 65(2):220301, feb 2022.
[18] Hsin-Yuse Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R. McClean. Quantum advantage in learning from experiments. Science, 376(6598) 18811186,11111111111111111181611 jun 2022.
10

---

[19] Tulia M Georgescu, Sahel Ashhab, and Franco Nori. Quantum simulation. Reviews of Modern Physics, 86(1):153, 2014.
[20] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li, and Simon C Benjamin. Theory of variational quantum simulation. Quantum, 3:191, 2019.
[21] Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon C Benjamin, and Xiao Yuan. Varia- tional based quantum simulation of imaginary time evolution. npj Quantum Information, 5(1):75, 2019.
[22] Youle Wang, Guangxi Li, and Xin Wang. Variational Quantum Gibbs State Preparation with Truncated Taylor Series. Physical Review Applied, 16(5):054035, nov 2021.
[23] Suguru Endo, Jinzhao Sun, Ying Li, Simon C Benjamin, and Xiao Yuan. Variational quantum simulation of general processes. Physical Review Letters, 125(1):01001,, 2020.
[24] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Sapuru-Guzik, and Jeremy L. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communicationss, 5(1 3(1134 sep 2014.
[25] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C Benjamin, and Xiao Yuan. Quantum computational chemistry. Reviews of Modern Physics, 92(1):01500) 5003,, 2020.
[26] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549(7671)::422 24:222246, sep 2017.
[27] Harper R. Grimsley, Sophia E. Economou, Edwin Barnes, and Nicholas J. Mayhall. An adaptive variational algorithm for exact molecular simulations on quantum computer. Nature Communications, 10(1), jul 2019.
[28] Ho Lun Tang, VO Shkolnikov, George S Barron, Harper R Grimsley, Nicholas J Mayhall, Edwin Barnes, and Sophia E Economou. qubit-adapt-vge: An adaptive algorithm for constructing hardware-efficcent ansätze quantum processor. PRX Quantum, 2(2):020310, 2021.
[29] Xin Wang. Zhixin Song, and Youle Wang. Variational Quantum Singular Value Decomposition. Quantum, 5:483, jun 2021.
[30] M. Cerezo, Kunal Sharma, Andrew Arrasmith, and Patrick Coles. Variational quantum state eigensolver. upj Quantum Information, 8(1):113, sep 2022.
[31] Seth Lloyd and Christian Weedbrook. Quantum generative adversarial learning. Physical review letters, 121(4):40502, 2018.
[32] Chenfeng Cao and Xin Wang. Noisc-assisted quantum autoencoder. Physical Review Applied, 15(5), may 2021.
[33] Samuel Yen-Chi Chen, Chao-Han Huck Yang, Jun Qi, Pin-Yu Chen, Xiaoli Ma, and Hsi- Sheng Goan. Variational quantum cireuits for deep reinforcement learning. IEEE Access, 8:141007-141024, 2020.
[34] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018.
[35] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9()):177, mar 2018.
[36] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 12(1):1791, dec 2021.
[37] Tyler Volkoff and Patrick Coles. Large gradients via correlation in random parameterized quantum circuits. Quantum Science and Technology, 6(2):025008, jan 2021.
11

---

[38] Zidu Liu, Wi-Wei Yu, L.-M. Duan, and Dong-Ling Deng. Presence and absence of barren plateaus in tensor-network based machine learning. Phys. Rev. Lett., 129:270501, Dec 2022.
[39] Xinbiao Wang, Junyu Liu, Tongliang Liu, Yong Luo, Yuxuan Du, and Dacheng Tao. Symmetric pruning in quantum neural networks. In The Eleventh International Conference on Learning Representations, 2023.
[40] Xia Liu, Geng Liu, Jiaxin Huang, Hao-Kai Zhang, and Xin Wang. Mitigating barren plateaus of variational quantum eigensolvers. arXiv preprint 1335532205.33539, may 2022.
[41] Daniel J. Egger, Jakub Mareček, and Stefan Woerner. Warm-starting quantum optimization. Quantum, 5:479, June 2021.
[42] Nishant Jain, Brian Coyle, Elham Kashefi, and Niraj Kumar. Graph neural network initialisation of quantum approximate optimisation. Quantum, 6:861, November 2022.
[43] Edward Grant, Leonard Wossnig, Mateusz Ostaszewski, and Marcello Benedetti. An initializa- tion strategy for addressing barren plateaus in parametrized quantum circuits. Quantum, 3, mar 2019.
[44] Kaining Zhang, Liu Liu, Min-Hsiu Hsieh, and Dacheng Tao. Escaping from the barren plateau via gaussian initializations in deep variational quantum circuits, 2022.
[45] Ankit Kulshrestha and Ilya Safro. Beinit: Avoiding barren platcaus in variational quantum algorithms, 2022.
[46] Yabo Wang. Bo Qi, Chris Ferrie, and Daoyi Dong. Trainability enhancement of parameterized quantum circuits via reduced-domail parameter initialization, 2023.
[47] Andrea Skolik, Jarrod R. McClean, Masoud Mohseni, Patrick van der Smagt, and Martin Leib. Layerwise learning for quantum neural networks. Quantum Machine Intelligence, 3(1), jan 2021.
[48] Juan Miguel Arrazola, Thomas R Bromley, Josh Izaac, Casey R Myers, Kamil Brá dler, and Nathan Killoran. Machine learning method for state preparation and gate synthesis on photonic quantum computers. Quantum Science and Technology, 4(2):024004, jan 2019.
[49] Viacheslav V. Kuzmin and Pictro Silvi. Variational quantum state preparation via quantum data buses. Quantum, 4:290, jul 2020.
[50] Lennart Bittel and Martin Kliesch. Training Variational Quantum Algorithms Is NP-Hard. Physical Review Letters, 127(12): 120502. sep 2021.
[51] Zoë Holmes, Andrew Arrasmith, Bin Yan, Patrick J. Coles, Andreas Albrecht, and Andrew T. Somborger. Barren plateaus preclude learning scramblers. Physical Review Letters, 126(19), sep 2020.
[52] Jun Qi, Chao-Han Huck Yang. Pin- Yu Chen, and Min-Hsiu Hsieh. Theoretical error performance analysis for variational quantum circuit based functional regression. npj Quantum Information, 9(1):4 2023.
International Conference on Machine Learning, pages 12144-12155. PMLR, 2021. [53] Xuchen You and Xiaodi Wu. Exponentially many local minima in quantum neural networks. In
[54] Eric R Anschuetz. Critical points in quantum generative models. arXiv preprint
0rX.v:200.006957. 2021.
[55] Ernesto Campos, Aly Nasrallah, and Jacob Biamonte. Abrupt transitions in variational quantum circuit training. Physical Review A, 2020.
[56] Iris Cong, Soonwon Choi, and Mikhail D. Lukin. Quantum convolutional neural networks. Nature Physics, (5(12):1273-111 aug 2019.
[57] Kouhei Nakaji and Naoki Yamamoto. Expressibility of the alternating layered ansatz for quantum computation. Quantum, 5:434, apr 2021.
12

---

[58] Shi-Ju Ran. Encoding of matrix product states into quantum circuits of one-and two- gates. Physical Review 101(3):03310, 2020.
[59] Jun Li, Xiaodong Yang. Xinhua Peng, and Chang-Pu Sun. Hybrid quantum-classical approach to quantum optimal control. Physical Review Letters, 118(15), apr 2017.
[60] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. Evaluating analytic gradients on quantum hardware. Physical Review A, 99(3), mar 2019.
[61] Andrea Mari, Thomas R. Bromley, and Nathan Killoran. Estimating the gradient and higher- order derivatives on quantum hardware. Physical Review A, 103(1), jan 2021.
[62] Iman Ahmadianfar, Omid Bozorg-Haddad, Haddad, and Xuefeng Chu. Gradient-based optimizer: A new metaheuristic optimization algorithm. Information Sciences, 540: 2020.
[63] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Phys. Rev. Lett., 87:167902, Sep 2001.
[64] Johannes Jakob Meyer. Fisher information in noisy intermediate-scale quantum applications. Quantum, 5:539, sep 2021.
[65] Martin Larocca, Nathan Ju, Diego Gareía-Martnn, Patrick J. Coles, and M. Cerezo. Theory of overparametrization in quantum neural networks, 2021.
[66] Diego Marcfa, Martin Larocca, and M. Cerezo. Effects of noise on the overparametriza- tion of quantum neural networks, 2023.
[67] Zoë Holmes, Kunal Sharma, M. Cerezo, and Patrick J. Coles. Connecting ansatz expressibility to gradient magnitudes and barren plateaus. PRX Quantum, 3(1):1-20, jan 2021.
[68] Emanuel Knill, Gerardo Ortiz, and Rolando D. Somma. Optimal quantum measurements of expectation values of observables. Phys. Rev. A, 75:012328, Jan 2007.
[69] Arnab Das and Bikas K Chakrabarti. Colloquium: Quantum annealing and analog quantum computation. Reviews of Modern Physics, 80(3);1061, 2008.
[70] Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 149-117-158, 2014.
[71] Jonathan Romero, Ryan Babbush, Jarrod McClean, Cornelius Hempel, Peter Love, and Alán Aspuru-Guzik. Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz. Quantum Science and Technology, 4(1):014008,, 2018
[72] Gian Giacomo Guerreschi and Anne Matsuura. Qaoa for max-cut requires hundreds of qubits for quantum speed-up. Scientific reports, 2019
[73] Paddle Quantum. http://giinhhccmmmpdddlppdddddgn
[74] Shi-Xin Zhang, Jonathan Allcock, Zhou-Quan Wan, Shuo Liu, Jiace Sun, Hao Yu, Xing-Han Yang. Jiezhong Qiu, Zhaofeng Ye, Yu-Qin Chen, Chee-Kong Lee, Yi-Cong Zheng, Shao-Kai Jian, Hong Yao, Chang- Yu Hsieh, and Shengyu Zhang. TensorCircuit: a quantum software framework for the NISQ era. Quantum, 7:912, feb 2023.
[75] Numerical Experiments of this work. https://tthhb.ccom/ceengggggg/// harprggghhiigiiimmmaaninggggn state.
[76] Jonas Haferkamp. Random quantum circuits are approximate unitary I-designs in depth o(nt5+o(1))) Quantum, 6:795, 2022.
[77] Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Back Kim, and Henry Yuen. Exploring entanglement and optimization within the hamiltonian variational ansatz. PRX Quantum, 122), dec 2020.
[78] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application fidelity estimation. Physical Review A, 80(1 23043444 jul 2009.
13

---

[79] Jay M. Gambetta, A. D. Córcoles, S. T. Merkel, B. R. Johnson, John A. Smolin, Jerry M. Chow, Colm A. Ryan, Chad Rigetti, Poletto. Thomas A. Ohki, Mark B. Ketchen, and M. Steffen. Characterization of Addressability by Simultaneous Randomized Benchmarking. Physical Review Letters, 109(24):240504, dee 2012.
Appendix for "Statistical Analysis of Quantum State Learning Process in Quantum Neural Networks"
A Preliminaries
A.1 Subspace Haar integration
The central technique used in work is the subspace Haar integration, i.e., series of formulas on calculating Haar integrals over a certain subspace of the given Hilbert space. In this section, we give brief introduction to the common Haar integrals and then the basic formulas on subspace Haar integrals used in our work together with the proofs.
Haar integrals refer to the matrix integrals over the d-degree unitary group U(d) with the Haar measure dju, which is the unique uniform measure on (dd) such that
Jena dp(V))(() - Ju dp(V))(VV)) = - dn(V))(UV),
(S1)
for any integrand f and group element U (d)... If an ensemble V of unitaries V matches the Haar measure up to the (-degree moment, i.e.,
f (V)
Evev(pr,(V))
(S2)
Juca)
then V is called unitary I-design [78]. Pt, denotes arbitrary polynomial of degree most t in the entries of V and most in those of Vt. Evevf-l denotes the expectation over the ensemble V. The Haar integrals over polynomials can be analytically solved and expressed into closed forms according to the following lemma.
Lemma S1 Let (dd) GL(C")) ) be arbitrary representation of unitary group U(d). Suppose (i)
that the direct sum decomposition op to irreducible representations is & = + denotes the t copy of the irreducible representation g(5), A set of orthonormal basis in the representation space of (()) is denoted as ((o.,k.)). ). For an arbitrary linear operator A : Edd + Cd' the following equality holds [79]
j.k Qk where &F
E tr(e)) J.Kk tr( (
[ {(U)Ap(U)(u((U)
Q.K.M.
(S3)
where Q,k.KK' E, 3 al the transfer operator from the representation subspace of σ6)) to that of o The denominator the right hand side of (S3) be simplified as tr(Q), jM Qak,k) tr((,,w) dy. where P3, E, 10,,a Q2,kk is the projector to the representation subspace of & and dj is the dimension of the representation space of ((1).
By choosing different representations of the unitary group U(d), some commonly used equalities can be derived, such
S.na vAvtdu(V)
tr(A), 1, d dir dirAurC-ute C((AuC))((AC) d(o2-1)
(S4)
I Jui vt VV (r(AC)
Ir Br
B
1
(S5)
d
d
14

---

where I is the identity operator on the d-dimensional Hilbert space H. A, B and C' are arbitrary linear operators H. According to the linearity of the integrals, the following equalities can be further derived
u(d tr(V (TV)) = tr(AB)
(S6)
d JNCO Ir(V) AV BV) Atr (((C))
de
(S7)
tr(AC) tr tr D + tr Atr AtrCrt(BD)
d)
where A, B, C and D are arbitrary linear operators on H.
The subspace Haar integration can be regarded as a simple generalization of the formulas above. Suppose that Hsub is subspace with dimension dsub of the Hilbert space H. is an ensemble whose elements are unitaries in H. with a block-diagonal structure U P PUP. P. P is the projector the projector from H to the orthogonal complement of Hsub- Integrals with respect to such an ensemble are dubbed as "subspace Haar integrals", which can reduced back the common Haar integrals by taking Haub H. The corresponding formulas of subspace Haar integrals are developed in the following lemmas, where Eveul: Eu[-] denotes the expectation with respect to the ensemble U.
from H Haub and PU P is a random unitary with the Haar measure on Hsub. P
Lemma S2 The expectation of a single element U E U with respect to the ensemble U equals to the projector to the orthogonal complement, i.e..
Eu U - P.
(S8)
Proof The fact that Haar integrals of inhomogenous polynomials pt, with & o l' over the whole space equals zero leads the vanishment the block in Haub, i.e.
Eu
U Eu [P + PUP] = P,
(S9)
which is just the projector to the orthogonal complement Haub-
Similarly, we know all the subspace Haar integrals involving only U or Ut will leave projector after integration. For example, it holds that E3 [U] PAP for an arbitrary linear operator A.
Lemma S3 For an arbitrary linear operator A on H. the expectation of U AU with respect to the random variable U Uis
tr(PA) dsub
Eu U AU]AU]
P P)A(I
(S10)
Proof Eq. (S10) be special case of Lemma S1 since U can be seen the complete reducible representation (d(duus) composed of (d - dsub) trivial representations oj with & 1,... (d daub) and one natural representation gf(2) This gives rise to
(1)
tr(
k.k' (IQ.) PLA.K-PAA
(S11)
tr tr(Q)A)
Q2 tr(PA) P. daub
tr(
Alternatively, Eq. (S10) can just be seen result of the block matrix multiplication, i.e..
EgJutAU AUT Eu + PUt PUP)
Ep PAPUP PUTPAP PUTPAPUPI
(S12)
+ tr(PAP) P.
dauh
where tr(PAP) tr(p2A) = tr(PA).
15

---

Corollary S4 Suppose (i)) is a Haar-random pure state in Haub- For arbitrary linear operators A on H. the following equality holds
tr(PA)
Bp [1)) =
(S13)
daub
where Epp. is the expectation with respect the random state (p))-
Proof Suppose k(o)) an arbitrary fixed state in Hsub. The random state (ip) can be written in terms of U U as (p) Upp))) such that
By [( Bueu [[PolU* AU]
(S14)
Eq. (S13) is naturally obtained from Lemma S3 by taking the expectation over (spp) which satisfies Plyaa) lsoo) and Plyy)
the following equality holds Lemma S5 For arbitrary linear operators A, B, C on H and U E U, the
Ey jutAU AU CU)
PAPBPCP + (PB) PAPCP + (PC) PAPBP+
tr (PA) PBPCP
dsub
doub
dzub
tr (PAPBPPC) (r(PAPC) (TAAP))((PB)
(S15)
doub dsub tr (
dzub
tr(PB)p)
PBP
dsubs (d sub
dsub
Proof Here we simply employ the block matrix multiplication to prove this equality. We denote
11 12
the 2 x blocks with indices
respectively where the index 2 corresponds to Haub. Thus
21
22
[1
the random unitary U can be written U
where In is the identity matrix on the U22
orthogonal complement of Hsub and U22 is a Haar-random unitary on Haub- The integrand becomes
Ui AUBUICU
U.. U2
Au
A12U22 Ule
A22
)
Bn
Bz
B12 Bza
(
Ci1 U C21
U22
C12U122
(S16)
The four matrix elements of the multiplication results are
11: An + A1a + An
+ A12U22 Br2
12: An AnBriC2us
Cizuuu An U A22 C22
21: A
B1 Cn + Az2 B21 42 A12 Cn + U A22 Brg Oz1, Cn
22: Ann Bu Cr2
+ A Cru U Am U Crp Ur
+ Ut Am2 Uu2 U2
(S17)
Since inhomogeneous Haar integrals always vanish on Hauh, the elements above can be reduced to
11: An Brn
12: AnBraUi
21: B2 Cu.
(S18)
22: U1122n Az C22
16

---

Let d2 = dsub dim Hsub and I22 be the identity matrix in Hsub. Utilizing Eqs. (S4) and (S5), the expectation each block becomes
tr B22 A12C21
11: AnBBICI1
d2
tr Cr
tr A22 B11
12:
A11
21:
d2
d2
(S19)
tr (An B11
tr(A22 (22) tr Bz2)
22:
122
I22
d2
d2
d2 (222 lr(C22) - 1r(
tr(
(222)
Bzz
122
d2 d2(d3 -)
d2
Written in terms of subspace projectors P and P. the results become exactly as Eq. (S15).
Corollary S6 Suppose (p) a Haar-random pure state in Haub For arbitrary linear operators A on H. the following equality holds
Epp [(g]A11) tr((PA)3) + (tx(PA))2
(S20)
d + 1)
where Ep1-1 is the expectation with respect to the random state ((p).
Proof Suppose (Pa) is an arbitrary fixed state in Hsub. The random state (ip) can be written in terms of U as (p)) Ulpo) such that
Epp [[(pp A|]) = Eveu [Kpo U AU (po ( AUTA))))))))
(S21)
Eq. (S20) is naturally obtained from Lemma S5 by taking C = and = 1poXPPl which satisfies PB BP = PBP B and B 1.
Lemma For arbitrary linear operators A, B, on H and U U, the following equality holds
Eu [ur(Ul AU B) tr(UiCUD) (((PAP)) (PCCPP)
(PP)) tr(PCPD (((PA)t((PB)
daub
d
tr (PBPAPCPD) (PAPBPPPC)
daub tr (PP)) ((PAAC)
daub
(S22)
Leub
(( + tr (rP)
(dub Lub - 1)
Proof Similarly with the proof of Lemma S5, the block matrix multiplication gives
tr(Ut AUB) = (
An (UZzA2
AraU22
)
Bu B12
Bz
B22
(S23)
=tr(An)Bn)) + (A + tr(U
App
Hence have
Es
- Ba
+ tr(
(S24)
+ (4) +HAgshahhhJHUuCCCDDDDHHHHHAAAHAL
+ (11
17

---

where all inhomogeneous terms have been ignored. Utilizing Eqs. (S4), (S6) and (S7), the expectation becomes
Ey
B11 (r(C
tr(An B1) )1) tr()22)
tr(Cii D11) tr tr (r
d2
d2
Ir( B21 A12C21 D12)
Ir(A21
B12
+
d2
d2
(S25)
(tr(Azz) tr (22) tr (Czz) tr (D2) + tr A22 tr B22 D22))
d2
(r (tr(A22 tr B22) tr (D2)) + (22)) tr (O2) tr B22 D22))
d2 d2
Written in terms of subspace projectors P and P, the results become exactly as Eq. (S22).
Finally, similar to the unitary t-design, we introduce the concept of "subspace t-design". If an ensemble W of unitaries matches the ensemble U rotating the subspace Haub up the t-degree moment, then W is called a subspace unitary t-design with respect to Haub. In the main text, the ensemble comes from the unknown target state. Alternatively, if random QNN U()) with some constraints such as keeping the loss function constant ((0) = Lo, i.e.,
W- U(O), θ (0 [()) Lo),
(S26)
forms approximate subspace 2-design, then similar results as in the main text can be established yet with different interpretation: there is an exponentially large proportion of local minima on constant-loss-sectee of the training landscape.
A.2 Perturbation positive definite matrices
To identify whether a parameter point is a local minimum, we need to check whether the Hessian matrix is positive definite, where the following sufficient condition is used in the proof of our main theorem in the next section.
Lemma S8 Suppose X is positive definite matrix and Y is a Hermitian matrix. If the distance between Y and X is smaller than the minimal eigenvalue X, i.e., ||Y X X|100 < || then is positive definite. Here || lloo denotes the Schatten-ro norm.
Proof For an arbitrary vector (v), we have
(o|Ylu) (o|X + (u)Y- X
|X - - 0.
(S27)
Note that || just represents the minimal eigenvalue of the positive matrix X. Thus, Y is positive definite.
A.3 Tail inequalities
In order to bound the probability of avoiding local minima, need to some "tail inequalities" in probability theory, especially the generalized Chebyshev's 's inequality for matrices, which we summarize below for clarity.
Lemma 59 (Markov's inequality) For a non-negative random variable X and O, the probability that X is at least a is upper bounded by the expectation of X divided by a, i.e.
[[[]
Pr[X N a)
(S28)
Proof The expectation can be rewritten and bounded as
E| = Pr[X a] X X al +
Pr 2 al E
X a)
(S29)
> Pr[X a] E[X X 2 2 Pr 2 a a
Thus have Pr[X 2 a| < /
18

---

Lemma S10 (Chebyshev's inequality) For real random variable X and & >> O, the probability that X deviates from the expectation [[X] by E is upper bounded by the variance of divided by ² i.e.
Var[X]
Pr[JX B[X] _e]
(S30)
Proof Applying Markov's inequality in Lemma S9 to the random variable (X R[X])² gives
E[X])* Pr[ E[X] 2 Pr[(X - 2 [
Var[X]
(S31)
E2
Alternatvely,, the proof can be carried out similarly as Eq. (S29) with respect (X -
Lemma S11 (Chebyshev's inequality for matrices) For a random matrix and e > 0, the probabil- ity that X deviates from the expectation E[X] by in terms of the norm ||
satisfies
Pr Pr[ B[X]Ia 20/5 oa E
(S32)
where o. = B [|a] denotes the variance of X in terms of the norm || lla-
Proof Applying Markov's 's inequality in Lemma S9 to the random variable ||X - [[x]
gives
Pr[l - E|X]I 2 =] = Pr[] E 2 Ed1 E
E
o2
(S33)
E²
Note that here the expectation EE| [ is still a matrix while the "variance" a is a real number.
A.4 Quantum Fisher information matrix
Given a parameterized pure quantum state [x)(0)), the quantum Fisher information (QFI) matrix Fuv [64] is defined as the Riemannian metric induced from the Bures fidelity distance di (0,00, 0') = (=)))))(())) (up to factor 2 depending on convention), i.e.,
0² 06,
(0)
d0
8)
- Re (0,,0.1)))) (0.0)))(10000)
(S34)
6=0
Note that (0uس] actually refers to 0e,
(0)). Using the normalization condition
(b)v) = 1,
((+)))) = (0 + (010,0) Re [(,, = O,
(S35)
(()(())))))) b)) = 2e (00,0,b)))) + (0,4)a = 0.
the QFI can be rewritten as
F
2 Re (1.+) - (0, +1)) 1
(S36)
The QFI characterizes the sensibility of a parameterized quantum state to small change of parameters, and can be viewed as the real part of the quantum geometric tensor.
B Detailed proofs
In this section, we provide the detailed proofs of Lemma 1, Theorem and Proposition in the main text. Here we d to denote the dimension of the Hilbert space. For qubit system with N qubits, we have d = 2N As in the main text, we represent the value of certain function at 0 0" by appending the superscript "*" for simplicity of notation, e.g., VL 0= as VL" and Hclo-o- as (,,) we introduce the notation V.,+,3 = I U, W, if < 3 and Va-BB = if a > 3. Note that the product II, is by default in the increasing order from the right the left. The derivative with respect to the parameter 0, is simply denoted 0, a We remark that our results hold for all kinds of input states into J0, QNNs in spite that we use (0) @N in the definition of (e)) for simplicity.
H². In addition, for a parameterized quantum circuit U(e) = M
19

---

Lemma 1 The expectation and variance of the gradient V L and Hessian matrix He of the fidelity 0* with respect to the target state ensemble T satisfy
loss function [(0) 1 -K))=(())
Er FrVV [*] [ 0, Varr = filp fi(p.d)Fmm
(S37)
Er [ dp² F", [arr(0,0,__]] & f2(p, d)1 112
(S38)
d-1
where F denote the QFI matrix. fi and f2 are functions of the overlap p and the Hilbert space dimension d, i.e.,
p² p²(1-p2) p²)
fe(p.)) 32(1 p2)
2(1 p²)
d p²
(S39)
d
Proof Using the decomposition in Eq. (4), the loss function can be expressed by
C = ( = 1-p2
- (1 (0) Ielx") 2pv 1 p2 Re ((v>" (S40)
where e(0) b (0) denotes the density matrix of the output state from the QNN. According to Lemma S2 and Corollary S4, the expectation of the loss function with respect to the ensemble can be calculated
tr "0"X""" Del
Er [()] p² (1
p2)
d-1
(S41)
dp² 1 9()),
1 - p²
d
where g0) (xb (e()) ()* denotes the fidelity distance between the output states at and 0 By definition, g(0) takes the global minimum at 0 0", i... & |4>*X*/ Xv. Thus the commutation between the expectation and differentiation gives
dp²
Er [VC = V (ET (CT)l 0=0-
Vg(())e=o- 0,
d-1
(S42)
dp² d-1 (0)l)
dp² -1
dp² - F
ET H2
H0)
d-1
d
Note that Hg (0) a- is actually the QFI matrix F of (b)( at 0 0" (see Appendix A.4). which always positive semidefinite. To estimate the variance, we need to calculate the expression of derivatives first due to the non-linearity of the variance, unlike the case of Eq. (S42) where the operations taking the expectation and derivative is exchanged. The first order derivative can be expressed by
o,C (dd==(dDDlo>) -
920 |Dul'
2pq Re ((v) [Dxl")).
(S43)
where q= = 1I- p2 and D On @ a traceless Hermitian operator since Dr, 0, e) At 0 = 0" the operator D2 is reduced to D which satisfies several useful properties
D [0<(1) 10 Xv"1 + (0,*"1,
(wi 1D (v"10~²") (0 = (x(()))))** 0,
(S44)
(w Dil'") = 10
(0 (bb) = =0,
(w* D2 (p) 11=+00 (16 (0) + 10= " 110*) (1110,1)))
where we have used the facts of (w/1²) = 1 and (15))p;; > 0. Note that 10 actually refers to 0 becomes
(a.lv))) Thus the variance of the first order derivative
VarT(0, = ET (0, Er10,,-1)² = Er (0,
(S45)
= =4²2² Er (Re(s 10)
According to Lemma S2 and Corollary 54, it holds that
Er
(Re 12, " 27 (0,40*000 (1b* 18 10/ 11)=)
Er 10 (8
(S46)
Fip
2(d - 1)
4(d 1)
20

---

Using the generators in the PQC, Fug could be expressed as where Fup is the QFI diagonal element.
Fuu- = 2 ((01(22)1)) - (201622(13))))
(S47)
where S2 = Vu- Vt M-M Finally, the variance of 0,, at 0 = 0* equals to
Fa
p²²1 p²)
Varrl0,C"] 4ppq²
F up
(S48)
4(d
d-1
The second order derivative can be expressed by
(Hc) = OL -
=
00,
(S49)
=-²² (yb (D Puulub") (b/)) q² (26 ID | 2pg Re ((1) 1 1)))
where Du = 02 2 g a traceless Hermitian operator since tr Du = 0, 2) = 0. Please do not confuse DN with Dr, above. At 0", the Duv is reduced to Dis which satisfies the following properties
D = -,00000000"- = 2 [10 " Xx*1
10 [0, "0,00""""""
(S50)
(w) D 10 (14 = Re 11 0x0 +
-F
(S51)
(w+ Dio (+)) = 2 Re [(bb 10, X0 [+
(S52)
Here the notation 2 Re[-] of square matrix A actually means the sum of the matrix and its Hermitian
conjugate, i.e., 2 Re[[A] A + AI. From Eq. (S50) we know that the rank of Djw is at most 4. Substituting the expectation in Eq. (S42), the variance of the second order derivative at 0 0" becomes
Varr(0,0,C* -r [0,001 - Er (p)))()))
2 d mv)
G²
+ 9 Fr 11cc
(S53)
24 Fu Br [1b 1D | + 4 (Re( ID [ d
where the inhomogeneous cross terms vanish after taking the expectation according to Lemma S2 and have been omitted. Using Corollaries S4 and S6, the expectations in Eq. (S53) can be calculated as
Er [( 1 33] tr((D - 2 ((1=*1() 1(D 21 - (16 D 11)))
d(d -1)
Fr.
Er [(b-1Dr (D
d 1
(S54)
Er [(Re(b+ me (
2 ET [(+++D (aul("))( D [
(1b* (DD (e) 21 - (+i D Nv l2b2)2
2(d 1)
Thus the variance of the second order derivative at 0 0" can be written as
Di 1122 2 ((15*) | (D ) (1(1)) (x/i 1Di (2) d(d 1)
(S55)
+ 2p² q2 (1= )1 (D" l85t32
9² F
1
Note that the factor
( (D2 -D 110' -1 (1b"
(S56)
21

---

is non-negative because the operator (I -1=0* is positive semidefinite. Hence the variance can be upper bounded by
get
2p²0²
Varr 1
|| 1
(66
(D
(107))
d(d - 1)
d-1
2p q²
(
9² F
2
1
+
I1 (DD
(S57)
d(d - 1)
d
d
d
21²
p² + 29²²
||
| 110
d 1
where we have used the properties
D l22 S
rank (w)) Di S 21 [1(D 2 = |iD
(S58)
Utilizing the quantum gates in the QNN, the operator Duo can be written as
Duv V
iS2
V p+1- Ca
(S59)
where we assume μ S v without loss of generality. Thus |/ can be upper bounded by
DD S 4110,,Swwlo. S 111 |bo.
(S60)
Finally, the variance of the second order derivative 0 0" can be bounded
Varr(0,0.CC) f2(p, d) 12 1 12
(S61)
The factor fz(p, d) reads
f2(p.d) 32(1 - p²)
2(1 - p²) p² +
(S62)
d-1
d
which vanishes at least of order 1/d.
Note that when p E {0, 1}. S1, /2 and hence the variances of first and second order derivatives become exactly zero, indicating h takes the optimum in all cases. This is nothing but the fact that the range the loss function is [0, 1], which reflects that the bound of Varr[O,0
is tight in p.
We remark that the vamishing gradient here is both conceptually and technically distinct from barren plateaus [35]. Firstly, here we focus on a fixed parameter point 0" instead of a randomly chosen point on the training landscape. Other points apart from 0" is allowed to have non-vanishing gradient expectation, which leads to prominent local minima instead of plateaus. Moreover, the ensemble T used here originates from the unknown target state instead of the random initialization. The latter typically demands polynomially deep circuit to form a 2-design. Technically, constant overlap p assumed to construct the ensemble T instead of completely random over the entire Hilbert space. Thus our results apply to adaptive methods, while barren plateaus from the random initialization are not.
Theorem If the fidelity loss function satisfies L()*) < <1 the probability that O is not local minimum of C up to a fixed precision = (E1, with respect to the target state ensemble T is upper bounded by
Prr LocalMinn(" c)) 2fi of w|1
f2 d) 1
(S63)
(dp² (4 et + +02))
where ex denotes the minimal eigenvalue of the QFI matrix at 0 = r" fr and fa are defined in Lemma which vanish at least of order 1/d.
Proof By definition in Eq. (5) the main text, the probability Prr Lin <) can be upper bounded by the sum of two terms: the probability that one of the gradient component is larger than
22

---

é,, and the probability that the Hessian matrix is not positive definite up to the enror i..,
M
Prr LoooloMMiiin .c]]= = Prr
U100,07>a)
o2l
(S64)
S
Prr
U
[10,5 > ci)
+ Prt [ -
==11
The first term be easily upper bounded by combining Lemma and Chebyshev's inequality, i.e.,
U10,c1>01
M
M
al S Varr(0,c41
M
fi d) Fr (S65)
Prr
PrT 10,,
where the diagonal element of the QFI matrix is upper bounded Fuu S 21 by definition and thus tr F s 2||w||B Here the generator norm vector w is defined
w (I|S) |e, [/0............................. | (lxo);
(S66)
so that the squared vector 2-norm of w equals to || = Ex= 11 bound of the first term, i.e.
Thus we obtain the upper
2 (p, (p.d))))wl) d)ll@13 Prt U102,c an)
x
(S67)
é
takes extra efforts to bound the second term. After assuming p² > 1/d to ensure that Er H positive semidefinite, a sufficient condition of the positive definiteness can be obtained by perturbing HH using Lemma S8, i.e.,
|| 1 < || + +22
H2 + c2 22 00
(S68)
Note that ||ET HH + -2/ = d-I 6* + 62, where ex denotes the minimal eigenvalue of the QFI Fr. necessary condition for H2 + 62T y 0s hence obtained by the contrapositive, i.e.,
40²=1e²
dp
H x 1 +
|| - Er
E2.
(S69)
Thus the probability that H2 not positive definite can be upper bounded by
dp" - e" + E2
Prr 1HE x -22]] Prr
|| Er[H2ll
(S70)
The generalized Chebyshev's inequality in Lemma S11 regarding H and the Schatten-co norm gives
2 e²
Prr H2 Er( 2 2
(S71)
where the "norm variance" is defined as o². Erll - Er[ By taking dp² obtain
d-1
6*
+
C2.
o²
Prr Prr[HE 1 -2l
(S72)
/dpa_1
2' d-1 6" C2 )²
Utilizing Lemma 1, o can be further bounded by
8² < of
Erlll Er[H21111
> Er ((H2) (Er(H22l)an)
M
M
Varr [3,0,6] s f2(p, d)
Σ
11
(S73)
m,==1
A,==1
d)
Σ
14 11
fz(p, cf)pll)
1=11
23

---

Combining Eqs. (S72) and (S73), we obtain the upper bound of the second term, i.c.
Prr |r + -224 f f2 d) d
(S74)
( +
Substituting the bounds for the first and second terms into Eq. (S64), one finally arrives at the desired upper bound for the probability that 0* is not a local minimum up fixed precision (E1, e2).
Note that the conclusion can be generalized to the scenario of mixed states or noisy states easily using the mathematical tools we developed in Appendix A.1, For example, suppose that the output state of the QNN p(0) and the target state is (Ø). The loss function can be defined as the fidelity distance ((0) 1 (Ø) p(() (o). Utilizing Lemmas S3 and S7, similar results can be carried out by calculating the subspace Haar integration.
Proposition 3 The expectation and variance of the fidelity loss function & with respect to the target state ensemble T can be exactly calculated as
dp²
Eg [C(0)] 1²
d d-1 g0).
(S75)
1 1²
(d - (1 1111-17) 12)
Varr [C(0)]
d - (00)
1p²
22²²
d(d-1) ((0)
where g(0) = 1- - (()))())))
Proof The expression of the expectation Ey [4] has already been calculated in Eq. (S41). Considering Lemma S2, the variance of the loss function is
Varr[4] [4] = Er (C - Er(C))
- p²
d - ((00"))/=>> 1) + q² (2 (elb=t) + 2pg Re ((v+ ((bb)1))))))))))))))))))))))((
Er
(S76)
(d - 1)2 (elp"))))) - -1)2+ 20t
aº
d lel"")) - 1) ET [(W- [el
qº Er [( le/bb 1 + +pp²y² Er Re ((bb lelx)))
where q / - pd and e(0) can be calculated as
According to Corollaries S4 and S6, the terms above
(elw")
Er [( [(l+-))))>))
[elpb>]]
d
(tr(e²) - 2(1²"' 1/001e 122 + (1 (1110))))) + (1 (W (elw")))
Er (W lelbb
d(d
(S77)
2(1 - (w (el
d(d 1)
Er [ (wblle/et Iel XV*" 1- (10 lelpb02 2(d - 1)
ET Re (elv=)))))
2
Thus the variance of the loss function becomes
[ar+[C] (1 (15 le 1²²)²²
+ 21 (10 (e(
+ 2p" (e/
(d 1)²
d(d 1)
d
(S78)
92 (1 (((b))))²))))
q - 2) (1l (elv)))) + +pp (v (eww)))
d( - 1)
Substituting the relation (v (e|b*)> = g()), the desired expression obtained.
If the quantum gate U, in the QNN satisfies the parameter-shift rule, the explicit form of the factor g( (0) could known along the axis of 0₂ passing through 0", which is summarized in Corollary $12. We use 0p to represent the other components except for l,.. namely 0, {0>)vga.
24

---

Corollary S12 For ONNs satisfying the parameter-shig rule by 2 = I. the expectation and variance of the fidelity loss function L restricted by only varying the parameter By from 0 with respect to the target state ensemble T can be exactly calculated as
dp² 1
Er Clop=03
=1 =1 -ppppp
d g(Ox),
(S79)
1 1-p² p²
(d 1-2)(1-00 x22
Vart
Clo, , =0
= d 1 g(Om)
4p²
2p²
d(d (dd-1 g(0m)
where y(0p)) F sin? (0 07))
Proof According to Proposition 3, we only need to calculate the factor g(0))o, =0 We simply denote this factor as g(0,,, the explicit expression of which could be calculated by just substituting the parameter-shift rule. Alternatively, the expression of g(O,,) can be directly written down by considering the following facts. The parameter-shift rule ensures that g(8xx must take the form of linear combinations of 1, cos(20 and ,20) since (b,) = e -0220 = cos f - i sin pup2pp and g(O,,) takes the form of (.) Furthermore, g(0,,) takes its minimum at 0% so that is an even function relative to 8 = f%.- Combined with the fact that g(Oz)) also takes zero at 62, we know g(0μ) x [1 - cos( (20, - 8.]]]. The coefficient can be determined by considering that the second order derivative of g(0,) equals to the QFI matrix element pp by definition, so that
g(O,,) = g le =
F
4 Fiull [1 (2 - f.1i = 2 un
1
sin 2 (0 - 0..)
(S80)
The expressions of the expectation and variance of the loss function can be obtained by directly substituting Eq. (S80) into Proposition 3.
C Generalization to the local loss function
In the main text, we focus on the fidelity loss function, also known as the "global" loss function [36], where the ensemble construction and calculation are preformed in clear and meaningful manner. However, there is another type of loss function called "local" loss function [36], such as the energy expectation in the variational quantum eigensolver (VQE) which aims to prepare the ground state of
a physical system. The local loss function takes the form of
(()) (0) /1 (O)),
(S81)
where H is the Hamiltonian of the physical system as summation of Pauli strings. Eq. (S81) can formally reduce to the fidelity loss function by taking H = I - [oXo). In this section, we generalize the results of the fidelity loss function to the local loss function and show that the conclusion keeps the same, though the ensemble construction and calculation are more complicated.
The ensemble we used in the main text decomposes the unknown target state into the learnt component ( and the unknown component |p ), and regards 1& ) as Haar random state in the orthogonal complement of ( This way of thinking seems to be more subtle in the case of the local loss function since the Hamiltonian is usually already known in the form of Pauli strings and hence is unnatural to assume an unknown Hamiltonian. However, known Hamiltonian does not imply a known target state, i.c., the ground state of the physical system. One needs to diagonalize the Hamiltonian to find the ground state, which requires an exponential cost in classical computers. That is to say, what one really does not know is the unitary used in the diagonalization, i.e., the relation between the learnt state (b*)) and the eigen-basis of the Hamiltonian. We represent this kind of uncertainty by a unitary V from the ensemble V, where V comes from the ensemble U mentioned in Appendix A. by specifying P |1/ X Such an ensemble V induces an ensemble of loss functions via
(( = (0) (VV
(S82)
similar with the loss function ensemble induced by the unknown target state in the main text. V can be interpreted as all of the possible diagonalizing unitaries that keeps the loss value L(O") constant, denoted as L. In the following, similar with those for the global loss function, we calculate the expectation and variance of the derivatives of the local loss function in I Lemma S13 and bound the probability of avoiding local minima in Theorem $14. Hence, the results and relative discussions in the main text could generalize to the case of local loss functions.
25

---

Lemma S13 The expectation and variance of the gradient VL and Hessian matrix H of the local loss function ( ((()) at 0 0" with respect to the ensemble V satisfy
By [
Vary|0,<"1 (H,
tr H dC d F",
(S83)
By [
Vary [0,0, S f2(H, d) 1
where F denotes the QFI matrix. fi and fz are functions of the Hamiltonian H and the Hilbert space dimension d, i.e,,
2 f2(H, = 32
(H²) - (HY
2 2
(S84)
d-1
d d-1
d(d 2)
where we introduce the notation (-)x = (v3*) -1b5%).
Proof Using Lemma S3, the expectation of the local loss function can be directly calculated as
By [C(0)] = - -* tr dL"
d-1 (
(S85)
where g = 1 (00) (0) ()))
denotes the fidelity distance between the output states at and 0" By definition, g()) takes the global minimum at 0 0". Thus the commutation between the expectation and differentiation gives
1r dL
Ey [ (Ey (c))
Vg(())l=o- 0,
d-1
(S86)
1r H dL"
d-1 (0)0)) = 1r dL
Ey H
d-1 F
By definition, (,) actually the QFI matrix J of (0) at 0 0" (see Appendix A.4), which is always positive semidefinite. To estimate the variance, we need to calculate the expression of derivatives first due to the non-line non-linearity of the variance. The first order derivative of the local loss function can be expressed by
0,6 tr(V HV[V 2 Re(b V V'HV),
(S87)
where Dr 0ne is traceless Hermitian operator since Dj, Op 2) 0. By definition, know that /1b)* is not changed by V, i.e. VIø*) = (w'), which leads to the reduction 0, = 2 Re( ( HVI0,o*)) Hence, the variance of the first order derivative
0* is
Vary = Ev [[0,C] Ev[0,c=)]]] = Ey [(0
Ev [22G((01[V188]
(S88)
Ev [(*"1H\\1,,'")) Ev [10 a (Vt H|
+ 2EEv [1b6 | 10,10 [/
Utilizing Lemmas S2 and S3, we obtain
Ev
2+ = (1) 10
Ev (0.4"11 H |
Ey (Hb*H 1/ (0,,,,,,''''""""" (0, [})]]
(S89)
(H²). (H)²
up + (H) 10, e
2(d-1)
where we introduce the notation (-), = (1b*) . (10) and hence L- = (H).. The 1/2 factor in the third line arises from the definition of the QFI matrix. Note that there are three terms above canceling each other due to the fact
2 Re (0, (1.)) (1, (M1.)) ((b))))))))))))))))))))))))))))) =
(S90)
+ (0.
= [2 = 0.
26

---

Therefore, the variance of the first order derivative at 0 = 0" equals to
(H²)- (H)
Vary [p-h" = Ey (2Re(v"|HV10,)
(S91)
pp
d-
The second-order derivative can be expressed by
,,0,C (He))= = tr HDHDV
(S92)
where pu 0n.000 is traceless Hermitian operator since tr Duv o₂ 3, Q) = 0. By direct expansion, the variance of the second order derivative at 0 can be expressed as
Varv[0,,0.C"] - Ev [(0,0,c*)]] (Evv (0,0,,
(S93)
where the second term is already obtained in Eq. (S86). Lemma S7 directly implies
Ev [(0n0.1))]] = Ev [Lr(VV tr(V HV HVV [Wo)]
= pD + (D ww)
d-1 (1r H - (Ir Duo (Dpw)-)
2
d- (111)) ((11)))(
pul (DDwv)
1
(tr 11 - (11). Dw )a)
d(d 2)
(S94)
(tr(1122) - -2(113) + (tr)) 2(D + (Dw))
dld - 2)
dld () 2) ((t(HH)) - 2(H )- + (H) ( Duu )=²
dd - () - 2) [(tr H - (H) (tr mmm 2((D + (D
According to Eq. (S86), (Dju)= = -Fay in Eq. (S51) and L = (H),.. we have
ju
(Bx10,0,c**)² = H dL'
2
H (H) (H), 2 d d-1
F
(Di.))
(S95)
d -
Combining Eqs. (594) and (S95) together with the condition Duu = we obtain
2
Varv|0,0,44 = d- - ((H22) (H) - (D)
1
+ d(d - 2) (Ir(H)?) - -(H +
- -22))) + (D
(S96)
1
[ - 2(H (H) 13
d(d - 1)(d - 2)
1
(tr H1 - (1) - -2,D + d 2-2
d d / (D (Dm))3))
d(d - 1)(d 2)
Note that we always have d 2 2 in qubit systems. If rank H 2 then it holds that
tr( - 2(H²) + 3 > H 3 2 11 2 (rank H)] H| 2 H 2 0.
(S97)
Otherwise if rank H = 1 (the case of rank H = 0 is trivial), then we assume H = A|oXol and holds that
tr(HH2)-((H33) + (1) = x2 2x 11>>)>1 2 11)1 x² -1- (1-1()))))) 20. 0. (S98)
Hence we conclude that it always holds that
ur(H²2 2(H (H) 0.
(S99)
Similarly, because tr Due-- = 0, we know rank D pm 2 2 and thus
tr() 2(D 2 (rank D pm)) )| yM 1|3c
211 113 2 0.
(S100)
27

---

Therefore, we can upper bound the variance by just discarding the last two terms in Eq. (S96)
2
Varv(0,0.f7] d d-1 (1H)) (D) - -D
(S101)
+ 1 -) (Ir( - (HT3) 2((D + (D)))
On the other hand, we have
tr (22) 2(H²) + (H) = tr(H+) - (H²) - - S tr(H2),
(S102)
since (11)) (H) = - X 1)H 2 0. A similar inequality also holds for Djw- Thus the variance can be further bounded by
1
2 Varv(000,c11 d (1H)), (H)))
4|| D d(d- ( 2)
(S103)
where we have used the properties in Eq. (S58). Using the inequality in Eq. (S60) associated with the gate generators, the variance of the second order derivative at 0 = 0 can be ultimately upper bounded by
Vary|0,0,cC|| s S2(H, 11 12, 1
(S104)
The factor fa d) reads
(H²), (H)2
2 d(d 2)
(2H 32
(S105)
d-
which vanishes at least of order O(poly(V)2-N) with the qubit count N log, d if | loc Oppoly(N)).
Theorem S14 L" < H.H. the probability that 0" is not local minimum of the local cost function up to fixed precision (E1, E2) with respect to the ensemble V is upper bounded by
(H,(H,))llu c
(2 d)) (HH,d))(l13
Pry (oLoaalMin(O" ,0) .015
2
(S106)
tr -C- ex - 62) d-1
where e* denotes the minimal eigenvalue of the QFI matrix at 0: fi and fz are defined in Eq. (S84) which vanish at least of order (poly((N)2 with the qubit count N log, d if H to E (ppol((N)).
Proof Utilizing Lemma $13, the proof is exactly the same as that of Theorem up to the different hessian expectation [yy H2] and coefficient functions fi and f2-
28


Reviews:
[{"review_id": "JMfGpWzXmQ", "reviewer": "Reviewer_a4pD", "summary": "This paper introduces a new statistical analysis for training variational quantum circuits (e.g., in terms of quantum neural networks), where the alternating-layered ansatz (Nakaji et al.; ALT), also referred to as the entanglement circuit for quantum ML in Chen et al. 2019 [4], has been characterized as a general quantum state learning task.\n\nIn general, the presentation flow is quite good, including a proper introduction to the $l_p$ norm and Dirac notations. The authors have made considerable efforts to guide the readers from the existing learning definition in vector-to-vector mapping to standard encoding based parameterized quantum state learning.\n\nAlthough some recent works on error analysis in quantum circuit learning [1] and classical encoding circuits [2,3] are unfortunately omitted, the paper actually provides a careful and detailed review of related work in the appendix.\n\nIn general, while the theorem is neat, moving from elaborating fidelity loss to fisher information based bound analysis, this paper also conducts a solid local minima analysis. Despite the fact that learnability is considered a no-go perspective and some related work (e.g., [1]) is missing, I believe the theoretical findings and its supporting numerical results conducted good takeaways to the community. \n\nIn general, I tend to accept this paper.\n\n***\n\n**References**\n\n1. \"Theoretical error performance analysis for variational quantum circuit based functional regression.\" J Qi et al. npj Quantum Information 9.1 (2023):. Nature\n2. \"Quantum Circuit Learning,\" K. Mitarai et al., Physical Review A 98.3 (2018): 032309.\n3. \"Quantum machine learning in feature hilbert spaces, M. Schuld, Physical Review Letters\"\n4. \"Variational Quantum Circuits for Deep Reinforcement Learning\" 2019", "questions": "1. the ensemble setting in Appendix A. 1 is not clear on the motivation of using model ensemble.", "limitations": "- The no-go theorem, while important for understanding the limitations of QNNs, might be a potential barrier to the application of quantum neural networks in real-world scenarios.\n\n- The paper implies that significant future progress will be needed, potentially borrowing insights from the field of deep learning, to overcome the limitations of current QNNs.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper provides a clear characterization of the curvature of local minima, which is important to understand the sensitivity of output state with respect to QNN (VQC learning) parameters.\n\n- It provides quantitative limits on good initial guesses related to no free lunch (NFL) theories and adaptive methods for improving the learnability and scalability of QNNs.\n\n- Good presentation quality.\n\n- The paper suggests that no single QNN is universally the best-performing model for learning all target quantum states. This introduces additional complexity for practical applications as it may necessitate more structured QNN architectures and innovative optimization tools.", "weaknesses": "- the ensemble setting in Appendix A. 1 is not clear on the motivation of using model ensemble.\n- despite the results, there is a level of uncertainty remaining as the exact scaling of QNN depth needed to form a subspace 2-design is not very clear", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's recognition of our work as technically solid, well written, and valuable to the community. We are also grateful to the reviewer for drawing our attention to the literature that we had overlooked. We will ensure to include these references in the revised version of the manuscript. The following is our point-by-point response to your comments and questions.\n\n> $\\textbf{Comment 1:} $``The ensemble setting in Appendix A.1 is not clear on the motivation of using model ensemble.'' \n\n$\\textbf{Re 1:}$ We thank the reviewer for this comment on the ensemble setting. The motivation of our ensemble setting originates from the empirical observation that the probability of encountering local minima when running a variational quantum algorithm depends on the loss value (i.e. the fidelity in quantum state learning tasks). Especially for adaptive methods which are usually not covered by common trainability analyses, the training process often tends to stagnate when a certain loss value is reached. This phenomenon motivates us to study the learnability at a certain loss value. In other words, we want to explore the average learnability among the quantum states $|\\phi\\rangle$ which have the same fidelity $p$ with the current learned state $|\\psi\\rangle$, i.e., $|\\langle\\phi|\\psi\\rangle|=p$, where our ensemble naturally arises. Graphically, this ensemble forms a circle on the Bloch sphere centered $|\\psi\\rangle$ as shown in Fig. 1(b) in the manuscript. Mathematically abstracting and generalizing this set of ``quantum states with fixed-fidelity'' leads to the ensemble setting introduced in Appendix A.1.\n\n> $\\textbf{Comment 2:} $``Despite the results, there is a level of uncertainty remaining as the exact scaling of QNN depth needed to form a subspace 2-design is not very clear.'' \n\n$\\textbf{Re 2:}$ Thanks for this insightful comment. As mentioned in the outlook section, although it is well known that a local random quantum circuit of polynomially depth forms an approximate unitary 2-design [1], it remains an open question what the scaling of the depth is to constitute a subspace 2-design. But we can still provide some qualitative analysis. First, the scaling is at most exponential in the number of qubits because the Haar measure over the whole Hilbert space can directly induce a subspace 2-design by constraining the space. Moreover, whether a random QNN can form a subspace 2-design strongly depends on the desired loss value. If the desired loss value is too close to the theoretical minimum, it will be extremely hard for a random QNN to cover those states with such a loss value so that the depth needed will be very large. On the other hand, if the loss value is near its average level, e.g. $1/d$ for the fidelity loss function, the required depth will be relatively smaller since there are many states concentrated into this range.\n\nHere we specially clarify that this specific depth scaling will not affect our conclusion in the manuscript since our ensemble takes average over random target states instead of random QNNs. We mention this issue in the outlook section only because if this depth scaling is known, it would allow us to directly apply our mathematical tools to the setting of random QNNs.\n\n[1] Jonas Haferkamp. Random quantum circuits are approximate unitary t-designs in depth $o(nt^{5+o(1)})$. Quantum, 6:795, 2022."}, {"review_id": "j69FZK2zz2", "reviewer": "Reviewer_oE2w", "summary": "This paper investigates the learnability of the QNN in the task of quantum state learning from a statistical perspective. The paper develops a no-go theorem that proves that when the loss function value is lower than a critical threshold, the probability of avoiding local minima decreases exponentially with the number of qubits, while only increasing polynomially with the circuit depth. Moreover, the paper conducts some numerical experiments to validate the proposed theorem.", "questions": "1. Why choose the ALT structure as the research study in the numerical experiment?  ALT in fact provably does not suffer from the vanishing gradient problem, and does this affect the experimental results as well as the theoretical proof?\n\n2. The abstract mentioned that \"the results hold for any circuit structure\", and is there any theoretical or experimental proof of this?", "limitations": "The paper discusses the limitations and addresses them.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper studies a novel research problem, namely the limitation of quantum neural networks in quantum state learning tasks, and analyzes the influence of loss function value information on training difficulty from a statistical perspective, which has certain value for understanding and improving the principles and methods of quantum machine learning.\n\n2. It provides a rigorous and quantitative theoretical analysis showing that when the loss function value is below a critical threshold, the probability of avoiding local minimum decay exponentially with the number of qubits, but only grows polynomially with the circuit depth, revealing the tradeoff between learnability and scalability of QNNs.", "weaknesses": "1. The theoretical analysis is only applicable to pure state learning tasks, and in fact, mixed states or noisy states may be encountered in quantum machine learning, so the conclusions and methods may need further generalization and verification.\n\n2. Numerical experiments only use one kind of QNN but do not consider other possible circuit structures and parameterization methods, the results may have certain biases and limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's positive assessment on the correctness, novelty and value of our work. We also thank the reviewer for the helpful feedback. Below is our point-by-point response to the comments and questions.\n\n> $\\textbf{Comment 1:}$ ``The theoretical analysis is only applicable to pure state learning tasks, and in fact, mixed states or noisy states may be encountered in quantum machine learning, so the conclusions and methods may need further generalization and verification.''\n\n$\\textbf{Re 1:}$ Many thanks for raising this highly practical issue. In the main text, we focused on the case of pure states for the sake of simplicity and ease of better understanding quantum state learning. However, the mathematical tools we developed in Appendix A can be directly applied to the scenario of mixed states or noisy states. For example, suppose that the output state of the QNN is $\\rho(\\pmb{\\theta})$ and the target state is $|\\phi\\rangle$. The loss function can be defined as the fidelity distance $\\mathcal{L}(\\pmb{\\theta})=1-\\langle\\phi|\\rho(\\pmb{\\theta})|\\phi\\rangle$. Utilizing Lemmas S3 and S7, similar results can be carried out by calculating the subspace Haar integration. We shall add this generalization in the revised version of our manuscript.\n\n> $\\textbf{Comment 2:}$ ``Numerical experiments only use one kind of QNN but do not consider other possible circuit structures and parameterization methods, the results may have certain biases and limitations.''\n\n$\\textbf{Re 2:}$  Many thanks for this helpful comment! Theoretically, our theorem hold for any circuit structure since the proof does not involve specific QNN structures (see our response to the question below for detailed explanation). However, to make the numerical experiments more convincing independently, we agree with your suggestion and will conduct additional experiments using different and common circuit structures and add them in the revised version of our manuscript. Thanks for the suggestion again and we believe considering other possible circuit structures will strengthen our manuscript.\n\n> $\\textbf{Comment 3:}$ ``Why choose the ALT structure as the research study in the numerical experiment? ALT in fact provably does not suffer from the vanishing gradient problem, and does this affect the experimental results as well as the theoretical proof?''\n\n$\\textbf{Re 3:}$ Thanks a lot for this good question. We choose the ALT structure because it is one of the most extensively used and studied ansatz in variational quantum algorithms [1]. To the best of our knowledge, the ALT ansatz does have better trainability than the hardware-efficient ansatz used in the original paper of barren plateaus. Shallow ALT circuits indeed do not suffer from the vanishing gradient problem. However, if one consider deep circuits to extend the expressibility of QNNs, random QNNs of the repeated-layer type will in general approximate unitary 2-designs given a sufficiently large depth [2], including the ALT ansatz. Thus, the deep ALT ansatz will also suffer from the vanishing gradient problem. Putting aside the points on ALT mentioned above, the specific circuit structure does not affect our theoretical proof (see our response to the next question for detailed explanation), though it may slightly affect the experimental results due to the difference of trainability.\n\n[1]. Nakaji, Kouhei, and Naoki Yamamoto. Expressibility of the alternating layered ansatz for quantum computation. Quantum 5:434, 2021.\n\n[2]. Jonas Haferkamp. Random quantum circuits are approximate unitary t-designs in depth $o(nt^{5+o(1)})$. Quantum, 6:795, 2022.\n\n\n> $\\textbf{Comment 4:}$ `` The abstract mentioned that \"the results hold for any circuit structure\", and is there any theoretical or experimental proof of this?''\n\n$\\textbf{Re 4:}$  This is a very insightful question. To provide a clear explanation to this question, we would like to start by reviewing how previous results on QNN trainability depends on the circuit structure. For example, in the original paper of barren plateaus [1], one of the hypotheses is that the random initialized QNN approximates a unitary 2-design so that the Haar integration in the calculation could be carried out safely. This means that their conclusion only applies to random initialized deep QNNs while shallow ones are not subject to such limitations. On the other hand, there is also some literature that does not make any assumption on the circuit structure and initialization of parameters [2], where the ensemble comes from the randomness of unknown learning targets, as in the setup of the Hayden-Preskill thought experiment [2]. The setting in our paper resembles the latter. We suppose that no more information about the target state is known except the measured loss value, so that we can take averages over the orthogonal complement space reasonably. Our theoretical proof does not involve any specific circuit structure and the only relevant hyper-parameters are the qubit count, the circuit depth and the value of quantum Fisher information. Therefore, our results naturally hold for any circuit structure.\n\n[1] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9(1):1–7, mar 2018.\n\n[2] Zoë Holmes, Andrew Arrasmith, Bin Yan, Patrick J. Coles, Andreas Albrecht, and Andrew T. Sornborger. Barren plateaus preclude learning scramblers. Physical Review Letters, 126(19), sep 2020."}, {"review_id": "qeLzRdGbad", "reviewer": "Reviewer_HYxZ", "summary": "The paper studies parameterized quantum circuits (aka QNNs). These architectures face trainability issues (e.g. barren plateaus) as the number of qubit grows, and several approaches have been explored to mitigate these. The paper analyzes these strategies using the task of training a circuit to transform |0> input state into a desired output state, and provides theoretical and numerical evidence of difficulty of training the circuit.", "questions": "Discussion in 3.3 mentions complementarity of the abundance of local minima and barren plateaus on the expressibility axis. How do recent results on mitigating barren plateaus via architectural choices instead of initialization (e.g. Wang et al., ICLR'23) affect this understanding?", "limitations": "There does not seem to be negative social impact of this theoretical research.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper adds new, original result to an important, open problem of training QNNs. The result provide scaling law of the probability of avoiding local minima irrespective of techniques such as special initialization strategy. Importantly, the result explicitly involves the precision parameter, which is one of crucial differentiators between classical networks and QNNs that necessarily use quantum measurement.\n\nTheoretical results are followed with extensive numerical simulations confirming the results in practice.", "weaknesses": "The paper is focused on a specific loss, specific task, which leads e.g. to a specific type of dependence of local minima on parameter count (e.g. discussion in lines 206-209 on pg. 6). It is not fully clear how insights from this task translate to other losses/tasks.\n\nThe result showing that the number of local minima decreases with the expressibility of the circuit is in line with previous work, but those earlier results are not discussed in detail in the discussion. E.g., Larocca et al. Theory of overparametrization in quantum neural networks. 2021 [Ref 57] is cited in the introduction but not in discussion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful for the reviewer's recognition of our work as a novel and technically solid paper with good impact. A detailed response to the reviewer's comments and questions is provided below in a point-by-point manner.\n\n>$\\textbf{Comment 1:}$ ``The paper is focused on a specific loss, specific task, which leads e.g. to a specific type of dependence of local minima on parameter count (e.g. discussion in lines 206-209 on pg. 6). It is not fully clear how insights from this task translate to other losses/tasks.''\n\n$\\textbf{Re 1:}$ Thanks a lot for the comment. In the main text, we focus on quantum state learning tasks with the fidelity loss function of pure states for the sake of simplicity and ease of understanding. However, the mathematical tools we developed in Appendix A can be directly applied to other scenarios tasks. First, we show similar results for the energy loss function (the expectation value of a Hermitian operator, or say the local loss function) in variational quantum eigensolvers or combinatorial problems in Appendix C. Second, utilizing Lemmas S3 and S7 in Appendix A, similar results can be carried out for the case of mixed states or noisy states by calculating the subspace Haar integration. The loss function can be written as $\\mathcal{L}(\\boldsymbol{\\theta})=1-\\langle\\phi|\\rho(\\boldsymbol{\\theta})|\\phi\\rangle$ where $\\rho(\\boldsymbol{\\theta})$ is the noisy output state of QNN and $|\\phi\\rangle$ is the target state. This generalization will be added in the revised version of our manuscript. \n\nExtending the results to other loss functions, such as alternative distance measures between quantum states, is not as straightforward and requires more careful proof. However, here we can provide a general statement of the insight behind the rigorous results above. The loss value below the average level indicates that the current parameters are relatively good. At this point, moving in a random optimization direction is likely to be less beneficial than staying in place, suggesting the presence of a local minimum. The probability of avoiding such a local minimum should be proportional to the ratio of the number of selected directions (training parameters) over the total number of all possible directions (Hilbert space dimension). Hence, the probability should decay exponentially with the number of qubits, while grows polynomially with the number of training parameters.\n\n>$\\textbf{Comment 2:}$ ``The result showing that the number of local minima decreases with the expressibility of the circuit is in line with previous work, but those earlier results are not discussed in detail in the discussion. E.g., Larocca et al. Theory of overparametrization in quantum neural networks. 2021 [Ref 57] is cited in the introduction but not in discussion.''\n\n$\\textbf{Re 2:}$ Great thanks for drawing our attention to the literature that we had overlooked in the discussion. Indeed, we agree that the reduction of local minima with the increasing expressibility here bears some resemblance to Ref. [1]. Both of them reflect the notion that high-dimensional spaces can aid optimization. However, due to differences in settings, in Ref. [1], the reduction of local minima occurs after a computational phase transition at $M_c$ upon reaching over-parameterization. In contrast, our work implies that this reduction occurs from the beginning of increasing expressibility in an average sense. We will include this discussion in the revision.\n\n[1] Martin Larocca, Nathan Ju, Diego García-Martín, Patrick J. Coles, and M. Cerezo. Theory of overparametrization in quantum neural networks, 2021.\n\n>$\\textbf{Comment 3:}$ ``Discussion in 3.3 mentions complementarity of the abundance of local minima and barren plateaus on the expressibility axis. How do recent results on mitigating barren plateaus via architectural choices instead of initialization (e.g. Wang et al., ICLR'23) affect this understanding?''\n\n$\\textbf{Re 3:}$ Thanks for the very insightful question. The complementarity of barren plateaus and local minima discussed here is based on two assumptions, respectively. (a) The QNN is randomly initialized and deep enough to form a unitary $2$-design, so that the Haar integration can give rise to exponentially vanishing mean value and variance of gradients. (b) No prior information is known about the target state except for the loss value $\\mathcal{L}^*<\\mathcal{L}_c$, so that the subspace integration can give rise to a locally minimal landscape with a probability exponentially close to $1$. A high-overlap initial guess may break assumption (a) but not (b), so it would still encounter local minima, as we discussed in our paper. On the other hand, a good choice of circuit architecture which takes advantage of the specific prior information of the target state, such as the symmetry of the transverse field Ising model considered in Ref. [1], could simultaneously break both assumptions (a) and (b). Thus, problem-inspired architectural choices as in Ref. [1] are likely to not only mitigate barren plateaus, but also reduce the local minima caused by the lack of prior information. We agree that the recent progress on symmetric pruning scheme will shed new lights on the study of QNN. In the revised version, we will elaborate more discussions on recent related papers.\n\n[1] Wang, X., Liu, J., Liu, T., Luo, Y., Du, Y. and Tao, D., 2022, September. Symmetric Pruning in Quantum Neural Networks. In The Eleventh International Conference on Learning Representations (ICLR 2023).\n"}, {"review_id": "GJlEqK5r2M", "reviewer": "Reviewer_atEi", "summary": "The authors present a no-go theorem that reveals the limitations of learning unknown quantum states using QNNs, even with high-quality initial states. They prove that the probability of avoiding local minima decreases exponentially with the number of qubits but grows polynomially with circuit depth. The curvature of local minima is determined by the quantum Fisher information and a loss-dependent constant. These findings provide insights into the role of prior information and the scalability of QNNs, impacting their learnability and effectiveness.", "questions": "1. In this work, it focus on learning pure states through QNN, and whether the statement is also true for the mixed states.\n2. Whether the no-go theorem is also true for other loss functions, such as using another metric as the distance in loss?\n3. In the numerical experiments, how to calculate the probability $Pr_{\\mathbb{T}}[LocalMin(\\theta^*,\\epsilon)]$?", "limitations": "  ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work explores the trainability of quantum neural networks. The theoretical findings give the limits on the learnability of QNN in general cases which provide some insight into the development of QNN in future studies.", "weaknesses": " ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's recognition of our work as a technically solid paper with good impact. Below is out point-by-point response to the reviewer's questions.\n\n>$\\textbf{Comment 1:}$ \"In this work, it focus on learning pure states through QNN, and whether the statement is also true for the mixed states.''\n\n$\\textbf{Re 1:}$ Thanks a lot for this highly practical question. In the main text, we indeed focused on the case of pure states for the sake of simplicity. Understanding the learning of pure quantum states is central to quantum state learning.\nHowever, we want to remark that the mathematical tools we developed in Appendix A can be also applied to the scenario of mixed or noisy output states, leading to similar conclusions. For example, suppose that the output state of the QNN is $\\rho(\\boldsymbol{\\theta})$ and the target state is $|\\phi\\rangle$. The loss function can be defined as the fidelity distance $\\mathcal{L}(\\boldsymbol{\\theta})=1-\\langle\\phi|\\rho(\\boldsymbol{\\theta})|\\phi\\rangle$. Utilizing Lemmas S3 and S7, similar results can be carried out by calculating the subspace Haar integration. We shall add this generalization in the revised version of our manuscript. Nevertheless, when the output state and the target state are both mixed states, our theoretical tools can not be directly applied for the following reasons. First, the Bures fidelity of two mixed states $F(\\rho,\\sigma)=\\operatorname{tr}\\sqrt{\\rho^{1/2}\\sigma\\rho^{1/2}}$ is hard to measure accurately on quantum devices. Second, for two mixed states, it is subtle and unclear to define the orthogonal decomposition like in Eq. (4), i.e., decompose the target state into the learned component and the unknown component, which may be left for future research.  \n\n>$\\textbf{Comment 2:}$ \"Whether the no-go theorem is also true for other loss functions, such as using another metric as the distance in loss?''\n\n$\\textbf{Re 2:}$ This is a very good question. Our theorem is indeed also true for certain other loss functions, such as the energy loss function (the expectation value of a Hermitian operator, or say the local loss function) in variational quantum eigen-solvers or combinatorial problems as shown in Appendix C. However, extending the results to other loss functions, such as alternative distance metrics, is not as straightforward and requires careful case-by-case proof utilizing the mathematical tools we developed in Appendix A, because the bound analysis for the Hessian matrix depends on the specific choice of loss functions. Nonetheless, here we can provide a general statement of the insight behind the rigorous results. The loss value below the average level actually indicates that the current parameters are relatively good. At this point, moving in a random optimization direction is likely to be less beneficial than staying in place, suggesting the presence of a local minimum. The probability of avoiding such a local minimum should be proportional to the ratio of the number of selected directions (training parameters) over the total number of all possible directions (Hilbert space dimension). Thus, the probability should in principle decay exponentially with the number of qubits, while grows polynomially with the number of training parameters.\n\n>$\\textbf{Comment 3:}$ \"In the numerical experiments, how to calculate the probability $\\operatorname{Pr}_{\\mathbb{T}} [\\operatorname{LocalMin}(\\boldsymbol{\\theta}^* , \\epsilon)]$?''\n\n$\\textbf{Re 3:}$ Thanks for this careful question. In general, we numerically estimate the desired probability $\\operatorname{Pr}_{\\mathbb{T}} [\\operatorname{LocalMin}(\\boldsymbol{\\theta}^* , \\epsilon)]$ by sampling and counting the frequency of local minima. To be specific, we first choose a parameter point $\\boldsymbol{\\theta}^*$ randomly to obtain the QNN output state $|\\psi^*\\rangle=|\\psi(\\boldsymbol{\\theta}^*)\\rangle$ and specify the desired overlap $p$ and the error tolerance $\\epsilon$. Then, we generate a Haar-random state $|\\psi^\\perp\\rangle$ within the orthogonal complement of $|\\psi^*\\rangle$ as the unknown component and perform a superposition according to Eq. (4) to obtain a single target state sample $|\\phi\\rangle$. Then, for each sample, we calculate the gradient and Hessian matrix to check whether they satisfy the condition of local minimum in Eq. (5). After generating $200$ samples, we count how many times the condition of local minimum is satisfied and regard the frequency as an estimation of the probability. The detailed source code used in numerical experiments is available in the supplementary materials for your convenience. We will also describe this clearly in more details in the revision."}, {"review_id": "NdLUYcc2eJ", "reviewer": "Reviewer_KReL", "summary": "This paper describes a formalization and experimental verification of the thesis that a quantum state $\\vert\\phi\\rangle$ is the local minimum in the process of the QNN training. The paper is well written and provides all necessary support documents for its understanding. This work is an extension and is complementary to the work on the observed plateaus in the learning landscape during the training of QNN. \n\nThe most interesting finding is that the probability that a state $\\vert\\phi\\rangle$ being the local minimum is inversely proportional to the number of qubits and proportionally growing with the depth of the QNN (number of layers in the network). This seems to be in opposition with the original work \"Barren plateaus in quantum neural network training landscapes\" where the learnability decreases with the number of qubits in the state. \n\nThe formal description seems to uphold the hypothesis. ", "questions": "- What are the more formal conclusions beyond a simple better initialization or problem aware initialization? Because your paper concerns a quite serious issue a p@rediciable discussion should be provided. \n- Is there a ratio between the depth $d$ and $n$ so that the occurrence of the local minima is minimized? What is the order of such ratio?", "limitations": "- The paper should be better discussed as for the consequences and unique conclusions. While there is a considerable amount of explanation I feel the authors failed to provide details on how to avoid the observed effect", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Problem description and formalization\n- The experimental verification of the observed phenomenon\n", "weaknesses": "- The main weakness is the significance of the result. While the result is interesting and proven, it is a bit expected. In particular, the result shows us that with increasing embedding i.e. the number of parameters the representational power increases while it also vanishes with increasing number of qubits. So the first conclusion is not surprising and the second conclusion seems to follow the previous works. However, more importantly, because this papers concerns an unknown state, a conclusion should be drawn if this effect can be avoided at all. Because independently of this initial setting an unknown state can occur. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and recognition of our work as interesting and technically sound. A detailed response to the reviewer's comments and questions is provided below in a point-by-point manner.\n\n>$\\textbf{Comment 1:}$ ``The main weakness is the significance of the result. While the result is interesting and proven, it is a bit expected. In particular, the result shows us that with increasing embedding i.e. the number of parameters the representational power increases while it also vanishes with increasing number of qubits. So the first conclusion is not surprising and the second conclusion seems to follow the previous works. However, more importantly, because this paper concerns an unknown state, a conclusion should be drawn if this effect can be avoided at all. Because independently of this initial setting an unknown state can occur.''\n\n$\\textbf{Re 1:}$ Thanks for the comments. In general, our no-go theorem can be regarded as a no-free-lunch (NFL) theorem in quantum state learning tasks, which implies that the probability of avoiding local minima in learning an unknown state always vanishes exponentially with the qubit count, while only grows polynomially with the circuit depth. Although this conclusion seems partially intuitive, we emphasize that the formal statement and rigorous proof is non-trivial because we prove that the theorem holds for any initial state and we develop a complete mathematical toolkit to accomplish the proof (see ``subspace integration'' in Appendix A). Moreover, our results are distinct from previous works since our results place crucial theoretical limits for adaptive training methods, which is beyond the scope of barren plateaus [1]. Finally, we have discussed that prior information can indeed help to reduce the local minimum phenomenon in Section 3.3 (line 240-247). We will make this point more clear in the revised version of our manuscript.\n\n[1] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9(1):1–7, mar 2018.\n\n>$\\textbf{Comment 2:}$ ``What are the more formal conclusions beyond a simple better initialization or problem aware initialization? Because your paper concerns a quite serious issue a prediciable discussion should be provided.''\n\n$\\textbf{Re 2:}$ Thanks for this good question. Our results establish a rigorous limit for training methods without prior information, especially for those beyond the reach of barren plateaus such as simple good initial guesses and plain adaptive methods. Hence, our results suggest that a problem-inspired QNN architacture taking advantage of prior knowledge of the target state is vitally necessary, as discussed in Section 3.3. Specifically, an example of prior knowledge from quantum many-body physics is the tensor network states [1] satisfying the entanglement area law, which lives only in a polynomially large space but generally can not be solved in two and higher spatial dimensions by classical computers. Other examples include the UCCSD ansatz [2] in quantum chemistry which utilizes the fact that the Hamiltonians usually contains few-body interactions, and the QAOA ansatz [3] in combinatorial optimization which makes use of the quantum adiabatic evolution. The ways of leveraging prior information are diverse and dependent on specific problems, necessitating further research in the future. We will enhance the clarity of this aspect in the revision.\n\n[1]. Felser, Timo, Simone Notarnicola, and Simone Montangero. Efficient tensor network ansatz for high-dimensional quantum many-body problems. Physical Review Letters 126.17:170603, 2021.\n\n[2]. Jonathan Romero, Ryan Babbush, Jarrod R McClean, Cornelius Hempel, Peter J Love, and\nAlán Aspuru-Guzik. Strategies for quantum computing molecular energies using the unitary\ncoupled cluster ansatz. Quantum Science and Technology, 4(1):014008, 2018.\n\n[3]. Farhi, Edward, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 2014.\n\n>$\\textbf{Comment 3:}$ ``Is there a ratio between the depth $d$ and $n$ so that the occurrence of the local minima is minimized? What is the order of such ratio?''\n\n$\\textbf{Re 3:}$ Thanks for this constructive question. According to the scaling $\\mathcal{O}(N^22^{-N}D^2/\\epsilon^2)$ established in our manuscript, the desired critical value of the ratio $\\lambda=N/D$ indeed exists if we rewritten the scaling as $\\mathcal{O}(\\lambda^22^{-D\\lambda}D^4/\\epsilon^2)$ and fix the depth $D$. Through a straightforward differentiation, one can find the critical value of the ratio $\\lambda_c$ is of order $\\mathcal{O}(D^{-1})$, which can also be seen from the original scaling where there is a maximum at $N_c$ of order $\\mathcal{O}(1)$. This reflects the fact that the linear growth of training parameters in each layer with the qubit count can rarely improve the exponential suppression from the lack of prior information about the target state which lives in the exponentially large Hilbert space."}]

Author rebuttal:
Dear PC,

We want to express our sincere gratitude to the Program Committee for their hard work in shaping the conference's scientific program. We would also like to thank all the reviewers for recognizing our work as a novel and technically solid paper and recommending acceptance of our submission.

We appreciate the reviewers' time and efforts in reviewing our work and providing constructive feedback. We have addressed all the comments and questions raised by the reviewers in the rebuttal.

Thank you for considering our work!

Yours Sincerely,

Authors of Paper 11169.

Meta-review: This submission investigates the trainability of the QNN in the task of quantum state learning by characterizing the landscape of the loss function.  Specifically, it provides a no-go theorem that proves when the loss function value is lower than a certain threshold, the probability of avoiding local minima decreases exponentially with the number of qubits, while only increasing polynomially with the circuit depth. There is a consensus on the theoretical contribution of the paper.  Besides the presentation issues mentioned in the rebuttal phase, the authors are also advised to provide further discussions about the paper’s relation to VQE, which is closer to the investigated task than general QNN tasks.  In particular, there is work on the convergence of VQE training in the overparameterized setting, as well as other overparameterization work in both VQE and QNN settings, which is worth discussing.
Decision: Accept (poster)