  Several researchers, including Leonid Levin, Gerard 't Hooft, and Stephen
Wolfram, have argued that quantum mechanics will break down before the
factoring of large numbers becomes possible. If this is true, then there should
be a natural set of quantum states that can account for all experiments
performed to date, but not for Shor's factoring algorithm. We investigate as a
candidate the set of states expressible by a polynomial number of additions and
tensor products. Using a recent lower bound on multilinear formula size due to
Raz, we then show that states arising in quantum error-correction require
n^{Omega(log n)} additions and tensor products even to approximate, which
incidentally yields the first superpolynomial gap between general and
multilinear formula size of functions. More broadly, we introduce a complexity
classification of pure quantum states, and prove many basic facts about this
classification. Our goal is to refine vague ideas about a breakdown of quantum
mechanics into specific hypotheses that might be experimentally testable in the
near future.
