Physics – Quantum Physics
Scientific paper
2003-11-07
Physics
Quantum Physics
Journal version, extensively revised and expanded. Points out connections among tree size, error correction, and persistence o
Scientific paper
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.
No associations
LandOfFree
Multilinear Formulas and Skepticism of Quantum Computing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Multilinear Formulas and Skepticism of Quantum Computing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multilinear Formulas and Skepticism of Quantum Computing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-343109