Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
summary
Gives an efficient procedure that, using four copies of an n‑qubit state, samples the scaled convolution q_psi of the Weyl‑operator characteristic distribution p_psi, computes the empirical mean eta = E_{q_psi}[scaled p_psi], and distinguishes Haar‑random states (eta ≈ 0) from states with nonnegligible stabilizer fidelity (eta bounded away from 0). Corollary: circuits with only omega(log n) T-gates cannot produce computationally pseudorandom states.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:15Quantum Computing Crash Course: States
- 1:32Quantum Computing Crash Course: Evolution
- 2:59Stabilizer States and Clifford Circuits
- 6:01Low-Stabilizer-Complexity States
- 9:42Efficient Distinguisher: Weyl Operators
- 12:06Efficient Distinguisher: Algorithm
- 16:54Corollary: T-gate Lower Bound
- 18:43Open Problems
related talks
01h 04mLearning Beyond Stabilizer States
50mMaking the Leap to Quantum PCPs
33mLightning Talks
09mSample efficient identity testing and independence testing of quantum states
22mLower Bounds on Stabilizer Rank
01h 02mHow did we miss the random purification channel?
01h 03mConstant depth pseudoentanglement - Shallow circuits, deep backstory
42mLearning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time