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 "Sure/Shor separator" -- that is,
a set of quantum states that can account for all experiments performed
to date, but not for Shor's factoring algorithm. We propose 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.