††thanks: The first two authors contributed equally to this work.††thanks: The
first two authors contributed equally to this work.

# Effect of barren plateaus on gradient-free optimization

Andrew Arrasmith  Theoretical Division, Los Alamos National Laboratory, Los
Alamos, NM 87545, USA  M. Cerezo  Theoretical Division, Los Alamos National
Laboratory, Los Alamos, NM 87545, USA  Center for Nonlinear Studies, Los
Alamos National Laboratory, Los Alamos, NM, USA  Piotr Czarnik  Theoretical
Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA  Lukasz
Cincio  Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM
87545, USA  Patrick J. Coles  Theoretical Division, Los Alamos National
Laboratory, Los Alamos, NM 87545, USA

###### Abstract

Barren plateau landscapes correspond to gradients that vanish exponentially in
the number of qubits. Such landscapes have been demonstrated for variational
quantum algorithms and quantum neural networks with deep circuits, global cost
functions, large entanglement, or hardware noise. For obvious reasons, it is
expected that gradient-based optimizers will be significantly affected by
barren plateaus. However, whether or not gradient-free optimizers are impacted
is a topic of debate, with some arguing that gradient-free approaches are
unaffected by barren plateaus. Here we show that, indeed, gradient-free
optimizers do not solve the barren plateau problem. Our main result proves
that cost function differences, which are the basis for making decisions in a
gradient-free optimization, are exponentially suppressed in a barren plateau.
Hence, without exponential precision, gradient-free optimizers will not make
progress in the optimization. We numerically confirm this by training a
parameterized quantum circuit in a barren plateau landscape with several
gradient-free optimizers (Nelder-Mead, Powell, and COBYLA algorithms), and
show that the number of shots required in the optimization grows exponentially
with the number of qubits. These results provide new insight into the training
landscapes of quantum neural networks and will inform the development of
strategies to mitigate or avoid barren plateaus.

##  1 Introduction

Parameterized quantum circuits offer a flexible paradigm for programming Noisy
Intermediate Scale Quantum (NISQ) computers. These circuits are utilized in
both Variational Quantum Algorithms (VQAs) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
12, 13, 14] and Quantum Neural Networks (QNNs) [15, 16, 17, 18]. Both VQA and
QNN approaches involve efficiently evaluating a cost function
$C(\boldsymbol{\theta})$ or its gradient $\nabla C(\boldsymbol{\theta})$ on a
quantum computer. A classical optimizer is then employed to train the
parameters $\boldsymbol{\theta}$ of a parameterized quantum circuit
$V(\boldsymbol{\theta})$ to minimize the cost.

Rigorous scaling results are urgently needed for this exciting approach to
near-term quantum computing. Gradient scaling is one of the few directions of
significant progress. The most famous gradient scaling result is the barren
plateau phenomenon [19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
33], whereby the gradient of the cost function shrinks exponentially with the
number of qubits. Various issues lead to barren plateaus, such as deep
ansatzes that lack structure [19, 21, 31], global cost functions [20, 21],
high levels of noise [22, 32], scrambling target unitaries [24], and large
entanglement [28, 29].

Without effort to avoid barren plateaus, this phenomenon can have a major
impact on the scaling of one’s algorithm. Specifically, the exponential
suppression of the gradient implies that one would need an exponential
precision to make progress in the optimization, consequently, causing one’s
algorithm to scale exponentially in the number of qubits. The standard goal of
quantum algorithms is polynomial scaling, unlike the exponential scaling of
classical algorithms. Hence, the exponential scaling due to barren plateaus
could erase the possibility of a quantum speedup with a parametrized quantum
circuit. It is therefore crucial to study barren plateaus in VQAs and QNNs in
order to understand when quantum speedup is possible.

This has spawned an important research direction of finding strategies to
avoid barren plateaus. Some examples include employing local cost functions
[20], modifying the architecture [25, 26], pre-training [34], parameter
correlation [35], layer-by-layer training [36], and initializing layers to the
identity [37]. These strategies are promising. However, more analytical and
numerical studies are needed to understand how effective they are in general,
for example, as in Ref. [38].

One possible strategy to consider is the choice of optimizer. It is widely
believed that gradient-based optimizers will be directly impacted by barren
plateaus, for obvious reasons. Moreover, higher-order derivatives are also
exponentially suppressed in a barren plateau [23], so optimizers based on such
derivatives will also be impacted. Nevertheless, there still remains the
question of whether gradient-free optimizers could somehow avoid the barren
plateau problem. This is currently a topic of debate [20, 28]. The question is
naturally made subtle by the fact that gradient-free optimizers can
potentially use global information about the landscape, rather than being
restricted to using local gradient information.

In this work, we present an analytical argument suggesting that gradient-free
approaches will, indeed, be impacted by barren plateaus. Specifically, we show
that cost function differences,
$C(\boldsymbol{\theta}_{B})-C(\boldsymbol{\theta}_{A})$, will be exponentially
suppressed in a barren plateau. This holds even when the points
$\boldsymbol{\theta}_{A}$ and $\boldsymbol{\theta}_{B}$ are not necessarily
close in parameter space. Gradient-free optimizers use such cost function
differences to make decisions during the optimization. Hence, our results
imply that such optimizers will either need to spend exponentially large
resources to characterize cost function differences, or else these optimizers
will not make progress in the optimization.

We confirm our analytical results with numerical simulations involving several
gradient-free optimizers: Nelder-Mead, Powell, and COBYLA. For each of these
optimizers, we attempt to train a deep parametrized quantum circuit,
corresponding to the barren plateau scenario in Ref. [19]. In all cases, we
find that the number of shots (i.e., the amount of statistics) required to
begin to train the cost function grows exponentially in the number of qubits.
This is the same behavior that one sees for gradient-based methods, and is a
hallmark of the barren plateau phenomenon.

##  2 Theoretical Background

Here we provide background needed to understand our results. We first consider
the cost function used to train parameterized quantum circuits. Then we
consider optimizers that can be used to optimize this cost function, with a
specific focus on gradient-free optimizers. Finally, we give background on the
barren plateau phenomenon.

###  2.1 Cost function

Consider a parameterized quantum circuit $V(\boldsymbol{\theta})$, whose
parameters will be trained by minimizing a cost function
$C(\boldsymbol{\theta})$. In this work, we consider a highly general cost
function that can be expressed in the form

$C(\boldsymbol{\theta})=\sum_{x=1}^{S}f_{x}(\boldsymbol{\theta},\rho_{x})\,.$
(1)

Here, $\boldsymbol{\theta}$ is a vector of $m$ continuous parameters,
$\\{\rho_{x}\\}_{x=1}^{S}$ are $n$-qubit input quantum states from a training
set $\mathcal{S}$ of size $S$, and $f_{x}$ are functions that encode the
problem and which can be different for each input state.

