Preprint · arXiv · February 13, 2018
Quantum versus Classical Online Streaming Algorithms with Advice
Kamil Ravilevich Khadiev, Aliya Khadieva, Mansur Ziatdinov, Dmitry Kravchenko, Alexander Rivosh, Ramis Yamilov
Abstract
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with 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 a case of logarithmic or sublogarithmic size of memory, even if classical online algorithms get advice bits. Furthermore, we show that a quantum online algorithm with a constant number of qubits can be better than any deterministic online algorithm with a constant number of advice bits and unlimited computational power.
More by Ilnaz Mannapov
- Quantum Versus Classical Online Streaming Algorithms with Logarithmic Size of MemoryLobachevskii Journal of Mathematics · 2023 · Citations: 13
- 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