PaperlayerView exact revision on arXiv

Source-linked AI summary

Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits

M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, Patrick J. Coles

arXiv:2001.00550v3quant-phcs.LG

TL;DR

VQAs lack rigorous scaling guarantees, especially for hardware-efficient ansatzes and cost functions whose operationally meaningful choices are unclear. This paper rigorously analyzes gradient scaling for global and local costs in shallow alternating layered ansatzes, finding exponential decay for global costs but at-worst polynomial decay for local costs at depth O(log n).

  • Problem

    VQAs have few rigorous scaling results, while choosing operationally meaningful cost functions for many applications is unclear.

    Source: INTRODUCTION · p. 1

  • Method

    The paper derives gradient-variance bounds for global and local cost functions in randomly initialized shallow alternating layered ansatzes composed of local 2-design blocks.

    Source: General framework · p. 3, DISCUSSION · p. 8

  • Results

    Global costs exhibit exponentially vanishing gradients even in shallow circuits, whereas local costs vanish polynomially for depth O(log n).

    Source: INTRODUCTION · p. 2, DISCUSSION · p. 8

  • Takeaways & Limitations

    Cost-function locality connects VQA trainability to operational relevance, motivating careful cost selection and revisions for some proposed VQAs.

    Source: INTRODUCTION · p. 2, DISCUSSION · p. 8

    Whether these scaling behaviors extend to other ansatzes, cost functions, and architectures remains an open question.

    Source: DISCUSSION · p. 9

Abstract

from arXiv · show

Variational quantum algorithms (VQAs) optimize the parameters $\vec{\theta}$ of a parametrized quantum circuit $V(\vec{\theta})$ to minimize a cost function $C$. While VQAs may enable practical applications of noisy quantum computers, they are nevertheless heuristic methods with unproven scaling. Here, we rigorously prove two results, assuming $V(\vec{\theta})$ is an alternating layered ansatz composed of blocks forming local 2-designs. Our first result states that defining $C$ in terms of global observables leads to exponentially vanishing gradients (i.e., barren plateaus) even when $V(\vec{\theta})$ is shallow. Hence, several VQAs in the literature must revise their proposed costs. On the other hand, our second result states that defining $C$ with local observables leads to at worst a polynomially vanishing gradient, so long as the depth of $V(\vec{\theta})$ is $\mathcal{O}(\log n)$. Our results establish a connection between locality and trainability. We illustrate these ideas with large-scale simulations, up to 100 qubits, of a quantum autoencoder implementation.

INTRODUCTION

The paper examines how cost-function locality governs trainability in variational quantum algorithms, developing analytical tools to characterize gradient suppression in local-2-design ansätze. It also considers optimization procedures and numerical autoencoder experiments while discussing associated limitations and extensions.

INTRODUCTION

  • Global cost functions exhibit exponentially vanishing gradients, including for shallow parametrized quantum circuits, so costs with operational meaning may require revision.This contrasts with prior results for deep circuits and motivates balancing operational relevance against trainability when choosing C.Source: INTRODUCTION · p. 2
  • Local cost functions have gradients that vanish polynomially and remain trainable when the circuit depth is O(log n).The paper’s large-scale quantum autoencoder illustration reports a barren plateau for the global cost in and proposes a trainable local alternative.Source: INTRODUCTION · p. 2

Warm-up example

  • In the warm-up example, global cost gradient variance is 1/8(3/8)^(n−1), exponentially vanishing in n, whereas local cost variance is 1/8n^2, vanishing polynomially, and exhibits no barren plateau.Source: Warm-up example · pp. 2–3

General framework

  • The general framework expresses costs as expectation values of operators on arbitrary input states and analyzes gradients in an alternating layered ansatz of fixed-size neighboring-qubit blocks.The ansatz can be hardware-efficient and compatible with one- and two-dimensional connectivity; gradient variance quantifies concentration around zero.Source: General framework · pp. 3–4

