Barren plateaus in quantum neural network training landscapes — TEI-tagged view

Jarrod R. McCleanpersName, Sergio BoixopersName, Vadim N. SmelyanskiypersName, Ryan BabbushpersName, Hartmut NevenpersName (2018date). “Barren plateaus in quantum neural network training landscapes.” Nature Communicationstitle·j.

Object of study — gradientsterm·key of randomly initialized parameterized quantum circuitsterm·key in hybrid quantum-classical algorithmsterm·key

Research question — whether random circuits are a good initial guess for training parameterized quantum circuitsterm·key

Contribution — proof and numerics that gradientsterm·key vanish exponentially in qubitterm·key number for random circuits - barren plateausterm·dom

Full text — tagged

The reference list is not part of the text we hold for this paper. Our copy was extracted from the publisher's page and the bibliography did not survive that extraction, so the article below ends before its references. Nothing has been removed by us.

Barren plateausterm·dom in quantum neural network training landscapes Abstract Many experimental proposals for noisy intermediate scale quantumterm·dom devices involve training a parameterized quantum circuitterm·mth with a classical optimization loop. Such hybrid quantum-classical algorithmsterm·key are popular for applications in quantum simulation, optimization, and machine learning. Due to its simplicity and hardware efficiency, random circuits are often proposed as initial guesses for exploring the space of quantum states. We show that the exponential dimension of Hilbert spaceterm·key and the gradientterm·key estimation complexity make this choice unsuitable for hybrid quantum-classical algorithmsterm·key run on more than a few qubitsterm·key. Specifically, we show that for a wide class of reasonable parameterized quantum circuitsterm·key, the probability that the gradientterm·key along any reasonable direction is non-zero to some fixed precision is exponentially small as a function of the number of qubitsterm·dom. We argue that this is related to the 2-designterm·mth characteristic of random circuits, and that solutions to this problem must be studied.

Introduction Rapid developments in quantum hardware have motivated advances in algorithms to run in the so-called noisy intermediate scale quantumterm·dom (NISQterm·dom) regime 1 . Many of the most promising application-oriented approaches are hybrid quantum–classical algorithmsterm·key that rely on optimization of a parameterized quantum circuitterm·mth 2 – 8 . The resilience of these approaches to certain types of errors and high flexibility with respect to coherence time and gate requirements make them especially attractive for NISQterm·dom implementations 3 , 9 – 11 .

The first implementation of such algorithms was developed in the context of quantum simulation with the variational quantum eigensolver 2 , 3 . This algorithm has been successfully demonstrated on a number of experimental setups with extensions to excited states and other forms of incoherent error mitigation 2 , 9 , 12 – 16 . Since then, the quantum approximate optimization algorithm was developed in a similar context to address hard optimization problems 5 , 17 – 19 . This algorithm has also been demonstrated on quantum devices 20 . These approaches have even been extended to both quantum machine learning and error correction 6 , 7 , 20 – 23 .

While the precise formulation of these methods and their domains of applicability differ considerably, they typically tend to rely upon the optimization of some parameterized unitary circuit with respect to an objective function that is typically a simple sum of Pauli operators or fidelity with respect to some state. This framework is reminiscent of the methodology of classical neural networks 23 , 24 . As with any non-linear optimization, the choice of both the parameterization and the initial state is important. In quantum simulation, there is often a choice inspired by physical domain knowledge 3 , 17 , 25 – 29 . However, in all domains of applicability, there have been implementations that utilize parametrized random circuits of varying depth 7 , 13 , 21 , 23 , 30 . Within quantum simulation that approach has been referred to as a “hardware efficient ansatz” 13 . This is in contrast to the previous proposals, such as the variational quantum eigensolver 2 , 3 , 9 , which used parametrized structured circuits inspired by the problem at hand, such as unitary coupled cluster.

