Performance and Limitations of QAOA at Constant Levels on Large Sparse Hypergraphs and Spin Glass Models

Watch a technical conference talk from TQC 2023 exploring the performance analysis and limitations of the Quantum Approximate Optimization Algorithm (QAOA) at constant levels when applied to large sparse hypergraphs and spin glass models. Delve into rigorous mathematical proofs demonstrating how QAOA's expected performance can be analyzed through a saddle-point approximation of sum-over-paths integral, supported by a novel generalization of the multinomial theorem. Learn about the correspondence between pure q-spin models and Max-q-XORSAT problems on random sparse Erdos-Renyi hypergraphs, revealing important limitations in QAOA's ability to achieve optimal solutions for certain q-spin models where q is greater than or equal to 4 and even. Understand the implications of these findings for quantum algorithm hardness of approximation in scenarios involving complete graph visibility.