To ensure algorithmic efficiency, we assume that the number $m$ of parameters
in $\boldsymbol{\theta}$ is in $\mathcal{O}(\operatorname{poly}(n))$. In
addition we consider that any $\theta_{\mu}\in\boldsymbol{\theta}$
parametrizes a unitary of the form $e^{-i\theta_{\mu}H_{\mu}}$. We assume
$H_{\mu}$ is a Hermitian operator with two distinct non-zero eigenvalues
(e.g., $H_{\mu}$ could be a Pauli operator).

We remark that the cost function in (1) contains as special cases many
relevant applications. For instance, in a binary classification problem the
cost function is given by the mean squared-error
$C(\boldsymbol{\theta})=\sum_{x}(y_{x}-\widetilde{y}(\boldsymbol{\theta},\rho_{x}))^{2}$
[39, 40, 17, 16]. Here, the training set is given by
$\mathcal{S}=\\{\rho_{x},y_{x}\\}$ where $y_{x}$ are the true labels, and
$\widetilde{y}(\boldsymbol{\theta},\rho_{x})$ are the labels predicted by the
Quantum Neural Network. In addition, the cost of several Variational Quantum
Algorithms is covered by (1). In this case, the cost takes a simpler form,
where the training set contains a single state ($S=1$) and the cost is
$C(\boldsymbol{\theta})={\rm Tr}[OV(\boldsymbol{\theta})\rho
V^{\dagger}(\boldsymbol{\theta})]$, with $O$ a Hermitian operator [3, 4, 5, 6,
7, 8, 9, 10, 11, 12, 13, 14].

The goal is then to solve the optimization problem

$\boldsymbol{\theta}_{\text{opt}}=\operatorname*{arg\,min}_{\boldsymbol{\theta}}C(\boldsymbol{\theta})\,.$
(2)

This involves choosing an optimizer, which can either be a gradient-based or
gradient-free optimizer. Various gradient-based approaches [41, 42, 43, 44]
have been proposed for training parameterized quantum circuits, and these will
be directly impacted by barren plateaus. Optimizers employing higher-order
derivatives are also impacted by barren plateaus [23]. In this work we
consider the case when one employs a gradient-free optimization method. In the
next section we review some widely-used gradient-free optimizers.

###  2.2 Gradient-Free Optimizers

We will refer to any optimization method that only accesses a zeroth-order
oracle (i.e., does not directly access derivative information) as being
gradient free. This is a very large class of methods, but they all depend on
being able to distinguish cost function values at different points. Though our
analytical results are general to any such optimizer, we now introduce three
particular gradient-free optimizers that we will examine numerically: Nelder-
Mead, Powell’s Method, and COBYLA.

####  2.2.1 Nelder-Mead

One popular gradient-free optimization strategy is the Nelder-Mead algorithm
[45]. In this approach, one constructs a simplex in the space to be optimized
over. Then one modifies it with a sequence of reflect, expand, contract, and
shrink operations to move the simplex and then shrink it around the minimum.
These operations are chosen based on conditional comparisons of the cost
function values at each vertex as well as proposed new vertices. See Figure 1a
for an illustration these operations.

When used in an environment where the errors in those cost function values are
large enough to cause mistakes in these comparisons, however, this algorithm
is vulnerable to performing shrink operations prematurely, which slows the
optimization down and may lead to a false appearance of convergence [46]. Due
to this difficulty, one would expect the number of iterations required to
converge with Nelder-Mead to be especially bad in limited precision
environments, though we note that there are a number of modifications that
attempt to improve the method’s robustness to noise [46, 47].

Figure 1: Graphical depiction of the gradient-free optimizers considered.
Panel a shows the different operations that the Nelder-Mead algorithm performs
on the initial (grey) simplex: reflection (red), reflection with expansion
(blue), reflection with contraction (green), and shrinking (turquoise). Panel
b shows two iterations of the Powell method (with black for the first
iteration and red for the second). Note that the direction of the final step
is changed, reflecting a modified search direction. Finally, panel c shows an
illustration of a COBYLA step from an initial (grey) simplex. After fitting a
plane to the initial simplex, the method steps along the fitted slope to form
a new simplex (red). The trust region is shown as a solid blue circle. A
smaller trust region which might be used later in the optimization is
illustrated with the dashed blue circle (though for this particular step the
trust region would likely not be contracted).

####  2.2.2 Powell’s Method

The Powell algorithm [48] is another popular gradient-free optimizer that
performs sequential line searches. This method starts with some input set of
search vectors $V=\\{\boldsymbol{v}_{i}\\}$, usually just the coordinate
directions in the parameter space. Searching along each of these directions in
sequence, this method looks for the displacement $\\{a_{i}\\}$ along each
direction that would minimize the cost when only varying parameters along the
current direction. Finding the displacements $\\{a_{i}\\}$ is typically done
with Brent’s parabolic interpolation method [49], though in principle one
could use any univariate gradient free optimizer.

After sweeping through all of the search vectors, the iteration is completed
by replacing the search vector $\boldsymbol{v}_{j}$ that corresponds to the
greatest displacement, $a_{j}=\max({a_{i}})$, and replacing it with

$\boldsymbol{v}_{j}\to\sum_{i}a_{i}\boldsymbol{v}_{i}.$ (3)

By making this replacement, convergence is accelerated and the method avoids
getting stuck in a cyclic pattern of updates. See Figure 1b for a sketch of
two iterations of this method.

####  2.2.3 COBYLA

Constrained Optimization BY Linear Approximation (COBYLA) is another popular
gradient-free optimizer by Powell [50]. This algorithm constructs a simplex
and uses the $m+1$ points in the parameter space, with $m$ being the number of
parameters, to define a hyperplane to capture the local slope of the cost
function. The algorithm then replaces the highest cost function value point on
the simplex by stepping from the lowest cost point along the direction of the
slope. The method steps as far as possible along this estimated slope while
staying within a lower bound on the radius of the trust region.

The lower bound on the size of the trust region is decreased when the
algorithm detects that is has stopped making progress, allowing the method to
converge. Note, however, that the size of the trust region never increases in
COBYLA. An iteration of this method (showing a shrinking trust region) is
sketched in Figure 1c.

###  2.3 Barren Plateaus

When the cost function exhibits a barren plateau, the cost function gradient
vanishes exponentially with the system size. Without loss of generality we
consider here the following generic definition of a barren plateau.

######  Definition 1 (Barren Plateau).

Consider the cost function defined in Eq. (1). This cost exhibits a barren
plateau if, for all $\theta_{\mu}\in\boldsymbol{\theta}$, the expectation
value of the cost function partial derivative $\partial
C(\boldsymbol{\theta})/\partial\theta_{\mu}=\partial_{\mu}C(\boldsymbol{\theta})$
is $\text{E}_{\boldsymbol{\theta}}[\partial_{\mu}C(\boldsymbol{\theta})]=0$
and its variance vanishes exponentially with the number of qubits $n$ as

