Publications
Article · Lobachevskii Journal of Mathematics · February 1, 2023
Quantum Versus Classical Online Streaming Algorithms with Logarithmic Size of Memory
Kamil Ravilevich Khadiev, Aliya Khadieva, Dmitry Kravchenko, Ilnaz Mannapov, Alexander Rivosh, R. Yamilov
Abstract
Abstract We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with a non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in the case of the logarithmic or sublogarithmic size of memory.
Optimization and Search ProblemsQuantum Computing Algorithms and ArchitectureAlgorithms and Data Compressiononline algorithmscompetitive ratioone-way automata
More by Ilnaz Mannapov
- The Improvement of Decision Tree Construction Algorithm Based on Quantum Heuristic AlgorithmsLobachevskii Journal of Mathematics · 2023 · Citations: 5
- Two-way and one-way quantum and classical automata with advice for online minimization problemsTheoretical Computer Science · 2022 · Citations: 12
- The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0arXiv · 2019 · Citations: 23
- Quantum Online Algorithms with Respect to Space and Advice ComplexityLobachevskii Journal of Mathematics · 2018 · Citations: 31