Title: Formula Size Lower Bounds and Quantum States
Speaker: Scott Aaronson, IAS
Date: September 27, 2004 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In a paper entitled "Multilinear Formulas and Skepticism of Quantum Computing," I challenged those who believe quantum computing is fundamentally impossible to find a "Sure/Shor separator" -- that is, a natural set of quantum states that can account for all experiments performed to date, but not for Shor's factoring algorithm. As an example, I proposed the set of states expressible by polynomial-size trees of linear combinations and tensor products. The purpose of this talk is to report what I currently know about tree size and related measures of the complexity of quantum states. Using a lower bound on multilinear formula size due to Ran Raz, I will show that all states that correspond to sufficiently good erasure codes have tree size n^Omega(log n) (previously, I only knew this for random linear codes). I will also relate Raz's lower bound method to a physics notion called "persistence of entanglement." Finally, I will show *exponential* lower bounds on a measure called "manifestly orthogonal tree size." These results reveal unexpected connections between quantum mechanics and the lower bound techniques of classical complexity theory.