Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lobachevskii Journal of Mathematics

Quantum Online Algorithms with Respect to Space and Advice Complexity

Kamil Ravilevich Khadiev, Aliya Khadieva, Ilnaz Mannapov

Published Nov 1, 2018• 32 citations
Publisher

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.

DOI
10.1134/s1995080218090421

Related papers

Quantum Online Algorithms with Respect to Space Complexity

Kamil Ravilevich Khadiev, Aliya Khadieva, Ilnaz Mannapov

Online algorithm is a well-known computational model. 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 polylogarithmic space case and show that in this case, quantum online algorithms can be better than deterministic ones as well.

arXiv:1709.08409•Sep 25, 2017•3 citations

Quantum Online Streaming Algorithms with Constant Number of Advice Bits.

Kamil Ravilevich Khadiev, Mansur Ziatdinov, Ilnaz Mannapov +2 more

Online algorithms are known model that is investigated with respect to a competitive ratio typically. In this paper, we investigate streaming algorithms as a model for online algorithms. We focus on quantum and classical online algorithms with advice. Special problem $P_k$ was considered. This problem is obtained using Black Hats Method. There is an optimal quantum online algorithm with single advice bit and single qubit of memory for the problem. At the same time, there is no optimal deterministic or randomized online algorithm with sublogarithmic memory for the same problem even the algorithm gets $o(\log n)$ advice bits. Additionally, we show that quantum online algorithm with a constant number of qubits can be better than deterministic online algorithm even if deterministic one has a constant number of advice bits and unlimited computational power.

•Feb 13, 2018•5 citations

Quantum versus Classical Online Algorithms with Advice and Logarithmic Space.

Kamil Ravilevich Khadiev, Aliya Khadieva, Dmitry Kravchenko +1 more

In this paper, we consider online algorithms. Typically the model is investigated with respect to competitive ratio. We consider algorithms with restricted memory (space) and explore their power. We focus on quantum and classical online algorithms. We show that there are problems that can be better solved by quantum algorithms than classical ones in a case of logarithmic memory. Additionally, we show that quantum algorithm has an advantage, even if deterministic algorithm gets advice bits. We propose Black Hats Method. This method allows us to construct problems that can be effectively solved by quantum algorithms. At the same time, these problems are hard for classical algorithms. The separation between probabilistic and deterministic algorithms can be shown with a similar method.

•Oct 26, 2017•4 citations

Quantum versus Classical Online Streaming Algorithms with Advice

Kamil Ravilevich Khadiev, Aliya Khadieva, Mansur Ziatdinov +4 more

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.

arXiv:1802.05134•Feb 13, 2018•0 citations

Quantum Online Algorithms for a Model of the Request-Answer Game with a Buffer

Kamil Ravilevich Khadiev, Dianhuan Lin

In this paper, we considered online algorithms as a request-answer game between two players: an adversary that generates input requests and an online algorithm that answers them. A generalized version of the game that has a buffer of limited size was studied. The adversary loads data to the buffer, while the algorithm has random access to elements of the buffer. For the model, quantum and classical (deterministic or randomized) algorithms were a focus of attention. A specific problem and a quantum algorithm that works better than any classical (deterministic or randomized) algorithm, in terms of competitive ratio, were provided. At the same time, for the problem, classical online algorithms in the standard model are equivalent to the classical algorithms in the request-answer game with a buffer model.

Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki•Jan 1, 2020•7 citations

Quantum Versus Classical Online Streaming Algorithms with Logarithmic Size of Memory

Kamil Ravilevich Khadiev, Aliya Khadieva, Dmitry Kravchenko +3 more

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.

arXiv:1710.09595•Lobachevskii Journal of Mathematics•Feb 1, 2023•9 citations
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.
Online algorithm is a well-known computational model. 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 polylogarithmic space case and show that in this case, quantum online algorithms can be better than deterministic ones as well.
Online algorithms are known model that is investigated with respect to a competitive ratio typically. In this paper, we investigate streaming algorithms as a model for online algorithms. We focus on quantum and classical online algorithms with advice. Special problem PkP_kPk​ was considered. This problem is obtained using Black Hats Method. There is an optimal quantum online algorithm with single advice bit and single qubit of memory for the problem. At the same time, there is no optimal deterministic or randomized online algorithm with sublogarithmic memory for the same problem even the algorithm gets o(log⁡n)o(\log n)o(logn) advice bits. Additionally, we show that quantum online algorithm with a constant number of qubits can be better than deterministic online algorithm even if deterministic one has a constant number of advice bits and unlimited computational power.
In this paper, we consider online algorithms. Typically the model is investigated with respect to competitive ratio. We consider algorithms with restricted memory (space) and explore their power. We focus on quantum and classical online algorithms. We show that there are problems that can be better solved by quantum algorithms than classical ones in a case of logarithmic memory. Additionally, we show that quantum algorithm has an advantage, even if deterministic algorithm gets advice bits. We propose Black Hats Method. This method allows us to construct problems that can be effectively solved by quantum algorithms. At the same time, these problems are hard for classical algorithms. The separation between probabilistic and deterministic algorithms can be shown with a similar method.
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.
In this paper, we considered online algorithms as a request-answer game between two players: an adversary that generates input requests and an online algorithm that answers them. A generalized version of the game that has a buffer of limited size was studied. The adversary loads data to the buffer, while the algorithm has random access to elements of the buffer. For the model, quantum and classical (deterministic or randomized) algorithms were a focus of attention. A specific problem and a quantum algorithm that works better than any classical (deterministic or randomized) algorithm, in terms of competitive ratio, were provided. At the same time, for the problem, classical online algorithms in the standard model are equivalent to the classical algorithms in the request-answer game with a buffer model.