${\rm
Var}_{\boldsymbol{\theta}}[\partial_{\mu}C(\boldsymbol{\theta})]\leqslant
F(n)\,,\quad\text{with}\quad
F(n)\in\mathcal{O}\left(\frac{1}{b^{n}}\right)\,.$ (4)

for some $b>1$. As indicated, the expectation values are taken over the
parameters $\boldsymbol{\theta}$.

We remark here that, as shown in Definition 1, the barren plateau phenomenon
is a probabilistic statement. In fact, from Chebyshev’s inequality we know
that ${\rm Var}_{\boldsymbol{\theta}}[\partial_{\mu}C(\boldsymbol{\theta})]$
bounds the probability that the cost function partial derivative deviates from
its mean of zero as

$P(|\partial_{\mu}C(\boldsymbol{\theta})|\geqslant c)\leqslant\frac{{\rm
Var}_{\boldsymbol{\theta}}[\partial_{\mu}C(\boldsymbol{\theta})]}{c^{2}}\,,$
(5)

for any $c>0$. In practice this means that by randomly initializing the
parameters $\boldsymbol{\theta}$, there is a high probability that one ends up
in a flat region of the landscape where the gradients are exponentially
suppressed.

Let us now discuss different mechanisms that can lead to barren plateaus in
the cost function landscape. As shown in the seminal work of Ref. [19], deep
random unstructured circuits which form $2$-designs on $n$ qubits will exhibit
barren plateaus. Here we use the term deep when the depth of the ansatz is in
$\mathcal{O}(\operatorname{poly}(n))$. For instance, as shown in [51, 52, 53]
local circuits will form $2$-designs when their depth is in
$\mathcal{O}(\operatorname{poly}(n))$.

The barren plateau phenomenon was extended in [20] to a type of shallow depth
ansatz known as the layered hardware efficient ansatz, where random local
gates act on alternating pairs of neighboring qubits in a brick-like
structure. Here it was shown that the locality of the cost function can be
linked to its trainability. Specifically, global cost functions (those where
one compares operators living in exponentially large Hilbert spaces) exhibit
barren plateaus for any circuit depth. On the other hand, it was shown that
local cost functions (where one compares operators on an individual qubit
level) are trainable when the ansatz depth is in $\mathcal{O}(\log(n))$, as
here their gradients vanish at worst polynomially (rather than exponentially)
with the system size.

Barren plateaus have also been shown to arise in more general QNN
architectures [21, 28]. In perceptron-based QNNs with hidden and visible
layers, connecting a large number of qubits in different layers with random
global perceptrons (and hence highly entangling them) can lead to
exponentially vanishing gradients. These results have shown that the barren
plateau phenomenon is a generic problem that can arise in multiple
architectures for quantum machine learning.

Finally, in [22] a noise-induced barren plateau mechanism was found. Here it
was proven that the presence of noise acting before and after each unitary
layer in a parametrized quantum circuit leads to exponentially vanishing
gradients for circuits with linear or super-linear depth. When the cost
exhibits a noise-induced barren plateau we have
$|\partial_{\mu}C(\boldsymbol{\theta})|\leqslant\widehat{F}(n)$ with
$\widehat{F}(n)\in\mathcal{O}(1/\widehat{b}^{n})$ for some $\widehat{b}>1$.
The underlying mechanism here is that the state gets corrupted due to noise,
leading to a flattening of the whole cost landscape. This phenomenon is
conceptually different from the previous barren plateaus as here one does not
average over the parameters $\boldsymbol{\theta}$. Nevertheless, the noise-
induced barren plateau still satisfies Definition 1, which is a weaker
condition.

##  3 Main Results

In this section we first present our main analytical results in the form of
Proposition 1 and Corollary 1. We then discuss the implications for employing
gradient-free optimizers in a barren plateau.

###  3.1 Exponentially suppressed cost differences

Here we consider two relevant scenarios where we analyze, on average, how
large the difference $\Delta
C=C(\boldsymbol{\theta}_{B})-C(\boldsymbol{\theta}_{A})$ between two points in
the landscape can be. First we consider the case when
$\boldsymbol{\theta}_{A}$ and $\boldsymbol{\theta}_{B}$ are not independent,
but rather $\boldsymbol{\theta}_{B}$ can be obtained from
$\boldsymbol{\theta}_{A}$ through a given translation in parameter space. We
then analyze the case when $\boldsymbol{\theta}_{A}$ and
$\boldsymbol{\theta}_{B}$ are independent.

The following proposition constitutes the main result of our work. The proof
is presented in the Appendix.

######  Proposition 1.

Consider the cost function of Eq. (1). Let $\boldsymbol{\theta}_{A}$ be a
randomly chosen point in parameter space. Let
$\boldsymbol{\theta}_{B}=\boldsymbol{\theta}_{A}+L\hat{\boldsymbol{\ell}}$ be
a point at a distance $L=\|\boldsymbol{\theta}_{B}-\boldsymbol{\theta}_{A}\|$
from $\boldsymbol{\theta}_{A}$ in parameter space, for some unit vector
$\hat{\boldsymbol{\ell}}$. If the cost exhibits a barren plateau according to
Definition 1, then the expectation value of the difference $\Delta
C=C(\boldsymbol{\theta}_{B})-C(\boldsymbol{\theta}_{A})$ is

$\text{E}_{\boldsymbol{\theta}_{A}}[\Delta C]=0\,,$ (6)

and the variance is exponentially vanishing with $n$ as

${\rm Var}_{\boldsymbol{\theta}_{A}}[\Delta C]\leqslant G(n)\,,$ (7)

with

$G(n)=m^{2}L^{2}F(n)\,,\quad\text{and}\quad
G(n)\in\widetilde{\mathcal{O}}\left(\frac{1}{b^{n}}\right)\,,$ (8)

for some $b>1$. Here $m$ is the dimension of the parameter space, and $F(n)$
was defined in (4).

Let us here recall that we have assumed that
$m\in\mathcal{O}(\operatorname{poly}(n))$. Similarly, we have that
$\theta_{\mu}$ parametrizes a unitary generated by a Hermitian operator
$H_{\mu}$ with two distinct non-zero eigenvalues. From the latter it then
follows that $L$ is always in $\mathcal{O}(\operatorname{poly}(n))$, and hence
that $G(n)\in\widetilde{\mathcal{O}}(1/b^{n})$.

From the previous results one can readily evaluate the case when
$\boldsymbol{\theta}_{B}$ and $\boldsymbol{\theta}_{A}$ are independent. This
case is of relevance to global optimizers, such as Bayesian approaches, where
initial points on the landscape are chosen independently. This scenario can be
analyzed by computing the expectation value
$\text{E}_{\boldsymbol{\theta}_{A},\boldsymbol{\theta}_{B}}[\Delta
C]=\text{E}_{\boldsymbol{\theta}_{B}}[\text{E}_{\boldsymbol{\theta}_{A}}[\Delta
C]]$. From Proposition 1, we can derive the following corollary.

######  Corollary 1.

