The Virtues of the Quantum Approximate Optimization Algorithm
Talkat Near-Term Quantum Computers: Fault Tolerance + Benchmarking + Quantum Advantage + Quantum Algorithms · 2024-04-22..04-26·
summary
QAOA alternates simple cost-phase and single-qubit rotations and delivers concrete, testable claims: MaxCut p=1 provable worst‑case approximation ≥0.6924, SK model analysis gives p=1 expected value ≈0.303 and Parisi optimum ≈0.76333, and numeric evaluation reaches past 2/π by p≈11 and is carried to p=27. Locality proofs show factorization and failure provable for p < O(log n) (e.g., with 1,000,000 logical qubits depth <10 fails for some problems). Supremacy results hold at shallow depth; optimization requires very small angles.
AI-written summary · about
chapters (11)
- 0:00QAOA introduction
- 1:25Combinatorial optimization
- 8:20Max cut on 3-regular graphs
- 13:22E3LIN2 problem ratios
- 19:15Sherrington-Kirkpatrick model
- 29:44Max-cut on large girth graphs
- 31:57Quantum supremacy in QAOA
- 37:21QAOA limitations
- 42:47Warm-starting QAOA
- 46:01Summary of QAOA
- 48:16Q&A
related talks
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
21mBeating classical heuristics for the binary paint shop problem with the QAOA
18mSAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum(…)
32mOptimal Quantum Programs
15mAssertion-Based Optimization of Quantum Programs
19mAn Industry Perspective on the Path Forward in Quantum Optimization
29mA Verified Optimizer for Quantum Circuits
41mQuantum Computing in Practice: Where We Are, What Works, and What’s Next