When little structure is known about the problem, or constraints of the existing quantum hardware may prevent utilizing that structure, choosing a random implementable circuit seems to provide an unbiased choice. One might also expect, based on recent experimental designs for “quantum supremacy”, that random quantum circuitsterm·key are a powerful tool for such a task 31 . Also, despite concerns about gradient-based methods in classical deep neural networksterm·mth 32 – 34 , they are successful 24 , even if using random initialization 33 , 35 . However, in the quantum case one must remember that the estimation of even a single gradientterm·key component will scale as O (1/ ε α ) for some small power α 36 as opposed to classical implementations where the same is achieved in O (log(1/ ε )) time, where ε is the desired accuracy in the gradientterm·key that is inevitably tied to its magnitude.

We will present results related to random quantum circuitsterm·key in the context of the exponential dimension of Hilbert spaceterm·key and gradient-based hybrid quantum–classical algorithmsterm·key. A cartoon depiction of this is given in Fig. 1 . We show that for a large class of random circuits, the average value of the gradientterm·key of the objective function is zero, and the probability that any given instance of such a random circuit deviates from this average value by a small constant ε is exponentially small in the number of qubitsterm·dom. This can be understood in the geometric context of concentration of measureterm·key 37 – 39 for high-dimensional spaces. When the measure of the space concentrates in this way, the value of any reasonably smooth function will tend towards its average with exponential probability, a fact made formal by Levy’s lemmaterm·key 40 . In our context, this means that the gradientterm·key is zero over vast reaches of quantum space. The region where the gradientterm·key is zero does not correspond to local minima of interest, but rather an exponentially large plateau of states that have exponentially small deviations in the objective value from the average of the totally mixed state. We argue that the depth of circuits which achieve these undesirable properties are modest, requiring only O ( n 1/ d ) depth circuits on a d dimensional array, and numerically evaluate the constant factors one expects to encounter for small instances of this kind. While our results highlight the importance of avoiding random initialization in parametric circuit approaches, they do not discount the value of random quantum circuitsterm·key in other applications such as information security or demonstrations of quantum supremacy. We close with an outlook on how this result should shape strategies in ansatz design for scaling to larger experiments. Fig. 1 Cartoon of concentration of quantum observables. The sphere depicts the phenomenon of concentration of measureterm·key in quantum space: the fraction of states that fall outside a fixed angular distance from zero along any coordinate decreases exponentially in the number of qubitsterm·dom 40 . This implies a flat plateau where observables concentrate on their average over Hilbert spaceterm·key and the gradientterm·key is exponentially small. The fact that only an exponentially small fraction of states fall outside of this band means that searches resembling random walks will have an exponentially small probability of exiting this “barren plateauterm·dom”

Results Gradientterm·key concentration in random circuits We will discuss random parameterized quantum circuitsterm·mth (RPQCsterm·mth) 1 U ( θ ) = U ( θ 1 , . . . , θ L ) = ∏ l = 1 L U l ( θ l ) W l , where U l ( θ l ) = exp(− iθ l V l ), V l is a Hermitian operator, and W l is a generic unitary operator that does not depend on any angle θ l . Circuits of this form are a natural choice due to a straightforward evaluation of the gradientterm·key with respect to most objective functions and have been introduced in a number of contexts already 26 , 41 . Consider an objective function E ( θ ) expressed as the expectation value over some Hermitian operator H , 2 E ( θ ) = ⟨ 0 ∣ U ( θ ) † H U ( θ ) ∣ 0 ⟩ .

When the RPQCsterm·mth are parameterized in this way, the gradientterm·key of the objective function takes a simple form: 3 ∂ k E ≡ ∂ E ( θ ) ∂ θ k = i 0 U - † V k , U + † H U + U - 0 , where we introduce the notations U - ≡ ∏ l = 0 k - 1 U l ( θ l ) W l , U + ≡ ∏ l = k L U l ( θ l ) W l , and henceforth drop the subscript k from V k → V for ease of exposition. Finally, we will define our RPQCsterm·mth U ( θ ) to have the property that for any gradientterm·key direction ∂ k E defined above, the circuit implementing U ( θ ) is sufficiently random such that either U − , U + , or both match the Haar distribution up to the second moment, and the circuits U − and U + are independent.

