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

Unbounded-error quantum computation with small space bounds

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