Consider the cost function of Eq. (1). Let $\boldsymbol{\theta}_{A}$ and
$\boldsymbol{\theta}_{B}$ be two randomly chosen points in parameter space.
Without loss of generality we assume that
$\boldsymbol{\theta}_{B}=\boldsymbol{\theta}_{A}+L\hat{\boldsymbol{\ell}}$ for
random $L$ and $\hat{\boldsymbol{\ell}}$ so that
$\text{E}_{\boldsymbol{\theta}_{A},\boldsymbol{\theta}_{B}}[\cdots]=\text{E}_{\boldsymbol{\theta}_{A},L,\hat{\boldsymbol{\ell}}}[\cdots]$.
If the cost exhibits a barren plateau according to Definition 1, then the
expectation value of the difference $\Delta
C=C(\boldsymbol{\theta}_{B})-C(\boldsymbol{\theta}_{A})$ is
$\text{E}_{\boldsymbol{\theta}_{A},L,\hat{\boldsymbol{\ell}}}[\Delta C]=0$,
and the variance is exponentially vanishing with $n$ as

${\rm Var}_{\boldsymbol{\theta}_{A},L,\hat{\boldsymbol{\ell}}}[\Delta
C]\leqslant\widehat{G}(n)\,,$ (9)

with

$\widehat{G}(n)=m^{2}\overline{L}^{2}F(n)\,,\quad\text{and}\quad\widehat{G}(n)\in\widetilde{\mathcal{O}}\left(\frac{1}{b^{n}}\right)\,,$
(10)

for some $b>1$. Here $m$ is the dimension of the parameter space, $F(n)$ was
defined in (4), and

$\overline{L}=\text{E}_{L,\hat{\boldsymbol{\ell}}}\left[L\right]$ (11)

is the average distance between any two points in parameter space.

The proof of Corollary 1 readily follows from Proposition 1 by additionally
computing the expectation value over $L$ and $\hat{\boldsymbol{\ell}}$.
Moreover, here we can see that $\widehat{G}(n)$ is exponentially vanishing
with the system size as $\overline{L}\in\mathcal{O}(\operatorname{poly}(n))$.

From Proposition 1 we have that given two dependent set of parameters
$\boldsymbol{\theta}_{A}$ and a set $\boldsymbol{\theta}_{B}$ related trough a
translation in parameter space, then the probability that the difference
$\Delta C=C(\boldsymbol{\theta}_{B})-C(\boldsymbol{\theta}_{A})$ is larger
than a given $c>0$ can be bounded as

$P(|\Delta C|\geqslant c)\leqslant\frac{G(n)}{c^{2}}\,,$ (12)

where we have used (5), and Eq. (9) from Proposition 1. Note that a similar
result can be obtained for the case when $\boldsymbol{\theta}_{A}$ and
$\boldsymbol{\theta}_{B}$ are independent, but here one replaces $G(n)$ by
$\widehat{G}(n)$ in (12). This implies that, with high probability, the
difference $\Delta C$ will be exponentially vanishing with the system size,
for both cases when $\boldsymbol{\theta}_{A}$ and $\boldsymbol{\theta}_{B}$
are dependent or independent. Moreover, we remark that this is a direct
consequence of the fact that the cost exhibits a barren plateau.

###  3.2 Implications for gradient-free optimizers

Let us first recall that, as discussed in the previous section, the capability
of distinguishing the cost function value at different sets of parameters is
at the core of gradient-free optimization methods. Therefore, the precision
required to differentiate choices fundamentally limits the scaling of these
methods, with smaller differences requiring greater precision. If an
optimizer’s precision requirements are not met, then each decision the method
makes becomes randomly chosen by shot noise, leading to many optimizers
effectively becoming either random walks or random sampling.

The results in Proposition 1 pertain to gradient-free optimizers that compare
points that are a given distance and direction apart. For example, simplex-
based methods like Nelder-Mead fall under this category. As we show that cost
differences are exponentially suppressed with the system size in a barren
plateau, this leads to applications having sampling requirements that scale
exponentially. Exponentially scaling sampling requirements, in turn, hinder
the possibility of achieving quantum speedup with such an algorithm.

Similarly, Corollary 1 tells us that cost function differences between
randomly chosen points are also exponentially suppressed. This means that
either random search methods or methods that use random initialization, such
as Bayesian optimization [54], will also struggle with barren plateau
landscapes. Therefore, using randomness in the selection of points cannot
evade this exponential scaling result.

Let us finally remark that Proposition 1 and Corollary 1 make no assumption
about how close (or far) the parameters $\boldsymbol{\theta}_{A}$ and
$\boldsymbol{\theta}_{B}$ are in parameter space other than that
$L=\|\boldsymbol{\theta}_{B}-\boldsymbol{\theta}_{A}\|\in\mathcal{O}(\operatorname{poly}(n))$.
Given that for any practical application the number of parameters $m$ should
scale no faster than $m\in\mathcal{O}(\operatorname{poly}(n))$ (or the problem
will become untrainable for reasons having nothing to do with barren
plateaus), this seems very reasonable. For example, if all of the parameters
are single qubit rotations, the parameter space is a $m$-dimensional torus
with unit radius. On that torus, the greatest length of the shortest path
between two points is:

$\displaystyle L_{\mathrm{max}}=$
$\displaystyle\max_{\boldsymbol{\theta}_{A},\boldsymbol{\theta}_{B}}\|\boldsymbol{\theta}_{A}-\boldsymbol{\theta}_{B}\|$
(13) $\displaystyle=$ $\displaystyle\sqrt{m}\pi.$

This means that our results are valid for both local and global optimizers as
sampling points that are further apart cannot overcome the suppressed slope.

##  4 Numerical Implementation

Figure 2: Single layer of the hardware efficient ansatz employed in our
numerical implementations, shown here for $n=4$. The $U$ gates are general
single qubit unitaries
$U(\theta_{1},\theta_{2},\theta_{3})=R_{Z}(\theta_{2}+\pi)R_{X}(\pi/2)R_{Z}(\theta_{1}+\pi)R_{X}(\pi/2)R_{Z}(\theta_{3})$.
Here $R_{Z}(\alpha)=e^{-i\alpha/2\sigma_{Z}}$,
$R_{X}(\alpha)=e^{-i\alpha/2\sigma_{X}}$, and $\sigma_{Z}$, $\sigma_{X}$ are
Pauli matrices.

In this section we present numerical results obtained by simulating a
variational quantum compiling algorithm [7, 12]. Here, one trains a
parametrized quantum circuit $V(\boldsymbol{\theta})$ to approximate a target
unitary $U$. Specifically, we consider the toy-model problem where
$U=\mathbbm{1}$ and the goal is to train the parameters in
$V(\boldsymbol{\theta})$ such that
$V(\boldsymbol{\theta})|\boldsymbol{0}\rangle=|\boldsymbol{0}\rangle$, with
$|\boldsymbol{0}\rangle=|0\rangle^{\otimes n}$ the all-zero state. As shown in
[7, 12], the following local cost function is faithful

