Quantum versus classical online streaming algorithms with logarithmic size of memory
DOI10.1134/s1995080223020208arXiv1710.09595OpenAlexW2951323686MaRDI QIDQ6043926
Dmitry Kravchenko, Ramis Yamilov, Aliya Khadieva, Alexander Rivosh, Kamil Khadiev, Ilnaz Mannapov
Publication date: 25 May 2023
Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1710.09595
quantum computationonline algorithmautomatonbranching programBDDstreaming algorithmonline minimization problem
Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Foundations, quantum information and its processing, quantum axioms, and philosophy (81Pxx)
Cites Work
- Superiority of exact quantum automata for promise problems
- Competitive analysis of maintaining frequent items of a stream
- Quantum online algorithms with respect to space and advice complexity
- Exponential separation of quantum and classical online space complexity
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Unary probabilistic and quantum automata on promise problems
- Quantum branching programs and space-bounded nonuniform quantum complexity
- Two-way and one-way quantum and classical automata with advice for online minimization problems
- Quantum online streaming algorithms with logarithmic memory
- Automata and quantum computing
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Nondeterministic unitary OBDDs
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- On the computational power of probabilistic and quantum branching program
- The Frequent Items Problem in Online Streaming Under Various Performance Measures
- Quantum Computation and Quantum Information
- Competitive Analysis of Aggregate Max in Windowed Streaming
- Branching Programs and Binary Decision Diagrams
- Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
- Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
- Classical and Quantum Computations with Restricted Memory
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Quantum versus classical online streaming algorithms with logarithmic size of memory