Main results

  • Under local 2-design assumptions, Theorem 1 and its corollary show that global-cost gradient variance is exponentially vanishing in n for m ≥ 2 under stated projector or traceless-operator conditions.The corollary covers the global cost CG and allows operator sums with constant or polynomially many terms, subject to the stated layer and coefficient assumptions.Source: Main results · pp. 4–5
  • Theorem 2 establishes lower bounds for m-local costs, including ultralocal costs and VQE Hamiltonians with up to m/2-neighbor interactions, using forward and backward light-cone structure.The theorem assumes the surrounding circuits and ansatz blocks form local 2-designs and expresses the bound through local operators, input-state reductions, and Hilbert-Schmidt-distance terms.Source: Main results · p. 5

Numerical results

  • The autoencoder’s original global cost develops a plateau at 20 qubits and becomes untrainable above 20, while the local cost trains with as few as 10 shots per evaluation.Random initialization also places the global cost near 1 because the probability of starting near the global minimum vanishes exponentially with nB.Source: Numerical results · pp. 7–8
  • Increasing circuit depth makes local-cost optimization harder, with the shots needed to reach a fixed cost appearing to grow exponentially with layer count.This behavior is consistent with the variance bound in Theorem 2, although it may saturate at very large depth.Source: Numerical results · p. 8, Figure 6 · p. 8

Main results

  • For shallow alternating layered ansatzes, global observables have exponentially decaying gradient variance, whereas local observables have polynomially decaying lower bounds when depth is O(log n).For polylogarithmic depth, the local-cost lower bound enters a transition regime that vanishes faster than polynomially but slower than exponentially.Source: Main results · p. 5, DISCUSSION · p. 8

DISCUSSION

  • The discussion cautions that many-bodiness, rather than nonlocality alone, may cause barren plateaus, while operator cardinality is ruled out as the key variable.The authors also leave open whether the scaling extends to other ansatzes, costs, architectures, and deeper-than-O(log n) regimes.Source: Main results · p. 5, DISCUSSION · pp. 8–9

Numerical results

  • Global costs exhibit barren plateaus even for shallow ansatzes, while local costs remain trainable for autoencoders up to 100 qubits.The global autoencoder cost could not be minimized beyond 20 qubits, whereas the proposed local cost was minimized through 100 qubits.Source: Numerical results · pp. 7–8, DISCUSSION · p. 9

DISCUSSION

  • The results apply to exact local 2-design blocks, while simulations suggest cost-dependent barren plateaus also occur for simpler approximate-design ansatzes beyond the theorems’ scope.Deep alternating layered ansatzes eventually behave like random circuits and recover barren plateaus for both local and global costs.Source: Main results · p. 6, Figure 4 · p. 6, Numerical results · p. 8

Variance of the cost function partial derivative

  • The analysis uses forward and backward light cones to derive gradient-variance formulas for alternating layered ansatzes whose blocks form independent 2-designs.The proof framework applies to both one-dimensional and two-dimensional square connectivity because their light-cone structure is treated identically.Source: Variance of the cost function partial… · pp. 9–10

Computing averages over V

  • Independent ansatz blocks that form local 2-designs permit expectation values to be evaluated using Haar-equivalent sampling and second-moment Weingarten calculus.The cost is degree at most two in each block and its conjugate, so 2-design formulas suffice for the required averages.Source: Computing averages over V · p. 10

Intuition behind the main results

  • For a global cost, variance scales as O(1/2^(2n)) and worsens with each integrated block, whereas a local cost requires one block regardless of total qubits and scales as O(1/n^2).Source: Intuition behind the main results · pp. 10–11
  • For local costs across L layers, the gradient remains no faster than polynomially vanishing when mL ∈ O(log(n)).Integrating L−1 blocks yields the coefficient 2^(m(L−1)/2)/(2^m+1)^(L−1).Source: Intuition behind the main results · p. 11

