Exponential separation of quantum and classical online space complexity
From MaRDI portal
Publication:733715
DOI10.1007/s00224-007-9097-3zbMath1183.68292arXivquant-ph/0606066OpenAlexW3105424158MaRDI 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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (6)
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 ⋮ Quantum online streaming algorithms with logarithmic memory ⋮ Unbounded-error quantum computation with small space bounds ⋮ Quantum Chebyshev's Inequality and Applications
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Exponential separation of quantum and classical online space complexity
