Exponential separation of quantum and classical online space complexity

DOI10.1007/S00224-007-9097-3zbMATH Open1183.68292arXivquant-ph/0606066OpenAlexW3105424158MaRDI QIDQ733715FDOQ733715

Authors: François Le Gall 

Publication date: 19 October 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/quant-ph/0606066

Recommendations

• Quantum online algorithms with respect to space and advice complexity
• Exponential separation of quantum and classical communication complexity
• Quantum online streaming algorithms with logarithmic memory
• Space-bounded quantum complexity
• scientific article; zbMATH DE number 1775389

zbMATH Keywords

quantum computationcommunication complexityonline space complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum search of spatial regions
• Data streams: algorithms and applications.
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• Title not available (Why is that?)
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Quantum communication complexity of symmetric predicates
• Quantum lower bounds by polynomials
• On the distributional complexity of disjointness
• On quantum and probabilistic communication
• Nondeterministic Quantum Query and Communication Complexities
• Title not available (Why is that?)
• Quantum communication and complexity.
• Exponential separations for one-way quantum communication complexity, with applications to cryptography
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum Weakly Nondeterministic Communication Complexity
• On the complexity of simulating space-bounded quantum computations
• Space-bounded quantum complexity
• Parallel computation for well-endowed rings and space-bounded probabilistic machines

Cited In (8)

• Quantum online streaming algorithms with logarithmic memory
• Unbounded-error quantum computation with small space bounds
• Space complexity of streaming algorithms on universal quantum computers
• Quantum Chebyshev's Inequality and Applications
• Quantum algorithm for dynamic programming approach for DAGs and applications
• Time-Space Complexity Advantages for Quantum Computing
• Quantum versus classical online streaming algorithms with logarithmic size of memory
• Deterministic construction of QFAs based on the quantum fingerprinting technique

This page was built for publication: Exponential separation of quantum and classical online space complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q733715)