Exponential separation of quantum and classical online space complexity

DOI10.1007/s00224-007-9097-3zbMath1183.68292arXivquant-ph/0606066MaRDI QIDQ733715

François Le Gall

Publication date: 19 October 2009

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

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

zbMATH Keywords

quantum computation; communication complexity; online space complexity

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

81P68: Quantum computation

68Q12: Quantum algorithms and complexity in the theory of computing

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the distributional complexity of disjointness
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Quantum communication and complexity.
• On the complexity of simulating space-bounded quantum computations
• Space-bounded quantum complexity
• On quantum and probabilistic communication
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• The Probabilistic Communication Complexity of Set Intersection
• Quantum communication complexity of symmetric predicates
• Nondeterministic Quantum Query and Communication Complexities
• Communication Complexity
• Quantum lower bounds by polynomials
• Quantum Weakly Nondeterministic Communication Complexity