$C(\boldsymbol{\theta})={\rm
Tr}[O_{L}V(\boldsymbol{\theta})|\boldsymbol{0}\rangle\\!\langle\boldsymbol{0}|V^{\dagger}(\boldsymbol{\theta})]\,,$
(14)

where

$O_{L}=\mathbbm{1}-\frac{1}{n}\sum_{i=1}^{n}|0_{i}\rangle\langle 0_{i}|\,,$
(15)

in that can verify that $C(\boldsymbol{\theta})\in[0,1]$, with
$C(\boldsymbol{\theta})=0$ iff
$V(\boldsymbol{\theta})|\boldsymbol{0}\rangle=|\boldsymbol{0}\rangle$ (up to
global phase). We remark that there is an efficient quantum circuit to compute
$C(\boldsymbol{\theta})$ [12].

For $V(\boldsymbol{\theta})$ we employ a layered hardware efficient ansatz as
shown in Fig. 2. Moreover, we recall that Ref. [19] showed that a cost
function such as (14) with a layered hardware efficient ansatz that is
randomly initialized will exhibit barren plateaus when the depth of
$V(\boldsymbol{\theta})$ scales at least linearly in $n$.

In our numerics we simulated the aforementioned quantum compilation task for
different numbers of qubits $n=5,6,\ldots,11$. Letting $p$ be the number of
layers in the ansatz in Fig. 2, we choose $p=n$, so that the depth grows
linearly in $n$. This corresponds to the barren plateau scenario in Ref. [19].
For each value of $n$, we solved the optimization of Eq. (2) by employing the
Nelder-Mead, Powell, and COBYLA methods. These simulations were performed
using MATLAB (Nelder-Mead) and SciPy (Powell and COBYLA). In all cases we
randomly initialized the parameters $\boldsymbol{\theta}$ in the ansatz and we
ran the optimizer until a cost function value $C=0.4$ was achieved or until a
maximal total number of shots used throughout the optimization was surpassed.
For simplicity we use the default values for hyper-parameters not related to
optimization termination. We note that we chose a relatively large value
($C=0.4$) for the cost threshold because we are interested in the initial
stages of the training process, i.e., the question of whether one can get past
the barren plateau. With this choice, the computational expense of reaching
this threshold does not take into account the difficulty of finding a minimum,
it only reflects the burden of the barren plateau.

Since the goal is to heuristically determine the precision (i.e., the number
of shots $N$) needed to minimize the cost, we first ran simulations with
different values of $N$ allocated per cost-function evaluation. For each $N$
we simulated $20$ optimization instances (runs) with different initial points
and we kept track of $N_{\text{total}}$ used throughout the optimization. The
next step was to determine the value of $N$ for which a cost of $C=0.4$ could
be reached and which minimizes the median total number of shots
$N_{\text{total}}$ computed over different runs. We analyze the scaling of
this median value as a function of $n$ below.

Figure 3: Median value of the total shot number $N_{\textrm{total}}$ necessary
to reach $C=0.4$ plotted versus the number of qubits $n$. We show results for
Nelder-Mead (blue diamonds), Powell (red asterisks), and COBYLA (pink squares)
implementations, as well as results for a gradient-descent implementation
(black crosses) for reference. Each data point was obtained from a sample of
$20$ runs initialized by random initial angles $\boldsymbol{\theta}$.

In Fig. 3 we present our numerical results. Here we can see that the total
number of shots scales exponentially with $n$ for the Powell method, and
scales super-exponentially for the Nelder-Mead optimizer. For the COBYLA
method, the $N_{\text{total}}$ behavior as a function of $n$ is not very
regular but it is consistent with at least an exponential increase. As a
reference point we also show in Fig. 3 results obtained with a custom
gradient-descent optimizer. As expected, the total number of shots also scales
exponentially in this case.

##  5 Discussion

With a wide range of applications spanning chemistry, optimization, and big
data analysis, training parameterized quantum circuits is arguably the leading
paradigm for near-term quantum computing. Yet barren plateaus in the training
landscape remains an obstacle to making these paradigms scalable. Hence, one
of the most important lines of research in this field is developing methods to
avoid barren plateaus.

In this work, we consider the question of whether the choice of optimizer
could be a potential strategy in avoiding barren plateaus. We focus on
gradient-free optimizers, since there has been recent debate in the community
about whether barren plateaus effect such optimizers.

Our main result is an analytical argument suggesting that gradient-free
optimizers will, indeed, be impacted by barren plateaus. Proposition 1 is
relevant to gradient-free optimizers that search through the landscape
starting from a (random) initial point. For example, this includes simplex-
based optimizers like Nelder-Mead. This proposition asserts that the variance
of cost function differences is exponentially suppressed in a barren plateau.
This implies that such optimizers will need to expend exponentially large
resources in order to make decisions about where to move in the landscape.

Corollary 1 considers a slightly different scenario, where both points are
randomly and independently chosen. This is relevant to global gradient-free
optimizers, such as Bayesian methods, which initially choose multiple random
points on the landscape, and then proceed from this initial set of points.
This corollary implies that these optimizers will also need to utilize
exponentially large resources in order to make progress.

We also numerically attempt to train in a barren plateau scenario using
several gradient-free optimizers. We ask how many shots are required to begin
to train the cost function. In all cases, we find that the required number of
shots grows exponentially in the number of qubits. This is consistent with our
main result, and demonstrates that barren plateaus can lead to exponential
scaling even for gradient-free optimizers. We note that this exponential
scaling is a lower bound on the asymptotics. For the Nelder-Mead we find
super-exponential scaling, likely due to the chances of prematurely shrinking
the simplex when it is hard to order the cost values [46]. For the case of
COBYLA, there may be a similar effect from prematurely shrinking the radius of
the trust region, though this is not clearly demonstrated in our data.
Finally, the Powell method appears to show exponential scaling. It is likely
that the reason Powell shows better scaling is that, unlike the other
optimizers, statistical noise does not have a cumulative effect on the state
of the optimizer.

Our work casts doubt on the notion that the choice of optimizer could provide
a strategy to avoid barren plateaus. While the asymptotically exponential
scaling cannot be avoided, we note that the size limits of trainable problems
may be extended by a careful choice of optimization strategy. For example,
techniques using neural networks [34] or natural evolutionary strategies [55]
may improve the constants multiplying the exponential scaling. However, we
emphasize that all such strategies at minimum require the comparison of cost
function values at different points and thus are subject to our scaling
analysis.

This result highlights the difficult challenge posed by barren plateaus.
Future work certainly should continue to develop strategies to avoid them.
Additionally, in future work, we hope to develop a unified treatment that
covers the impact of barren plateaus on various types of optimizers, gradient-
based and gradient-free.

## Acknowledgements

