Exponential separation of quantum and classical online space complexity
From MaRDI portal
Publication:733715
DOI10.1007/s00224-007-9097-3zbMath1183.68292arXivquant-ph/0606066MaRDI QIDQ733715
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
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