Research map / Optimization / Optimizers
Exponential Hardness of Optimization from the Locality in Quantum Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that the variation range of a QNN cost function under adjusting any local unitary vanishes exponentially in qubit number for random circuits forming unitary 2-designs (1-designs for fidelity costs), with numerical checks on VQE, quantum autoencoder, and quantum state learning.
Problem
Gradient-based barren plateaus and gradient-free optimization both suffer from exponential hardness in QNN training; prior results only bound local derivatives or differences between fixed points, not the entire range of the cost function over a local unitary.
Approach
Characterizes trainability by the full variation range (max minus min) of the cost when optimizing a single local unitary inside a QNN, showing it vanishes exponentially under 2-design randomness of surrounding circuits, which unifies gradient-based and gradient-free limitations without assuming a parameterization.
Key results
- Theorem 1: E[variation range] <= w(H)/2^(n/2-3m-2) for 2-designs, bounding the variance and deviation probability exponentially.
- Proposition 2: for fidelity-type cost with 1-designs, E[variation range] <= 1/2^(n-2m), a tighter O(2^-n) bound.
- Numerical simulations on VQE, quantum autoencoder, and quantum state learning (up to about 10 qubits) show exponential decay whose slopes nearly match the theoretical bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Vary a local unitary within a circuit whose surrounding circuit part forms a unitary 2-design | Generic QNN · Generic QNN | expected variation range: w(H)/2^{n/2−3m−2} | Hurt |
| Use a unitary 1-design for a surrounding circuit part in fidelity-type cost optimization | Quantum state learning · Quantum state learning | expected variation range: 1/2^{n−2m} | Hurt |
| Use a random circuit forming a 2-design around a local gate | VQE · VQE, 1-dimensional spin-1/2 Heisenberg model | variation range | Hurt |
| Use a random circuit forming a 2-design around a local gate | Quantum autoencoder · Quantum autoencoder | variation range: O(2^{−n/2}) | Hurt |
| Use a random circuit forming a 1-design around a local gate | Quantum state learning · Quantum state learning | variation range: O(2^{−n}) | Hurt |
Surprising findings
- Gate-by-gate optimization is ineffective regardless of optimizer, and reparameterization within local unitaries does not help, according to the theory.
Limitations
- Numerical verification limited to small systems (up to about 10 qubits) with Adam optimization for maxima/minima, which may not converge exactly.
- Bounds require random circuits forming 2-designs (or 1-designs for fidelity costs) and a local subsystem with fixed size m not scaling with n.
- Does not cover global unitaries without the parameter-shift property (e.g., controlled Pauli rotations).
Experimental setup
Benchmarks: VQE on 1D Heisenberg model quantum autoencoder quantum state learning fidelity cost
Metrics: sample-averaged variation range of cost function scaling exponent of decay with qubit number
Baselines: McClean et al. 2018 gradient variance results Arrasmith et al. 2020/2022 gradient-free cost difference bounds Cerezo and Coles 2021
Builds on: barren plateau (McClean et al. 2018) unitary designs (Dankert et al. 2009) parameter-shift rule
Closest papers by meaning
- Exploring channel distinguishability in local neighborhoods of the model space in quantum neural networks (ICLR 2025 · similarity 0.89)
- ATP: Adaptive Threshold Pruning for Efficient Data Encoding in Quantum Neural Networks (CVPR 2025 · similarity 0.88)
- Exponential Quantum Communication Advantage in Distributed Inference and Learning (NeurIPS 2024 · similarity 0.87)
- A Unified Theory of Quantum Neural Network Loss Landscapes (ICLR 2025 · similarity 0.87)
- Characterizing Trainability of Instantaneous Quantum Polynomial Circuit Born Machine (NeurIPS 2026 · similarity 0.87)
- TensorRL-QAS: Reinforcement learning with tensor networks for improved quantum architecture search (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.