AA and LC were initially supported by LDRD program of LANL under project
number 20190065DR. MC acknowledges support from the Center for Nonlinear
Studies at Los Alamos National Laboratory (LANL). Piotr C. was supported by
the Laboratory Directed Research and Development (LDRD) program of Los Alamos
National Laboratory (LANL) under project number 20190659PRD4. PJC acknowledges
initial support from the LANL ASC Beyond Moore’s Law project. This work was
supported by the U.S. DOE, Office of Science, Office of Advanced Scientific
Computing Research, under the Accelerated Research in Quantum Computing (ARQC)
program.

## References

  * Cerezo  _et al._ [2021a] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles,  _Variational quantum algorithms,_Nature Reviews Physics 1, 19 (2021a).
  * Bharti  _et al._ [2021] K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik,  _Noisy intermediate-scale quantum (nisq) algorithms,_arXiv preprint arXiv:2101.08448 (2021).
  * Peruzzo  _et al._ [2014] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien,  _A variational eigenvalue solver on a photonic quantum processor,_Nature communications 5, 1 (2014).
  * McClean  _et al._ [2016] J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik,  _The theory of variational hybrid quantum-classical algorithms,_New Journal of Physics 18, 023023 (2016).
  * Farhi  _et al._ [2014] E. Farhi, J. Goldstone, and S. Gutmann,  _A quantum approximate optimization algorithm,_arXiv preprint arXiv:1411.4028 (2014).
  * Romero  _et al._ [2017] J. Romero, J. P. Olson, and A. Aspuru-Guzik,  _Quantum autoencoders for efficient compression of quantum data,_Quantum Science and Technology 2, 045001 (2017).
  * Khatri  _et al._ [2019] S. Khatri, R. LaRose, A. Poremba, L. Cincio, A. T. Sornborger, and P. J. Coles,  _Quantum-assisted quantum compiling,_Quantum 3, 140 (2019).
  * LaRose  _et al._ [2019] R. LaRose, A. Tikku, É. O’Neel-Judy, L. Cincio, and P. J. Coles,  _Variational quantum state diagonalization,_npj Quantum Information 5, 1 (2019).
  * Arrasmith  _et al._ [2019] A. Arrasmith, L. Cincio, A. T. Sornborger, W. H. Zurek, and P. J. Coles,  _Variational consistent histories as a hybrid algorithm for quantum foundations,_Nature communications 10, 1 (2019).
  * Cerezo  _et al._ [2020a] M. Cerezo, A. Poremba, L. Cincio, and P. J. Coles,  _Variational quantum fidelity estimation,_Quantum 4, 248 (2020a).
  * Cirstoiu  _et al._ [2020] C. Cirstoiu, Z. Holmes, J. Iosue, L. Cincio, P. J. Coles, and A. Sornborger,  _Variational fast forwarding for quantum simulation beyond the coherence time,_npj Quantum Information 6, 1 (2020).
  * Sharma  _et al._ [2020a] K. Sharma, S. Khatri, M. Cerezo, and P. J. Coles,  _Noise resilience of variational quantum compiling,_New Journal of Physics 22, 043006 (2020a).
  * Bravo-Prieto  _et al._ [2019] C. Bravo-Prieto, R. LaRose, M. Cerezo, Y. Subasi, L. Cincio, and P. Coles,  _Variational quantum linear solver,_arXiv preprint arXiv:1909.05820 (2019).
  * Cerezo  _et al._ [2020b] M. Cerezo, K. Sharma, A. Arrasmith, and P. J. Coles,  _Variational quantum state eigensolver,_arXiv preprint arXiv:2004.01372 (2020b).
  * Schuld  _et al._ [2014] M. Schuld, I. Sinayskiy, and F. Petruccione,  _The quest for a quantum neural network,_Quantum Information Processing 13, 2567 (2014).
  * Cong  _et al._ [2019] I. Cong, S. Choi, and M. D. Lukin,  _Quantum convolutional neural networks,_Nature Physics 15, 1273 (2019).
  * Beer  _et al._ [2020] K. Beer, D. Bondarenko, T. Farrelly, T. J. Osborne, R. Salzmann, D. Scheiermann, and R. Wolf,  _Training deep quantum neural networks,_Nature Communications 11, 808 (2020).
  * Verdon  _et al._ [2018] G. Verdon, J. Pye, and M. Broughton,  _A universal training algorithm for quantum deep learning,_arXiv preprint arXiv:1806.09729 (2018).
  * McClean  _et al._ [2018] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven,  _Barren plateaus in quantum neural network training landscapes,_Nature communications 9, 1 (2018).
  * Cerezo  _et al._ [2021b] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles,  _Cost function dependent barren plateaus in shallow parametrized quantum circuits,_Nature Communications 12, 1791 (2021b).
  * Sharma  _et al._ [2020b] K. Sharma, M. Cerezo, L. Cincio, and P. J. Coles,  _Trainability of dissipative perceptron-based quantum neural networks,_arXiv preprint arXiv:2005.12458 (2020b).
  * Wang  _et al._ [2020] S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles,  _Noise-induced barren plateaus in variational quantum algorithms,_arXiv preprint arXiv:2007.14384 (2020).
  * Cerezo and Coles [2021] M. Cerezo and P. J. Coles,  _Higher order derivatives of quantum neural networks with barren plateaus,_Quantum Science and Technology 6, 035006 (2021).
  * Holmes  _et al._ [2021a] Z. Holmes, A. Arrasmith, B. Yan, P. J. Coles, A. Albrecht, and A. T. Sornborger,  _Barren plateaus preclude learning scramblers,_Physical Review Letters 126, 190501 (2021a).
  * Pesah  _et al._ [2020] A. Pesah, M. Cerezo, S. Wang, T. Volkoff, A. T. Sornborger, and P. J. Coles,  _Absence of barren plateaus in quantum convolutional neural networks,_arXiv preprint arXiv:2011.02966 (2020).
  * Zhang  _et al._ [2020] K. Zhang, M.-H. Hsieh, L. Liu, and D. Tao,  _Toward trainability of quantum neural networks,_arXiv preprint arXiv:2011.06258 (2020).
  * Abbas  _et al._ [2021] A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli, and S. Woerner,  _The power of quantum neural networks,_Nature Computational Science 1, 403 (2021).
  * Marrero  _et al._ [2020] C. O. Marrero, M. Kieferová, and N. Wiebe,  _Entanglement induced barren plateaus,_arXiv preprint arXiv:2010.15968 (2020).
  * Patti  _et al._ [2021] T. L. Patti, K. Najafi, X. Gao, and S. F. Yelin,  _Entanglement devised barren plateau mitigation,_Physical Review Research 3, 033090 (2021).
  * Uvarov and Biamonte [2021] A. Uvarov and J. D. Biamonte,  _On barren plateaus and cost function locality in variational quantum algorithms,_Journal of Physics A: Mathematical and Theoretical 54, 245301 (2021).
  * Holmes  _et al._ [2021b] Z. Holmes, K. Sharma, M. Cerezo, and P. J. Coles,  _Connecting ansatz expressibility to gradient magnitudes and barren plateaus,_arXiv preprint arXiv:2101.02138 (2021b).
  * Du  _et al._ [2020] Y. Du, M.-H. Hsieh, T. Liu, S. You, and D. Tao,  _On the learnability of quantum neural networks,_arXiv preprint arXiv:2007.12369 (2020).
  * Arrasmith  _et al._ [2021] A. Arrasmith, Z. Holmes, M. Cerezo, and P. J. Coles,  _Equivalence of quantum barren plateaus to cost concentration and narrow gorges,_arXiv preprint arXiv:2104.05868 (2021).
  * Verdon  _et al._ [2019] G. Verdon, M. Broughton, J. R. McClean, K. J. Sung, R. Babbush, Z. Jiang, H. Neven, and M. Mohseni,  _Learning to learn with quantum neural networks via classical neural networks,_arXiv preprint arXiv:1907.05415 (2019).
  * Volkoff and Coles [2021] T. Volkoff and P. J. Coles,  _Large gradients via correlation in random parameterized quantum circuits,_Quantum Science and Technology 6, 025008 (2021).
  * Skolik  _et al._ [2021] A. Skolik, J. R. McClean, M. Mohseni, P. van der Smagt, and M. Leib,  _Layerwise learning for quantum neural networks,_Quantum Machine Intelligence 3, 1 (2021).
  * Grant  _et al._ [2019] E. Grant, L. Wossnig, M. Ostaszewski, and M. Benedetti,  _An initialization strategy for addressing barren plateaus in parametrized quantum circuits,_Quantum 3, 214 (2019).
  * Campos  _et al._ [2021] E. Campos, A. Nasrallah, and J. Biamonte,  _Abrupt transitions in variational quantum circuit training,_Physical Review A 103, 032607 (2021).
  * Farhi and Neven [2018] E. Farhi and H. Neven,  _Classification with quantum neural networks on near term processors,_arXiv preprint arXiv:1802.06002 (2018).
  * Killoran  _et al._ [2019] N. Killoran, T. R. Bromley, J. M. Arrazola, M. Schuld, N. Quesada, and S. Lloyd,  _Continuous-variable quantum neural networks,_Physical Review Research 1, 033063 (2019).
  * Kübler  _et al._ [2020] J. M. Kübler, A. Arrasmith, L. Cincio, and P. J. Coles,  _An adaptive optimizer for measurement-frugal variational algorithms,_Quantum 4, 263 (2020).
  * Sweke  _et al._ [2020] R. Sweke, F. Wilde, J. J. Meyer, M. Schuld, P. K. Fährmann, B. Meynard-Piganeau, and J. Eisert,  _Stochastic gradient descent for hybrid quantum-classical optimization,_Quantum 4, 314 (2020).
  * Arrasmith  _et al._ [2020] A. Arrasmith, L. Cincio, R. D. Somma, and P. J. Coles,  _Operator sampling for shot-frugal optimization in variational algorithms,_arXiv preprint arXiv:2004.06252 (2020).
  * Stokes  _et al._ [2020] J. Stokes, J. Izaac, N. Killoran, and G. Carleo,  _Quantum natural gradient,_Quantum 4, 269 (2020).
  * Nelder and Mead [1965] J. A. Nelder and R. Mead,  _A simplex method for function minimization,_The computer journal 7, 308 (1965).
  * Barton and Ivey Jr [1991] R. R. Barton and J. S. Ivey Jr,  _Modifications of the nelder-mead simplex method for stochastic simulation response optimization,_1991 Winter Simulation Conference Proceedings (1991), 10.1109/WSC.1991.185709.
  * Huang [2018] X. Huang,  _Robust simplex algorithm for online optimization,_Physical Review Accelerators and Beams 21, 104601 (2018).
  * Powell [1964] M. J. Powell,  _An efficient method for finding the minimum of a function of several variables without calculating derivatives,_The computer journal 7, 155 (1964).
  * Brent [2013] R. P. Brent,  _Algorithms for minimization without derivatives_ (Courier Corporation, 2013).
  * Powell [1994] M. J. Powell, in  _Advances in optimization and numerical analysis_ (Springer, 1994) pp. 51–67.
  * Harrow and Low [2009] A. W. Harrow and R. A. Low,  _Random quantum circuits are approximate 2-designs,_Communications in Mathematical Physics 291, 257 (2009).
  * Brandao  _et al._ [2016] F. G. Brandao, A. W. Harrow, and M. Horodecki,  _Local random quantum circuits are approximate polynomial-designs,_Communications in Mathematical Physics 346, 397 (2016).
  * Harrow and Mehraban [2018] A. Harrow and S. Mehraban,  _Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates, _arXiv preprint arXiv:1809.06957 (2018).
  * Močkus [1975] J. Močkus, in  _Optimization techniques IFIP technical conference_ (Springer, 1975) pp. 400–404.
  * Anand  _et al._ [2021] A. Anand, M. Degroote, and A. Aspuru-Guzik,  _Natural evolutionary strategies for variational quantum computation,_Machine Learning: Science and Technology (2021), 10.1088/2632-2153/abf3ac.

