Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture
summary
Given a basis for an n×n matrix subspace with a promised rank‑one element (wanting ≈1% Frobenius error), the result gives a concrete algorithm: a Sum‑of‑Squares relaxation plus a rounding that uses degree‑√n moments to extract a vector, yielding a 2^{O(√n)} time algorithm up to poly factors. Key structural claim is that rank‑one matrices are 2^{-O(√n)}-convex, proved via a log‑rank‑type argument that finds a 2^{-O(√n)}‑measure subset whose average is approximately rank one.
AI-written summary · about
chapters (13)
- 0:00Start
- 0:56The Problem
- 8:36Structured Eigenvalue Problem
- 9:44Outline
- 11:00Algorithm - Relaxation + Rounding
- 11:59Round first, relax later
- 14:33Solutions as Distributions
- 16:30Wishing for Convexity
- 19:02"Approximating" Convexity
- 23:18Key Idea: Structure Theorem
- 26:56Proving Structure Theorem: Example
- 28:30The Log-Rank Conjecture
- 30:02Lovett's Thm to Structure Thm