Sketch of the proof of the main theorems

  • The proofs algorithmically integrate blocks with Weingarten calculus represented as tensor networks, generating four new tensors after each integration.This representation makes the expectation values needed for gradient-variance bounds tractable.Source: Sketch of the proof of the main theorems · p. 11

Proof of Theorem 2

  • Theorem 2 restricts relevant local operators to the forward light-cone and combines tensor-network integration results to establish its bound.The theorem also applies when the observable has the more general form specified in Eq. (16).Source: Proof of Theorem 2 · pp. 11–12

Proof of Theorem 1

  • Theorem 1 handles operators outside the forward light-cone by decomposing the remaining subsystem and bounding resulting Hilbert-Schmidt distances to obtain the upper bound.The proof uses bounds DHS(ρ1,ρ2) ≤ 2 and a corresponding bound on the operator terms.Source: Proof of Theorem 1 · pp. 12–13

Ansatz and optimization method

  • The gradient-free optimizer randomly initializes parameters, searches a d = 10 subspace, and increases shots from 10 up to 10^5 as optimization plateaus.With exponentially vanishing gradients, any optimizer requires exponentially increasing precision in n to detect useful cost changes.Source: Ansatz and optimization method · p. 13

Supplementary Information for “Cost Function Dependent Barren

The supplementary information supplies proofs and derivations for the manuscript’s propositions, theorems, and corollaries, including the quantum-autoencoder local-cost result.

Preliminaries

The preliminaries define unitary designs, Haar integration, subsystem notation, and operator identities used to analyze gradients in alternating layered ansätze.

  • A unitary t-design reproduces averages of degree-t polynomials in unitary matrix elements and their adjoints under the normalized Haar measure.Averaging such polynomials over the design is indistinguishable from integrating over U(d) with the Haar distribution.Source: Preliminaries · p. 16
  • Computational-basis and bitstring notation fixes subsystem dimensions, concatenation, and operator components for the subsequent Haar-integral calculations.Source: Preliminaries · p. 16
  • The preliminaries establish moment and partial-trace lemmas for operators on single, bipartite, tripartite, and multipartite Hilbert spaces.These identities support later calculations involving conjugated operators, tensor-product subsystems, and nonoverlapping supports.Source: Preliminaries · pp. 17–19

Proof of Proposition 1

The proof of Proposition 1 bounds the parameter-space regions where global and local costs are below a threshold, revealing sharply different asymptotic behavior.

  • For the local cost, neighborhoods of the minimum can retain constant probability as n grows, unlike the global-cost trainable region.Source: Proof of Proposition 1 · p. 21
  • The probability that the global cost C_G is at most any fixed δ in (0,1) vanishes exponentially with n.This formalizes the narrow-gorge phenomenon for the global cost.Source: Proof of Proposition 1 · p. 21
  • The inequality’s range of validity depends on the cost-function parameter λ and holds for δ in (1 − (2λ)^−1, 1], with λ = 1 used in the main text.Source: Proof of Proposition 1 · p. 21

Proof of Proposition 2

The proof of Proposition 2 analyzes average parameter gradients by decomposing an ansatz block and using local unitary-design assumptions on neighboring circuit regions.

  • The proposition applies when either the ansatz region before or after the differentiated block forms a 1-design.Source: Proof of Proposition 2 · p. 22
  • The proof decomposes the circuit around the parameterized block and tracks the forward light-cone containing gates causally connected to its output.Source: Proof of Proposition 2 · p. 22
  • The average partial derivative of a cost expressed as Tr[O V(θ)ρV(θ)†] is zero when both neighboring regions form 1-designs.Source: Proof of Proposition 2 · pp. 22–23

Supplementary Note 4: Variance of the cost function partial derivative

This supplementary note derives gradient-variance expressions for alternating layered ansätze, then evaluates the global-cost case for a single layer. The resulting bound shows exponentially vanishing global-cost gradients.

Supplementary Note 4: Variance of the cost function partial derivative

  • The gradient variance is computed from the second moment because the mean gradient vanishes when the relevant circuit portions are 1-designs.Independence of circuit regions and a 2-design assumption permit successive expectation-value evaluations.Source: Supplementary Note 4: Variance of the… · pp. 23–24

