Warm-up example

To illustrate cost-function-dependent barren plateaus, we first consider a toy problem corresponding to the state preparation problem in the Introduction with the target state being $$ ∣\mathit{0}⟩$$. We assume a tensor-product ansatz of the form $$ V\left(\mathit{\theta }\right){=⨂}_{j=1}^n{e}^{-i{\theta }^j{\sigma }_x^{\left(j\right)}/2}$$, with the goal of finding the angles θ^j such that $$ V\left(\mathit{\theta }\right)∣\mathit{0}⟩=∣\mathit{0}⟩$$. Employing the global cost of (1) results in $$ C_{\mathrm{G}}=1-{\prod }_{j=1}^n{\cos }^2\frac{{\theta }^j}{2}$$. The barren plateau can be detected via the variance of its gradient: $$ \mathrm{Var}\left[\frac{\partial C_{\mathrm{G}}}{\partial {\theta }^j}\right]=\frac{1}{8}{\left(\frac{3}{8}\right)}^{n-1}$$, which is exponentially vanishing in n. Since the mean value is $$ ⟨\frac{\partial C_{\mathrm{G}}}{\partial {\theta }^j}⟩=0$$, the gradient concentrates exponentially around zero.

On the other hand, consider a local cost function:

Fig. 2

Cost function landscapes.

a Two-dimensional cross-section through the landscape of $$ C_{\mathrm{G}}=1-{\prod }_{j=1}^n{\cos }^2\left({\theta }^j/2\right)$$ for n = 4 (blue) and n = 24 (orange). b The same cross-section through the landscape of $$ C_{\mathrm{L}}=1-\frac{1}{n}{\sum }_{j=1}^n{\cos }^2\left({\theta }^j/2\right)$$ is independent of n. In both cases, 200 Haar distributed points are shown, with very few (most) of these points lying in the valley containing the global minimum of C_G (C_L).

Moreover, this example allows us to delve deeper into the cost landscape to see a phenomenon that we refer to as a narrow gorge. While a barren plateau is associated with a flat landscape, a narrow gorge refers to the steepness of the valley that contains the global minimum. This phenomenon is illustrated in Fig. 2, where each dot corresponds to cost values obtained from randomly selected parameters θ. For C_G we see that very few dots fall inside the narrow gorge, while for C_L the narrow gorge is not present. Note that the narrow gorge makes it harder to train C_G since the learning rate of descent-based optimization algorithms must be exponentially small in order not to overstep the narrow gorge. The following proposition (proved in the Supplementary Note 2) formalizes the narrow gorge for C_G and its absence for C_L by characterizing the dependence on n of the probability C ⩽ δ. This probability is associated with the parameter space volume that leads to C ⩽ δ.

Proposition 1

Let θ^j be uniformly distributed on [−π, π] ∀j. For any δ ∈ (0, 1), the probability that C_G ≤ δ satisfies

For any $$ \delta \in \left[\frac{1}{2},1\right]$$, the probability that C_L ≤ δ satisfies

General framework

For our general results, we consider a family of cost functions that can be expressed as the expectation value of an operator O as follows

It is typical to express O as a linear combination of the form $$ O=c_0\mathbb{1}+{\sum }_{i=1}^N{c}_i{O}_i$$. Here O_i ≠ $$ \mathbb{1}$$, $$ c_i\in \mathbb{R}$$, and we assume that at least one c_i ≠ 0. Note that C_G and C_L in (1) and (2) fall under this framework. In our main results below, we will consider two different choices of O that respectively capture our general notions of global and local cost functions and also generalize the aforementioned C_G and C_L.

As shown in Fig. 3a, V(θ) consists of L layers of m-qubit unitaries W_kl(θ_kl), or blocks, acting on alternating groups of m neighboring qubits. We refer to this as an Alternating Layered Ansatz. We remark that the Alternating Layered Ansatz will be a hardware-efficient ansatz so long as the gates that compose each block are taken from a set of gates native to a specific device. As depicted in Fig. 3c, the one dimensional Alternating Layered Ansatz can be readily implemented in devices with one-dimensional connectivity, as well as in devices with two-dimensional connectivity (such as that of IBM’s³⁶ and Google’s³⁷ quantum devices). That is, with both one- and two-dimensional hardware connectivity one can group qubits to form an Alternating Layered Ansatz as in Fig. 3a.

Fig. 3

Alternating Layered Ansatz.

