Classical algorithms and quantum limitations for maximum cut on high-girth graphs
summary
Shows a concrete limitation: for graphs of girth ≥6 any one-local algorithm (classical or quantum) can only achieve cut fraction 1/2 + C/√D with C ≤ 1/√2 ≈ 0.707, so depth‑1 QAOA (~0.31) and classical threshold (~0.33) are far from the Parisi optimum ≈0.76. Proof uses random-walk correlations and adjacency-matrix powers plus Cauchy–Schwarz to bound neighbor correlations; a polytime classical 0.63 algorithm exists and extensions to higher locality remain open.
AI-written summary · about
chapters (6)
- 0:00Introduction
- 0:17Overview
- 2:00Local algorithms
- 2:41Quantum computers
- 5:02State of the art
- 8:36Main technique
related talks
52mThe Virtues of the Quantum Approximate Optimization Algorithm
46mSymmetries, Graph Properties, and Quantum Speedups
01h 10mQuantum Advantage with Shallow Clifford Circuits
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
44mQuantum Complexity of Clique Homology
36mA Combinatorial Approach to Complexity Transitions in Quantum Physics
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
22mQuantum algorithms and the power of forgetting