Variance of the cost function partial derivative for a single layer of the Alternating Layered Ansatz

  • For a single-layer alternating layered ansatz, the calculation generalizes the warm-up example and supplies the tools used in the main theorems.The derivation evaluates the variance formulas explicitly before treating deeper circuits.Source: Variance of the cost function partial… · p. 25

A. Variance of global cost function partial derivative

  • The global-cost calculation assumes n = mξ, with each block acting on m qubits and the trained parameter located in one block.The circuit is partitioned into blocks, with the final layer included in VR and the remaining portion represented by VL.Source: A. Variance of global cost function… · p. 25

1. Expectation value over VR

  • Integrating over VR and VL uses local 2-design identities, tensor-network contractions, Pauli tracelessness, and reduced-state purities.The VL calculation introduces reduced states and their purities, which enter the resulting expression for the variance.Source: §1 · p. 25, §2 · pp. 25–26

2. Expectation value over VL

  • The single-layer global cost function exhibits a barren plateau, with its gradient variance vanishing exponentially in n.Equation (113) establishes this behavior after bounding the reduced-state-purity contribution.Source: §2 · p. 26

B. Variance of the local cost function partial derivative

This section evaluates local-cost gradients for the single-layer ansatz and identifies conditions under which they avoid barren plateaus. The bound depends on local support and the input state's deviation from maximal mixing.

B. Variance of the local cost function partial derivative

  • When training a parameter in block W, the local-cost gradient is nonzero only for measured qubits in W's subsystem.This support restriction simplifies the variance calculation relative to the global-cost case.Source: B. Variance of the local cost function… · p. 27
  • If the reduced input state remains at Hilbert-Schmidt distance Ω(1/poly(n)) from the maximally mixed state, the gradient variance vanishes polynomially with n.The distance condition supplies the lower-bound scaling used to establish trainability.Source: B. Variance of the local cost function… · p. 27
  • Under that condition, the local cost function has no barren plateau.The conclusion applies to the single-layer analysis and follows from the polynomial variance bound.Source: B. Variance of the local cost function… · p. 27
  • For an m-local cost, the local operators act on at most m qubits and include ultralocal costs and VQE Hamiltonians with up to m/2-neighbor interactions.The operator decomposition covers one-body terms as well as the specified neighboring interactions.Source: B. Variance of the local cost function… · p. 27
  • Theorem 2 lower-bounds the variance for m-local costs when the surrounding circuit portions and every ansatz block form local 2-designs.The bound is expressed using operators in the forward light-cone and subsystems in the backward light-cone.Source: B. Variance of the local cost function… · pp. 27–28

1. Expectation value over VR

This section derives the expectation values entering the local-cost variance bound by integrating circuit blocks in the relevant light-cones. It compares two operator placements and identifies the tensor contractions responsible for their different bounds.

1. Expectation value over VR

  • The expectation-value calculation integrates blocks in VL using local 2-design identities and tensor-network representations, with non-light-cone blocks simplifying to identities.The procedure repeatedly rewrites the resulting tensors so the next block can be integrated.Source: §1 · pp. 28–29
  • For Case 1, where Oi acts on the topmost m qubits, integrating over (L −l) blocks produces delta-function contractions in p and q.This is the configuration represented in Supplementary Figures 1 and 2(a).Source: §1 · pp. 29–30, Figure 2 · p. 31
  • The expectation-value expansion reduces overlapping-support contributions to contractions involving Hilbert-Schmidt distances of partially traced states.Operators with no overlapping support contribute zero, while the remaining terms are organized by light-cone subsystems.Source: §1 · pp. 30, 32
  • For Case 2, where Oi acts on Sw, integrating over (L −l)(L −l + 2)/4 blocks also produces identity traces over m/2 qubits.These traces generate multiplicative factors 2^m/2 that do not arise in Case 1.Source: §1 · pp. 30–31, Figure 2 · p. 31
  • Tτ is larger for Case 2 than Case 1, and for fixed L the difference between the two values scales as 1/2^m(L−l−1)/2.As m increases, Case 1 at fixed (L −l) converges to Case 2 at (L −l + 1).Source: §1 · pp. 30–31
  • The resulting expression quantifies how far a reduced state is from a product with a maximally mixed subsystem; if that subsystem is maximally mixed, angles in W cannot be trained.The variance bound is therefore tied to reduced-state structure inside the relevant light-cones.Source: §1 · p. 32
  • Theorem 1 upper-bounds global-cost gradient variance for local-2-design ansätze, covering rank-projector and traceless-operator cases.The theorem is stated for a trainable parameter in a block W and is evaluated using the same block-integration machinery.Source: §1 · p. 33

