Lower Bounds on Stabilizer Rank
summary
Proves a concrete barrier for Clifford+T simulation by showing the stabilizer rank of the n-fold magic state is linear Ω(n) (n/100) and the approximate rank is Ω(√n / log n) for small constant δ, so decompositions into few stabilizer states cannot represent |H>^⊗n. Proof reduces stabilizer states to indicator-of-affine-subspace times quadratic-phase functions over F2 and then uses combinatorial counting to find two different Hamming-weight inputs that force agreement. Open goal: close to exponential.
AI-written summary · about
chapters (10)
- 0:00ARE QUANTUM COMPUTERS MORE POWERFUL THAN CLASSICAL COMPUTERS?
- 2:30QUANTUM CIRCUITS
- 3:08UNIVERSAL GATE SETS What type of gates are allowed?
- 5:44SIMULATION OF CLIFFORD CIRCUITS
- 7:57BOUNDS ON STABILIZER RANK
- 10:29STABILIZER STATES AS QUADRATIC POLYNOMIALS
- 13:02STABILIZER FUNCTIONS
- 15:35QUADRATIC UNCERTAINTY PRINCIPLE Aside the Quadratic Uncertainty Principle, a well known conjecture in analysis of boolean
- 17:31PROOF PLAN
- 20:34OPEN PROBLEMS
related talks
01h 04mLearning Beyond Stabilizer States
45mOn the NLTS Conjecture
20mLow-Stabilizer-Complexity Quantum States Are Not Pseudorandom
50mMaking the Leap to Quantum PCPs
01h 10mQuantum Advantage with Shallow Clifford Circuits
48mQuantum Linear Algebra Using Subspace States
51mOn constant T-depth circuits
33mLightning Talks