## Appendix

##  Appendix A Proof of Proposition 1

We now prove our main result. We restate the proposition here for convenience.

######  Proposition 1.

Consider the cost function of Eq. (1). Let $\boldsymbol{\theta}_{A}$ be a
randomly chosen point in parameter space. Let
$\boldsymbol{\theta}_{B}=\boldsymbol{\theta}_{A}+L\hat{\boldsymbol{\ell}}$ be
a point at a distance $L=\|\boldsymbol{\theta}_{B}-\boldsymbol{\theta}_{A}\|$
from $\boldsymbol{\theta}_{A}$ in parameter space, for some unit vector
$\hat{\boldsymbol{\ell}}$. If the cost exhibits a barren plateau according to
Definition 1, then the expectation value of the difference $\Delta
C=C(\boldsymbol{\theta}_{B})-C(\boldsymbol{\theta}_{A})$ is

$\text{E}_{\boldsymbol{\theta}_{A}}[\Delta C]=0\,,$ (16)

and the variance is exponentially vanishing with $n$ as

${\rm Var}_{\boldsymbol{\theta}_{A}}[\Delta C]\leqslant G(n)\,,$ (17)

with

$G(n)=m^{2}L^{2}F(n)\,,\quad\text{and}\quad
G(n)\in\widetilde{\mathcal{O}}\left(\frac{1}{b^{n}}\right)\,,$ (18)

for some $b>1$. Here $m$ is the dimension of the parameter space, and $F(n)$
was defined in (4).

Proof. We begin by noting that finite differences in cost values can be
expressed as:

$\displaystyle\Delta C=$ $\displaystyle
C(\boldsymbol{\theta}_{B})-C(\boldsymbol{\theta}_{A})$ (19) $\displaystyle=$
$\displaystyle\int_{\boldsymbol{\theta}_{A}}^{\boldsymbol{\theta}_{B}}\boldsymbol{\nabla}C(\boldsymbol{\theta})\cdot
d\boldsymbol{\theta}\,.$

