Quantum computers that can be simulated classically in polynomial time

ABSTRACT

A model of quantum computation based on unitary matrix operations was introduced by Feynman and Deutsch. It has been asked whether the power of this model exceeds that of classical Turing machines. We show here that a significant class of these quantum computations can be simulated classically in polynomial time. In particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. This contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the Polynomial Time Turing Hypothesis. In other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to Turing machines for any problem. The techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. In a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. The results generalize the quantum model in that they do not require the matrices to be unitary. In a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice Boolean formulae. All our results are based on the use of gates that are defined in terms of their graph matching properties.

REFERENCES

• 1: A. Barenco, A universal two-bit gate for quantum computation, Proc. R. Soc. Lond. A449, 679-683, (1995).
• 2: P. A. Benioff, Quantum mechanical Hamiltonian models of discrete processes that erase their own histories: Application to Turing machines, Int. J. Theor. Phys., 21:6/7, 177, (1982).
• 3: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 4: A Borodin , S Cook , N Pippenger, Parallel computation for well-endowed rings and space-bounded probabilistic machines, Information and Control, v.58 n.1-3, p.113-136, July/Aug./Sept. 1983 [doi>10.1016/S0019-9958(83)80060-6]
• 5: R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, Cambridge University Press, 1991.
• 6: Russ Bubley , Martin Dyer, Graph orientations with no sink and an approximation for a hard case of #SAT, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.248-257, January 05-07, 1997, New Orleans, Louisiana, United States
• 7: P. B. urgisser, M. Clausen, and M.A. Shokrollahi, Algebraic Complexity Theory, Springer Verlag, (1996).
• 8: P. B. urgisser, Completeness and Reduction in Algebraic Complexity Theory, SpringerVerlag, (2000).
• 9: A. Cayley, Sur les determinates gauches, Crelle's J., 38, 93, (1854).
• 10: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 11: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 12: D. Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. R. Soc. Lond. A400, 97-117, (1985).
• 13: D. Deutsch, Quantum computational networks, Proc. R. Soc. Lond. A425, 73-90, (1989).
• 14: D. Deutsch, A. Barenco, and A. Ekert, Universality of quantum computation, Proc. R. Soc. Lond. A449, 669-677, (1995).
• 15: D. P. DiVincenzo, Two-bit gates are universal for quantum computation, Phys. Rev. A, 51:2, 1015-1022, (1995).
• 16: Peter van Emde Boas, Machine models and simulations, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 17: R. P. Feynman, Simulating physics with computers, Int. J. Theor. Phys., 21:6/7,467-488, (1982).
• 18: D. Gottesman, The Heisenberg representation of quantum computers, quant-ph/9807006, (1998).
• 19: Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
• 20: H. B. Hunt , R. E. Stearns, The complexity of very simple Boolean formulas with applications, SIAM Journal on Computing, v.19 n.1, p.44-70, Feb. 1990 [doi>10.1137/0219003]
• 21: M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
• 22: K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro, Computability by probabilistic machines, in Automata Studies, C. E. Shannon and J. McCarthy, eds. (Princeton Univ. Press, 1956), pp. 183-212.
• 23: E. H. Lieb, A theorem on Pfaffans, J. Comb. Theory, 5, 313-319, (1968).
• 24: K. Murota. Matrices and Matroids for Systems Analysis, Springer-Verlag, Berlin, 2000.
• 25: C. H. Papadimitriou, Computational Complexity, Addison- Wesley, Reading, MA, (1994).
• 26: R.W. Robinett. Quantum Mechanics, Oxford University Press, New York, 1997.
• 27: 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]
• 28: V. Strassen, Gaussian elimination is not optimal, Numer. Math., 13, 354-356, (1968)
• 29: L. Troyansky and N. Tishby. Permanent uncertainty: On the quantum evaluation of the determinant and the permanent ofa matrix. In Proceedings of Phys. Comp. 96.
• 30: A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. Lond. Math. Soc., Ser.2, 42, 230-265 (1936).
• 31: L. G. Valiant, The complexity of computing the permanent, Theor. Comp. Sci., 8(2), 189-201, (1979).
• 32: L. G. Valiant, Completeness classes in algebra, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.249-261, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804419]
• 33: L. G. Valiant, Expressiveness of matchgates, submitted for publication, February 2001.
• 34: L. G. Valiant , V. V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science, v.47 n.1, p.85-93, Nov. 1986
• 35: A. C.-C. Yao, Quantum circuit complexity, Proc 34th Symp. On Foundations of Computer Science, (IEEE Computer Society, Los Alamitos, CA, 1993), pp. 352- 360.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Measurement, Performance, Theory, Verification