### DIMACS Theoretical Computer Science Seminar

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.

Paper at http://www.arxiv.org/abs/quant-ph/0311039