Lightning Talks
summary
Observation: pure symmetric n‑qubit states satisfy a quantitative de Finetti rigidity: the trace‑distance of any m‑qubit marginal to a product state is at least ~(m/n) times the global state's distance from product, giving a linear lower bound and implying that any depth‑K circuit that outputs an exactly symmetric pure state must be O(4^K)-close to a product state. Construction: replace cat states with a W state to get a W test that one‑sided tests Exact‑N/2 with soundness 1 − Θ(1/n^2); with polynomially many given input copies and parallel repetition this boosts to inverse‑exponential error, yielding TC^0 computations in QAC^0 and a separation from AC0P via a light‑cone argument.
AI-written summary · about
chapters (11)
- 0:00Quantum definiteness theorems
- 3:18Maximally quantum states
- 8:38Low-depth quantum circuits
- 14:12Rigidity proof technique
- 21:45Jackson Morris's talk
- 22:05QAC0 circuits
- 24:51QAC0 results and questions
- 26:41QAC0 vs AC0P separation
- 27:46TC0 with input copies
- 30:56W test and majority
- 31:42Low-depth quantum problems
related talks
49mCertifying almost all quantum states with few single-qubit measurements
55mFew Single-Qubit Measurements Suffice to Certify Any Quantum State
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
02h 41mLightning Talks
45mQuantum Pseudo-Randomness From Domain Walls and Spectral Gaps
58mLimitations for Quantum PCPs
01h 02mProduct Mixing, Quantum Separation, and Comfortable Juntas
44mQuantum Meets Minimum Circuit Size Problem