PaperlayerView exact revision on arXiv

Source-linked AI summary

Does provable absence of barren plateaus imply classical simulability?

M. Cerezo, Martin Larocca, Diego García-Martín, N. L. Diaz, Paolo Braccia, Enrico Fontana, Manuel S. Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, Eric R. Anschuetz, Zoë Holmes

arXiv:2312.09121v3quant-phcs.LGstat.ML

TL;DR

The paper asks whether structures that prevent barren plateaus also make parametrized quantum-circuit losses classically simulable. Through a general argument and case-by-case analysis, it links barren-plateau avoidance to polynomially sized subspaces and finds efficient classical simulation for many considered models, sometimes after quantum data acquisition. The authors therefore qualify this conclusion with limitations involving scope, average-case behavior, smart initializations, and architectures that may work heuristically without analytic guarantees.

  • Problem

    The paper addresses whether the structure enabling provable barren-plateau avoidance can also support efficient classical simulation of the loss.

  • Method

    The authors analyze barren-plateau proofs and identify polynomially sized subspaces in which the relevant state, circuit, and observables can be represented or sampled for simulation.

  • Results

    The case studies show that all considered barren-plateau-avoidance methods can be efficiently classically simulated, with quantum devices sometimes needed only for initial non-adaptive data acquisition.

  • Takeaways & Limitations

    Many parametrized quantum circuits with provably barren-plateau-free landscapes may have limited information-processing advantages beyond the quantum role in collecting data.

  • Takeaways & Limitations

    The paper focuses on analytically studied scaling and acknowledges architectures that may work in practice without a known simulability method or proof of barren-plateau freedom.

Abstract

from arXiv · show

A large amount of effort has recently been put into understanding the barren plateau phenomenon. In this perspective article, we face the increasingly loud elephant in the room and ask a question that has been hinted at by many but not explicitly addressed: Can the structure that allows one to avoid barren plateaus also be leveraged to efficiently simulate the loss classically? We collect evidence-on a case-by-case basis-that many commonly used models whose loss landscapes avoid barren plateaus can also admit classical simulation, provided that one can collect some classical data from quantum devices during an initial data acquisition phase. This follows from the observation that barren plateaus result from a curse of dimensionality, and that current approaches for solving them end up encoding the problem into some small, classically simulable, subspaces. Thus, while stressing that quantum computers can be essential for collecting data, our analysis sheds doubt on the information processing capabilities of many parametrized quantum circuits with provably barren plateau-free landscapes. We end by discussing the (many) caveats in our arguments including the limitations of average case arguments, the role of smart initializations, models that fall outside our assumptions, the potential for provably superpolynomial advantages and the possibility that, once larger devices become available, parametrized quantum circuits could heuristically outperform our analytic expectations.

I. INTRODUCTION

The article asks whether the structure that prevents barren plateaus also enables efficient classical simulation, arguing that this is often the case for widely used models. The argument links barren-plateau avoidance to polynomially sized subspaces, while retaining important caveats about scope and exceptions.

  • I. INTRODUCTION: Barren plateaus concentrate loss landscapes exponentially around their mean, requiring exponential training resources and obstructing scalable variational algorithms.The article presents this concentration as a curse of dimensionality motivating architectures and training strategies that avoid barren plateaus.
  • I. INTRODUCTION: Many barren-plateau-avoidance strategies exploit simple problem structure, including shallow local-measurement circuits, small Lie algebras, identity initializations, symmetries, noise, measurements, and selected generative models.These examples are presented as commonly studied routes to provably non-barren landscapes.
  • I. INTRODUCTION: The article argues that a wide class of provably barren-plateau-free landscapes can be simulated in polynomial time classically or with quantum-enhanced classical algorithms.Quantum-enhanced simulation still uses a quantum computer during initial data acquisition, but not in hybrid quantum-classical optimization loops.
  • I. INTRODUCTION: Barren plateaus arise from overlaps in exponentially large operator spaces, whereas restricting the evolved observable to a polynomially large subspace avoids concentration and enables classical representation of the loss.The loss is expressed as an inner product between the Heisenberg-evolved observable and the initial state.
  • I. INTRODUCTION: The case studies support efficient classical simulation for all considered barren-plateau-avoidance methods, using subspaces identified from the proofs of non-exponential concentration.When needed, a quantum computer is accessed non-adaptively to generate a classical surrogate rather than to run a hybrid optimization loop.
  • I. INTRODUCTION: The claims apply to many standard variational and quantum-learning architectures but not to all quantum learning protocols, and the authors do not prove universal simulability.Potential exceptions include unknown subspaces, smart initializations, and highly structured problems in the full exponential space.

