Critical Points in Quantum Generative Models
Authors: Eric Ricardo Anschuetz
Venue: ICLR 2022 Poster (2022)
Keywords: loss landscapes
quantum
Wishart spin-glass model

Abstract: One of the most important properties of neural networks is the clustering of local minima of the loss function near the global minimum, enabling efficient training. Though generative models implemented on quantum computers are known to be more expressive than their traditional counterparts, it has empirically been observed that these models experience a transition in the quality of their local minima. Namely, below some critical number of parameters, all local minima are far from the global minimum in function value; above this critical parameter count, all local minima are good approximators of the global minimum. Furthermore, for a certain class of quantum generative models, this transition has empirically been observed to occur at parameter counts exponentially large in the problem size, meaning practical training of these models is out of reach. Here, we give the first proof of this transition in trainability, specializing to this latter class of quantum generative model. We use techniques inspired by those used to study the loss landscapes of classical neural networks. We also verify that our analytic results hold experimentally even at modest model sizes.

Published as a conference paper at ICLR 2022
CRITICAL POINTS IN QUANTUM GENERATIVE MOD- ELS
Eric R. Anschuetz
MIT Center for Theoretical Physics Cambridge, MA 02139, USA eans @mit. edu
ABSTRACT
One of the most important properties of neural networks is the clustering of local minima of the loss function near the global minimum, enabling efficient train- ing. Though generative models implemented on quantum computers are known to be more expressive than their traditional counterparts, it has empirically been observed that these models experience a transition in the quality of their local min- critical number of parameters, all local minima far from the global minimum in function value; above this critical parameter count, all local minima good approximators of the global minimum. Furthermore, for certain class of quantum generative models, this transition has empirically been observed occur parameter counts exponentially large in the problem size, meaning practical training of these models is out of reach. Here, we give the first proof of this transition in trainability, specializing to this latter class of quantum generative models. We use techniques inspired by those used to study the loss landscapes of classical neural networks. We also verify that our analytic results hold experimentally even at modest model sizes.
ima. Namely, below
INTRODUCTION
1.1 MOTIVATION
One of the great successes of neural networks the efficiency at which they are trained via gradient- based methods. Thouug training algorithms often involve the optimization of complicated, non- convex, high-dimensional functions, training via gradient descent in many contexts manages to con- verge to local minima that good approximations of the global minimum in loss function value. This phenomenon has begun to be understood the context random matrix theory. particularly when applied to dense classifiers (Choromanska al. 2015 Chaudhari & Soatto 2017).
Quantum generative models hold great promise in their ability to sample from probability distri- butions out of the reach of classical models (Arute et al.) 2019 Gao al. 2021). Though deep quantum generative models are helieved to be difficult to train due to vanishing gradients (McClean al. 2018 Cerezo et al. 2021 Marrero et al. 2020). the situation for shallow models is murkier.
Some shallow quantum models have empirically shown great promise in being trainable (Wiersemal al. 2020 Kim et al. 2020; Kim Oz 202T). while others have empirically been shown to suffer from poor distributions of local minima Kiani et al., 2020) Campos et al. 2021). Numerically, all of these models have been seen to experience a phase transition in trainability: below some critical depth, local minima are poor approximators of the global minimum. Above this critical depth, they are good approximators. This transition has been poorly understood analytically, as typically the dis- tribution of local minima monotonically improves as the size of the model increases (Choromanska ctt al. 2015 Chaudhari & Soatto 2017).
1.2
OUR CONTRIBUTIONS
In this work, in the training of a certain class of quantum generative models. To achieve this, we first show that this class of randomized quantum models is approximated in distribution by Wishart random field
the first to analytically show the presence of a computational phase transition

---

Published as a conference paper at ICLR 2022
on the hypertorus. We are then able to use techniques from Morse theory exactly caleulate the distribution of local minima (and general critical points) of this random field. Finally, we analyze this distribution in the limit of large model size, and analytically show the presence of this trainability phase transition. Roughly, we show that in this limit the expected density of local minima for a model with p parameters and Hilbert space dimension m (exponential in the problem size) loss value 0 - E S _ follows a generalization of the beta distribution (Gordy 1998) :
E [Crto (E)] ~ m & - -2E))
(1)
This distribution experiences a transition in behavior at p = 2m: when p < 2m, local minima exponentially concentrated (i.e. with width m= far away from the global minimum E 0, implying poor optimization performance in this regime. When p 2 2m, this distribution is exponentially concentrated at E' = 0, implying good optimization performance. We also verify our results numerically, demonstrating this concentration of minima even at small problem sizes.
For the class of quantum generative models we consider, our results mirror the empirical results Kiani et al.] (2020); Campos et al. (202I) in that only unreasonably overparameterized quantum models have good local minima. Though these results are pessimistic. we emphasize here that our results only apply to a certain class of quantum generative models. We are also able to give a heuristic explanation based on our proof techniques as to how one may be able to construct models of reasonable size that are still trainable at the expense of computational overhead in implementing the model, as seen empirically in Wiersema et al. 22020; Kim et al. (2020); Kim & Oz (202I).
2 PRELIMINARIES
2.1 QUANTUM GENERATIVE MODELS
quantum system of size n naturally represented by a quantum stute, which a normalized vector (15) E C² Here, we use the typical physics notation |-) to denote a vector, instead of (say) th, when we are describing quantum state. A quantum state in C2 can be considered a generalization of probability distributions over 2n states (i.e. over states described by n bits), where the norm squared of entries of (e)) give the distribution. The task in quantum generative modeling is to prepare a state (1)) that is close under some metric to a given target state (hharge))
As operations that map probability distributions to probability distributions are naturally described by stochastic matrices, operations that map quantum states to quantum states are naturally described by unitary matrices; equivalently, they described by the matrix exponentials of 2n x 2" skew- Hermitian matrices. Multiple quantum operations can then be described by the sequential matrix multiplication of various matrix exponentials. It is then apparent that can construct quantum generative model by parameterizing these matrix exponentials, giving rise to the layered structure:
0 =
II U. (0) (b) = II 10. (
where here is the depth of the model and Qi are fixed Hermitian matrices. Typically, is poly- nomial in n, i.e. logarithmic in the dimension of the initial state vector (vo). In most quantum generative models, various 0; are completely dependent, e.g. 0, = 0.+5 for all i (Romero et al.) 2018). For simplicity, we assume throughout this work that each independent parameter appears constant number times in the model, and the total number of independent parameters is given by p = q/r. Though the linear nature of the model may be surprising, this model structure (for large enough depth q) is known to be a universal approximator of all (pure) quantum states, even for fixed number of allowed Q: (Solovay) 1995, Kitaev] 1997).
For completely general (i.e. dense) Qi in equation 2 the model is not efficient to implement on quantum computer. Thus, due to their efficiency in physical implementation, these Q, are typically taken to be members of the n-qubit Pauli group IP,, which is a generating subset of the additive group of all n x n Hermitian matrices. The Pauli group is also convenient to study analytically, as is the normalizer of the group (called the Clifford group). The assumption that each Q₂ is Pauli operator also allows us to use single parameter 0 for each layer of the model without loss of generality; in principle, more parameters can describe each layer by parameterizing sparse Q: However, as the
2

---

Published as a conference paper at ICLR 2022
Pauli group generates Hermitian matrices, this is special case of the class of models we consider here (at the expense of larger and new dependencies among the 8,).
In quantum generative modeling, we are in many cases given a 2" x 2" Hermitian matrix H (called the problem Hamiltonian) where ( is the eigenvector associated with the smallest eigenvalue of H (called the ground state). In this formulation, optimization proceeds via the minimization of:
often not given the target state (rarga)) directly. Instead,
FVOA (0) (0) H 10).
(3)
In physics notation, (0) is the conjugate transpose of the complex vector (0). Assuming no degenera-
cies in the eigenspectrum of H and sufficiently expressive model, the minimizer (0)) of equation
is the ground state of H. up to overall phase due to the quadratic nature of equation 3 Assuming H efficiently expressible as the weighted sum of O (poly (n)) Pauli matrices, equation 3 and its gradients can be efficiently measured on quantum computer (Peruzzo et al. [0014] Romero et al. 2018). This and similar formulations of quantum generative modeling with equation 3 as the loss function are called variational quantum algorithms (VQAs) (Peruzzo et al. 2014). Generally, the goal of these algorithms is to find the state (0) that optimizes equation 3 up to potentially some con- stant additive error in loss. Though there are other formulations of quantum generative modeling, we here focus on VQAs as they do not require coherent access to data [/rarger), which is generally believed to be difficult (Aaronson) 2015
Typically, models VQAs come in one of two flavors: Hamiltonian agnostic models, and Hamil- tonian informed models. Hamiltonian agnostic models are constructed such that the Q, present in the model definition are independent of H, and are generally more efficient to implement. This is most analogous to the case in classical generative modeling, where the model structure is usually independent from the specific choice of data distribution. We prove the existence of computational phase transition for class of Hamiltonian agnostic models this work. We also give some heuristic and numerical evidence that similar transition exists for Hamiltonian informed ansatzes, but that the trainable phase is more easily reached.
2.2 RANDOM FIELDS ON MANIFOLDS
As in previous results on the loss landscapes of machine learning models (Choromanska et al. 2015 Chaudhari & Soatto 2017), we will map the distribution of randomized class of quantum genera- tive models to a random field on a manifold. This will then enable us to use standard mathematical techniques to study the distribution of critical points of the model.
Though they can be expressed in many ways, here we will be interested in random fields of the form:
FRF (a) x
Σ
on ......0 Oi
0g .....-
Here, M is some point on a manifold, and J is a random variable. In the context of most studies of machine learning loss landscapes, M is typically the hypersphere and J a symmetric matrix of i..dd Gaussian random variables, i.e. Gaussian orthogonal ensemble (GOE) matrix.
We will instead find that VQAs are naturally described as Wishart hypertoroidal random fields (WHRFs). For these models. the manifold M is a tensor product embedding of the hypertorus into exponentially large Fuclidean space; that is, points on this embedding are described by the Kronecker produet:
COS (0:) sin (0:)
o
(5)
for angles -I < 02 < π. Furthermore, in these models, J is drawn from a normalized complex Wishart distribution. The complex Wishart distribution a natural multivariate generalization of the gamma distribution, and is given by the distribution of the square of a complex Gaussian random matrix. Specifically, for X E Cuxm a matrix with i.i.d. complex Gaussian columns with covariance matrix Σ, the matrix
W
X X m
(6)
3

---

