Quantum Online Algorithms with Respect to Space and Advice Complexity

Abstract

Online computation is a well-known area of computer science. We introduce quantum online algorithms and investigate them with respect to a competitive ratio in two points of view: space complexity and advice complexity. We start with exploring a model with restricted memory and show that quantum online algorithms can be better than classical ones (deterministic or randomized) for sublogarithmic space (memory), and they can be better than deterministic online algorithms without restriction for memory. Additionally, we consider the polylogarithmic space case and show that in this case, quantum online algorithms can be better than deterministic ones as well. Another point of view to the online algorithms model is advice complexity. So, we introduce quantum online algorithms with a quantum channel with an adviser. Firstly, we show that quantum algorithms have at least the same computational power as classical ones have. We give some examples of quantum online algorithms with advice. Secondly, we show that if we allow to use shared entangled qubits (EPR-pairs), then a quantum online algorithm can use half as many advise qubits compared to a classical one. We apply this approach to the well-known Paging Problem.

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