Quantum Versus Classical Online Streaming Algorithms with Logarithmic Size of Memory
Kamil Ravilevich Khadiev, Aliya Khadieva, Dmitry Kravchenko, Ilnaz Mannapov, Alexander Rivosh, Ravil Islamovich Yamilov · Lobachevskii Journal of Mathematics · 2023
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.