Published as a conference paper at ICLR 2022
normalized complex Wishart distributed with scale matrix Σ and degrees of freedom. We will find that the degrees of freedom m will greatly affect the distribution of local minima of the WHRF, and thus also of the class of quantum generative models that consider.
3 QUANTUM GENERATIVE MODELS AS RANDOM FIELDS
We first show that a certain randomized class of Hamiltonian agnostic VQAs can be expressed as WHRFs. This will allow to more easily study the critical points of the model using techniques from random matrix theory. Though we leave the full statement and proof for Appendix A we give an informal statement and discussion here.
Theorem (VQAs as WHRFs, informal). Consider the class of models
0 II U. (0) 1o0
II 10,Q: 11/0) ==1
where each Q; is drawn uniformly from the Pauli group Fr, and (bb) is the first column of uniformly random member of the Clifford group. Let p be the number of distinct 0,, and let = q/p. Under reasonable assumptions on the eigenvalues of H (with minimum eigenvalue x1 and mean eigenvalue
A), the random loss function
(0) H (0) A1
FR (0)
(8)
X À1
converges in distribution to the random field
2 Σ
FWHRF (0)
Win Wip Re M.n,, Wzg Wap
(9)
where w are points on the hypertorus (5 xp parameterized by 0 and J complex Wishart random matrix normalized by its number of degrees of freedom m.
Note that for convenience, we have shifted and scaled the typical VQA loss such that it is always greater than zero and independent from overall scalings of the problem Hamiltonian.
In the course of this mapping, we find that the degrees of freedom of the Wishart matrix J (formally a real number) is given by the ratio:
H |1l
2
(10)
H
Here, Il.ll, denotes the nuclear norm, and ||- the Frobenius norm. Generally, this ratio is exponen-
tial in n, particularly when modeling the class of ground states typically represented by VQAs (Pe- ruzzo al. [0044] Farhi al. 2014 Romero et al., 2018). Though we are unable to prove Theorem for Hamiltonian informed models, there are heuristic reasons to believe that they are described by similar random field with m O (poly (n)), as opposed to equation 10 (see Appendix A.3 and em- pirical evidence in Sec. 5). We will later find that a number of independent model parameters p that twice the degrees of freedom of the matrix J marks the transition from the underparameterized to the overparameterized regime of FWHRF, where the quality of local minima improves.
The general idea for showing this equivalence relies on the path integral expansion of the VQA loss function. Effectively, this is just Taylor expansion of the unitary matrices composing the model, which exact even at a finite number of terms. One can then show that terms in this expansion can be assumed independent with negligible error in distribution, and then show that the resulting random process is asymptotically a WHRF. The reasonable assumptions on the eigenvalues of H essentially just requirement that the eigenvalues of H are not "unnaturally" spread out; for the quantum states VQAs typically model, this is never the case. We give a full description of these requirements with the full proof in Appendix
4

---

Published as a conference paper at ICLR 2022
4
THE LOss LANDSCAPE OF WISHART HYPERTOROIDAL RANDOM FIELDS
4.1 EXACT RESULTS
Having shown that VQAs can be described as WHRFs, now focus discussion entirely WHRFs. Our strategy for showing the distribution of critical points of this random field will be similar to that in Auffinger al. (013)), where similar results were shown for Gaussian spherical random fields. Namely, we will lean heavily on the Kac-Rice formula, which gives the expected number of critical points of certain index at given range of function values for random fields on manifolds. We give an informal description of the Kac-Rice formula here, with the formal version given in Appendix B
Lemma 1 (Kac-Rice formula (Adler Taylor 2009), informal). Let M be a compact, oriented manifold. Assume random field F (or on M is sufficiently nice. Then, the number of critical points of index at most with (0) E B for an open set B C R
CCrts (B)) =
det ( 1 ((F(O) B) sk}
VF =
Pa (V)
(11)
where V. is the covariant gradient, (-) is the index of " Po is the probability density of F (o) at σ,, and do is the volume element on M.
From Lemma we see that when the joint distribution of F FF, and F is known, then the expected number of critical points with function values in open B can be calculated. Per- haps surprisingly, as in the Gaussian case, the joint distribution of these derivatives for WHRFs is fairly simple. Once again leaving the full proof for Appendix C we show the distribution of the Hessian conditioned to be at critical point of function value x can be described by the shifted sum of a Wishart matrix with an independent GOE matrix. Similarly, the distribution of the gradient conditioned on the function value being is given by normal distribution.
Lemma 2 (Hessian and gradient distributions, informal). The scaled Hessian mā,0, FWHRF (wr) conditioned on FWHRF (w) = x and FIHRe (w) = 0 is distributed as
mū.j (x) = -2rmad; + rWi + rv/2maN
(12)
where W is Wishart distributed with 2m degrees of freedom, N GOE distributed, and they are independent. Furthermore, the scaled gradient mr,FFHRRr (w) conditioned on FWHRF (w) distributed as
mG (x) <2mraNk
(13)
where N& are i.i.d. standard normal distributions independent from all Waj and Nij.
With all of the pieces in place, we are able to explicitly calculate the expected distribution of local formula (with full calculations left for Appendix C). In Sec.
minima in WHRFs via the we find empirical evidence that these results hold not only in expectation, but distribution; we leave further analytic investigation of this to future work.
Theorem (Distribution of critical points in WHRFs, informal). Let
(C(a) Σ (2 ((()))
(14)
be the empirical spectral measure of the random matrix
(x))= (w+=""+++r v22aN))
(15) where W Wishart distributed with 2m degrees of freedom, N GOE distributed, and they are independent. X (x) is the ith smallest eigenvalue of C (x)). Then, the distribution of the expected number of critical points of index is of WHRF a function value >> given by
TE [Crte (F))
= =()) & T (m) 1m [erS (m((A-2rEl)dvcce))
{
(CC)) k+1 2 2rFi F(1-7)m-1 mE
(16)
5

---

Published as a conference paper at ICLR 2022
where
P. 7 2m
(17)
We call the parameter 7 the overparameterization factor. It describes the ratio between the number of parameters of the model and twice the degrees of freedom m of the model. We will later find that y governs the phase transition between underparamelerized phase of the model-whert local minima are far from the global minimum- and an overparameterized phase-where local minima are good approximators of the global minimum.
4.2 ASYMPTOTIC RESULTS AS p + 00
Though Theorem 2 gives the exact distribution of critical points, it is difficult to use in practice. This difficulty comes from the expectation over cigenvalues of the sum of independent Wishart and Gaussian matrices. Surprisingly, however, the cigenvalues of both Wishart and Gaussian orthogonal matrices converge to fixed distributions. Essentially, asymptotically in the size of the matrix, the eigenvalue distribution of all normalized Wishart matrices are the same (given by the Marchenko- Pastur distribution) and the eigenvalue distribution of all Gaussian orthogonal matrices are the same (given by the Wigner semicircle distribution).
Luckily, we can characterize the asymptotic distribution of eigenvalues of the sums of these matrices using the tools of free probability theory. Roughly, free probability theory is the probability theory of noncommutative random variables (c.g. random matrices). As the distribution of the sum of two random variables in commutative probability theory can be described by the convolution of the dis- tributions of the two independent random variables, so can the free convolution of the distributions of two freely independent noncommutative random variables. Using the asymptotic free independence of Wishart and Gaussian orthogonal random variables, we are able to show that asymptotically the eigenvalue distribution of their sum weakly converges to the free convolution of a Marchenko-Pasee Pastur distribution with semicircle distribution.
However, weak convergence is not enough; due to the exponential factor in the expectation in The- orem any large deviations from the asymptotic convergence -venn if they occur with exponen- tially vanishing probability-can potentially cause large deviations from the naive application of free probability theory. Thus, our results rely using large deviations theory show that to (logarith- mic) leading order these deviations do not contribute to the final result. This is due to the contribu- tion the expectation from the deviations being dominated by what is predicted by free probability theory. These results can be summarized via the following theorem (proved in Appendix D):
Theorem (Logarithmic asymptotics of the local minima distribution, informal). Let du be the free convolution of a scaled Marchenko-Pasten and scaled Wigner semicircle distribution, with Xg. (1). Then, the expected distribution of
the infimum of its support. Let p, m >> with L local minima of a WHRF at a fixed function value E > 0 is given by
1 In (Crlo (E))) p
In
Tq
+
(1 - E)
+ 2
1
(7 (7-1 (1)
27
27
(18)
X
2F duc +o(1).
+
In
2F
1
r
Note that, though we only prove the asymptotic distribution of local minima in Theorem expect similar theorems to also hold for critical points of constant index & (taking X + > in the integrand). The only difference in the derivation is the exact form of the large deviations of the kth smallest eigenvalue of C' (xr). This is similar to the case in Gaussian hyperspherical random fields, which are often used to model neural network loss functions (Auffinger et al. 2013
Choromanska et al. 2015 Chaudhari & Soatto 2017).
4.3 DISCUSSION OF THE CRITICAL POINT DISTRIBUTION
Let us now discuss the implications of Theorem 3 Note first that the rescaled logarithmic number of critical points diverges when q -> oc. Following the derivation closely, finds that this is

---

Published as a conference paper at ICLR 2022
due to an exponentially suppressed (when is exponential in n) gradient. We believe that this is a manifestation of the "barren plateau" phenomenon, where for many deep VQA models it can be shown that there is an exponentially vanishing variance of the gradient over the loss landscape (Mc- Clean et al., 2018: Cerezo et al. 2021] Marrero et al. 2020). This interpretation suggests that these barren plateau regions are filled with many small "bumps" that are exponentially shallow. Further- more, note that this class of random fields exhibits banded behavior in the eigenvalues. That is, local minima only exist in the band - E S Es. where Eg is the solution to
1 = 2r
(19)
This banded behavior is similar to that in the Gaussian spherical case. We will see, however, that this does not give necessarily good guarantees on the distribution of local minima. This is due to Eo being generally far from 0 when Y as p. m + co. To illustrate this, we focus now on two cases: p 2 2m (the overparameterized regime) and < m (the underparameterized regime).
4.3.1 p 2 2m
First, let us consider when p 2 2m, i.e. y 2 1. In this limit, the Wishart term of C is low-rank, and F& has support on eigenvalues < for all E > O. Therefore, the condition XE.1 > 2Er is never satisfied, and to leading order in p there are no local minima at a function value E > 0. That is, all local minima are global minima in the p - oo limit when ? 2 1. Though the choice of model is slightly different, we suspect that a related phenomenon may be what gives rise to the phase transition in training numerically observed in Kiani et al. (2020); Wiersema et al. (2020) Kim et al. (2020); Kim & Oz 202T): Campos et al. (2021).
4.3.2 p < m
When the number of distinct parameters is poly (n) and considering a physically relevant problem Hamiltonian such that the number of degrees of freedom m is exp (n), we have that p < m (i.e. < 1) for large n. In this limit, the spectral distribution L is dominated by the Wishart term of C, as its eigenvalues are O (1) while the eigenvalues of the GOE term are O (V7). Furthermore, the Marchenko Pastur distribution in this limit only has support at A 1 - O (V7). Therefore, the expected number of local minima at function value will be proportional to
{ 02E E O
11 2J-
E [Crto (E)) x -mE-olp) Em (1 (1-2E+ + O (VT))
(20)
In particular, up to shifts on the order of /7. the distribution of local minima is roughly that of a compound confluent hypergeometric (CCH) distribution (Gordy 1998). The CCH distribution can be considered a generalization of the beta distribution, and for our parameters has mean on the order of 1 - and standard deviation the order of m m-1 Restoring the overall scaling in equation & this implies that in this limit the local minima of the variational loss function exponentially concentrate (in expectation) near half the mean eigenvalue of H A instead of the smallest eigenvalue. Even worse, the CCH distributed form of the local minima implies that, even when beginning at an initial function value well below half of the mean eigenvalue of H Λ1 the found loss will only improve by fraction of the initial function value before the optimization algorithm finds local minimum. This is insufficient to find the optimal loss to constant additive error when beginning training at a random point, as is often the goal in VQAs (Peruzzo et al., 2014). Empirically, we find that this occurs not just in expectation but also for individual model instances in Sec. 5
5 NUMERICAL EXPERIMENTS
We now test our analytic predictions using numerical simulations. First, we investigate the empirical performance of the class of randomized models we study theoretically, and give numerical evidence of things we were unable to prove. Then, we give numerical evidence that, for models dependent on the objective Hamiltonian, the effective degrees of freedom parameter m7 can be much smaller than predicted. In all cases, we numerically test the predictions of our results by modeling the ground state of the ID n site spinless Here, we take units such that the mean eigenvalue of the considered Hamiltonian (minus its smallest eigenvalue) is E 1. We give further details of our numerical simulations in Appendix B
Hamiltonian (Negele & Orland 1998) at half filling.
7

---

Published as a conference paper at ICLR 2022
5.1
EMPIRICAL PERFORMANCE RANDOM ANSATZES
(a)
30
y= 0.018
Critical point density
20
y= 0.036
10
y= 0.051
0.2
0.4
0.6
0.8
(b)
20
-ー V
y= 0.006
y= 0.013
10
y= 0.019
0.0
0.2
0.4
0.6
0.8
Energy E
Figure I: Here we plot the distribution of found local minima found after 52 separate training instances using randomized model on (a) 2 and (b) 2 256-dimensional models. Dashed lines denote the predicted region local minima will lic. Note the clustering of local minima at a finite function value when y <<
40
Critical point density
Expectation over ansatzes
Fixed ansatz
30
20
10
0.00
0.05
0.10
0.15
0.20
0.25
Energy E
Figure 2: Here we plot the distribution of found local minima found after 52 separate training instances using the randomized model, with p 48 and 2" = 64 model dimension. For even a small model size, qualitatively the expected distribution of critical points and the distribution of critical points for fixed random ansatz are in agreement.
First, we analyzed the performance of a VQA this loss function via the random model construc- tion procedure defined in Theorem[] Previous numerical results on related Hamiltonian agnostic ansatzes have already shown the concentration of local minima far away in loss value from the global minimum below some degrees-of-freedde
transition, and concentration at the global mini- mum above this transition (Kiani et al.) 2020, Campos al., (021). Here, we tracked where our analysis predicts the local minima to lie as a function of for y < 1, up to deviations on the order of / that arise from numerically considering the problem at finite size (as discussed in Sec. 4.3.2).
Concretely, for given training instance and depth layers of Pauli rotations, where each Pauli rotation was chosen uniformly from all nonidentity Pauli matrices qubits. The numbers of model layers consider typical of current physical im- plementations of Hamiltonian agnostic VQAs (Kandala et al. 2017). A summary of the normalized distribution of found local minima for the randomized model with model dimension 2" = 64, 256 is given in Figure I along with the predicted region which all local minima should lie in the + oo limit discussed in Theorem 3 See Appendix E for details on how this distribution was generated.
generated an ansatz. (0) composed of
We see that almost all found local minima lie within the predicted region, even at small p, n. In particular, for small 7, the distribution of local minima almost entirely localized within /7 of the
8

---

Published as a conference paper at ICLR 2022
predicted 1 - (in units of the mean eigenvalue of H - A1). Finally, numerically observe that the distribution local minima are qualitatively similar in expectation and for a single choice of random model in Figure 2
5.2 EMPIRICAL PERFORMANCE HAMILTONIAN INFORMED MODEL
Previous numerical results (Wiersema et al. 2020) on VQAs have shown that only moderate num- ber of model parameters suffices for efficient training when using a Hamiltonian informed model. As discussed in Sec. we believe this is due to this class of models effectively limiting the degrees of freedom m of the associated WHRF model; to test this, we performed more numerical experi- ments using Hamiltonian informed ansatz. We once again tracked where analysis predicts the local minima to lie as a function of for 7 < 1, up to deviations on the order v7.
30
Critical point density
0.018
20
Y 0.038
y= 0.057
10
0.0
0.1
0.2
0.3
0.4 0.5
0.6
0.7
Energy E
Figure 3: Here we plot the distribution of found local minima after 52 separate training instances using a Hamiltonian informed model. Dashed lines denote the predicted region local minima will lie. We see that the predicted region is overly pessimistic. We believe that this is due to the Hamiltonian informed model lowering the effective degrees of freedom m of the WHRF instance the ansatz maps to; see Sec.
We show the empirical distribution of local minima Fig. 3 for 2 256, along with the predicted region local minima should lie as discussed in Sec. 4.3.2 The predicted local minima distribution overly pessimistic (particularly at larger p). We suspect this due to the fact that the ansatz is constructed in a way that minimizes the effective degrees of freedom of the WHRF m such that is close to 1 for smaller p than is predicted analytically.
CONCLUSION
Though variational quantum algorithms are perhaps the most promising way to use the error-prone quantum devices of today for practical computational tasks, there many caveats with regard to their trainability. In particular, previous work has shown that utilizing deep quantum models that independent of the problem Hamiltonian though the model is expressive enough to capture the ground state of interest, in practice optimizing the loss function is infeasible (McClean et al. 2018 Cerezo al.] 2021 Marrero al. (2020). We extended these results by showing a particular class of random models independent of the problem instance not only can exhibit these vanishing gradients at large depth, but also has a concentration of local minima near the mean eigenvalue of the objective Hamiltonian. This is in contrast to the case in traditional neural networks, where even generic model structure tends lead concentration of local minima in band near the global minimum of the loss function.
introduce vanishing gradient phenomenon where,
Though our results may not seem encouraging for quantum generative models, we emphasize that we expect our analytic results to hold only when the model is independent of the problem Hamiltonian. Indeed, we found empirically (and heuristically) good performance for a particular Hamiltonian informed ansatz, where our analytic results seem much too pessimistic. In principle, this new way of thinking about variational quantum algorithms may inform future quantum generative model design; leave for future work the study of how various model choices may impact the distribution of critical points of the loss function positively, and how practical considerations such as noisy model implementations may play role.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
The full statement of Theorem 1 along with all of its assumptions and its proof, given in Ap- pendix A Similarly, Lemma 2 and Theorem 2 are fully stated and proved in Appendix C These results rely on the Kac-Rice formula, informally stated as Lemma [] for completeness. we give the full assumptions of this formula in Appendix [ and there also show the assumptions are met for the model we consider. Furthermore, the full assumptions and proof of Theorem 3 is given in Ap- pendix [ along with the proofs of supplementary lemmas needed to prove the statement. Finally, full details of our numerical simulations and how to reproduce the results are given in Appendix
ACKNOWLEDGMENTS
We grateful Tongyang Li, John Napp. and Aram Harrow for insightful discussion and helpful remarks regarding a draft of this work. E.R.A. is supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. 4000063445, and Lester Wolfe Fellow- ship and the Henry W. Kendall Fellowship Fund from M.I.T.
REFERENCES
Scott Aaronson. Read the fine print. Nat. Phys., 11:291-293, 4 2015. doi: 10. 10.1038/nphys3272.
Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A, 70: 052328, 11 2004. doi: 10. R..10./Phyy.e
Héctor Abraham et al. Qiskit: An open-source framework for quantum computing, 2019.
Robert J. Adler and Jonathan E. Taylor. Random Fields on Manifolds, pp. 301-330. Springer, New York, NY, 2009. ISBN 978-0-387-499 16-6. doi: 10. 10.10077978-0-3377-88 10-16887--8111666111 16-6-12.
G. Ben Arous and Alice Guionnet. Large deviations for Wigner's law and Voiculescu's non- commutative entropy. Probab. Theory Relat. Fields, 108(4):517-542, 1997. doi: 10.1007/ s0044000501 19.
G. Ben Arous, Amir Dembo, and Alice Guionnet. Aging of spherical spin glasses. Probab. Theory Relat. Fields, 120(1):1 -67, 2001. doi: 00.10077P1..000777..
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G.S.L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, et Quantum supremacy using programmable supercon- ducting processor. Nature, 574(7779):505-511 2019. doi: 10.
Antonio Auffinger, Gérard Ben Arous, and Jifí Černý. Random matrices and complexity of spin glasses. Commun. Pure Appl. Math., 66(2):165-20)) 2013. doi: 10. 10.1002//pa.21442.
Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, and Garnet Kin-
Lic Chan. Low-depth quantum simulation of materials. Phys. Rev. X, 8:011044, 2018. doi: 10.1103/PhysRexx.8.0100 1044.
Ernesto Campos, Aly Nasrallah, and Jacob Biamonte. Abrupt transitions in variational quantum circuit training. Phys. Rev. A, 103:032607, 3 2021. doi: 103. 103.032607.
M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nat. Commun., 12(1): 2021. doi: 10.10388/41447--0122222222
Pratik Chaudhari and Stefano Soatto. On the energy landscape of deep networks, 2017.
Anna Choromanska, MIkael Henaff, Michael Mathieu, Gerard Ben Arous, and Yann LeCun. The Loss Surfaces of Multilayer Networks. In Guy Lebanon and S. V. N. Vishwanathan (eds.), Pro- ceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, vol- San Diego, California. USA,
ume 38 of Proceedings of Machine Learning Research, pp. 2015. PMLR. URL http: attp:://proceccing. m.r.m.m..... mlr. press / v38 choromanska15. html
10

---

Published as a conference paper at ICLR 2022
Amir Dembo and Ofer Zeitouni. Large Deviations Techniques and Applications. Springer- Verlag Berlin Heidelberg, 2010. ISBN 9783642033117. doi: (10007/978--3642-0331111
D.P. DiVincenzo, D.W. Leung, and B.M. Terhal. Quantum data hiding, JEEE Trans. Inf. Theory, 48 (3):580-559) -580, 2002. doi: 10.1 109558.9
Morris Eaton. Chapter 8:
The Wishart Distribution, volume 53 of Lecture Votes-Monograph Series, pp. 302-333. Institute of Mathematical Statistics, Beachwood, Ohio, USA, 2007. doi: 10.1214/lnms/11 http://nm//19225111111/ 196285114.
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algo- rithm, 2014.
Xun Gao, Eric R. Anschuetz, Sheng- Tao Wang, Ignacio Cirac, and Mikhail Lukin, Enhancing generative models via quantum correlations, 2021.
Michael B. Gordy. A generalization of generalized beta distributions. Finance and Economics Dis- cussion Series, 4 1998. URL
http://wwww..ee.a.eeeeeeeeoo//// wtw.://e/eeeeeeoee/ee/ee/ees ---geneaaiizaiinn of btt.raaaeeeeoooooaaaaaaaaaaaaaaa pitrrrieetttaa--csssstorotootoo. htm
Alice Guionnet and Mylène Maïda. Large deviations for the largest eigenvalue the sum of two random matrices. Electron. J. Probab., 25:24 pp.. 2020. doi: 10. E0.1445/19-
Alice Guionnet and Ofer Zeitouni. Large deviations asymptotics for spherical integrals. J. Funct. Anal., I 188(2):461 - 515, 2002. ISSN 0022-1236. doi: 10. 11000/0ff...00...3....
Fumio Hiai and Denes Petz. Chapter 4: Random Matrices and Asymptotically Free Relation, vol- ume 77 Mathematical Surveys and Monographs, pp. 113-174. American Mathematical Soci- ety, USA, 2006. ISBN 0821841351. doi: 10.1090/surv/077.
Fumio Hiai and Dénes Petz. Eigenvalue density of the Wishart matrix and large deviations. Infin. Dimens. Anal. Quantum Probab. Relat. Top., 01(04):633-666, 1998. doi: 10.1142/
5021902579800034X.
Tiefeng Jiang. Maxima of entries of haar distributed matrices. Probab. Theory Relat. Fields, 131 (1):121-144, 2005. doi: 10.10007/004440-000-077663
Kurt Johansson. Shape fluctuations and random matrices. Commun. Math. Phys., 209(2):437-476. 2000. doi: 10. 10.10077:0002200050007,
Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-efficicen variational quantum eigensolver for small molecules and quantum magnets. Nature, 549(7671))242-222 2017. doi: 10. 10.10038nature23879.
A.I. Khuri, T. Mathew, and D.G. Nel. A test determine closeness of multivariate Satterthwaite's approximation. J. Multivar. Anal., 51(1):201 - 209, 1994. ISSN 0047-259X. doi: 10. 10.10v6/j.va. 1994.1057.
André I. Khuri, Thomas Mathew, and Bimal K. Sinha. Chapter 10: Multivariate Mixed and Random Models, volume 906, pp. 256-296. John Wiley & Sons, 2011. doi: 10.1002/978 11818811111166616 164860. ch10.
Andrea I. Khuri. The probability of a negative linear combination of independent mean squares. Biom. J., 36(8):899-910. 1994. doi: 111002//imj.4411300000
Bobak Toussi Kiani, Seth Lloyd, and Reevu Maity. Learning unitaries by gradient descent, 2020.
Joonho Kim and Yaron Oz. Quantum energy landscape and VQA optimization, 2021.
Joonho Kim, Jaedeok Kim, and Dario Rosa. Universal effectiveness of high-depth circuits in varia- tional eigenproblems, 2020.
Alexei Y. Kitaev. Quantum computations: algorithms and enror correction. Russ. Math. Surv. 52 (6): 191- 12 1997. doi: 10. 10.00000mmmmm 10..0777mm119977752000haaeeel 1997:05522naahhh00015555555

