Trainability Barriers in Low-Depth QAOA Landscapes

Abstract

The Quantum Alternating Operator Ansatz (QAOA) is a prominent variational quantum algorithm for solving combinatorial optimization problems. Its effectiveness depends on identifying input parameters that yield high-quality solutions. However, understanding the complexity of training QAOA remains an under-explored area. Previous results have given analytical performance guarantees for a small, fixed number of parameters. At the opposite end of the spectrum, barren plateaus are likely to emerge at $\Omega (n)$ parameters for $n$ qubits. In this work, we study the difficulty of training in the intermediate regime, which is the focus of most current numerical studies and near-term hardware implementations. Through extensive numerical analysis of the quality and quantity of local minima, we argue that QAOA landscapes can exhibit a superpolynomial growth in the number of low-quality local minima even when the number of parameters scales logarithmically with $n$. This means that the common technique of gradient descent from randomly initialized parameters is doomed to fail beyond small $n$, and emphasizes the need for good initial guesses of the optimal parameters.

minor updates

References in corpus (21)

• Quantum Computing in the NISQ era and beyond
• Barren plateaus in quantum neural network training landscapes
• A Quantum Approximate Optimization Algorithm
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Training variational quantum algorithms is NP-hard
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• $XY$-mixers: analytical and numerical results for QAOA
• Theory of overparametrization in quantum neural networks
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Benchmarking the Quantum Approximate Optimization Algorithm
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Non-trivial symmetries in quantum landscapes and their resilience to quantum noise
• Fast Simulation of High-Depth QAOA Circuits
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm
• JuliQAOA: Fast, Flexible QAOA Simulation
• Energy Landscapes for the Quantum Approximate Optimisation Algorithm

Cited by in corpus (8)

• Barren Plateaus in Variational Quantum Computing
• Quantum Approximate Multi-Objective Optimization
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm
• Decoded Quantum Interferometry Under Noise