a Each block W_kl acts on m qubits and is parametrized via (27). As shown, we define S_k as the m-qubit subsystem on which W_kL acts, where L is the last layer of V(θ). Given some block W, it is useful for our proofs (outlined in the Methods) to write $$ V\left(\mathit{\theta }\right)=V_{\mathrm{R}}\left({\mathbb{1}}_{\overline{w}}\otimes W\right)V_{\mathrm{L}}$$, where V_R contains all gates in the forward light-cone $$ \mathcal{L}$$ of W. The forward light-cone $$ \mathcal{L}$$ is defined as all gates with at least one input qubit causally connected to the output qubits of W. We define $$ \overline{\mathcal{L}}$$ as the compliment of $$ \mathcal{L}$$, S_w as the m-qubit subsystem on which W acts, and $$ S_{\overline{w}}$$ as the n − m qubit subsystem on which W acts trivially. b The operator O_i acts nontrivially only in subsystem $$ S_{k-1}\in \mathcal{S}$$, while $$ O_{i^{\prime }}$$ acts nontrivially on the first m/2 qubits of S_k+1, and on the second m/2 qubits of S_k. c Depiction of the Alternating Layered Ansatz with one- and two-dimensional connectivity. Each circle represents a physical qubit.

The index l = 1, …, L in W_kl(θ_kl) indicates the layer that contains the block, while k = 1, …, ξ indicates the qubits it acts upon. We assume n is a multiple of m, with n = mξ, and that m does not scale with n. As depicted in Fig. 3a, we define S_k as the m-qubit subsystem on which W_kL acts, and we define $$ \mathcal{S}=\left\{S_k\right\}$$ as the set of all such subsystems. Let us now consider a block W_kl(θ_kl) in the lth layer of the ansatz. For simplicity we henceforth use W to refer to a given W_kl(θ_kl). As shown in the Methods section, given a θ^ν ∈ θ_kl that parametrizes a rotation $$ e^{-i{\theta }^{\nu }{\sigma }_{\nu }/2}$$ (with σ_ν a Pauli operator) inside a given block W, one can always express

The contribution to the gradient ∇C from a parameter θ^ν in the block W is given by the partial derivative ∂_νC. While the value of ∂_νC depends on the specific parameters θ, it is useful to compute $$ {⟨{\partial }_{\nu }C⟩}_V$$, i.e., the average gradient over all possible unitaries V(θ) within the ansatz. Such an average may not be representative near the minimum of C, although it does provide a good estimate of the expected gradient when randomly initializing the angles in V(θ). In the Methods Section we explicitly show how to compute averages of the form 〈…〉_V, and in the Supplementary Note 3 we provide a proof for the following Proposition.

Proposition 2

The average of the partial derivative of any cost function of the form (6) with respect to a parameter θ^ν in a block W of the ansatz in Fig. 3 is

provided that either W_A or W_B of (7) form a 1-design.

Here we recall that a t-design is an ensemble of unitaries, such that sampling over their distribution yields the same properties as sampling random unitaries from the unitary group with respect to the Haar measure up to the first t moments³⁸. The Methods section provides a formal definition of a t-design.

Proposition 2 states that the gradient is not biased in any particular direction. To analyze the trainability of C, we consider the second moment of its partial derivatives:

where we used the fact that $$ {⟨{\partial }_{\nu }C⟩}_V=0$$. The magnitude of Var[∂_νC] quantifies how much the partial derivative concentrates around zero, and hence small values in (9) imply that the slope of the landscape will typically be insufficient to provide a cost-minimizing direction. Specifically, from Chebyshev’s inequality, Var[∂_νC] bounds the probability that the cost-function partial derivative deviates from its mean value (of zero) as $$ \mathrm{Pr}\left(\mid {\partial }_{\nu }C\mid \ge c\right)\le \mathrm{Var}\left[{\partial }_{\nu }C\right]/c^2$$ for all c > 0.

Main results

Here we present our main theorems and corollaries, with the proofs sketched in the Methods and detailed in the Supplementary Information. In addition, in the Methods section we provide some intuition behind our main results by analyzing a generalization of the warm-up example where V(θ) is composed of a single layer of the ansatz in Fig. 3. This case bridges the gap between the warm-up example and our main theorems and also showcases the tools used to derive our main result.

The following theorem provides an upper bound on the variance of the partial derivative of a global cost function which can be expressed as the expectation value of an operator of the form

Theorem 1

Consider a trainable parameter θ^ν in a block W of the ansatz in Fig. 3. Let Var[∂_νC] be the variance of the partial derivative of a global cost function C (with O given by (10)) with respect to θ^ν. If W_A, W_B of (7), and each block in V(θ) form a local 2-design, then Var[∂_νC] is upper bounded by

(i)For N = 1 and when each $$ {\widehat{O}}_{1k}$$ is a non-trivial projector, then defining $$ R={\prod }_{k=1}^{\xi }{r}_k^2$$, we have



(ii)For arbitrary N and when each $$ {\widehat{O}}_{ik}$$ satisfies $$ \mathrm{Tr}\left[{\widehat{O}}_{ik}\right]=0$$ and $$ \mathrm{Tr}\left[{\widehat{O}}_{ik}^2\right]\le 2^m$$, then

From Theorem 1 we derive the following corollary.

Corollary 1

Consider the function F_n(L, l).

(i)Let N = 1 and let each $$ {\widehat{O}}_{1k}$$ be a non-trivial projector, as in case (i) of Theorem 1. If $$ c_1^{2}R\in \mathcal{O}\left(2^n\right)$$ and if the number of layers $$ L\in \mathcal{O}\left(\mathrm{poly}\left(\log \left(n\right)\right)\right)$$, then


