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 set of quantum states that can account for all quantum computing 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^{Ω(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.

REFERENCES

• 1: S. Aaronson. Book review on A New Kind of Science, Quantum Information and Computation (QIC) 2(5), 2002.
• 2: D. S. Abrams and S. Lloyd. Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems, Phys. Rev. Lett. 81:3992--3995, 1998.
• 3: D. Aharonov , M. Ben-Or, Fault-tolerant quantum computation with constant error, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.176-188, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258579]
• 4: Dorit Aharonov , Amnon Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780546]
• 5: Andris Ambainis , Leonard J. Schulman , Amnon Ta-Shma , Umesh Vazirani , Avi Wigderson, The Quantum Communication Complexity of Sampling, SIAM Journal on Computing, v.32 n.6, p.1570-1585, 2003 [doi>10.1137/S009753979935476]
• 6: M. Arndt, O. Nairz, J. Vos-Andreae, C. Keller, G. van der Zouw, and A. Zeilinger. Wave-particle duality of C60 molecules, Nature 401:680--682, 1999.
• 7: A. Aspect, P. Grangier, and G. Roger. Experimental realization of Einstein-Podolsky-Rosen-Bohm gedankenexperiment: a new violation of Bell's inequalities, Phys. Rev. Lett. 49:91--94, 1982.
• 8: S. L. Braunstein, C. M. Caves, N. Linden, S. Popescu, and R. Schack. Separability of very noisy mixed states and implications for NMR quantum computing, Phys. Rev. Lett. 83:1054--1057, 1999.
• 9: H. J. Briegel and R. Raussendorf. Persistent entanglement in arrays of interacting particles, Phys. Rev. Lett. 86:910--913, 2001.
• 10: P. Burgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory, Springer-Verlag, 1997.
• 11: A. R. Calderbank and P. W. Shor. Good quantum error-correcting codes exist, Phys. Rev. A 54:1098--1105, 1996.
• 12: J. Cronin. CP symmetry violation---the search for its origin, Nobel Lecture, December 8, 1980.
• 13: W. Dur and H. J. Briegel. Stability of macroscopic entanglement under decoherence, submitted, 2003.
• 14: V. Fitch. The discovery of charge-conjugation parity asymmetry, Nobel Lecture, December 8, 1980.
• 15: J. R. Friedman, V. Patel, W. Chen, S. K. Tolpygo, and J. E. Lukens. Quantum superposition of distinct macroscopic states, Nature 406:43--46, 2000.
• 16: M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial time hierarchy, Math. Systems Theory 17:13--27, 1984.
• 17: G. C. Ghirardi, A. Rimini, and T. Weber. Unified dynamics for microscopic and macroscopic systems, Phys. Rev. D, 34:470, 1986.
• 18: S. Ghosh, T. F. Rosenbaum, G. Aeppli, and S. N. Coppersmith. Entangled quantum state of magnetic dipoles, Nature 425:48--51, 2003.
• 19: O. Goldreich. On quantum computing, 2004. www. wisdom. weizmann. ac. il/ oded/on-qc. html
• 20: D. Gottesman. Class of quantum error-correcting codes saturating the quantum Hamming bound, Phys. Rev. A. 54:1862--1868, 1996.
• 21: D. Gottesman. The Heisenberg representation of quantum computers, Int. Conf. on Group Theoretic Methods in Physics, 1998.
• 22: F. Green, S. Homer, C. Moore, and C. Pollett. Counting, fanout, and the complexity of quantum ACC, Quantum Information and Computation 2(1):35--65, 2002.
• 23: G. 't Hooft. Quantum gravity as a dissipative deterministic system, Classical and Quantum Gravity 16:3263--3279, 1999.
• 24: D. Janzing, P. Wocjan, and T. Beth. Cooling and low energy state preparation for 3-local Hamiltonians are FQMA-complete, manuscript, 2003.
• 25: A. Yu. Kitaev. Quantum computation: algorithms and error correction, Russian Math. Surveys 52(6):1191--1249, 1997.
• 26: E. Knill, R. Laflamme, R. Martinez, and C. Negrevergne. Implementation of the five qubit error correction benchmark, Phys. Rev. Lett. 86:5811, 2001.
• 27: E. Knill, R. Laflamme, R. Martinez, and C. -H. Tseng. An algorithmic benchmark for quantum information processing, Nature 404:368--370, 2000.
• 28: E. Knill, R. Laflamme, and W. Zurek. Resilient quantum computation, Science 279:342, 1998.
• 29: A. J. Leggett. Testing the limits of quantum mechanics: motivation, state of play, prospects, J. Phys. Condensed Matter 14:R415--451, 2002.
• 30: L. A. Levin, The Tale of One-Way Functions, Problems of Information Transmission, v.39 n.1, p.92-103, January-March 2003 [doi>10.1023/A:1023634616182]
• 31: L. Levin, D. Gottesman, P. Shor, et al. Discussion on sci. physics. research newsgroup, February-March 2000.
• 32: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 33: R. Penrose. The Emperor's New Mind, Oxford Univ. Press, 1989.
• 34: R. Raussendorf, D. E. Browne, and H. J. Briegel. Measurement-based quantum computation on cluster states, Phys. Rev. A 68:022312, 2003.
• 35: Ran Raz, Multi-linear formulas for permanent and determinant are of super-polynomial size, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.633-641, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007353]
• 36: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 37: A. Steane. Multiple particle interference and quantum error correction, Proc. Roy. Soc. Lond. A, 452:2551--2577, 1996.
• 38: G. Vidal. Efficient classical simulation of slightly entangled quantum computations, Phys. Rev. Lett. 91:147902, 2003.
• 39: A new kind of science, Wolfram Media Inc., Champaign, Ilinois, US, 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Theory

Keywords:
error-correcting codes, matrix rank, multilinear formula size, quantum computing