II. DEFINITIONS FOR BARREN PLATEAUS AND SIMULABILITY

The paper defines loss computation and three simulation classes for parametrized-circuit losses, distinguishing fully classical simulation, quantum-enhanced classical simulation, and on-demand quantum simulation. It also restricts attention to expectation-value losses with efficiently described instances and notes that stronger all-parameter guarantees remain an open area.

  • Variational algorithms train parametrized quantum circuits by repeatedly estimating a loss on quantum hardware and using classical optimization for parameter updates.
  • The fundamental loss considered is an expectation value determined by an input state ρ, parametrized circuit U(θ), and non-trivial Hermitian observable O.The paper focuses on this form while noting that lessons may extend to losses requiring multiple such quantities.
  • Instances are specified by an efficiently sampleable parameter distribution and efficient classical descriptions of ρ, U(θ), and O that permit polynomial-time quantum estimation.Examples include a state-preparation circuit, gate dictionary, and Pauli decomposition of the observable.
  • Loss computation is defined probabilistically over sampled parameters, with stronger variants requiring accurate computation for every parameter setting and possibly gradients.The paper emphasizes that average-case random-point simulation may not suffice for training, while all-parameter computation is stronger.
  • CSIM uses only a polynomial-time classical algorithm, QESIM permits polynomial-time quantum data acquisition followed by classical computation, and QSIM allows on-demand quantum access.QESIM data can be stored classically using efficient tomography or classical shadows, whereas QSIM usually implements the parametrized circuit on quantum hardware.
  • A quantum advantage is possible outside CSIM, while problems in QESIM but not CSIM already require a quantum device for initial data acquisition.Problems in QESIM ∩ CSIM may be especially suited to near-term implementation because their classical simulation can use acquired quantum data.

III. WHAT LEADS TO ABSENCE OF BARREN PLATEAUS?

Absence of barren plateaus is linked to restricted adjoint-action subspaces in operator space. When these subspaces are polynomially sized and identifiable, the loss avoids exponential concentration under suitable state and measurement conditions.

  • Barren plateaus arise when overlaps between exponentially large operators become exponentially small and concentrated, reflecting a curse of dimensionality.
  • The adjoint action of a structured unitary can restrict evolved operators to proper or effective subspaces of operator space.Proper subspaces contain only selected operators, whereas effective subspaces allow broader support but have large overlaps mainly within a smaller region.
  • Expanding the measurement operator in an orthogonal basis decomposes the loss into inner products associated with the subspaces generated by each basis element.The same analysis can instead expand the initial state and study its corresponding subspaces.
  • Polynomially sized identifiable subspaces define CpolySub and indicate that part of the loss is evaluated within non-exponentially large operator spaces.
  • For shallow hardware-efficient ansätze, local measurements evolve into operators supported on at most O(log(n)) neighboring qubits, yielding polynomial-sized proper subspaces.Global measurements such as O = Z⊗n instead generate exponentially large subspaces; local terms place the problem class in CpolySub.
  • Polynomial subspaces alone are insufficient: if the state or measurement has negligible projection onto them, the loss can still become exponentially concentrated.For shallow hardware-efficient circuits, area-law states with local measurements satisfy the relevant non-concentration condition, whereas volume-law states can retain exponential concentration.
  • The paper’s Claim 1 states that standard provably barren-plateau-free architectures generate exactly or approximately polynomially sized subspaces that can be identified classically.Most analyzed strategies yield proper subspaces for all parameter values, while some models yield effective subspaces with high probability.

IV. CONNECTION BETWEEN ABSENCE OF BARREN PLATEAUS AND SIMULABILITY