which implies that Var[∂_νC] is exponentially vanishing in n if m ⩾ 2.

(ii)Let N be arbitrary, and let each $$ {\widehat{O}}_{ik}$$ satisfy $$ \mathrm{Tr}\left[{\widehat{O}}_{ik}\right]=0$$ and $$ \mathrm{Tr}\left[{\widehat{O}}_{ik}^2\right]\le 2^m$$, as in case (ii) of Theorem 1. If $$ N\in \mathcal{O}\left(2^n\right)$$, $$ c_i\in \mathcal{O}\left(1\right)$$, and if the number of layers $$ L\in \mathcal{O}\left(\mathrm{poly}\left(\log \left(n\right)\right)\right)$$, then


which implies that Var[∂_νC] is exponentially vanishing in n if m ⩾ 2.

Let us now make several important remarks. First, note that part (i) of Corollary 1 includes as a particular example the cost function C_G of (1). Second, part (ii) of this corollary also includes as particular examples operators with $$ N\in \mathcal{O}\left(1\right)$$, as well as $$ N\in \mathcal{O}\left(\mathrm{poly}\left(n\right)\right)$$. Finally, we remark that F_n(L, l) becomes trivial when the number of layers L is Ω(poly(n)), however, as we discuss below, we can still find that Var[∂_νC_G] vanishes exponentially in this case.

Our second main theorem shows that barren plateaus can be avoided for shallow circuits by employing local cost functions. Here we consider m-local cost functions where each $$ {\widehat{O}}_i$$ acts nontrivially on at most m qubits and (on these qubits) can be expressed as $$ {\widehat{O}}_i={\widehat{O}}_i^{{\mu }_i}\otimes {\widehat{O}}_i^{{\mu }^{\prime }}$$:

where $$ {\widehat{O}}_i^{{\mu }_i}$$ are operators acting on m/2 qubits which can be written as a tensor product of Pauli operators. Here, we assume the summation in Eq. (16) includes two possible cases as schematically shown in Fig. 3b: First, when $$ {\widehat{O}}_i^{{\mu }_i}$$ ($$ {\widehat{O}}_i^{{\mu }^{\prime }}$$) acts on the first (last) m/2 qubits of a given S_k, and second, when $$ {\widehat{O}}_i^{{\mu }_i}$$ ($$ {\widehat{O}}_i^{{\mu }^{\prime }}$$) acts on the last (first) m/2 qubits of a given S_k (S_k+1). This type of cost function includes any ultralocal cost function (i.e., where the $$ {\widehat{O}}_i$$ are one-body) as in (2), and also VQE Hamiltonians with up to m/2 neighbor interactions. Then, the following theorem holds.

Theorem 2

Consider a trainable parameter θ^ν in a block W of the ansatz in Fig. 3. Let Var[∂_νC] be the variance of the partial derivative of an m-local cost function C (with O given by (16)) with respect to θ^ν. W_A, W_B of (7), and each block in V(θ) form a local 2-design, then Var[∂_νC] is lower bounded by

with

where $$ i_{\mathcal{L}}$$ is the set of i indices whose associated operators $$ {\widehat{O}}_i$$ act on qubits in the forward light-cone $$ \mathcal{L}$$ of W, and $$ k_{{\mathcal{L}}_{\mathrm{B}}}$$ is the set of k indices whose associated subsystems S_k are in the backward light-cone $$ {\mathcal{L}}_{\mathrm{B}}$$ of W. Here we defined the function $$ ϵ\left(M\right)=D_{\mathrm{HS}}\left(M,\mathrm{Tr}\left(M\right)\mathbb{1}/d_M\right)$$ where D_HS is the Hilbert–Schmidt distance and d_M is the dimension of the matrix M. In addition, $$ {\rho }_{k,k^{\prime }}$$ is the partial trace of the input state ρ down to the subsystems $$ S_k{S}_{k+1}...S_{k^{\prime }}$$.

Let us make a few remarks. First, note that the $$ ϵ\left({\widehat{O}}_i\right)$$ in the lower bound indicates that training V(θ) is easier when $$ {\widehat{O}}_i$$ is far from the identity. Second, the presence of $$ ϵ\left({\rho }_{k,k^{\prime }}\right)$$ in G_n(L, l) implies that we have no guarantee on the trainability of a parameter θ^ν in W if ρ is maximally mixed on the qubits in the backwards light-cone.

From Theorem 2 we derive the following corollary for m-local cost functions, which guarantees the trainability of the ansatz for shallow circuits.

Corollary 2

Consider the function F_n(L, l). Let O be an operator of the form (16), as in Theorem 2. If at least one term $$ c_i^2ϵ\left({\rho }_{k,k^{\prime }}\right)ϵ\left({\widehat{O}}_i\right)$$ in the sum in (18) vanishes no faster than Ω(1/poly(n)), and if the number of layers L is $$ \mathcal{O}\left(\log \left(n\right)\right)$$, then