---

Published as a conference paper at ICLR 2022
V.A. Marčenko and L.A. Pastur. DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES. Math. USSR Sb., 1(4):457-43) April 1967. doi: 10.1070/
Carlos Ortiz Marrero, Mária Kieferová, and Nathan Wiebe. Entanglement induced barren plateaus, 2020.
Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nat. Commun., 9(1):4812, 2018. doi: 10.10388/444467-018-077000
John W. Negele and Henri Orland. Chapter 8: Stochastie Methods, pp. 400-446
CRC Press, 1998. ISBN 9780738200521.
URL https: /wwww rout ledge.
Com/ uu Many particle Systems/ Www.eeee-raanda///aaaaeaaa
9780738200521
Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao- Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O' O'Brien. A variational eigenvalue solver on photonic quan- tum processor. Nat. Commun., 5(1):4213, 2014. doi: 10. 10.0038/commm5213.
G.F. Pivaro, S. Kumar, G. Fraidenraich, and C.F. Dias. On the exact and approximate eigenvalue distribution for of Wishart matrices. JEEE Trans. Veh. Technol, 66(11):10537-105555 2017. doi: 10. N0.11099/V12201.27227555
Jonathan Romero, Ryan Babbush, Jarrod R. McClean, Cornelius Hempel, Peter J. Love, and Alán Aspuru-Guzik: Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz. Quantum Sci. Technol., 4(1):014008, 10 2018. doi: 10. (0.1088/2058.
(088/20589955//aad3ee 9565/aad3e4.
F.E. Satterthwaite. An approximate distribution of estimates of variance components. Biometrics Bull., 2(6): 1946. ISSN 00994987. doi: 10.2307/3002019.
Sukin Sim, Peter D. Johnson, and Alán Aspuru-Guzik. Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms. Advanced Quantum Technologies, 2(12): 2019, doi: 10.
Robert M. Solovay, 1995. Unpublished manuscript.
M.S. Srivastava. Singular Wishart and multivariate beta distributions. Ann. Statist, 31(5):1537- 1560, 10 2003. doi: 00.2214/as/1065705111
Nikolai G. Ushakov. 1. Basic properties of the funncttt pp. 1-66. De Gruyter, 2011. doi: 10.1515/97831 10935981119
Dave Wecker, Matthew B. Hastings, and Matthias Troyer. Progress towards practical quantum variational algorithms. Phys. Rev. A, 92:042303, Oct 2015. doi: 10. 1ee.110/yyeeev..2..06...
B.L. Welch. The generalization of 'Student's' 's' problem when several different population variances are involved. Biometrika, 34(1/2):28-35, 1947. ISSN 00063444. doi: 10.2307/2332510.
Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim, and Henry Yuen. Exploring entanglement and optimization within the Hamiltonian variational ansatz. PRX Quantum, 1:020319, 2020. doi: 10.1103/PRXuuatuum 1.020319.
Eugene P. Wigner. On the distribution of the roots of certain symmetric matrices. Ann. Math., 67 (2):325-327, 1958, ISSN 0003486X. doi: 10.2307/1970088.
Soonyu Yu, Jaena Ryu, and Kyoohong Park. derivation of anti- Wishart distribution. Multivar: Anal., 131:121-133 125,,, 2014. ISSN 0047-259X. doi: io0001...imma.2214.0.0000
12

---

Published as a conference paper at ICLR 2022
A VARIATIONAL QUANTUM ALGORITHMS AS RANDOM FIELDS
A.1 VARIATIONAL QUANTUM ALGORITHMS
Variational quantum algorithms (VQAs) are class of quantum generative model where one ex- presses the solution of some problem as the smallest eigenvalue and its corresponding eigenvector (typically called the ground state) of an objective Hermitian matrix H. Given a choice of generative model-often called an ansatz in the quantum algorithms literature:
0
U, (0,) (pb) [=1
II
(21)
that for some choice A closely approximates the ground state of H, the solution is encoded as the minimum of the loss function
F (0) (0) H 10).
(22)
This loss function can be computed a quantum computer efficiently, under some conditions on the matrix H. For simplicity of analysis, throughout this paper we will consider the loss function
F (0) ( H 1) ~1 A
(23)
where A is the smallest eigenvalue of H; this has the same loss landscape as equation 22 but is minimized at F = 0 (assuming sufficiently expressive 10)) and is normalized by the mean eigenvalue of H Åy In equation 21 q is referred to as the depth of the circuit, and the initial vector (i.e. quantum state) /vb)) C is fixed throughout the optimization procedure. Different choices of U, constitute different choices ansatz for the ground state of H.
Ansatz design choice generally falls in one of two categories: Hamiltonian informed ansatzes, and Hamiltonian agnostic ansatzes. Examples of Hamiltonian informed ansatzes include the chemistry- inspired unitary coupled cluster ansatz (Peruzzo et al., 2014) and the adiabatically inspired quan- tum approximate optimization algorithm (QAOA) ansatz (Farhi et al., 2014), known outside of the context of combinitarial optimization the Hamiltonian variational ansatz (HVA) (Wecker al., 2013). These ansatzes depend solely on the problem objective Hamiltonian H, and are usually physically motivated ansatzes which, some limit, have convergence guarantees. Hamiltonian ag- nostic ansatzes, conversely, depend solely on the hardware the VQA is run on, and not at all on the problem objective H. This class of ansatzes includes the gardware-efficiem ansatz (Kandala al. 2017]. These ansatzes are designed to eke out as much depth as possible in the objective ansatz (0) by using U, that can be easily implemented on the given quantum device.
Though hardware-efficient ansatzes generally can be run at larger depth than Hamiltonian informed ansatzes, the very generic nature of the ansatz circuit means this class of ansatz more difficult to train, often encountering barren plateaus in the optimization landscape that are difficult to escape from when g is large (MeClean et al., 2018 Cerezo et al., 2021 Marrero et al.] 2020). Heuristi- cally, this can be understood as Hamiltonian agnostic objective functions being expressive that it must explore essentially all of Hilbert space to find local minimum, exponentially suppressing the gradients of the loss function (Sim et al. 2019).
In this work we consider a class of ansatzes that, like the hardware-efficient ansatz, is independent of the problem instance. In particular, we consider random parameterized ansatzes of the form:
e -9.
(24)
for Pauli operators Qi, where each Q; is drawn uniformly and independently from the n-qubit Pauli operators. Throughout this paper, we will use to denote the total number of Pauli rotations in (0) as in equation 21, p to denote the total number of independent parameters 0,, and r, to denote the number of Pauli rotations governed by single independent parameter 6,. For simplicity, we will assume r; = ry = r for all j, and thus take
r
(25)
to be natural number.
13