The paper argues that provable barren-plateau avoidance often exposes polynomially sized subspaces, enabling classical loss simulation, sometimes with quantum data acquisition.

  • Simulation procedure: The simulation strategy identifies polynomial subspaces, characterizes the circuit’s adjoint action there, and computes or measures state and observable components.The relevant subspace is usually found by analyzing the proof of barren-plateau absence and the circuit’s internal structure.
  • Shallow hardware-efficient ansätze: For shallow hardware-efficient circuits with local measurements, the relevant operators lie within the measurement’s backwards light cone, so gates outside it can be removed.The reduced circuit acts only on the qubits in that light cone while leaving the loss unchanged.
  • Data acquisition: Components of a general initial state may require quantum measurements or classical-shadow tomography, whereas simple product states can be projected classically.The observable component is less problematic when its classical description already contains the required information.
  • Case studies: For the considered barren-plateau-free problems, the authors identify efficient procedures for subspace projections and unitary action, summarized with measurement protocols in Table 2.The analysis covers several circuit and generative-model families, with alternative classical simulation methods also noted.
  • Simulation guarantees: Proper polynomial subspaces permit classical approximation of the loss for every parameter value, while effective subspaces provide simulation only with high probability over sampled parameters.The latter guarantee may cover only the non-barren parts of the landscape.
  • Overall implication: Across the analyzed families, estimating the loss in polynomial time generally does not require implementing the parametrized circuit, although initial quantum data acquisition may remain necessary.The authors describe this as a soft dequantization of the variational information-processing component rather than of variational quantum computing as a whole.

V. CAVEATS AND FUTURE DIRECTIONS

The paper closes by presenting caveats to its simulability arguments and identifying future research directions motivated by those limitations.

  • Caveats: The authors organize the final discussion around caveats concerning the scope and strength of their claims.These caveats precede the proposed research directions.
  • Future directions: The paper also highlights new research directions arising from the analysis.The section is framed as both a qualification of the results and an agenda for further study.
  • Overall framing: The concluding discussion therefore treats simulability results as qualified rather than universally established.This follows the section’s explicit emphasis on caveats alongside opportunities.

A. Caveats

The caveats restrict the paper’s generality: its evidence is case-based, its guarantees depend on known subspaces and assumptions, and some non-concentrated models may remain hard to simulate.

  • Scope of evidence: The general argument comes from case studies of widely used architectures and does not analyze every work claiming absence of barren plateaus.The authors studied the works represented in Table 1 and invite broader checks of applicability.
  • Logical scope: The paper does not claim that every non-concentrated loss is classically simulable, because other non-exponential concentration mechanisms may exist.The stated implication is limited to the analyzed barren-plateau-free families and their known polynomial subspaces.
  • Counterexamples: Constructed non-concentrated losses can resist classical simulation through cryptographic hardness, although these examples differ from mainstream variational algorithms.They instead draw on conventional fault-tolerant algorithms and may exhibit superpolynomial quantum advantage.
  • Quantum-resource requirements: Quantum-resource requirements vary by case, from light Pauli-measurement protocols to circuits demanding substantially more quantum resources.A universal quantum computer may be unnecessary in some cases, while deep circuits can remain demanding.
  • Provability requirement: The argument requires provable barren-plateau absence, so heuristic large gradients from warm starts do not establish the known subspace needed for simulation.ADAPT-VQE is cited as a preliminary example with heuristic gradients and partial simulation results but no general guarantee throughout training.
  • Average-case limitation: Effective-subspace simulation holds with high probability over parameters, which may fail to support training if optimization enters nonsimulable or uninformative regions.This is weaker than simulation throughout the landscape.
  • Model assumptions: The claims do not directly apply to loss functions outside expectation-value formulations, including quantum Boltzmann machines based on thermal-state preparation.Thermal-state preparation is identified as a primitive expected to be hard to simulate classically.

B. New opportunities

The article proposes using barren-plateau analysis to guide classical simulation and quantum data acquisition, while identifying practical limits and open research directions.

  • Classical simulation of barren-plateau-free losses may be useful even when sampling from the resulting state remains prohibitively expensive.Parameters can be trained classically, transferred to quantum hardware, and followed by quantum operations or measurements.
  • Different loss functions require different simulation algorithms, motivating data-driven and quantum-inspired approaches rather than one universal simulator.The relevant subspaces and tomographic procedures can vary across tasks.
  • QESIM-but-not-CSIM problems may be nearer-term candidates because quantum data acquisition can use shallower circuits than implementing the full parameterized circuit.Classical optimization can also exploit faster hardware and automatic differentiation after data acquisition.
  • The connection between barren plateaus and tomography raises open questions about measure-first algorithms and the task dependence of data-acquisition protocols.The article notes that generic reuse of one shadows protocol has limitations.
  • Iterative quantum measurements could update a classical loss simulation as optimization progresses, improving faithfulness when the relevant subspace changes.A single initial data-acquisition phase may become unfaithful if later loss contributions arise outside the initial effective subspace.
  • Clever initializations, some generative models, and specially constructed exponentially large settings may fall outside the article’s simulability arguments.These cases can potentially retain barren-plateau-free landscapes without being covered by the proposed simulations.