On the other hand, if at least one term $$ c_i^2ϵ\left({\rho }_{k,k^{\prime }}\right)ϵ\left({\widehat{O}}_i\right)$$ in the sum in (18) vanishes no faster than $$ \mathrm{\Omega }\left(1/2^{\mathrm{poly}\left(\log \left(n\right)\right)}\right)$$, and if the number of layers is $$ \mathcal{O}\left(\mathrm{poly}\left(\log \left(n\right)\right)\right)$$, then

Hence, when L is $$ \mathcal{O}\left(\mathrm{poly}\left(\log \left(n\right)\right)\right)$$ there is a transition region where the lower bound vanishes faster than polynomially, but slower than exponentially.

We finally justify the assumption of each block being a local 2-design from the fact that shallow circuit depths lead to such local 2-designs. Namely, it has been shown that one-dimensional 2-designs have efficient quantum circuit descriptions, requiring $$ \mathcal{O}\left(m^2\right)$$ gates to be exactly implemented³⁸, or $$ \mathcal{O}\left(m\right)$$ to be approximately implemented^39,40. Hence, an L-layered ansatz in which each block forms a 2-design can be exactly implemented with a depth $$ D\in \mathcal{O}\left(m^{2}L\right)$$, and approximately implemented with $$ D\in \mathcal{O}\left(mL\right)$$. For the case of two-dimensional connectivity, it has been shown that approximate 2-designs require a circuit depth of $$ \mathcal{O}\left(\sqrt{m}\right)$$ to be implemented⁴⁰. Therefore, in this case the depth of the layered ansatz is $$ D\in \mathcal{O}\left(\sqrt{m}L\right)$$. The latter shows that increasing the dimensionality of the circuit reduces the circuit depth needed to make each block a 2-design.

Moreover, it has been shown that the Alternating Layered Ansatz of Fig. 3 will form an approximate one-dimensional 2-design on n qubits if the number of layers is $$ \mathcal{O}\left(n\right)$$⁴⁰. Hence, for deep circuits, our ansatz behaves like a random circuit and we recover the barren plateau result of⁹ for both local and global cost functions.

Numerical simulations

As an important example to illustrate the cost-function-dependent barren plateau phenomenon, we consider quantum autoencoders^11,41–44. In particular, the pioneering VQA proposed in ref. ¹¹ has received significant literature attention, due to its importance to quantum machine learning and quantum data compression. Let us briefly explain the algorithm in ref. ¹¹.

Consider a bipartite quantum system AB composed of n_A and n_B qubits, respectively, and let $$ \left\{p_{\mu },\mid {\psi }_{\mu }⟩\right\}$$ be an ensemble of pure states on AB. The goal of the quantum autoencoder is to train a gate sequence V(θ) to compress this ensemble into the A subsystem, such that one can recover each state $$ \mid {\psi }_{\mu }⟩$$ with high fidelity from the information in subsystem A. One can think of B as the “trash” since it is discarded after the action of V(θ).

To quantify the degree of data compression, ref. ¹¹ proposed a cost function of the form:

To address this issue, we propose the following local cost function

Here we simulate the autoencoder algorithm to solve a simple problem where n_A = 1, and where the input state ensemble $$ \left\{p_{\mu },\mid {\psi }_{\mu }⟩\right\}$$ is given by

Numerical results

In our heuristics, the gate sequence V(θ) is given by two layers of the ansatz in Fig. 4, so that the number of gates and parameters in V(θ) increases linearly with n_B. Note that this ansatz is a simplified version of the ansatz in Fig. 3, as we can only generate unitaries with real coefficients. All parameters in V(θ) were randomly initialized and as detailed in the Methods section, we employ a gradient-free training algorithm that gradually increases the number of shots per cost-function evaluation.

Fig. 4

Alternating Layered Ansatz for V(θ) employed in our numerical simulations.

Each layer is composed of control-Z gates acting on alternating pairs of neighboring qubits which are preceded and followed by single qubit rotations around the y-axis, $$ R_y\left({\theta }_i\right)=e^{-i{\theta }_i{\sigma }_y/2}$$. Shown is the case of two layers, n_A = 1, and n_B = 10 qubits. The number of variational parameters and gates scales linearly with n_B: for the case shown there are 71 gates and 51 parameters. While each block in this ansatz will not form an exact local 2-design, and hence does not fall under our theorems, one can still obtain a cost-function-dependent barren plateau.

Analysis of the n-dependence. Figure 5 shows representative results of our numerical implementations of the quantum autoencoder in ref. ¹¹ obtained by training V(θ) with the global and local cost functions respectively given by (22) and (23). Specifically, while we train with finite sampling, in the figures we show the exact cost-function values versus the number of iterations. Here, the top (bottom) axis corresponds to the number of iterations performed while training with $$ C_{\mathrm{G}}^{\prime }$$ ($$ C_{\mathrm{L}}^{\prime }$$). For n_B = 10 and 15, Fig. 5 shows that we are able to train V(θ) for both cost functions. For n_B = 20, the global cost function initially presents a plateau in which the optimizing algorithm is not able to determine a minimizing direction. However, as the number of shots per function evaluation increases, one can eventually minimize $$ C_{\mathrm{G}}^{\prime }$$. Such result indicates the presence of a barren plateau where the gradient takes small values which can only be detected when the number of shots becomes sufficiently large. In this particular example, one is able to start training at around 140 iterations.