Our results make use of properties of the Haar measureterm·key on the unitary group dμ Haar ( U ) ≡ dμ ( U ), which is the unique left- and right-invariant measure such that 4 ∫ U ( N ) d μ ( U ) f ( U ) = ∫ d μ ( U ) f ( V U ) = ∫ d μ ( U ) f ( U V ) , for any f ( U ) and V ∈ U ( N ), where the integration domain will be implied to be U ( N ) when not explicitly listed. While this property is valuable for proofs, quantum circuitsterm·key that exactly achieve this invariance generically require exponential resources. This motivates the concept of unitary t -designs 42 – 44 , which satisfy the above properties for restricted classes of f ( U ), often requiring only modest polynomial resources. Suppose { p i , V i } is an ensemble of unitary operators, with unitary V i being sampled with probability p i . The ensemble { p i , V i } is a t -design if 5 ∑ i p i V i ⊗ t ρ ( V i † ) ⊗ t = ∫ d μ ( U ) U ⊗ t ρ ( U † ) ⊗ t .

This definition is equivalent to the property that if f ( U ) is a polynomial of at most degree t in the matrix elements of U and at most degree t in the matrix elements of U * , then averaging over the t -design { p i , V i } will yield the same result as averaging over the unitary group with the respect to the Haar measureterm·key.

The average value of the gradientterm·key is a concept that requires additional specification because, for a given point, the gradientterm·key can only be defined in terms of the circuit that led to that point. We will use a practical definition that leads to the value we are interested in, namely 6 ⟨ ∂ k E ⟩ = ∫ d U p ( U ) ∂ k ⟨ 0 ∣ U ( θ ) † H U ( θ ) ∣ 0 ⟩ , where p ( U ) is the probability distribution function of U . A review on the properties of products of independent random matrices can be found in ref. 45 . The assumptions of independence and at least one of U − or U + forming a 1-design in our RPQCsterm·mth implies that 〈∂ k E 〉 = 0, as shown in the Methods.

Levy’s lemmaterm·key informs our intuition about the the expected variance of this quantity through simple geometric arguments. In particular, Haar random unitaries on n qubitsterm·key will output states uniformly in the D = 2 n − 1 dimensional hypersphere. The derivative with respect to the parameters θ is Lipschitz continuous with some parameter η that depends on the operator H . Levy’s lemmaterm·key then implies that the variance of measurementsterm·mth will decrease exponentially in the number of qubitsterm·dom. This intuition may be made more precise through explicit calculation of the variance, which is done in more detail in the Methods. The result to first order is 7 Var ∂ k E ≈ - Tr ρ 2 2 2 n - 1 Tr V , u † H u 2 U + - Tr H 2 2 2 n - 1 Tr V , u ρ u † 2 U - 1 2 3 n - 1 Tr H 2 Tr ρ 2 Tr V 2 where the notation ⟨ f ( u ) ⟩ U x indicates the average with u drawn from p ( U x ), and the first case corresponds to U − being a 2-designterm·mth and not U + , the second to U + being a 2-designterm·mth but not U − , and the third to both U + and U − being 2-designsterm·mth. We emphasize the fact that this variance depends at most on polynomials of degree 2 in U and polynomials of degree 2 in U * . Whereas a unitary 2-designterm·mth will exhibit the correct variance 43 , 46 , a unitary 1-design will exhibit the correct average value, but not necessarily the variance. As a result, if a circuit is of sufficient depth that for any ∂ k E , either U − or U + forms a 2-designterm·mth, then with high probability one will produce an ansatz state on a barren plateauterm·dom of the quantum landscape, with no interesting search directions in sight.

From these results, it is clear that only either U + or U − needs to be sufficiently random to poison the gradientterm·key for the remainder of the circuit. For example, while it is somewhat unintuitive, even the first element of a circuit, k = 1, will have a vanishing gradientterm·key due to the circuit following it, U + . Additionally, we see that there is no detailed dependence on the structure of V k , other than the rate at which they help randomize the circuit, determining at what depth one expects to find an approximate 2-designterm·mth.