VI. CONCLUSIONS

The conclusion argues that variational quantum computing should be reassessed because avoiding barren plateaus often coincides with classical simulability, while important exceptions and practical advantages remain possible.

  • Variational quantum optimization is difficult in practice, motivating barren-plateau research and a reassessment of how parameterized circuits are used.
  • The article argues that absence of barren plateaus should not be equated with practical usefulness because many such landscapes may be classically simulable.
  • Further work is needed on quantum data acquisition, classical optimization, and the scaling of simulation algorithms.
  • The authors leave open the possibility of polynomial or exponential quantum advantages in barren-plateau-free settings that remain classically hard.
  • Heuristic architectures may train successfully despite lacking analytic barren-plateau guarantees and known classical simulation methods.
  • The perspective calls for a more principled approach to variational quantum computing.

Supp. Info. A: Barren plateau-free models, polynomial subspaces, and simulation algorithms

The analysis examines each architecture by deriving its polynomial subspace and identifying tomography procedures that can support classical simulation.

  • For every architecture and technique, the authors define the problem class, review the barren-plateau proof, and identify the polynomially large relevant subspace.

1. Small dynamical Lie algebras

Small dynamical Lie algebras provide polynomial-dimensional operator subspaces that can prevent barren plateaus and enable simulation under suitable projection conditions.

  • 1. Small dynamical Lie algebras: The dynamical Lie algebra is generated by nested commutators of circuit generators and contains every unitary produced by the circuit.
  • 1. Small dynamical Lie algebras: Reducing circuit expressivity through symmetries is one route to avoiding barren plateaus, and equivariant circuits implement this structural restriction.
  • 1. Small dynamical Lie algebras: The class Cpolyg consists of circuits with simple polynomial-dimensional dynamical Lie algebras, efficiently preparable initial states, and a state or observable lying in the algebra.
  • 1. Small dynamical Lie algebras: For deep Cpolyg circuits, the variance scales inversely with the Lie-algebra dimension, and polynomially nonvanishing projections prevent barren plateaus.
  • 1. Small dynamical Lie algebras: The relevant simulation subspace is the dynamical Lie algebra because it is closed under the circuit’s adjoint action.
  • 1. Small dynamical Lie algebras: Simulation requires estimating state and observable projections onto the Lie algebra, for which the authors report efficient tomographic procedures in the considered cases.
  • 1. Small dynamical Lie algebras: Polynomial-time structure-constant computation may still be prohibitively expensive, leaving room for polynomial quantum speed-ups.
  • 1. Small dynamical Lie algebras: For decomposed Lie algebras, barren-plateau avoidance and simulation require a polynomially large simple component with large state and observable projections.

a. U(1)-equivariant circuit

U(1)-equivariant circuits preserve fixed-Hamming-weight sectors, and for constant weight the relevant dynamics occupy polynomial-sized subspaces. Tomography and efficient gate-action calculations then support classical simulation of the loss.

  • Setup: U(1)-equivariant circuits preserve the Hamming weight of computational-basis states.The circuit, input state, and observable are restricted to the fixed-weight setting.
  • Barren-plateau condition: For fixed Hamming weight k, the dynamical Lie algebra has dimension at most polynomial in n.The barren-plateau analysis relies on the restricted Lie algebra within the weight-k subspace.
  • Barren-plateau condition: CU(1)equiv avoids barren plateaus when the input state's Hamming weight satisfies k ∈ O(1).The stated sufficient condition is CU(1)equiv ⊂ BP under constant Hamming weight.
  • Small subspace: Constant-weight dynamics remain in a polynomial-sized Hilbert subspace.The restriction follows because both the unitary evolution and measurement preserve Hamming weight.
  • Simulation: Tomography in the fixed-weight basis and efficient local-gate action provide the ingredients for classical loss simulation.The subspace description can be stored efficiently, and the unitary action can be computed by examining local gates.