Fig. 5

Cost versus number of iterations for the quantum autoencoder problem defined by Eqs. (25)–(26).

In all cases we employed two layers of the ansatz shown in Fig. 4, and we set n_A = 1, while increasing n_B = 10, 15, …, 100. The top (bottom) axis corresponds to the global cost function $$ C_{\mathrm{G}}^{\prime }$$ of Eq. (22) (local cost function $$ C_{\mathrm{L}}^{\prime }$$ of (23)). As can be seen, $$ C_{\mathrm{G}}^{\prime }$$ can be trained up to n_B = 20 qubits, while $$ C_{\mathrm{L}}^{\prime }$$ trained in all cases. These results indicate that global cost function presents a barren plateau even for a shallow depth ansatz, and this can be avoided by employing a local cost function.

When n_B > 20 we are unable to train the global cost function, while always being able to train our proposed local cost function. Note that the number of iterations is different for $$ C_{\mathrm{G}}^{\prime }$$ and $$ C_{\mathrm{L}}^{\prime }$$, as for the global cost function case we reach the maximum number of shots in fewer iterations. These results indicate that the global cost function of (22) exhibits a barren plateau where the gradient of the cost function vanishes exponentially with the number of qubits, and which arises even for constant depth ansatzes. We remark that in principle one can always find a minimizing direction when training $$ C_{\mathrm{G}}^{\prime }$$, although this would require a number of shots that increases exponentially with n_B. Moreover, one can see in Fig. 5 that randomly initializing the parameters always leads to $$ C_{\mathrm{G}}^{\prime }\approx 1$$ due to the narrow gorge phenomenon (see Proposition 1), i.e., where the probability of being near the global minimum vanishes exponentially with n_B.

On the other hand, Fig. 5 shows that the barren plateau is avoided when employing a local cost function since we can train $$ C_{\mathrm{L}}^{\prime }$$ for all considered values of n_B. Moreover, as seen in Fig. 5, $$ C_{\mathrm{L}}^{\prime }$$ can be trained with a small number of shots per cost-function evaluation (as small as 10 shots per evaluation).

Analysis of the L-dependence. The power of Theorem 2 is that it gives the scaling in terms of L. While one can substitute a function of n for L as we did in Corollary 2, one can also directly study the scaling with L (for fixed n). Figure 6 shows the dependence on L when training $$ C_{\mathrm{L}}^{\prime }$$ for the autoencoder example with n_A = 1 and n_B = 10. As one can see, the training becomes more difficult as L increases. Specifically, as shown in the inset it appears to become exponentially more difficult, as the number of shots needed to achieve a fixed cost value grows exponentially with L. This is consistent with (and hence verifies) our bound on the variance in Theorem 2, which vanishes exponentially in L, although we remark that this behavior can saturate for very large L⁹.

Fig. 6

Local cost $$ C_{\mathrm{L}}^{\prime }$$ versus number of iterations for the quantum autoencoder problem in Eqs. (25–26) with n_B = 10.

Each curve corresponds to a different number of layers L in the ansatz of Fig. 4 with L = 2,…, 20. Curves were averaged over 9 instances of the autoencoder. As the number of layers increases, the optimization becomes harder. Inset: Number of shots needed to reach cost values of $$ C_{\mathrm{L}}^{\prime }=0.02$$ and $$ C_{\mathrm{L}}^{\prime }=0.05$$ versus number of layers L. As L increases the number of shots needed to reach the indicated cost values appears to increase exponentially.

In summary, even though the ansatz employed in our heuristics is beyond the scope of our theorems, we still find cost-function-dependent barren plateaus, indicating that the cost-function dependent barren plateau phenomenon might be more general and go beyond our analytical results.

Variance of the cost function partial derivative

Let us first discuss the formulas we employed to compute Var[∂_νC]. Let us first note that without loss of generality, any block W_kl(θ_kl) in the Alternating Layered Ansatz can be written as a product of ζ_kl independent gates from a gate alphabet $$ \mathcal{A}=\left\{G_{\mu }\left(\theta \right)\right\}$$ as

For the proofs of our results, it is helpful to conceptually break up the ansatz as follows. Consider a block W_kl(θ_kl) in the lth layer of the ansatz. For simplicity, we henceforth use W to refer to a given W_kl(θ_kl). Let S_w denote the m-qubit subsystem that contains the qubits W acts on, and let $$ S_{\overline{w}}$$ be the (n − m) subsystem on which W acts trivially. Similarly, let $$ {\mathcal{H}}_w$$ and $$ {\mathcal{H}}_{\overline{w}}$$ denote the Hilbert spaces associated with S_w and $$ S_{\overline{w}}$$, respectively. Then, as shown in Fig. 3a, V(θ) can be expressed as

