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

arXiv:1802.05134

Quantum versus Classical Online Streaming Algorithms with Advice

Kamil Ravilevich Khadiev, Aliya Khadieva, Mansur Ziatdinov, Dmitry Kravchenko, Alexander Rivosh, Ramis Yamilov, Ilnaz Mannapov

Published Feb 13, 2018• 0 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.1802.05134

Related papers

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 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

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 Online Algorithms with Respect to Space and Advice Complexity

Kamil Ravilevich Khadiev, Aliya Khadieva, Ilnaz Mannapov

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.

Lobachevskii Journal of Mathematics•Nov 1, 2018•32 citations

Quantum and Classical Log-Bounded Automata for the Online Disjointness Problem

Kamil Ravilevich Khadiev, Aliya Khadieva

We consider online algorithms with respect to the competitive ratio. In this paper, we explore one-way automata as a model for online algorithms. We focus on quantum and classical online algorithms. For a specially constructed online minimization problem, we provide a quantum log-bounded automaton that is more effective (has less competitive ratio) than classical automata, even with advice, in the case of the logarithmic size of memory. We construct an online version of the well-known Disjointness problem as a problem. It was investigated by many researchers from a communication complexity and query complexity point of view.

Mathematics•Jan 4, 2022•14 citations

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
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.
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.
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.
We consider online algorithms with respect to the competitive ratio. In this paper, we explore one-way automata as a model for online algorithms. We focus on quantum and classical online algorithms. For a specially constructed online minimization problem, we provide a quantum log-bounded automaton that is more effective (has less competitive ratio) than classical automata, even with advice, in the case of the logarithmic size of memory. We construct an online version of the well-known Disjointness problem as a problem. It was investigated by many researchers from a communication complexity and query complexity point of view.
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.