Concentration Bounds for Quantum States and QAOA Limitations

Explore a conference talk from TQC 2023 that delves into concentration bounds for quantum states and their implications for quantum approximate optimization algorithm (QAOA). Learn about groundbreaking research demonstrating concentration bounds for output states of shallow quantum circuits, injective matrix product states, and dense Hamiltonian evolution states. Discover how polynomial approximations prove these states' proximity to local operators, leading to concentrated distributions in computational basis measurements. Understand the significant implications for QAOA, including new limitations on dense instances at super-constant level, showing that for random spin models, QAOA can only succeed with negligible probability at level p = o(log log n). Follow along as the presentation covers introduction to concentration bounds, their applications, local approximations, shallow quantum circuits, dense Hamiltonian evolution, and concludes with insights into QCOA limitations.