Product Mixing, Quantum Separation, and Comfortable Juntas
summary
Proves full product‑mixing for SU_n: if A,B,C have Haar measure > e^{-c n^{1/3}} then Pr[a∈A,b∈B: ab∈C] is within 1.01×μ(C), and this threshold is sharp up to the constant c, giving the Gowers product‑free bound μ(A) ≤ e^{-c n^{1/3}}. Proof combines representation‑theoretic multiplicity lower bounds with analytic hypercontractivity (a constructed T_rho noise operator via Gaussian coupling), a level‑d inequality controlling L2 mass, and explicit comfortable d‑juntas to compute eigenvalues. Also yields an improved quantum/classical separation (one clean qubit plus O(log n) noisy qubits vs classical poly(n)).
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:33Anti-group theory problem
- 2:42Compact groups and measure
- 4:54Gowers conjecture
- 7:06Quasi-randomness and results
- 11:39Product mixing and applications
- 15:41Representation theory basics
- 20:18The Gowers operator
- 25:32Spectral bounds and proof
- 33:21Polynomials and dimensions
- 40:02Hypercontractivity
- 46:14Refining the proof
- 57:14Coupling and concluding
related talks
33mLightning Talks
20mUnitary property testing lower bounds by polynomials
58mLimitations for Quantum PCPs
20mConstraint Mixers for Optimization Problems on Circuit Model Quantum Computing
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
01h 00mQuantum Physics for Software Developers
43mEfficient Quantum Algorithm for Heisenberg Spin Systems
49mCertifying almost all quantum states with few single-qubit measurements