Exponential separation of quantum and classical online space complexity

ABSTRACT

The main objective of quantum computation is to exploit the natural parallelism of quantum mechanics to solve problems using less computational resources than classical computers. Although quantum algorithms realizing an exponential time speed-up over the best known classical algorithms exist, no quantum algorithm is known performing computation using less space resources than classical algorithms. In this paper, we study, for the first time explicitly, spacebounded quantum algorithms for computational problems where the input is given not as a whole, but bit by bit. We show that there exist such problems that a quantum computer can solve using exponentiallyless work space than a classical computer. More precisely, we introduce a very natural and simple model of a space-bounded quantum online machine and prove an exponential separation of classical and quantum online space complexity, in the bounded-error setting and for a total language. The language we consider is inspired bya communication problem that Buhrman, Cleve and Wigderson used to show an almost quadratic separation of quantum and classical bounded-error communication complexity. We prove that, in the framework of online space complexity, the separation becomes exponential.

REFERENCES

• 1: S. Aaronson and A. Ambainis. Quantum search of spatial regions. Theory of Computing, 1:47--79, 2005.
• 2: Farid Ablayev, Lower bounds for one-way probabilistic communication complexity and their application to space complexity, Theoretical Computer Science, v.157 n.2, p.139-159, May 5, 1996 [doi>10.1016/0304-3975(95)00157-3]
• 3: Dorit Aharonov , Alexei Kitaev , Noam Nisan, Quantum circuits with mixed states, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.20-30, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276708]
• 4: J. L. Balcázar, J. Diaz, and J. Gabarró. Structural Complexity I. Springer-Verlag, 1995.
• 5: Ziv Bar-Yossef , T. S. Jayram , Iordanis Kerenidis, Exponential separation of quantum and classical one-way communication complexity, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007379]
• 6: Robert Beals , Harry Buhrman , Richard Cleve , Michele Mosca , Ronald de Wolf, Quantum lower bounds by polynomials, Journal of the ACM (JACM), v.48 n.4, p.778-797, July 2001 [doi>10.1145/502090.502097]
• 7: 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]
• 8: M. Boyer, G. Brassard, P. Høyer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4-5):493--505, 1998.
• 9: Harry Buhrman , Richard Cleve , Avi Wigderson, Quantum vs. classical communication and computation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.63-68, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276713]
• 10: H. Buhrman. Quantum computing and communication complexity. Bulletin of the EATCS, 70:131--141, 2000.
• 11: 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]
• 12: Peter Høyer , Ronald de Wolf, Improved Quantum Communication Complexity Bounds for Disjointness and Equality, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.299-310, March 14-16, 2002
• 13: Bala Kalyanasundaram , Georg Schintger, The probabilistic communication complexity of set intersection, SIAM Journal on Discrete Mathematics, v.5 n.4, p.545-557, Nov. 1992 [doi>10.1137/0405044]
• 14: H. Klauck. Quantum communication complexity. In Proceedings of the Workshop on Boolean Functions and Applications at the 27th International Colloquium on Automata, Languages andPr ogramming, pages 241--252, 2000.
• 15: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 16: F. Le Gall. Quantum weaklyn ondeterministic communication complexity. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, to appear, 2006. Preprint version: Los Alamos e-print archive, quant-ph/0511025.
• 17: S. Muthukrishnan. Data Streams: Algorithms and Applications. Now Publishers, 2005.
• 18: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 19: A. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, v.106 n.2, p.385-390, Dec. 1992 [doi>10.1016/0304-3975(92)90260-M]
• 20: A. Razborov. Quantum communication complexityof symmetric predicates. Izvestiya Mathematics, 67(1):145--159, 2003.
• 21: John Watrous, Space-bounded Quantum complexity, Journal of Computer and System Sciences, v.59 n.2, p.281-326, Oct. 1999 [doi>10.1006/jcss.1999.1655]
• 22: John Watrous, On the complexity of simulating space-bounded quantum computations, Computational Complexity, v.12 n.1/2, p.48-84, July 2004 [doi>10.1007/s00037-003-0177-8]
• 23: Ronald de Wolf, Quantum communication and complexity, Theoretical Computer Science, v.287 n.1, p.337-353, 25 September 2002 [doi>10.1016/S0304-3975(02)00377-8]
• 24: Ronald de Wolf, Nondeterministic Quantum Query and Communication Complexities, SIAM Journal on Computing, v.32 n.3, p.681-699, 2003 [doi>10.1137/S0097539702407345]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.0 General

General Terms:
Algorithms, Theory

Keywords:
communication complexity, online, quantum computation, space complexity, streaming algorithms