Let us here recall that the Alternating Layered Ansatz can be implemented with either a 1D or 2D square connectivity as schematically depicted in Fig. 3c. We remark that the following results are valid for both cases as the light-cone structure will be the same. Moreover, the notation employed in our proofs applies to both the 1D and 2D cases. Hence, there is no need to refer to the connectivity dimension in what follows.

Let us now assume that θ^ν is a parameter inside a given block W, we obtain from (6), (27), and (28)

Finally, from (29) we can derive a general formula for the variance:

Computing averages over V

Here we introduce the main tools employed to compute quantities of the form 〈…〉_V. These tools are used throughout the proofs of our main results.

Let us first remark that if the blocks in V(θ) are independent, then any average over V can be computed by averaging over the individual blocks, i.e., $$ {⟨\dots ⟩}_V={⟨\dots ⟩}_{W_{11},\dots ,W_{kl},\dots }={⟨\dots ⟩}_{V_{\mathrm{L}},W,V_{\mathrm{R}}}$$. For simplicity let us first consider the expectation value over a single block W in the ansatz. In principle 〈…〉_W can be approximated by varying the parameters in W and sampling over the resulting 2^m × 2^m unitaries. However, if W forms a t-design, this procedure can be simplified as it is known that sampling over its distribution yields the same properties as sampling random unitaries from the unitary group with respect to the unique normalized Haar measure.

Explicitly, the Haar measure is a uniquely defined left and right-invariant measure over the unitary group dμ(W), such that for any unitary matrix A ∈ U(2^m) and for any function f(W) we have

From the general form of C in Eq. (6) we can see the cost function is a polynomial of degree at most 2 in the matrix elements of each block W_kl in V(θ), and at most 2 in those of $$ {\left(W_{kl}\right)}^{†}$$. Then, if a given block W forms a 2-design, one can employ the following elementwise formula of the Weingarten calculus^55,56 to explicitly evaluate averages over W up to the second moment:

Intuition behind the main results

The goal of this section is to provide some intuition for our main results. Specifically, we show here how the scaling of the cost function variance can be related to the number of blocks we have to integrate to compute $$ {⟨\cdots ⟩}_{V_{\mathrm{R}},V_{\mathrm{L}}}$$, the locality of the cost functions, and with the number of layers in the ansatz.

First, we recall from Eq. (38) that integrating over a block leads to a coefficient of the order 1/2^2m. Hence, we see that the more blocks one integrates over, the worse the scaling can be.

We now generalize the warm-up example. Let V(θ) be a single layer of the alternating ansatz of Fig. 3, i.e., V(θ) is a tensor product of m-qubit blocks W_k: = W_k1, with k = 1, …, ξ (and with ξ = n/m), so that θ^ν is in the block $$ W_{k^{\prime }}$$. In the Supplementary Note 5 we generalize this scenario to the when the input state is not $$ ∣\mathit{0}⟩$$, but instead is an arbitrary state ρ.

From (31), the partial derivative of the global cost function in (1) can be expressed as

On the other hand, for a local cost let us consider a single term in (3) where $$ j\in S_{\tilde{k}}$$, so that

Let us now briefly provide some intuition as to why the scaling of local cost gradients becomes exponentially vanishing with the number of layers as in Theorem 2. Consider the case when V(θ) contains L layers of the ansatz in Fig. 3. Moreover, as shown in Fig. 7, let W be in the first layer, and let O_i act on the m topmost qubits of $$ \mathcal{L}$$. As schematically depicted in Fig. 7, we now have to integrating over L − 1 blocks. Then, as proved in the Supplementary Note 5, integrating over a block leads to a coefficient 2^m/2/(2^m + 1). Hence, after integrating L − 1 times, we obtain a coefficient $$ 2^{m\left(L-1\right)/2}/{\left(2^m+1\right)}^{L-1}$$ which vanishes no faster than $$ \mathrm{\Omega }\left(1/\mathrm{poly}\left(n\right)\right)$$ if $$ mL\in \mathcal{O}\left(\log \left(n\right)\right)$$.

Fig. 7

The block W is in the first layer of V(θ), and the operator O_i acts on the topmost m qubits in the forward light-cone $$ \mathcal{L}$$ of W.

Dashed thick lines indicate the backward light-cone of O_i. All but L − 1 blocks simplify to identity in Ω_qp of Eq. (34).

As we discuss below, for more general scenarios the computation of Var[∂_νC] becomes more complex.

Sketch of the proof of the main theorems

Here we present a sketch of the proof of Theorems 1 and 2. We refer the reader to the Supplementary Information for a detailed version of the proofs.

