Convex Optimization and Quantum Information
summary
Explains concrete results connecting convex relaxations to quantum tasks: shows HSEP (separability support function) equals injective tensor norms and 2→4 problems, proves quasi‑polynomial hardness for 2→4, and gives SDP/SOS hierarchies (e.g. K‑extendable+PPT) for separability and local Hamiltonian energy with information‑theoretic convergence proofs via conditional mutual information. Compares SOS performance to epsilon nets algorithms (same quasi‑poly bounds), applies to Kagome Hamiltonian numerics, and lists open gaps between hardness and algorithmic guarantees.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:18outline
- 2:03quantum information noncommutative probability
- 11:12bipartite states
- 13:25entanglement and optimization
- 17:41complexity of hep
- 25:02multipartite states
- 29:32local Hamiltonians
- 33:05kagome antiferromagnet
- 35:23quantum marginal problem
- 38:58Other Hamiltonian problems
- 41:08SOS hierarchies for q info
- 43:061. SOS hierarchies for Sep
- 45:522. SOS hierarchies for 1 min
- 49:23classical analogue of Sep quadratic optimization over simplex
- 53:25Nash equilibria
- 54:19algorithm for approx Nash
- 57:47net-based algorithms
- 58:21nets for Banach spaces
related talks
01h 07mTwo Tensor Optimization Problems From Quantum Information
14mQuantum approach to classical optimization: why bother and what to do?
44mNo Quantum Speedup Over Gradient Descent for Non-Smooth Convex Optimization
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
20mA Quantum Interpretation of Separating Conjunction for Local Reasoning of Quantu
21mSoftware for Quantum Computing- Easing Solutions for Complex
50mMaking the Leap to Quantum PCPs
23mQuantum Information Effects