Note that as we are integrating over gradients (which form a conservative
vector field by definition) this integral is path independent. We can
therefore choose to integrate along the line segment between
$\boldsymbol{\theta}_{B}$ and $\boldsymbol{\theta}_{A}$, setting
$\boldsymbol{\theta}=\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}}$,
with $\hat{\boldsymbol{\ell}}$ being the unit vector along
$\boldsymbol{\theta}_{B}-\boldsymbol{\theta}_{A}$ and $\ell\in[0,L]$ where
$L=\|\boldsymbol{\theta}_{B}-\boldsymbol{\theta}_{A}\|$. We then have
$d\boldsymbol{\theta}=\hat{\boldsymbol{\ell}}d\ell$. To show that the mean
difference is zero, we simply take the expectation value of this integral with
respect to $\boldsymbol{\theta}_{A}$

$\displaystyle\text{E}_{\boldsymbol{\theta}_{A}}[\Delta C]=$
$\displaystyle\int_{0}^{L}\text{E}_{\boldsymbol{\theta}_{A}}[\boldsymbol{\nabla}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\cdot\hat{\boldsymbol{\ell}}]d\ell$
(20) $\displaystyle=$ $\displaystyle 0\,.$

This follows as averaging $\boldsymbol{\theta}_{A}$ over parameter space is
equivalent to averaging $\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}}$
over the same space (for any fixed $\ell\hat{\boldsymbol{\ell}}$), and the
average gradient over the parameter space is zero from the definition of a
barren plateau (see Definition 1).

Similarly, we can compute the magnitude of the second moment of this
difference as

$\displaystyle\big{|}\text{E}_{\boldsymbol{\theta}_{A}}[(\Delta
C)^{2}]\big{|}=$
$\displaystyle\Bigg{|}\int_{0}^{L}\int_{0}^{L}\text{E}_{\boldsymbol{\theta}_{A}}[(\boldsymbol{\nabla}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\cdot\hat{\boldsymbol{\ell}})(\boldsymbol{\nabla}C(\boldsymbol{\theta}_{A}+\ell^{\prime}\hat{\boldsymbol{\ell}})\cdot\hat{\boldsymbol{\ell}})]d\ell
d\ell^{\prime}\Bigg{|}$ (21) $\displaystyle=$
$\displaystyle\Bigg{|}\int_{0}^{L}\int_{0}^{L}\text{Cov}_{\boldsymbol{\theta}_{A}}\left((\boldsymbol{\nabla}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\cdot\hat{\boldsymbol{\ell}}),(\boldsymbol{\nabla}C(\boldsymbol{\theta}_{A}+\ell^{\prime}\hat{\boldsymbol{\ell}})\cdot\hat{\boldsymbol{\ell}})\right)d\ell
d\ell^{\prime}\Bigg{|}\,.$

Note that we have dropped the square of the mean as the mean is zero, so the
second moment is the covariance. Next, we upper bound this covariance using
the product of the variances using the Cauchy-Schwartz inequality

$\displaystyle\big{|}\text{E}_{\boldsymbol{\theta}_{A}}[(\Delta
C)^{2}]\big{|}\leq$
$\displaystyle\int_{0}^{L}\int_{0}^{L}\left(\text{Var}_{\boldsymbol{\theta}_{A}}(\boldsymbol{\nabla}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\cdot\hat{\boldsymbol{\ell}})\text{Var}_{\boldsymbol{\theta}_{A}}(\boldsymbol{\nabla}C(\boldsymbol{\theta}_{A}+\ell^{\prime}\hat{\boldsymbol{\ell}})\cdot\hat{\boldsymbol{\ell}})\right)^{\frac{1}{2}}d\ell
d\ell^{\prime}\,.$ (22)

Next, we split these variances into the covariances between individual
components of the gradient

$\displaystyle\big{|}\text{E}_{\boldsymbol{\theta}_{A}}[(\Delta
C)^{2}]\big{|}\leq$
$\displaystyle\int_{0}^{L}\int_{0}^{L}\left(\sum_{i=1}^{m}\sum_{j=1}^{m}\sum_{p=1}^{m}\sum_{q=1}^{m}\text{Cov}_{\boldsymbol{\theta}_{A}}\left(\partial_{i}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\hat{\ell}_{i},\partial_{j}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\hat{\ell}_{j}\right)\right.$
(23)
$\displaystyle\,\,\,\,\,\,\left.\text{Cov}_{\boldsymbol{\theta}_{A}}(\partial_{p}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\hat{\ell}_{p},\partial_{q}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\hat{\ell}_{q})\right)^{\frac{1}{2}}d\ell
d\ell^{\prime}\,.$

As before, these covariances can be bounded by variances using the Cauchy-
Schwartz inequality

$\displaystyle\big{|}\text{E}_{\boldsymbol{\theta}_{A}}[(\Delta
C)^{2}]\big{|}\leq$
$\displaystyle\int_{0}^{L}\int_{0}^{L}\Bigg{(}\sum_{i=1}^{m}\sum_{j=1}^{m}\sum_{p=1}^{m}\sum_{q=1}^{m}\left(\text{Var}_{\boldsymbol{\theta}_{A}}\left(\partial_{i}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\right)\text{Var}_{\boldsymbol{\theta}_{A}}\left(\partial_{j}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\right)\right)^{\frac{1}{2}}$
(24)
$\displaystyle\,\,\,\,\,\,\left(\text{Var}_{\boldsymbol{\theta}_{A}}\left(\partial_{p}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\right)\text{Var}_{\boldsymbol{\theta}_{A}}\left(\partial_{q}C(\boldsymbol{\theta}_{A}+\ell\hat{\boldsymbol{\ell}})\right)\right)^{\frac{1}{2}}\Bigg{)}^{\frac{1}{2}}d\ell
d\ell^{\prime}\,.$

If each variance can be bounded by a function $F(n)$, we can then write

$\displaystyle\big{|}\text{E}_{\boldsymbol{\theta}_{A}}[(\Delta
C)^{2}]\big{|}\leq$ $\displaystyle m^{2}\int_{0}^{L}\int_{0}^{L}F(n)d\ell
d\ell^{\prime}$ (25) $\displaystyle=$ $\displaystyle m^{2}L^{2}F(n)$
$\displaystyle=$ $\displaystyle G(n).$

If the cost exhibits a barren plateau, then by Definition 1,
$F(n)\in\mathcal{O}\left(\frac{1}{b^{n}}\right)$ for some $b>1$. It then
follows that if $m\in\mathcal{O}(\operatorname{poly}(n))$ and
$L\in\mathcal{O}(\operatorname{poly}(n))$, then
$G(n)\in\mathcal{O}\left(\frac{1}{b^{n}}\right)$ and Proposition 1 holds.