Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
summary
Proves Gaussian-style concentration for the Hamming weight distribution of n-qubit outputs by building local approximations via low-degree polynomial approximations to AND; depth-d circuits yield tail bounds ~exp(−k^2/n) with an effective locality factor q·2^d, so constant depth gives Chernoff-like decay. Extends to commuting dense Hamiltonian evolutions: p = o(log log n) layers produce k = o(n) locality with subexponential error. Combining this with the overlap-gap property and sign symmetry implies QAOA at p = o(log log n) on symmetric dense COPs has only subexponentially small success probability.
AI-written summary · about
chapters (8)
- 0:00Intro
- 1:09What are concentration bounds for quantum states?
- 6:56Local approximations imply concentration
- 8:59Concentration bounds for shallow circuits
- 16:23Local approximations to dense Hamiltonian evolutions
- 18:11Quantum approximate optimization algorithm (QAOA)
- 22:15Overlap gap property (OGP)
- 23:30Limitations on symmetric QAOA Consider COP that is symmetric under fipping all signs (eg. f-local for even) and has strong
related talks
52mThe Virtues of the Quantum Approximate Optimization Algorithm
21mBeating classical heuristics for the binary paint shop problem with the QAOA
33mLightning Talks
45mQuantum Pseudo-Randomness From Domain Walls and Spectral Gaps
01h 05mVerifiable quantum advantage: old and new ideas
17mBounds on the QAC0 Complexity of Approximating Parity
18mSAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum(…)
01h 08mPutting Quantum Supremacy on a Rigorous Footing