



01605nas a2200145   4500008004100000245005500041210005400096260001400150520117500164100002001339700001701359700002301376700002301399856003701422       2024                        eng d00aTrainability Barriers in Low-Depth QAOA Landscapes0 aTrainability Barriers in LowDepth QAOA Landscapes  c2/15/20243 a<p>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 Ω(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.</p>1 aRajakumar, Joel1 aGolden, John1 aBärtschi, Andreas1 aEidenbenz, Stephan  uhttps://arxiv.org/abs/2402.10188