Optimizing Noncommutative Polynomials: The SYK Model
summary
Random SYK Hamiltonians (Gaussian coefficients normalized so E[sum A_S^2]=1) live as implicit 2^{N/2}-dimensional Majorana matrices and have OPT(H) = Θ(√N) with high probability. Main claims: degree-6 SOS efficiently certifies OPT(H) ≤ C1√N with C1 ≈ 1.86, while degree-4 SOS fails; a matching lower bound Ω(√N) is proved via an efficient quantum certification algorithm that outputs n/2‑qubit states ρ with Tr(ρH) ≥ Ω(√N).
AI-written summary · about
chapters (10)
- 0:00Introduction to polynomials
- 1:43Defining the problem
- 6:09Representation theory
- 10:35Computational complexity
- 14:40Connection to chemistry
- 19:16The SYK model
- 24:56Upper and lower bounds
- 29:56Quantum certification
- 37:12Future research directions
- 42:26Physics heuristics and variants
related talks
31mA Positivity-First Approach to Sum-of-Squares Over the Hypercube
27mWeak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
01h 07mClassical algorithms for quantum Gibbs states
57mSum of squares spectral amplification (SOSSA)
39mFast Spectral Algorithms from Sum-of-Squares Analyses
43mEfficient Quantum Algorithm for Heisenberg Spin Systems
39mOptimization over the Hypercube via Sums of Nonnegative Circuit Polynomials