Source-linked AI summary
Effect of barren plateaus on gradient-free optimization
Andrew Arrasmith, M. Cerezo, Piotr Czarnik, Lukasz Cincio, Patrick J. Coles
TL;DR
The paper examines whether gradient-free optimizers can avoid barren plateaus, where exponentially suppressed gradients threaten scalable quantum optimization. It analytically shows that cost differences are likewise exponentially suppressed and numerically finds exponentially growing shot requirements for Nelder-Mead, Powell, and COBYLA.
Problem
Whether gradient-free optimizers are impacted by barren plateaus remains debated, despite barren plateaus threatening exponential scaling and potential quantum speedup.
Method
The paper analyzes cost-function differences used by gradient-free optimizers and tests Nelder-Mead, Powell, and COBYLA in a deep-circuit barren-plateau scenario.
Results
Cost-function differences are exponentially suppressed, while the shot count required for all tested optimizers to begin training grows exponentially with the number of qubits.
Takeaways & Limitations
Gradient-free optimization does not avoid barren-plateau scaling, although careful strategy choices may improve the constants multiplying the unavoidable exponential scaling.
Takeaways & Limitations
The asymptotically exponential scaling cannot be avoided, though some strategies may extend the size limits of trainable problems by improving multiplicative constants.
Abstract
from arXiv · showhide
Barren plateau landscapes correspond to gradients that vanish exponentially in the number of qubits. Such landscapes have been demonstrated for variational quantum algorithms and quantum neural networks with either deep circuits or global cost functions. For obvious reasons, it is expected that gradient-based optimizers will be significantly affected by barren plateaus. However, whether or not gradient-free optimizers are impacted is a topic of debate, with some arguing that gradient-free approaches are unaffected by barren plateaus. Here we show that, indeed, gradient-free optimizers do not solve the barren plateau problem. Our main result proves that cost function differences, which are the basis for making decisions in a gradient-free optimization, are exponentially suppressed in a barren plateau. Hence, without exponential precision, gradient-free optimizers will not make progress in the optimization. We numerically confirm this by training in a barren plateau with several gradient-free optimizers (Nelder-Mead, Powell, and COBYLA algorithms), and show that the numbers of shots required in the optimization grows exponentially with the number of qubits.
1 Introduction
Parameterized quantum circuits are trained by minimizing cost functions, but barren plateaus exponentially suppress gradients and can force exponential precision. This motivates asking whether gradient-free optimizers avoid the problem; the paper argues analytically and numerically that they do not.
- Parameterized quantum circuits support VQAs and QNNs, which train circuit parameters by minimizing a quantum-evaluated cost function.
- Barren plateaus cause cost-function gradients to shrink exponentially with the number of qubits.Reported causes include deep unstructured circuits, global cost functions, noise, scrambling target unitaries, and large entanglement.
- Exponential gradient suppression can require exponential precision, causing algorithmic scaling to become exponential in the number of qubits.The paper notes that this scaling could erase the possibility of quantum speedup with parametrized quantum circuits.
- Whether gradient-free optimizers can avoid barren plateaus remains debated, despite the expected impact on gradient- and higher-derivative-based methods.
- Cost function differences between optimization points are exponentially suppressed in barren plateaus, so gradient-free optimizers need exponentially large resources or make no progress.The result holds even when the compared parameter points are not close together.
- For Nelder-Mead, Powell, and COBYLA, the number of shots required to begin training grows exponentially with the number of qubits.The simulations use deep parametrized circuits representing the barren plateau scenario of Ref..
2 Theoretical Background
The paper reviews parameterized-circuit costs, zeroth-order optimizers, and barren plateaus. It describes how Nelder-Mead, Powell, and COBYLA use cost evaluations, and how barren plateaus arise from exponentially suppressed gradients in several circuit settings.
- The background frames parameterized-circuit training as minimizing a cost function over circuit parameters using a classical optimizer.
- The framework assumes O(poly(n)) parameters, with each parameter generating a unitary e^{-iθµHµ} whose Hermitian generator has two distinct non-zero eigenvalues.
- The cost-function family covers binary classification mean-squared error and variational-algorithm costs of the form Tr[OV(θ)ρV†(θ)].
- 2.2 Gradient-Free Optimizers: Gradient-free methods access only a zeroth-order oracle and distinguish cost values at different points; the numerical study examines Nelder-Mead, Powell’s Method, and COBYLA.
- 2.2.1 Nelder-Mead: Nelder-Mead updates a simplex through reflection, expansion, contraction, and shrinking operations selected by conditional cost comparisons.
- 2.2.1 Nelder-Mead: Cost-estimation errors can trigger premature Nelder-Mead shrinking, slowing optimization and creating a false appearance of convergence.
- 2.2.2 Powell: Powell performs sequential line searches along search vectors and replaces the vector associated with the greatest displacement to accelerate convergence.
- 2.2.3 COBYLA: COBYLA fits a hyperplane to simplex points, steps along the estimated slope within a trust-region radius, and decreases its lower bound when progress stops.Its trust-region size never increases.
3 Main Results
The paper analyzes cost differences between parameter points in barren plateaus and derives consequences for gradient-free optimization. These differences are exponentially suppressed for both translated and independently selected points, implying exponentially increasing sampling requirements.
- Analytical setup: The main results analyze cost differences ΔC between parameter points related by translations or chosen independently.The two scenarios cover optimizers comparing points at specified separations and methods using random initialization.
- Proposition 1: Proposition 1 shows that the expectation and variance of ΔC vanish exponentially with system size for translated parameter points.The result assumes a barren plateau and polynomially bounded parameter-space dimension and separation.
- Corollary 1: Corollary 1 shows that independently chosen parameter points also have zero-mean cost differences with exponentially vanishing variance.This extends the suppression result to random-search and globally initialized settings.
- Scaling consequence: With high probability, ΔC is exponentially vanishing for both dependent and independent parameter choices because the cost exhibits a barren plateau.The argument uses the exponentially vanishing scaling of G(n) and its independent-point counterpart.
- Implications for gradient-free optimizers: Gradient-free optimizers rely on distinguishing cost values, so suppressed differences require exponentially precise measurements or exponentially large sampling resources.Insufficient precision causes decisions to be randomized by shot noise, while exponentially scaling sampling requirements hinder quantum speedup.
- Implications for gradient-free optimizers: Randomness in selecting points cannot evade the exponential scaling: random search and random-initialized methods such as Bayesian optimization also struggle in barren plateaus.The result applies to local and global optimizers when parameter separations remain polynomially bounded.
4 Numerical Implementation
The numerical study trains a layered hardware-efficient circuit in a barren-plateau setting using three gradient-free optimizers and measures the shot precision needed to reach a target cost. The required shot count grows exponentially or faster with the number of qubits.
- Numerical setup: The task trains V(θ) to approximate the all-zero target state using a local cost function C(θ) that vanishes exactly at the target, up to global phase.The target unitary is U = 1, and the cost lies in [0, 1].
- Numerical setup: A layered hardware-efficient ansatz with depth p = n places the simulations in the barren-plateau regime identified for randomly initialized circuits.The simulations use n = 5, 6, . . . , 11 qubits.
- Numerical setup: The study evaluates Nelder-Mead, Powell, and COBYLA while varying shots per cost evaluation across 20 runs with different initial points.The selected shot allocation minimizes the median total shots needed to reach C = 0.4.
- Results: The median total shot count scales exponentially for Powell, super-exponentially for Nelder-Mead, and at least exponentially for COBYLA.A custom gradient-descent implementation also shows exponential total-shot scaling for reference.
5 Discussion
The discussion concludes that choosing a gradient-free optimizer does not remove barren-plateau scaling because optimization decisions rely on exponentially suppressed cost differences. Numerical results support exponential shot growth, although optimizer choice may affect prefactors and finite-size reach.
- Analytical implications: Gradient-free optimizers are impacted by barren plateaus because the variance of cost-function differences is exponentially suppressed.This forces random-start methods such as Nelder-Mead to expend exponentially large resources when deciding where to move.
- Analytical implications: Global gradient-free methods also require exponentially large resources because independently sampled points cannot provide sufficiently informative cost comparisons.The discussion identifies Bayesian methods as an example of this global-optimization setting.
- Numerical evidence: Numerical training confirms that the required number of shots grows exponentially with qubit number for the tested gradient-free optimizers.The exponential behavior is described as a lower bound on the asymptotics.
- Numerical evidence: Nelder-Mead exhibits super-exponential scaling, likely because statistical uncertainty can prematurely shrink its simplex when cost values are difficult to order.A similar trust-region effect may occur for COBYLA, but the data do not clearly demonstrate it.
- Scope and outlook: Optimizer choice may extend the size of trainable problems by improving constants multiplying the exponential scaling, but it cannot remove the asymptotic exponential dependence.The argument applies to strategies that compare cost values at different parameter points.
- Scope and outlook: The discussion presents barren plateaus as a continuing obstacle and calls for further strategies to avoid them, including a unified treatment across optimizer types.