As mentioned in the previous subsection, if each block in V(θ) forms a local 2-design, then we can explicitly calculate expectation values 〈…〉_W via (38). Hence, to compute $$ {⟨\mathrm{\Delta }{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^{{\mathit{p}}^{\prime }{\mathit{q}}^{\prime }}⟩}_{V_{\mathrm{R}}}$$, and $$ {⟨\mathrm{\Delta }{\mathrm{\Psi }}_{\mathit{p}\mathit{q}}^{{\mathit{p}}^{\prime }{\mathit{q}}^{\prime }}⟩}_{V_{\mathrm{L}}}$$ in (31), one needs to algorithmically integrate over each block using the Weingarten calculus. In order to make such computation tractable, we employ the tensor network representation of quantum circuits.

For the sake of clarity, we recall that any two-qubit gate can be expressed as $$ U={\sum }_{ijkl}{U}_{ijkl}∣ij⟩⟨kl∣$$, where U_ijkl is a 2 × 2 × 2 × 2 tensor. Similarly, any block in the ansatz can be considered as a $$ 2^{\frac{m}{2}}\times 2^{\frac{m}{2}}\times 2^{\frac{m}{2}}\times 2^{\frac{m}{2}}$$ tensor. As schematically shown in Fig. 8a, one can use the circuit description of $$ {\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i$$ and Ψ_pq to derive the tensor network representation of terms such as $$ \mathrm{Tr}\left[{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i{\mathrm{\Omega }}_{{\mathit{q}}^{\prime }{\mathit{p}}^{\prime }}^j\right]$$. Here, $$ {\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i$$ is obtained from (34) by simply replacing O with O_i.

Fig. 8

Tensor-network representations of the terms relevant to Var[∂_νC].

a Representation of $$ {\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i$$ of Eq. (34) (left), where the superscript indicates that O is replaced by O_i. In this illustration, we show the case of n = 2m qubits, and we denote $$ P_{\mathit{p}\mathit{q}}=∣\mathit{q}⟩⟨\mathit{p}∣$$. We also show the representation of $$ \mathrm{Tr}\left[{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i{\mathrm{\Omega }}_{{\mathit{q}}^{\prime }{\mathit{p}}^{\prime }}^j\right]$$ (middle) and of $$ \mathrm{Tr}\left[{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i\right]\mathrm{Tr}\left[{\mathrm{\Omega }}_{{\mathit{q}}^{\prime }{\mathit{p}}^{\prime }}^j\right]$$ (right). b By means of the Weingarten calculus we can algorithmically integrate over each block in the ansatz. After each integration one obtains four new tensors according to Eq. (38). Here we show the tensor obtained after the integrations $$ \int d\mu \left(W\right)\mathrm{Tr}\left[{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i{\mathrm{\Omega }}_{{\mathit{q}}^{\prime }{\mathit{p}}^{\prime }}^j\right]$$ and $$ \int d\mu \left(W\right)\mathrm{Tr}\left[{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i\right]\mathrm{Tr}\left[{\mathrm{\Omega }}_{{\mathit{q}}^{\prime }{\mathit{p}}^{\prime }}^j\right]$$, which are needed to compute $$ {⟨\mathrm{\Delta }{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^{{\mathit{q}}^{\prime }{\mathit{p}}^{\prime }}⟩}_{V_{\mathrm{R}}}$$ as in Eq. (31). c As shown in the Supplementary Note 1, the result of the integration is a sum of the form (49), where the deltas over p, q, $$ {\mathit{p}}^{\prime }$$, and $$ {\mathit{q}}^{\prime }$$ arise from the contractions between P_pq and $$ P_{{\mathit{p}}^{\prime }{\mathit{q}}^{\prime }}$$.

In Fig. 8b we depict an example where we employ the tensor network representation of $$ {\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i$$ to compute the average of $$ \mathrm{Tr}\left[{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i{\mathrm{\Omega }}_{{\mathit{q}}^{\prime }{\mathit{p}}^{\prime }}^j\right]$$, and $$ \mathrm{Tr}\left[{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i\right]\mathrm{Tr}\left[{\mathrm{\Omega }}_{{\mathit{q}}^{\prime }{\mathit{p}}^{\prime }}^j\right]$$. As expected, after each integration one obtains a sum of four new tensor networks according to Eq. (38).

Proof of Theorem 2

Let us first consider an m-local cost function C where O is given by (16), and where $$ {\widehat{O}}_i$$ acts nontrivially in a given subsystem S_k of $$ \mathcal{S}$$. In particular, when $$ {\widehat{O}}_i$$ is of this form the proof is simplified, although the more general proof is presented in the Supplementary Note 6. If $$ S_k\not\subset S_{\mathcal{L}}$$ we find $$ {\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^i\propto {\mathbb{1}}_w$$, and hence

Then, as shown in the Supplementary Information

By employing properties of D_HS one can show (see Supplementary Note 6)

Proof of Theorem 1

Let us now provide a sketch of the proof of Theorem 1, case (i). Here we denote for simplicity $$ {\widehat{O}}_k:={\widehat{O}}_{1k}$$. We leave the proof of case (ii) for the Supplementary Note 7. In this case there are now operators O_i which act outside of the forward light-cone $$ \mathcal{L}$$ of W. Hence, it is convenient to include in V_R not only all the gates in $$ \mathcal{L}$$ but also all the blocks in the final layer of V(θ) (i.e., all blocks W_kL, with k = 1, …ξ). We can define $$ S_{\overline{\mathcal{L}}}$$ as the compliment of $$ S_{\mathcal{L}}$$, i.e., as the subsystem of all qubits which are not in $$ \mathcal{L}$$ (with associated Hilbert-space $$ {\mathcal{H}}_{\overline{\mathcal{L}}}$$). Then, we have $$ V_{\mathrm{R}}=V_{\mathcal{L}}\otimes V_{\overline{\mathcal{L}}}$$ and $$ ∣\mathit{q}⟩⟨\mathit{p}∣=∣\mathit{q}⟩{⟨\mathit{p}∣}_{\mathcal{L}}\otimes ∣\mathit{q}⟩{⟨\mathit{p}∣}_{\overline{\mathcal{L}}}$$, where we define $$ V_{\overline{\mathcal{L}}}:={⨂}_{k\in k_{\overline{\mathcal{L}}}}{W}_{kL}$$, $$ ∣\mathit{q}⟩{⟨\mathit{p}∣}_{\mathcal{L}}:{=⨂}_{k\in k_{\mathcal{L}}}∣\mathit{q}⟩{⟨\mathit{p}∣}_k$$, and $$ ∣\mathit{q}⟩{⟨\mathit{p}∣}_{\overline{\mathcal{L}}}:{=⨂}_{k^{\prime }\in k_{\overline{\mathcal{L}}}}∣\mathit{q}⟩{⟨\mathit{p}∣}_{k^{\prime }}$$. Here, we define $$ k_{\mathcal{L}}:=\left\{k:S_k\subseteq S_{\mathcal{L}}\right\}$$ and $$ k_{\overline{\mathcal{L}}}:=\left\{k:S_k\subseteq S_{\overline{\mathcal{L}}}\right\}$$, which are the set of indices whose associated qubits are inside and outside $$ \mathcal{L}$$, respectively. We also write $$ O=c_0\mathbb{1}+c_1{\widehat{O}}_{\mathcal{L}}\otimes {\widehat{O}}_{\overline{\mathcal{L}}}$$, where we define $$ {\widehat{O}}_{\mathcal{L}}:{=⨂}_{k\in k_{\mathcal{L}}}{\widehat{O}}_k$$ and $$ {\widehat{O}}_{\overline{\mathcal{L}}}:{=⨂}_{k^{\prime }\in k_{\overline{\mathcal{L}}}}{\widehat{O}}_{k^{\prime }}$$.

Using the fact that the blocks in V(θ) are independent we can now compute $$ {⟨\mathrm{\Delta }{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^{{\mathit{q}}^{\prime }{\mathit{p}}^{\prime }}⟩}_{V_{\mathrm{R}}}={⟨\mathrm{\Delta }{\mathrm{\Omega }}_{\mathit{q}\mathit{p}}^{{\mathit{q}}^{\prime }{\mathit{p}}^{\prime }}⟩}_{V_{\overline{\mathcal{L}}},V_{\mathcal{L}}}$$. Then, from the definition of Ω_pq in Eq. (34) and the fact that one can always express

On the other hand, as shown in the Supplementary Note 7 (and as schematically depicted in Fig. 8c), when computing the expectation value $$ {⟨\dots ⟩}_{V_{\mathcal{L}}}$$ in (47), one obtains

Ansatz and optimization method

Here we describe the gradient-free optimization method used in our heuristics. First, we note that all the parameters in the ansatz are randomly initialized. Then, at each iteration, one solves the following sub-space search problem: $$ \underset{\mathit{s}\in {\mathbb{R}}^d}{\min }C\left(\mathit{\theta }+\mathit{A}\cdot \mathit{s}\right)$$, where A is a randomly generated isometry, and s = (s₁, …, s_d) is a vector of coefficients to be optimized over. We used d = 10 in our simulations. Moreover, the training algorithm gradually increases the number of shots per cost-function evaluation. Initially, C is evaluated with 10 shots, and once the optimization reaches a plateau, the number of shots is increased by a factor of 3/2. This process is repeated until a termination condition on the value of C is achieved, or until we reach the maximum value of 10⁵ shots per function evaluation. While this is a simple variable-shot approach, we remark that a more advanced variable-shot optimizer can be found in ref. ⁵⁷.

Finally, let us remark that while we employ a sub-space search algorithm, in the presence of barren plateaus all optimization methods will (on average) fail unless the algorithm has a precision (i.e., number of shots) that grows exponentially with n. The latter is due to the fact that an exponentially vanishing gradient implies that on average the cost function landscape will essentially be flat, with the slope of the order of $$ \mathcal{O}\left(1/2^n\right)$$. Hence, unless one has a precision that can detect such small changes in the cost value, one will not be able to determine a cost minimization direction with gradient-based, or even with black-box optimizers such as the Nelder–Mead method^58–61.