Numerical simulations The previous section shows that for reasonable classes of RPQCsterm·mth at a sufficient number of qubitsterm·dom and depth, one will end up on a barren plateauterm·dom. Here we verify this result for even modest depth one-dimensional (1D) random circuits with numerical simulations. This helps to clarify the rate of concentration for realistic circuits and shows the transition as the circuit grows in length from a single layer to a circuit demonstrating statistics analogous to a 2-designterm·mth.

The circuits and objective functions used in our numerical experiments begin with a layer of R Y ( π /4) = exp(− iπ /8 Y ) gates to prevent X , Y , or Z from being an especially preferential direction with respect to gradientsterm·key. Then, the circuit proceeds by a number of layers. Each layer consists of a parallel application of single qubitterm·key rotations to all qubitsterm·key, given by R P ( θ ) where P ∈{ X , Y , Z } is chosen with uniform probability and θ ∈[0, 2 π ) is also chosen uniformly. This layer is followed by a layer of 1D nearest neighbor controlled phase gates, as in Fig. 2 . Thus, the number of angles is the number of qubitsterm·dom times the number of layers. Fig. 2 Structure of quantum circuitsterm·key. a The generic subunit of circuits we study in this work, with a parameterized component U l ( θ l ) and non-parameterized unit W l for each layer l . b Example schematic of the 1D random circuits used in our numerical experiments. The circuit begins with R Y π 4 gates applied to all qubitsterm·key followed by a specified number of layers of randomly chosen Pauli rotations applied to each qubitterm·key and then a 1D ladder of controlled Z gates. The initial R Y π 4 gates are not repeated in each layer. The indices i and j in θ i , j index the layer and qubitterm·key, respectively. For each layer and qub it P i , j ∈{ X , Y , Z } and θ i , j ∈[0,2 π ) are sampled independently The objective operator H is chosen to be a single Pauli ZZ operator acting on the first and second qubitsterm·key, H = Z 1 Z 2 . The gradientterm·key is evaluated with respect to the first parameter, θ 1,1 . This simple choice helps to extract the exponential scaling. As complex objectives can be written as sums of these operators, the results for large objectives can be inferred from these numbers. Moreover, it is clear that for any polynomial sum of these operators, the exponential decay of the signal in the gradientterm·key will not be circumvented.

From Fig. 3 we see that for a single 2-local Pauli term, both the expected value of the gradientterm·key and its spread decay exponentially as a function of the number of qubitsterm·dom even when the number of layers is a modest linear function. Empirically for our linear connectivity, we see that value is about 10 n where n is the number of qubitsterm·dom, following the expected scaling of O ( n 1/ d ) where d is the dimension of the connectivity. For empirical reference, the expected gate depth in a chemistry ansatz such as unitary coupled cluster is at least O ( n 3 ), meaning that if the initial parameters were randomized, this effect could be expected on less than 10 orbitals, a truly small problem in chemical terms. We also observe in Fig. 4 that as the number of layers increases, there is a transition to a 2-designterm·mth where the variance converges. This leads to a distinct plateau as the circuit length increases, where the height of the plateau is determined by the number of qubitsterm·dom. An additional example with an objective function defined by projection on a target state is provided as Supplementary Figures 1 and 2 , showing the rapid decay of variance and similar plateaus as a function of circuit length. These results substantiate our conclusion that gradientsterm·key in modest-sized random circuits tend to vanish without additional mitigating steps. Fig. 3 Exponential decay of variance. The sample variance of the gradientterm·key of the energy for the first circuit component of a two-local Pauli term ∂ θ 1 , 1 E plotted as a function of the number of qubitsterm·dom on a semi-log plot. As predicted, an exponential decay is observed as a function of the number of qubitsterm·dom, n , for both the expected value and its spread. The slope of the fit line is indicative of the rate of exponential decay as determined by the operator Fig. 4 Convergence to 2-designterm·mth limit. Here we show the sample variance of the gradientterm·key of the energy for the first circuit component of a two-local Pauli term ∂ θ 1 , 1 E plotted as a function of the number of layers, L , in a 1D quantum circuitterm·mth. The different lines correspond to all even numbers of qubitsterm·key between 2 and 24, with 2 qubitsterm·key being the top line, and the rest being ordered by qubitterm·key number. The dotted black lines depict the 2-designterm·mth asymptotes for this Hamiltonian as determined by our analytic results. This shows the convergence of the second moment as a function of the number of layers to a fixed value determined by the number of qubitsterm·dom Contrast with gradientsterm·key in classical deep networks Finally, we contrast our results with the vanishing (and exploding) gradientterm·key problem of classical deep neural networksterm·mth 32 – 34 , 47 . At least two key differences are present in the quantum case: (i) the different scaling of the vanishing gradientterm·key and (ii) the complexity of computing expected values.

