__
TR03-079 | 8th November 2003 00:00
__

#### Multilinear Formulas and Skepticism of Quantum Computing

**Abstract:**
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.