---

Published as a conference paper at ICLR 2022
A.2 MAPPING VARIATIONAL QUANTUM ALGORITTMM TO RANDOM WISHART FIELDS
With the background of VQAs in place, we will now show the asymptotic (weak) equivalence of VQAs with the random choice of ansatz described in Appendix A. to Wishart random fields. Throughout this section, we will consider a problem Hamiltonian H on qubits, with ground state energy d and mean eigenvalue X. We also define the degrees of freedom parameter
H X1
m
(26)
H
|
whose interpretation will be discussed in Appendix AA.3 Twice the degrees freedom parameter will turn out to govern the location of the transition from the underparameterriee to the over- parameterized regime (see Appendix C). and for physically relevant Hamiltonians is expected to be exponential in (see Appendix A.3) We will also consider the Pauli decomposition of the nontrivial part of H:
A H --X Σ R,
(27)
where A is the number of terms in the Pauli decomposition and a the Pauli coefficients.
We begin by showing the convergence of class of randomized VQAs to a weighted sum of Wishart random fields at a rate Z log (n): the seemingly arbitrary shifts by the mean eigenvalue X and the ground state energy X1 here will aid in future discussion, when we approximate the weighted sum of Wishart random fields with single random field. The wide variety of assumptions will be discussed in detail in Appendix A.33
Theorem 4 (VQAs as RFs). Let (1b)) be an arbitrary stabilizer state (e.g. a computational basis state) qubits. Fix sequence of angles O, E [-T, n) such that each 0; is present times in the sequence. We let p = & denote the number of distinct parameters. Select an ansatz.
10) 1I (0)
= III FF0. (1b)
(28)
==1
i=1
by independently at random drawing each +Q; uniformly from the n-qubit Pauli group P,, and C from the n-qubit Clifford group Cn Consider the scaled and shifted
A= H -
H H-
(29)
-- 2-
-All..
where |1-1l, is the nuclear norm. Then, the random variational objective function
0 H 0) A1 (0 H 0) A1 X A1
FVDA (0)
(30)
2-n H X1ll.
has first two moments exponentially close in n as + do to those of
Sr
FXHX (w) = 2
x. H. xi.
Wi
+ 1,
(31)
i=p
where we are points on the circle parameterized by 0g and X is matrix i.i.d. complex standard jointly normal random variables. Furthermore, assuming
axl A1 <
<f())
(32)
for some (n)= = (1 their distributions are bounded in Lévy distance by Ô ((IeCA)A(o))))
Proof. The Feynman path integral representation (i.e. the exact Taylor expansion of the matrix exponentials using the fact that Pauli operators square to the identity) of the objective function equation 30 of the form
FVQA =
Σ
who wy (vol H0,,C,,,,,,, +
(33)
14

---

Published as a conference paper at ICLR 2022
where y labels term in the path integral expansion of U,
cos (0.) if 7 0
y
sin (0:)
if %/ =
(34)
is the amplitude, and We can rewrite the Feynman path integral as
Q = (-i) Irlla
Qi
(35)
i=1
P
60"
6r
PVQA+ =
X
!
X H. Xt.
wi
1,
(36)
i=1
==p
where
cos (8;)
W; =
sin (0t)
(37)
and X E x2"x is random matrix with rows
x
(Nol C
(38)
We will proceed as follows. First, we will bound the difference in the first two moments of equa- tion 36 and its equivalent, where the rows of X are i.i.d. Haar random, to be exponentially small in n. As Haar random vectors have first three moments matching those of random Gaussian vec- tors (scaled by 2- this gives the desired convergence through second moments. Then, we will show that the characteristic functions
of equation 36 and its i.idd. Haar random equivalent con- verge exponentially quickly in n for small enough x, giving a convergence in distribution at a rate ((()))())) by Ushakov (2011). Finally, convergence in distribution to equation 31 will follow A the error in the relevant higher-order moments between Haar random and scaled Gaussian vectors exponentially decays in by a generalization of Borel's lemma (Jiang 2005).
Obviously the first moment of equation 36 matches that of the i.i.d. Haar random case; off-diagonal entries in the path integral average to zero, and the diagonal entries are correct as C' is drawn from unitary 2-design (DiVincenzo et al. 2002). Let us now consider the second moments of the nontrivial parts of both, where we are concerned with terms of the form:
Corpu E (vol HQ
HQQ C(vo) (vol C' HQr HQr, C1ubi)
(39)
and how they differ from the i.i.d. Haar random equivalent
haguu EE [(vo) Ut (vo) (Wol UHU Wv)i
(40)
First, assume a == μ = v: as C drawn from a unitary 2-design DiVincenzo al. 2002), the
terms are equal. Similarly, if
Ya @ 7a ① Ya ① Tv + 0,
(41)
then both expectations are equal to zero; this is because Caßar must have an odd number of some Q, and hasp an odd number of some (or Ut).
Let us now consider when the above conditions are not satisfied. We consider simultancously terms of the form
RQ, (Wool RO Clvo) Taj + yas) (wval Ct R' C, +Wi Tus)
(42)
Le. all terms summed where unequal components of a and 7a8 (and Y/2 and 7v) swapped. Note that the parity of the permutation determines the sign of the term in equation [36 (and thus in equation 42). Here, R and are terms in the Pauli expansion of H. Consider the largest j where Ya and 7/3 differ; consider the of each pair of terms in equation 42 that have component
15

---

Published as a conference paper at ICLR 2022
permuted, but equal at all & j. Each pair of terms is of the form (with relative signs made explicit) (wol AQ, (b6) (wol Ct A'''R'',, wwo)
(43)
= = (vvol C AQ, BC (1bo A
for some A, For all Qj that commute with A' A'R'', the two terms cancel. In particular, QjA' RB" cannot be proportional to the identity. As H is traceless, both R and It' are also not proportional the identity. This can be done inductively for all j where Yo and 7/8 differ.
Consider the case where Ya + +/B F 7/ + "w: we must have that aa and Y have a coordinate i where they are both one, and where Yiu and Y are both zero (assuming equation i not satisfied). By equation 43 WLOG we can consider the product of Pauli observables between the two Q, as being not proportional
the identity. Then, averaging over Qi will yield zero. This the same as the i.i.d. Haar random case, as every term in the expansion of equation 42 must have only one of some unitary when Ya + 7/3 + 7/1- Yyu
Finally, consider the case where Yo + 7 Tv. Under this constraint, we must have the same number of terms each sum in equation[42] we call this number of terms 2 the Pauli case, every time combine terms in equation 43 introduces the anticommuting Pauli operators. As the value of the expectation over C is independent of the (nonidentity) Pauli in the expectation value, this introduces factor of every time combine terms. This gives
overall factor of 4, and we average only over
EcEcs [Wvol c SC (b))) (Nul C'S'C((e)))
(44)
for some S and S' that are equal and only R = R'. Similarly, in the i.i.d. Haar random case, only products of terms with Ya Y/p and Y "v are homogeneous in their unitaries and give nonzero expectations, yielding
2'E (wol Ut RU vo) Wol U [ob)
(45)
If R + R' (and S + S),, these are both If R = R'' (and S'), the latter is equal 2 and the former to 2 (1 + (2-))). Putting everything together and explicitly writing the overall
we have that the error in the second moment is on the order of factor of TH->;I1,"
2"
22n
A
62
2 n
(46)
H
A
where a are the coefficients of the Pauli expansion of - A. We also have that
a = 2
H
X = m ml2 2-22 | Arll?
(47)
where is defined in equation 26 Thus,
62 2- (m+)
(48)
Let us now consider the /th moment for > We will bound the higher moments of both models,
and show that their characteristic functions have infinite radii of convergence. Then, by showing that the difference in these characteristic functions vanishes exponentially in n for all x 2 0 bounded be- low (g(d)f(n)a we will show that the two models converge in distribution rate á [I((A)((n)))
By grouping terms as in equation 42 it is sufficient to only bound
]
t II
b. = (7- A1) ECwc
Σ
aj (vool Cts.C
(49)
where Siş is not proportional to the identity, S.j + Syj for all i i i'. and A is the number of terms in the Pauli decomposition of म. If term in the expansion of equation 49 contains two Siy that
16

---

Published as a conference paper at ICLR 2022
anticommute, the contribution to the moment from that term is zero C' (//b) is a stabilizer state for all C. Generally, the contribution to the moment is maximized when the Siy are "maximally dependent" that is, for d distinct Sij in term, the contribution to the moment is maximized when the Siy are generated by a cardinality [gg (d) + 1J subset of them. Thus, the contribution to the moment is bounded by 2 2-<llg(d)+1|n for some constant e (Aaronson & Gottesman 2004). Note that this also bounds the i.i.d. Haar random case. Putting everything together and using the multinomial theorem, the tth moment of the nontrivial part of both distributions is bounded by
A
b. S
Σ 2- 2-1(11((AA)))tt)) Σ4=
II
(50)
k1
KA
A
- A
This corresponds the case where = Siy = S₁ i.e. when there is maximal dependence
between the matrix elements. Here, k; indexes how many times S; appears in a term in equation 49)
and Il-Ilo denotes the number of nonzero coordinates of By equation 32 as - oo for any given A and
b. S (1 1
(z(2n))+ ls( -c
(51)
Thus, the Taylor series of the characteristic functions of both distributions have infinite radii of convergence, and both are completely determined by their moments. Furthermore, equation 51 gives us that the difference in their characteristic functions at 0 S x clg(A))(m)) is on the order of exp
Ar clg (A) as + c0. As the two distributions have equal moments for f(m)
1 S 2, can then be shown (Ushakov 2011) that the error Lévy distance between the two δ le(A))(m)m
Now that we have shown the weak convergence of our random class of VQAs to random field on the hypertorus, we can combine this result with a multidimensional generalization of the Welch- Satterthwaite equation (Satterthwaite] 1946; Welch 1947) to show that our distribution of VQAs has first two moments matching that Wishart hypertoroidal random field (WHRF). Once again, under further assumptions the spectrum of H/ we will also bound the higher moments of the two distributions to show convergence in distribution.
Theorem 5 (XHX RFs WHRFs). The random field given by equation 37 has first two moments equal to the Wishart hypertoroidal random field (WHRF)
2
FWHRF (0) m
Σ
Wiy Wi,
Wy W.g
where J ~ CW2 (m, Iae is a complex Wishart random matrix and the effective degrees of free- dom defined in equation 26 is formally a real number, but can be rounded to the nearest natural number with negligible error. Furthermore, assuming the largest eigenvalue of H as defined in equation is at most 2d for some constant e bounded below 1, their distributions are bounded in Lévy distance by 2- ((mi((x.g(mm)))
Proof. By the unitary invariance of random matrices with Gaussian entries, by diagonalizing A we can rewrite FxHx as the random field
2
FxHx (w) = H 2111.²
ui
(h+ (h+ X 2 (X.) + +x-21)
P wi
1=1
i=1
(53)
where X; is the ith column of X and f;j are the eigenvalues of Н. The sum over Kronecker products of columns is just the weighted sum of (at most) 2n independent Wishart random variables. each with single degree of freedom. It is known (Khuri et al. 1994 2011: Pivaro et al. 2017) that the first two moments of this weighted sum of independent Wishart random variables is equal (up to rounding of the degrees of freedom) to that of the single Wishart random variable
J CW20 (m, m I20).
(54)
17

---

Published as a conference paper at ICLR 2022
where is defined in equation 26
Let us now consider higher moments of both distributions. useful property of both Fxhx and FWHRF is that they are invariant under rotations on the hypertorus O w (for real orthogonal O E SO (2) SP) due to the invariance of the Wishart distribution under orthogonal transforma- tions (Eaton 2007). Due to this property, we will often take
ur = n (1,0.....00
(55)
i.c. perform calculations at fixed point on the hypertorus. For instance, by inspection of
the marginal distributions of the elements of X X x and J Srivastava 2003 Yu et al. 2014 we immediately see that
8r
Cr
X 2 x!)
Ut i=p
~ (1,1)
(56)
and
FWHRF (w) m
(( 1). .), I' (m, m m=
(57)
here, I' (k, 8) is a gamma distributed random variable with shape and scale 0. We therefore have that the noment-generating function for Fxxx (w) is
Mxnx (अ) =
II v=1
2
A1 :)
= det (1 (1-2-
(58)
H
and for FWERE (w) is
MWHRF (x) =(1
mm
(59)
Assuming the largest eigenvalue of H is at most 2 we see that these moment generating functions differ at any given 0 S x < 22mnn(1-e)n.lgffm) by at most O (2 (2-3(11e))) + m -xx3) As the two
distributions have equal first and second moments, can then be shown (Ushakov) 201T) that the error in Lévy distance between the two bounded by 2 ((mia(n,Ig(mm)))
Combining the two theorems, roughly that under reasonable assumptions on the spectrum of the random fields induced by the specific class of VQAS we consider can be approximated by WHRFs up to error the order of Ô (IR(A)(()))) A
+ mm=
m, n co.
A.3 DISCUSSION OF THE MAPPING
Let us now briefly discuss the intuition and assumptions behind the results proved in Appendix A.2 beginning with the random class of ansatzes we consider. Of course, in practice, VQA ansatzes are not chosen random. Indeed, VQA ansatzes have layered structure that precludes any indepen- dence between layers even if the layers were randomly chosen. Though this randomness assumption strong, heuristically deep enough circuits (that are independent of the problem Hamiltonian) will still look roughly uniform over stabilizer states in the Feynman path integral expansion performed in the proof of Theorem 4 giving qualitatively similar results. Furthermore, though throughout this paper we consider results in expectation over this distribution of ansatzes, we find numerically in Sec. 5.1 that our analytic results seem also hold in distribution; we therefore suspect that our analytic results in Appendix C hold more generally for individual ansatzes that are independent of the problem Hamiltonian.
Given the randomized class of ansatzes, in Theorem we show that the VQA loss function is close in distribution to that of the random field given in equation 31 (the "XHX" model). Intuitively, matrix elements
this just stems from the fact that different paths in the Feynman path integral in uniformly random stabilizer states. We then show that the eтror induced in higher moments by taking each of these paths be independent vanishes the boundedness of equation 322 to bound higher moments of the distribution. Luckily, in practice this bound holds; for extensive Hamiltonians, one expects (n) n.
co. To prove this formally, rely
18

---

Published as a conference paper at ICLR 2022
Theorem 5 extends Theorem 4 by showing that the XHX model can be written a sum of Wishart models weighted by the (scaled and shifted) eigenvalues of H, which can then be approximated by a single Wishart model. Heuristically, one can think of complex Wishart matrices as multidimensional generalizations of the gamma distribution; then, the approximation used in Theorem is just a multidimensional generalization of the Selch-Satterthwaite approximation (Satterthwaite 1946 Welch, (947). This approximation (in both the univariate and multivariate cases) is exact in the first two moments of the distribution when the effective degrees of freedom m given in equation 26 is allowed to be real. In practice, m is rounded to the nearest natural number, inducing slight error in the approximation. Generally, errors in higher moments in the Welch Satterthwaite approximation may be large when the moments of the approximated distribution is large, particularly when the coefficients of the sum can have arbitrary sign and are at different scales (Satterthwaite) 1946] K 1994). However, for physically relevant Hamiltonians, the spectral radius is much smaller than 2 and the coefficients of the sum are approximately equal. We show that under such conditions, errors in the moment generating functions vanish m, n at the given rate.
The effective degrees of freedom m as in equation 26 can be interpreted as roughly a signal-to-noise ratio of the mean eigenvalue of H - and generically is at least exponentially large in n (for small eigenvalue spacings, as is typically found in physical Hamiltonians studied with VQAs (Peruzzo) et al. 2014, Farhi et al., 2014: Romero al., 2018)). We show in Sec. [43.T that m sharply dictates the variational loss landscape; for a number of independent parameters 2 2m, local minima con- centrate near the global minimum. Conversely, for p bounded below 2m, local minima concentrate far away from the global minimum. This would imply that for the class of randomized ansatz we consider here, training large instances infeasible. However, consider an ansatz that is allowed to depend on the problem instance H, such as in the Hamiltonian variational ansatz (HVA) (Wecker) al. 2015). With a clever enough ansatz, one can in principle "reweigh" the coefficients of equa- tion 53 by having a nonuniform distribution over stabilizer states in the Feynman path integral ex- pansion of equation 33) effectively making m smaller. This would be consistent with what was numerically investigated in prior work (Wiersema et al. (2000) (and in Sec. 5.2). where it was shown that even for a modest number of parameters the distribution of local minima concentrate near the global minimum for the HVA. We leave further investigation in this direction for future work.
Finally, we note that all of our asymptotic equivalence results so far have been shown to converge at rate
p p= lg f n/A,
(60)
which is typically 2 lg (n) for physically relevant (i.e. two-local with arbitrary range, molecular in the plane wave dual basis (Babbush et al. 2018). etc.) Hamiltonians. In Appendix [D] we give the loss landscape of WHRFS (equation 52) as p.m + oo, taking into account large deviations in p. If grows as 52 (lg (p)). then in principle uncontrolled large deviations in the convergence of VQAs to WHRFs will dominate the asymptotics of the landscape (equation [8). In particular,
with probability ~ p deviations of the eigenvalues of the Hessian on the order of the eigenvalues themselves can occur, which are then "blown up" by factor exponentially large p if all deviations constructively interfere. Thus, though equation 18 holds for WHRFS, it does not necessarily hold for VQAs when p p= Ω (Ig (p)). the deviations of eigenvalues of the Hessian due to the mapping from VQAs to WHRFs are roughly independent between eigenvalues, however, then these deviations are further exponentially suppressed in p. and the result holds independently of how p scales with n. We believe in practice this is what occurs, and see numerically in Sec. 5.T that our analytic results hold well even when p> >> n.
B THE KAC-RICE FORMULA AND ITS ASSUMPTIONS
For completeness, we state the formal version of Lemma D with all assumptions here. We borrow heavily from (Adler & Taylor, 2009). By V. we mean the covariant gradient of f.
Lemma (Kac-Rice formula (Adler & Taylor 2009)). Let M be a compuct, oriented, N- dimensional Ct manifold with C² Riemannian metric 9- Let B C R be an open set such that O has dimension K - 1. Let f M > RKK be a random field on M, and let i (-) denote the index of Furthermore, assume that:
1. All components of f. f, and f are almost surely continuous and have finite variances over M.
19

---

Published as a conference paper at ICLR 2022
2. The marginal density P. (V (t)) of f at M is continuous at V 0.
3. The conditional densities ( (t), f (t)) are bounded above and continuous
at f O, uniformly in E M.
4. The conditional densities Ps (det (V2 (t) (t) 0) are continuous in the neighbor- hood of det (V² 0 and V (1) = O, uniformly in E M.
5. The conditional densities Pt (J (1) V (1) 0) are continuous for all I and for all V in a neighborhood of O, uniformly in E M.
6. The Hessian moments are bounded, i.e.
M <0.
sup max I REM JJ
(61)
7. The moduli of continuity with respect to (the canonical metric induced by) g of each com- ponent of f. f, and 2 all satisfy
IP ([w (n)²)
(62)
for all e > 0 as +
Then,
E
Crthh (B)
= Po (V) M
(63)
x E |lett (
sk} Vf = =0] do
where der is the volume element induced by g on M.
It obvious by Lemma 4 that conditions 2-6 satisfied by WHRFs given B (0, u). Further- more, as F is a polynomial in {cos (0.), sin (0:)). and its derivatives are continuous for any value of the components of m m-1J, and all have finite variance. Similarly, it is easy see that the mod- ulus of continuity of f and its gradients go as Jny" as - 0+, where J is the largest component of m -JJ. As the distributions of the components of Wishart matrix have exponential tails, the probability that J = Ω (1" is indeed o Nn and therefore all conditions are satisfied by WHRFs.
C THE LOss LANDSCAPE WISHART HYPERTOROIDAL RANDOM FIELDS
C.1 THE JOINT DISTRIBUTION OF FWHRF AND ITS DERIVATIVES
In order to utilize the Kac-Rice formula (Lemma 3). we must calculate the joint distribution of the random field
FWIIRE (0)
Wi Wi, J Ja W.y ... Weg
(64)
with its derivatives. In the course of proving Theorem 5, already have shown that the function value is gamma distributed (see equation 57). Here, we explicitly calculate the distribution of the Hessian when given the function value and that the covariant gradient is zero, and also calculate the distribution of the gradient given the function value. We will heavily lean on the rotational invariance property of the distribution discussed in the proof of Theorem S with once again the fixed point with all 0; = O. Note that for the given embedding of the hypertorus into R the Christoffel symbols are zero (i.e. we are considering the Euclidean hypertorus) and thus for the most part we can ignore the distinction between covariant and normal derivatives. Here, we choose local coordinates 0 such that:
cos (0,)
(65)
sin (f.)
20

---

Published as a conference paper at ICLR 2022
Perhaps surprisingly, will find that conditioned on being at critical point specified energy, the Hessian takes the simple form of a normalized and shifted Wishart matrix summed with nor- malized GOE matrix. The gradient conditioned on the function value is similarly simple, given by independent Gaussian variables.
Lemma 4 (Hessian and gradient distributions).. The sealed Hessian md,0,Fwrrr (w) conditioned on FWIRF (w) = x and On FWIRF (w) = 0 is distributed as
mCij (x) -2rmadd; + + + rV2ma
(66)
where W Wp (2m, Ip) and N GO are independent. māg FWURF (w) conditioned on FWIRF (w) = x is distributed as
Furthermore, the scaled gradient
m&g (z) /2mraN
(67)
where Ng are i.dd standard normally distributed random variables independent from all Wag and Nig.
{1.2] xP be the vector with the ith component equal to 2 and all others equal to 1, (i, similar with both the ith and jth component, and b the vector with all components equal to 1. Taking derivatives explicitly yields
Proof. Without loss of generality we take w n. Let
m0; FWHRF (n) = 2 Re (J(..b.....)) b). oo +... + 2 Re ((. (3(.......(.....))
(68)
and
mm0:0,FWHRF (n) = 2rd:jJ(b....... b)....,,
+ Re ((....).......,........... b) + Re (
+ 2 Re (J.......b.bbbb....... b3) + 2 Re J(a. ().b.... b)} + 2 Re (Jib..... b......b.).(.0....bbbb)) b)} +... + 2 Re (J(b.... (b..))
(69)
As J is a Wishart matrix with identity scale matrix, it can be written as X Xt for X a 29 m matrix with iid. standard complex normal entries. By performing
LQ decomposition of X.
one can then by inspection determine the distributions of the entries of J (Srivastava) 2003 Yu
et al. 2014). For ease of notation, we let т : {1,2]** x - fl..... 2?) be a mapping between representations of the indices of J. with the convention ((b.... b)) 1. We then find (taking ((t,..., 2)) < ((i...., 2)) WLOG) that
b). b) 2m 2mFFIIRE FWIRR (n),
(70)
2 Re (Je.....),.(0....))) v 2m FHRF (n
(71)
Re (J b)) 22mF (i.J.......
(72)
and, for 7 ((,...., b)) s m,
2 Re J.....,,... = v
(((.....))) b1)-1
b))-
+
Σ
(1).(1)...))) +
Σ
M, b) (w.).
1=1
(73)
and otherwise
2 Re
= Σ
M, (y b) (),
p=1
(74)
#=1
Here, M and M are symmetric with off-diagonal entries i.idd drawn from the standard normal
distribution, and [y-(()) M²-10))--- has entries i...d. drawn from I (m - 1, 1, Note that each 2T is chi-square distributed with 2 (m + 1) degrees of freedom; therefore, equa- tion 73 and equation 74 can be considered elements of real Wishart matrix W with 2m degrees
21

---

Published as a conference paper at ICLR 2022
of freedom. Also, note that equation 73 and equation 74 are independent of F (n)) when
conditioned on FWHRF (n) = x = 0. * O, the condition FHHe (n)) = is equivalent to
taking each sum over the elements of M from j 2 instead of μt 1, which is equivalent to taking
the convention ((b..... ..... b)) 29 and shifting the indices of M and M. Therefore, the (scaled) Hessian conditioned on FWHRF (n) - and Ōn FWHRF (n) = 0 is distributed as mūij (x) = - 2rmzó. + (O.W.OT) OO),) +
2mxNiyg
(75)
here, N GOEp (with the convention that diagonal entries N (0, and off-diagonal en- tries N (0, 1)), and O is matrix such that Osp = if and only if - (H) is of the form (b. ......... 2, ....,,,,,, b). and is otherwise equal The invariance of the Wishart distribution under
orthogonal transformations and partitioning (Eaton 2007 SSrivastaval 2003) leads to the final re- sult.
C.2 THE EXACT DISTRIBUTION OF CRITICAL POINTS
Given the joint distribution of FWIRF, its gradient, and its Hessian, we are now equipped to calculate the expected number critical points of a given index & using the Rac-Rice formula (Lemma 3 Theorem (Distribution of critical points in WHRFs). Les
(C(a) - Σ (1
1 P
(76)
be the empirical spectral measure of the random malrix
C (x) (W (W+ +22NN)
(77)
where W Wp (2m, Ip) and N FO are independent and X (x) is the ith smallest eigen- value of C (x). Then, the distribution of the expected number of critical points of index at an
energy E >> of FWHRE is given by
E. [Crl (F)]
= π & (m) ( m000"" [05 (1((A-2rEE)dvcce))
(1ole) 2 2rFi F0--)mm-
mE
(78)
where
? = P
(79)
2m
Proof. As discussed in Appendix B the assumptions of the Kac-Rice formula (i.e. Lemma satisfied. Furthermore, due to the invariance of the Wishart distribution with respect to rotations on the hypertorus (Eaton 2007 Srivastaval 2003), we can integrate out the volume element indepen-
dently; the volume of (81)* x2 is
dw = (2t))²
(80)
(
Additionally, we have from Lemma 4 that the probability density of the gradient vector being zero any w conditioned on HWHRF (w) x is
4Ttr
Pw V HwHRF (w) 0 HWHRF (w) x)
(81)
m
Taking the expectation over & via equation 57 and using the Hessian distrribution from Lemma have from Lemma that
y T (m) -1 (1+7)m
E [Crt& (B [))
E
(82)
x EC(x) [n([l([))222il]))) (m1 { {2c(1) > 2rx (11 dr.
Taking the derivative of this cumulative distribution with respect F. yields the final result.
22

---

Published as a conference paper at ICLR 2022
D LOGARITHMIC ASYMPTOTICS VIA FREE PROBABILITY THEORY
Though equation 78 is exact, it is difficult to use in practice. Luckily, we are able to use a surprising fact about the eigenvalue distributions of Wishart and GOE matrices; asymptotically. the empirical spectral distributions of these matrices weakly converge to fixed distributions. Concretely, in the
limit p + where y = 2m is held constant, the eigenvalue distribution of W/2m where W Wp (2m, Ip) weakly converges to the Prrchenko-Pasitue distribution (Marčenko & Pastur 1967):
dPMP. = (1- (efr>>1)6(A))) (2) 2 V (1+ vx)² - ->) (A-(1-1) (1-v))²) (1-(t-v)))aa dd. (83)
Similarly, the eigenvalue distribution of N VP where N ~ GOE, weakly converges to the Wigner semicircle distribution (Wigner I958):
d/s.c. /4 4 X2
(84)
2T.
Furthermore, by using free probability theory one can find the asymptotic distribution of eigenvalues for weighted sum of these matrices, given their eigenbases are in "generic position" with respect to each other. We now give brief review of free probability theory- at least in the context of random matrix
Later, we will also briefly review large deviations theory, which we use to bound the probability of large deviations from the weak convergence of the eigenvalue distributions of Wishart and GOE matrices. Note that, as we are unable to control large deviations in Theorem 4 in principle large deviations in the weak convergence of VQAs to WHRFs could dominate the large deviations in WHRFs; however, as discussed in Appendix A.3 this provably does not occur at shallow enough depths with respect to n, and there are reasons to believe does not occur even at large depths (which additionally give numerical evidence for in Sec.
We begin by reviewing the techniques in free probability theory and large deviations theory that we use in studying the asymptotic behavior of equation 78
D.1 FREE PROBABILITY THEORY
Free probability theory is the study of noncommutative random variables. Specializing to random matrix theory on N N matrices, we define the unital linear functional
1 N
o (X)
E [tr (X) [tr
(85)
as the free analogue of the expectation. Note that the eigenvalues of a matrix A are completely constrained by the trace of powers thereefree, one can study the average distribution of the eigenvalues of a random matrix A via the moments & (A*). Free independence (or freeness) is a generalization of the notion of independence in commutative probability theory to free probability theory. the context of random matrix theory, two N x N random matrices A and are said be freely independent if the mixed moments are identically zero; that is,
& ((At>: o ()" (D (B**)) ( o (A"*)) (L o (B*x)) =
(86)
for all n,, m4 N. Roughly, the free independence of two random matrices means that their eigen- bases are in "generic position" from one another.
Taking the analogy with commutative probability theory further, the analogue of the moment- generating function associated with the distribution of a random variable is the Stieltjes transform of the measure Jr:
du du(())
Gμ Gp (z)
(2)=
(87)
z-t
which can be inverted via the Stieltjes inversion formula:
du (1)
lim Tm (G,z + iie) π. c-00+
(88)
Similarly, the free analogue of the -eeneaatggenerating function is the R-transform, which can be defined via the Stieltjes transform as the solution to the implicit equation:
Ry (G,, (=)) +
(89)
G (2)
23

---

Published as a conference paper at ICLR 2022
The R-transform is important in that, if two random variables A and B are freely independent with probability measures μA and by respectively, the probability measure μA+B of A + satisfies
RpA+B Rya + Rys
(90)
This can be interpreted as the free analog of the additivity cumulants for commutative random variables. The probability measure UA+B is called free convolution of μa and μ,, and is denoted using the notation
μA+B MA + HBB
(91)
Thus, given the probability distributions of two free random variables A and B, there is a prescription for determining the probability distribution of their sum by taking their free convolution, just as the convolution in commutative probability theory describes the distribution of the sum of random variables.
D.2 LARGE DEVIATIONS THEORY
In order to bound the probability of large deviations from the weak convergence of the eigenvalue distribution C' to its asymptotic limit we will use results from large deviations theory, which we briefly review here. A sequence of measures { is said to satisfy large deviation principle in the limit - oo with speed s (n) and lower semicontinuous rate function I with codomain [0, oo] and only if (Dembo & Zeitouni 2010)
inf / (x) lim inf =E7
In (un (I)) S lim sup n- 8 (n)
In (un (1)) S inf (x)
(92)
n-000 8 (n)
=EF
for all Borel measurable sets that all Pn. are defined on. Here, I' denotes the closure of I' and n the interior of I'. The rate function / is said to be good if all level sets of are compact. Large deviations theory will be useful for us to bound the probabilities of large deviations of the empirical spectral distribution of (C(x)) as p + oo, and show that they do not contribute leading order in the (logarithmic) asymptotic distribution of critical points. We do this using Varadhan's 's lemma, which state now.
Lemma (Varadhan's 's lemma Demboo& & Zeitouni 2010)). Suppose {ur} satisfies large deviation principle with speed= 8 (n) and good rate function and let & be a real-valued continuous f Further assume either the tail condition
lim lim sup M-+00 n-o 8 (n)
1
(Ex.
(o())(EN))) t0 (Xn) MD])
(93)
or the moment condition for some 7 >
lim sup 1 n-ooo (n)
In (Eximan [oraloto(xx.)) <0.
(94)
Then,
lim In (Eximan (erla)o(xa))) = sup sup -x a (n)
(95)
D.3 LOGARITHMIC ASYMPTOTICS OF THE DISTRIBUTION OF CRITICAL POINTS
Equipped with these mathematical tools, prove our first result the asymptotic behavior of (C(#)) which is present in the expectation of equation 78
Lemma 6 (AA (Asymptotic behavior of (C(z)) Define G (z) as the implicit solution of the equation
Br (2) 2ny (z + 2rx) G (2)² + (z 2r (1-1)) G; (2) - -1
(96)
with the smallest imaginary part. Define
du = Im |
(97)
π
P_ is held constant. Then, the empirical spectral measure (C(x) satisfies Let p, m xc as a 3m large deviation principle as + oo with speed p² with good rate function uniquely minimized at pt with value of O.
24

---

Published as a conference paper at ICLR 2022
Proof. The empirical spectral measure of the random matrix N/VD satisfies large deviation prin- ciple at scale p², with good rate function minimized by Wigner's semicircle law [Arous & Guion- net 1997). Similarly, the empirical spectral measure of the random matrix W/ /2mm satisfies large deviation principle a scale p², with good rate function minimized by the Marchenko-Paae Pastur distri- bution (Hiai & Petz 1998). As the R-transform of the empirical spectral distribution of A satisfies the scaling property
RaA (z) A (az), the R-transform of the empirical spectral distribution of the weighted GOE term of C' is of the form
(98)
ROOE (2) yr
(99)
and the R-transform of the weighted Wishart term is of the form
2r
Wisshrr (2) - 2r7²²
(100)
By the asymptotic freeness of independent GOE and Wishart matrices (Hiai & Petz, 2006 ('C(2)
converges weakly to the fixed measure ja" with R-transform
R2 (2) = Rwisshar (z) + ROOE (z).
(101)
Equation 96 and equation equation 88 respectively.
97 now follow from inverting the R-transform R₂ via equation 89 and
We now consider large deviations in the weak convergence (C(x) w4 peg Conditioning on the empirical spectral distribution of W/2m and using the "strongest growth wins" principle (Dembo & Zeitouni 2010), we have that (A(()) satisfies a large deviation principle with speed p² with rate function given by
I (p)
inf (Juw/am (N) + K (HW//2m))
(102)
#w/22m
here, K the rate function governing convergence of the empirical spectral distribution of the Wishart ensemble (Hiai & Petz 1998) and Juw is the rate function governing convergence of the empirical spectral distribution of fixed matrix with asymptotic eigenvalue distribution Ww/2w summed with a GOE matrix (Guionnet & Zeitouni] 2002). This sum is obviously uniquely mini- mized by μ = ,u" when 7 (u²)=()
Now, we examine the asymptotic behavior the smallest eigenvalue X C(a) of C (x). Unlike the empirical spectral measure (C(()) which satisfies large deviation principle at a speed p², we will see that this eigenvalue satisfies large deviation principle at speed p, with deviations at this speed to the left of the asymptotic value X1,1-
Lemma (Asymptotic behavior of (((x)), Let X²,1 i be the infimum of the support of μr, as defined in equation 97 Then, the smallest eigenvalue X1 C((a) of C (x) satisfies large deviation principle with speed with good rate function that is infinite at y >> N and is uniquely minimized at X with value of
Proof. The limiting smallest eigenvalues AW, AA of W 1/2 and N/ vD both satisfy large devia- tion principles with speed that are infinite for X in the bulk of their respective limiting empirical spectral distributions [Johansson] 2000 Arous et al., 200T). As the proof of Lemma 6 we condi- tion large deviations of these eigenvalues (Dembo & Zeitouni 2010) and therefore have that the rate function governing X C(x)) is
7 (v) inf
(JAM (v) K (AW) + (AP)::
(103)
AW AN
here, is the rate function governing the convergence of AW, L that of AN, and that of the smallest eigenvalue C' (z) conditioned on the eigenvalue distributions of W and N. Using known results on the large deviations of the smallest eigenvalue of the sum of two matrices with fixed eigenvalues (i.e. JAw,x, AND (Guionnet & Maïda 2020), see that (y) is infinite for y > X and uniquely minimized at y X2 with value 0f
25

---

Published as a conference paper at ICLR 2022
Using Lemmas and
can prove the following logarithmic asymptotics on the expectation term equation 78 We will find that neither the large deviations in the convergence PC(x) or x will
contribute leading order in the logarithmic asymptoties of Crt& (E), as a speed p the only large
deviations are X| (()x) - _=1 which are dominated by lY (C()) X²21 in the expectation.
Lemma 8 (Logarithmic asymptotics of the determinant). Let dut be the spectral measure given in equation 97 with X the infimum of support. Let p. m 1 with P
2m =7 O (1). Then,
In (EC(E) (pfll((A-2 { { 2 Er }
p
(104)
/ (N 2 2r a 2rE dp (1).
Proof. As (C(E) satisfies a large deviation principle with speed p² with rate function minimized f by Lemma and as A C(E) 2r I 1, we have that the tail condition of Varadhan's lemma at speed p is satisfied (Dembo & Zeitouni 2010) and therefore
lim In (Eors) p-oopp
fe (1(((A-r { (x(( 2 22rE})
(105)
(f (1(1 2- (1))
(2)).
-sup XER
Here, 7 is as in equation T03
The supremum over À is obviously achieved when x = X by the
properties of 1 discussed Lemma 7 giving the leading order term in equation 104 The result being exact in the + co limit gives the subleading o (1).
Using Lemma 8 we can therefore finally calculate the logarithmic asymptotic distribution of local minima of WHRF.
Theorem 7 (Logarithmic asymptotics of the local minima distribution). Let dupz be the spectral measure given in equation 97 with Xε, the infimum of its support. Let p: m >> 1 with Ihe = 7 0 Then, the expected distribution of local minima of FwIRr at a fixed energy E > 0 is given by
1 In (Crto (E))) p
T4
1 (7-1-1) 1)
In
(1
E)
27
27
(106)
X 2F 2x)) duc +0
+ In
2E
r
Proof. The result follows directly from applying Lemma 8 Theorem
Note that, though we only prove the asymptotic distribution of local minima in Theorem expect similar theorems to also hold for critical points of constant index & (taking X - E in the integrand). The only difference in the derivation is the exact form of the large deviations of the kthh smallest eigenvalue of C' (æ:). This is similar to the case in Gaussian hyperspherical random fields (Auffinger al. 2013).
we
E DETAILS OF THE NUMERICAL SIMULATIONS
We now give further details the numerical simulations performed in Sec. 5 simulations via Qiskit (Abraham et al. 2019), and used standard gradient descent (via the method of finite differences) to optimize the VQA loss function
We performed all
F (0) (0) Hr. (0)
(107)
26

---

Published as a conference paper at ICLR 2022
until convergence. Hr,0 is the 1D n site spinless Hemii-Hubbard Hamiltonian Negele & Orland 1998
n-1 Hr-u=- (cle + +ctt))) E Uucfeecliet
a-1
(108)
where e is the fermionic annihilation operator. T; and U3 i.idd normally distributed in order to break translational invariance. In our simulations, these random variables were centered at T = and U 2, respectively, and each had a variance of 10-2
Our implementation of gradient descent used learning rate of 0.05 and momentum of 0.9, and halted when either the function value improved by no more than 10-5 or after 10 iterations, whichever came first. We initialized each instance at a uniformly random point in parameter space, with each parameter initialized within [-27, 27.].
To estimate the empirical distribution of local minima for the studied instances of the varitional quantum eigensolver (VQE) (Peruzzo 2014), we repeated this procedure 52 times, using a new ansatz and uniformly random starting point for each training instance. We also verified numerically that m as defined in equation 266 is at least on the order of 2 for H1,2, though we directly used equation 26 when computing 7. In all plotted instances, we normalize the energy scale by factor of CVQA, where
CVQA = X A1:
(109)
this is just the overall factor of equation 8 These units are such that the mean eigenvalue of H À in the subspace of interest is at E = 1.
In Sec. 5.2 we tested our analytic results against a Hamiltonian informed ansatz. Specifically, we used the Hamiltonian variational ansatz (HVA) (Wecker al. 2013). For the Hubbard Hamiltonian of equation 108 each HVA layer of the form
U.T (0:) -185.2 2.0., 21, -10., Hy,
(110)
Here, HT Coulomb is composed of the terms proportional to U; in HT, HT, the hopping terms on even links, and HT, HT.UUodd odd the hopping terms on odd links. We took the starting state (ub) to be the computational basis state [1) on the first 2 qubits and [0} on the other 2 qubits. To observe the effects of scaling the number of independent parameters p. we overparameterize our ansatz at a fixed overall depth by fixing the total number ansatz layers U.T.U be 6, but introduce extra parameters to govern each evolution. For instance, for a multiplicative factor 2, we double the number parameters by splitting into sum two terms
HT, Coulomb H Coulumb (H
.HT.U.Coalmb
(111)
HT. H1 even (2
evve
(112)
HT. HT.
(1))
HH(2) -T.UU.odd
(113)
and parameterize the evolution under each term separately. For f= this ansatz preserves the fermion number of the initial state; thus, for these simulations we calculate in this e-fermion subspace. For large f, this parameterization breaks the fermion number conservation the ansatz,
but still preserves the parity of the fermion number. In practice, then, the we compute should be considered an upper bound on the true 7, strengthening our empirical results.
27


Reviews:
[{"review_id": "zOF-bNNoPI0", "reviewer": "Reviewer_5aN5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n\n* The paper gives a rigorous analysis of a general result connected to an important open question in quantum machine learning, namely the ease or difficulty of finding high-quality solutions via gradient-based learning of parameterized quantum circuits. The paper's (mostly negative) result provides a useful starting point for researchers to build better quantum generative models, by avoiding the same assumptions used to derive results here.\n\n* The writing and presentation are very clean and polished, with important results given a more accessible informal statement in the main text, along with a precise and fully rigorous statement in the appendices. This goes a long ways towards making the difficult results presented more accessible to general readers.\n\n\n### Weaknesses\n\n* Despite the quality of the writing, the paper's results are still quite technical, and likely not accessible to most readers (even those working in quantum machine learning). This isn't necessarily a fault of the paper, but rather a consequence of the high technical level needed to derive results based on a non-trivial application of random matrix theory.\n\n* On the above note, I would encourage the authors to work a bit harder on including a more self-contained and accessible summary of their results for readers who can't or won't take the time to follow the entirety of the paper's technical development. This summary information is already available in a distributed form throughout the paper, with the description in the abstract doing a good job of qualitatively summarizing the main findings, and the last paragraph of Section 4.1 (along with Equation 16) doing a good job of defining the overparameterization factor and its defining role in this phase transition. However, it would be very useful to have a one-paragraph description in a more prominent place (end of introduction?), simply stating the expected quality of local minima as a function of (a) Hilbert space dimension (or number of qubits) and (b) quantum circuit parameter count.", "summary_of_the_paper": "The paper analyzes a general class of variational quantum circuits using random matrix theory, and gives a theoretical characterization of the distribution of high-quality local minima of the associated Hamiltonian loss function. A type of phase transition is predicted, where the model exhibits an abundance of high-quality local minima only at very large parameter counts, and a wide gap between global and typical local minima at more typical parameter counts. These predictions are compared with small numerical experiments, as well as previous works on this topic.", "summary_of_the_review": "Although quite technical, the paper's results are very relevant to the field of quantum machine learning, and proved in a quite general setting. I anticipate this to have a big impact on the design of variational quantum algorithms.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "u8v2GcdRQO", "reviewer": "Reviewer_F6sD", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main results are stated and proven in theorems 1,2 and 3.  Theorem 1 defines a randomized set of quantum variational problems and asserts that their loss landscape is the same as that of a random potential model with potential given by a complex Wishart random matrix.  Theorem 2 then computes the distribution of critical points of this random potential model, while theorem 3 gives its asymptotics.   This result is then interpreted to demonstrate the phase transition discussed in the summary.\nIn section 5 a numerical confirmation of the results is done on a 1d Hubbard Hamiltonian.\nIt is also suggested that a similar algorithm but using operators adapted to the Hamiltonian might do significantly better, and this suggestion is supported with citations and another numerical experiment.\n\nI found the main question well motivated and clearly asked, and an impressive variety of techniques were brought to bear on it.\nI was surprised by the basic claim that this class of models is sufficiently random to justify dropping all of the higher moments in computing the ground state energy.  The arguments given for this are explicit but intricate and while they look reasonable, I did not check them in complete detail.  I suspect that there is a much simpler argument waiting to be found, perhaps building on the comments in Appendix A.3.\nGiven this claim, the rest is conceptually straightforward but rather nontrivial to carry through successfully.", "summary_of_the_paper": "This paper obtains rather impressive results about the problem of estimating a quantum ground state energy using a variational method which could be implemented on a quantum computer.  Given a Hamiltonian H, the method generates quantum states by applying a succession of n-qubit Pauli operators to a random initial state (both chosen without knowledge of H), and measure the expectation of H.\nPrevious work suggested that there is a critical (and exponentially large) number of parameters required to get a good estimate. \nHere a theorem is formulated and proven that there is a phase transition of this type, with good estimates only above a threshold in the number of parameters, and with an explicit expression for the threshold.  The proof uses a combination of physics methods (series expansions), random matrix theory and the Kac-Rice method to count critical points of a random function.", "summary_of_the_review": "A sharp formulation and sound theoretical analysis of a well motivated and important claim, that quantum variational states which do not depend on specifics of the Hamiltonian under study, require exponentially many parameters to produce accurate ground state energies.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DLzssFrdk6X", "reviewer": "Reviewer_zxWF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Pros\n\nThe work leverages the concepts of random matrix theory to analyze the optimization\nperformance of quantum generative models.\n\n### Cons\n\n1. The paper is really hard to read. Several English grammar and word mistakes prevent\nthe readers from clearly understanding the main idea in the paper.\n\n2. A few concepts introduced in this work are either incorrect or imprecise and detailed descriptions of quantum generative circuits\nare totally missing.\n\n3. The proposed methods are not very technically sound because the barren plateau associated\nwith the optimization of QNN mainly arises from the quantum noise of NISQ devices.\nBut the work does not consider the noisy quantum circuits, which makes the work\ninsignificant in practice.\n\n4. Terminologies are introduced for granted without any explanation.\n\n5. The numerical experiments are not linked to the quantum simulation at all, and the\nexperimental simulation cannot corroborate the quantum theorems.\n\n6. I believe the paper including the abstract needs a major rewritten.\n\n## Feedbacks\n\n1. The abstract and each section contain some space that could be improved. \n\nFor example, \n\n(1) the claim “The clustering of local minima of the loss function near the global minimum” is imprecise\nbecause the local optimal minima are found but not clustered; \n\n(2) The sentence “...to local minima that are good approximations of the global minimum” is wrong because the\nlocal minima should be close to the global one but not an approximation. (e.g., approximation means you use other functions and methods to get the result.)\n\n2. The connections between local minima to the random matrix theory are still not very clear. \n\n- In particular, the authors do not take into account how to make use of their theory to improve optimization performance.\n\n3. Some key concepts related to QNN on NISQ devices are missing, e.g., barren plateau problems.", "summary_of_the_paper": "The work attempts to connect the optimization of quantum generative models with random fields on manifolds. Some theoretical and numerical analyses are provided. \n\nThe major idea is to apply random matrix theory for variational quantum circuits. When the authors provide some numerical experiments, overall the validation is not very strong and could be improved. \n\nThe connection between applying random fields and quantum circuit training is not very direct based on the current writing. Some related references in the field are missing. (e.g., [1,2]).\n\n***\n\n**Reference**\n\n1. Random matrix spectral form factor of dual-unitary quantum circuits.\" Communications in Mathematical Physics 387.1 (2021): 597-620.\n\n2. Abrupt transitions in variational quantum circuit training.\" Physical Review A 103.3 (2021): 032607.", "summary_of_the_review": "When the paper provides some attempts to combine random matrix to VQC training, the theoretical findings are not very correlated to their empirical findings. The current version is not very ready to get published and several claims and description need to be modified. \n\n\n**Additional Comments**\n\n1. The information on optimization settings (optimizers and initialization) is not provided in\nthe paper.\n\n2. Since the quantum generative model refers to a large model family, the ‘critical points’\nfor each concrete one are not the same. The paper does not show what specific models are\nused. Is it a quantum Bayesian network? Quantum hidden Markov model? Or anything\nelse?\n\n3. Many important related papers are not cited, e.g, for the expressiveness of QNN, which has to be credited from\n\n“The effect of data encoding on the expressive power of variational quantum machine learning models,” Physical Review A, 2021 - APS\n\n***\n\n### Post-Author Response \n\nI think most of my comments have been carefully covered by the authors. Thank you for your efforts during the rebuttal period. \n\nWith the current version, some of the writing, reproducible discussion, and presentation have been largely improved. \n\nI therefore increase my score to 6; one remaining place that would still improve is the current VQA experiments is limited to a single empirical case. \n\nSome of the variational circuit works have been studied in a classical-quantum format. The author could consider to add some connection to enhance potential impact of the works. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: *Summary:* 
 Study the location of local minima for quantum generative models. 

*Strengths:* 
- Rigorous analysis of an important question. 
- Clear writing with important conclusions. 

*Weaknesses:* 
- Technical writing might not be very accessible.

*Discussion:* 

Reviewers were mostly favorable about this submission. They found the topic important and the contribution significant. A main concern was that the writing might not be sufficiently self contained and the writing might not be accessible to a broad audience. Authors worked on the accessibility. In the initial review, zxWF expressed concerns about concepts, proposed methods, numerical experiments. zxWF found that the author responses carefully covered most of their comments and raised score as a consequence. zxWF still finds that some aspects could be improved, particularly in regard to experiments. F6sD found the question well motivated, the techniques impressive, and the claims important. 

*Conclusion:* 

Three reviewers are favorable about this work. Two of them find it good and one marginally above the acceptance threshold. I find the topic and the nature of the claims important. Considering the unanimously positive reactions from the reviewers I am recommending this article to be accepted. I ask the authors to take the comments from the reviewers carefully into account when preparing the final version of the paper.
Decision: Accept (Poster)