The gradientterm·key in a classical deep neural networkterm·mth can vanish exponentially in the number of layers 32 , 33 , while in a quantum circuitterm·mth the gradientterm·key may vanish exponentially in the number of qubitsterm·dom, as shown above. In the classical case, the gradientterm·key for a weight in a neuron depends on the sum of all the paths connecting that neuron to the output, and when the weights are initialized with random values the paths have random signs which cancels the signal 32 . The number of paths is exponential in the number of layers. In the quantum case, the number of paths is exponential in the number of gates, and also have random signs 31 . The gradientterm·key saturates to an exponential in the number of qubitsterm·dom because the output state is normalized.

The estimation of the gradientterm·key for each training batch for a classical neural network is limited by machine precision and scales with O (log(1/ ε )). Even if the gradientterm·key is small, as long as it is consistent enough between batches, the method may eventually succeed. On a quantum device, the cost of estimating the gradientterm·key scales as O (1/ ε α ) 36 . For any number of measurements much lower than 1/|| g || α , where || g || is the norm of the gradientterm·key, a gradient-based optimization will result in a random walk. By concentration of measureterm·key, a random walk will have exponentially small probability of exiting the barren plateauterm·dom. As a result, gradientterm·key descent without some additional strategy cannot circumvent this challenge on a quantum device in polynomial time.

Discussion We have seen both analytically and numerically that for a wide class of random quantum circuitsterm·key, the expected values of observables concentrate to their averages over Hilbert spaceterm·key and gradientsterm·key concentrate to zero. This represents an interesting statement about the geometry of quantum circuitsterm·key and landscapes related to hybrid quantum–classical algorithmsterm·key. More practically, it means that randomly initialized circuits of sufficient depth will find relatively little utility in hybrid quantum–classical algorithmsterm·key.

Historically, vanishing gradientsterm·key may have played a role in the early winter of deep neural networks 32 , 34 , 47 . However, multiple techniques have been proposed to mitigate this problem 24 , 35 , 48 , 49 , and the amount of training data and computational power available has grown substantially. One approach to avoid these landscapes in the quantum setting is to use structured initial guesses, such as those adopted in quantum simulation. Another possibility is to use pre-training segment by segment, which was an early success in the classical setting 48 , 50 . These or other alternatives must be studied if these ansatze are to be successful beyond a few qubitsterm·key.

Methods We explicitly show the expectation value of the gradientterm·key is 0 and that under our assumptions the variance decays exponentially in the number of qubitsterm·dom. By our definition of RPQCsterm·mth, we have that for any specified direction ∂ k E , both U − and U + are independently distributed and either U − or U + match the Haar distribution up to at least the second moment (they are a 2-designterm·mth). The assumption of independence is equivalent to 8 p ( U ) = ∫ d U + p ( U + ) ∫ d U - p ( U - ) × δ ( U + U - - U ) , which allows us to rewrite the expression as 9 ⟨ ∂ k E ⟩ = i ∫ d U - p ( U - ) Tr ρ - × ∫ d U + p ( U + ) V , U + † H U + .