A. N = 1, and bO1k is a non-trivial projector

This subsection proves the global-cost upper bound for the case of one non-trivial projector per subsystem. The proof combines light-cone decomposition, block integration, and bounds on Hilbert-Schmidt distances and contraction coefficients.

A. N = 1, and bO1k is a non-trivial projector

  • For non-trivial projectors bOk, the relevant region includes the forward light-cone L and last ansatz layer, with VR = VL ⊗ VL; complementary degrees are handled by traces over associated Hilbert spaces.The construction uses projectors onto HL and HL, while Trk traces over Hk and TrL∩w over qubits in SL ∩ Sw.Source: A. N = 1, and bO1k is a non-trivial… · pp. 33–34
  • Independence of the circuit blocks factorizes the expectation over VR into expectations over VL and its complement.This enables separate evaluation of the contributions associated with the light-cone and outside-light-cone subsystems.Source: A. N = 1, and bO1k is a non-trivial… · p. 34
  • The projector-rank assumptions and contraction estimates yield the stated upper bound on Var[∂νC].The proof combines the intermediate bound with the contribution from the coefficients tτ and the rank product R.Source: A. N = 1, and bO1k is a non-trivial… · pp. 34–36
  • Expanding the product produces 2^ξL terms, each associated with a Hilbert-Schmidt distance bounded by 2.This bound controls the sum entering the global-cost variance estimate.Source: A. N = 1, and bO1k is a non-trivial… · pp. 34–35

B. Arbitrary N and bOik is a traceless operators such that Tr[ bO2

The proof extends the variance analysis to arbitrary sums of tensor-product observables with traceless local factors, including cross terms between cost components.

B. Arbitrary N and bOik is a traceless operators such that Tr[ bO2

A. Proof of Corollary 1

The proof of Corollary 1 analyzes the two cases of Theorem 1 and shows that the resulting gradient-variance upper bounds vanish exponentially under the stated scaling conditions.

A. Proof of Corollary 1

B. Proof of Corollary 2

The proof of Corollary 2 establishes polynomial lower-scaling behavior when a relevant coefficient contribution does not vanish faster than inverse-polynomially and the circuit depth is logarithmic.

B. Proof of Corollary 2

  • If at least one contribution in the sum defining the variance is Ω(1/poly(n)) and L = O(log(n)), the relevant depth-dependent factor is also Ω(1/poly(n)).Source: B. Proof of Corollary 2 · p. 38
  • The proof assumes that at least one term c_i ε(ρ_k,k′) ε(bO_i) vanishes no faster than Ω(1/poly(n)).Source: B. Proof of Corollary 2 · p. 38
  • For polylogarithmic depth, the corresponding factor is only bounded below by an inverse polylogarithmic quantity rather than the logarithmic-depth inverse-polynomial bound.Source: B. Proof of Corollary 2 · p. 38

Faithfulness of local cost function for Quantum autoencoder

The quantum autoencoder analysis compares global and local cost functions through measurement-event probabilities and establishes faithfulness for the local cost.

Faithfulness of local cost function for Quantum autoencoder

Loading 2001.00550v3…