Predicting Barren Plateaus and Cragged Terrains in Variational Quantum Algorithms Using Empirical Hardness Models

Variational quantum algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA), are hybrid quantum-classical machine learning algorithms designed for near-term quantum hardware. However, practical implementation of VQAs is hindered by the appearance of "barren plateaus" in the cost landscape that necessitate exponentially precise measurements. While an extensive Lie algebraic theory of barren plateaus in the regime of deep quantum circuit depths has been developed, less is known about the behavior of barren plateaus for shallow depths. Using the class of machine learning models known as empirical hardness models (EHMs), we investigate the emergence of barren plateaus for QAOA applied to maximum independent set, an NP-hard combinatorial optimization problem in graph theory. We find that barren plateaus and VQA training difficulty are independently associated with various graph properties, and that EHMs can accurately predict barren plateaus. More saliently, we document the novel observation (and overwhelming presence) of "cragged terrains:" cost landscapes whose variance increases polynomially with system size.