We will utilize explicit integration over the unitary group with respect to the Haar measureterm·key, which up to the first moment can be expressed as 51 10 ∫ d μ ( U ) U i j U k m † = ∫ d μ ( U ) U i j U m k * = δ i m δ j k N , where N is the dimension of the space, typically 2 n for n qubitsterm·key. Using this expression, one may readily verify that 11 M = ∫ d μ ( U ) U O U † = Tr O N I , which we use in the following. Now, making use of the assumption that either U + or U − matches the Haar measureterm·key up to the first moment (it is a 1-design), we first examine the case where U − is at least a 1-design and find that 12 ⟨ ∂ k E ⟩ = i ∫ d μ U - Tr ρ - × V , ∫ d U + p ( U + ) U + † H U + = i N Tr V , ∫ d U + p ( U + ) U + † H U + = 0 , where we have defined ρ - = U - ∣ 0 ⟩ ⟨ 0 ∣ U - † and used the fact that the trace of a commutator of trace class operators is zero. In the second case, where we assume U + is at least a 1-design, 13 ⟨ ∂ k E ⟩ = i ∫ d U - p ( U - ) Tr ρ - ∫ d μ U + V , U + † H U + = i Tr H N ∫ d U - p ( U - ) Tr ρ - V , I = 0 . An advantage of the explicit polynomial formulas are that they allow an analytic calculation of the variance as well, which allows precise specification of the coefficient in Levy’s lemmaterm·key. In cases where the integrals depend on up to two powers of elements of U and U * , one may make use of the elementwise formula 51 14 ∫ d μ ( U ) U i 1 j 1 U i 2 j 2 U i 1 ′ j 1 ′ * U i 2 ′ j 2 ′ * = δ i 1 i 1 ′ δ i 2 i 2 ′ δ j 1 j 1 ′ δ j 2 j 2 ′ + δ i 1 i 2 ′ δ i 2 i 1 ′ δ j 1 j 2 ′ δ j 2 j 1 ′ N 2 - 1 - δ i 1 i 1 ′ δ i 2 i 2 ′ δ j 1 j 2 ′ δ j 2 j 1 ′ + δ i 1 i 2 ′ δ i 2 i 1 ′ δ j 1 j 1 ′ δ j 2 j 2 ′ N ( N 2 - 1 ) .

The variance of the gradientterm·key is defined by 15 Var [ ∂ k E ] = ⟨ ( ∂ k E ) 2 ⟩ , as we have seen above that 〈∂ k E 〉 = 0. Through use of the above formula for integration up to the second moment of the Haar distribution, one may evaluate this expression in 3 separate cases. For simplicity and relevance, we evaluate them in the asymptotic case including only the dominant contribution as determined by the inverse dimension.

In the case where U − is a 2-designterm·mth but not U + , 16 Var [ ∂ k E ] ≈ 2 Tr ( ρ 2 ) N 2 - 1 Tr H u 2 V 2 - ( H u V ) 2 U + = - Tr ( ρ 2 ) 2 2 n - 1 Tr V , H u 2 U + , where H u = u † H u and we have defined the notation ⟨ f ( u ) ⟩ U x to mean the average over u sampled from p ( U x ). In the case where U + is a 2-designterm·mth but not U − , 17 Var [ ∂ k E ] ≈ 2 Tr ( H 2 ) N 2 - 1 Tr ρ u 2 V 2 - ( ρ u V ) 2 U - = - Tr ( H 2 ) 2 2 n - 1 Tr V , ρ u 2 U - , where ρ u = u ρ u † . Finally in the case where both U + and U − are 2-designsterm·mth 18 Var [ ∂ k E ] ≈ 1 2 ( 3 n - 1 ) Tr H 2 Tr ρ 2 Tr V 2 .

In all cases, the exponential decay of the gradientterm·key as a function of the number of qubitsterm·dom is evident.

Electronic supplementary material Supplementary Information Peer Review File