Exponential Separation of Quantum and Classical Online Space Complexity

Abstract

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, space-bounded 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 exponentially less 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 by a communication problem (the set intersection function) 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.

13 pages. v3: minor changes

References in corpus (4)

• Quantum fingerprinting
• Tight bounds on quantum searching
• Quantum communication complexity of symmetric predicates
• Improved Quantum Communication Complexity Bounds for Disjointness and Equality

Cited by in corpus (6)

• Unbounded-error quantum computation with small space bounds
• Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
• Shallow Implementation of Quantum Fingerprinting with Application to Quantum Finite Automata
• Universal quantum computation with symmetric qubit clusters coupled to an environment
• Space Complexity of Streaming Algorithms on Universal Quantum Computers
• Implementation of Quantum Fourier Transform and Quantum Hashing for a Quantum Device with Arbitrary Qubits Connection Graphs