3. Shallow hardware efficient ansatz

Shallow hardware-efficient and related local circuits avoid barren plateaus under area-law or locality conditions because their observables remain confined to polynomial-sized effective subspaces. These subspaces enable classical simulation through light-cone truncation, tensor networks, or operator propagation.

  • Shallow hardware-efficient ansatz: A one-dimensional shallow hardware-efficient ansatz avoids barren plateaus when ρ follows an area law and O is local.The circuit uses O(log(n)) layers of nearest-neighbor two-qubit gates.
  • Shallow hardware-efficient ansatz: A local measurement's backwards light cone contains only O(log(n)) qubits, yielding polynomially many relevant Pauli operators.Gates outside the measurement light cone can be omitted when computing the adjoint action.
  • Shallow hardware-efficient ansatz: No shallow hardware-efficient ansatz with a local measurement lies outside QESIM.The loss can therefore be estimated classically after the required state information is obtained.
  • Generative models: Shallow one-dimensional generative circuits admit efficient matrix product state representations and output sampling.This supports simulation of quantum circuit generative-model losses.
  • Generic shallow local circuits: Generic shallow local circuits avoid barren plateaus for area-law input states, with effective dynamics restricted to low-bodyness Pauli operators.Classical shadows and related simulation algorithms provide the relevant initial-state components.
  • Simulation strategies: Forward state propagation and backward observable propagation offer complementary classical simulation routes.Tensor networks, MPOs, and Pauli propagation are useful depending on the state and measurement representation.

b. QCNN with post-selected pooling layers

QCNNs with pooling, non-unital noise, and dynamic resets can produce effective polynomial subspaces or shallow behavior that supports classical loss estimation. Classical shadows can also estimate the relevant observable expectations across parameter settings.

  • Post-selected QCNNs: Post-selected QCNN losses can be expressed through expectations of bounded-norm observables indexed by pooling outcomes and parameterized gates.The setting includes k-local observables and a finite gate net approximating continuous parameters.
  • Post-selected QCNNs: Theorem 1 establishes classical simulability for QCNNs with finitely netted parameterized two-qubit gates.The theorem fixes constant approximation and failure parameters.
  • Post-selected QCNNs: A polynomial-size classical shadow of ρ estimates the relevant QCNN expectations to additive error ϵ across all parameter settings.The construction requires no prior knowledge of U or O.
  • Non-unital noise: Non-unital contractive noise effectively makes one-dimensional circuits shallow by resetting qubits after parameterized layers.Light-cone arguments then restrict the evolved local measurement to O(log(n)) qubits.
  • Dynamic circuits: Dynamic circuits similarly use controlled resets, allowing reduced-subspace approximation arguments and classical simulation bounds.Mid-circuit measurements can be viewed as controlled rotations followed by qubit resets.

Supp. Info. B: Examples of non-concentrated but also non-simulable loss functions

The paper gives a contrived counterexample showing that non-concentrated loss landscapes need not be classically simulable. Continuous random parameters restore average-case simulability, while special initializations can retain hard global contributions.

  • Discrete-parameter counterexample: A non-concentrated loss function can nevertheless be classically non-simulable, establishing BP ≠ QESIM.The construction uses a polynomial-size circuit implementing a Boolean function hard to estimate on uniformly random inputs, even with advice.
  • Discrete-parameter counterexample: The discrete construction samples parameters so the circuit prepares uniformly random computational-basis states.The resulting loss estimates the hard Boolean function B(x).
  • Absence of concentration: Large variance of B(x) prevents the loss from exhibiting a barren plateau.If the variance were below 1/100, a constant-output classical algorithm would succeed on at least a 9/10 fraction of inputs.
  • Caveat: The discrete counterexample is explicitly described as contrived because discrete initialization performs much of the work.The paper contrasts it with continuous parameter sampling in [0, 2π].
  • Continuous parameters: Under continuous random parameters, high-weight contributions decay exponentially, placing the loss in an effective polynomial subspace with high probability.The continuous version is classically simulable with high probability after initial quantum data acquisition.
  • Implications: Measure-zero parameter settings can remain classically hard, suggesting smart initialization as a route to trainable yet non-simulable circuits.The hard global contribution has exponentially many terms that cannot be classically simulated efficiently.
Loading 2312.09121v3…