4.7 Article

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

Journal

MATHEMATICS
Volume 10, Issue 1, Pages -

Publisher

MDPI
DOI: 10.3390/math10010143

Keywords

quantum computation; online algorithms; streaming algorithms; online minimization problems; automata

Categories

Funding

  1. Kazan Federal University Strategic Academic Leadership Program [PRIORITY-2030]

Ask authors/readers for more resources

In this paper, the competitive ratio of online algorithms is considered, and one-way automata are explored as a model for these algorithms. Both quantum and classical online algorithms are focused on. Specifically, a quantum log-bounded automaton is proposed for a specially constructed online minimization problem, which outperforms classical automata even with advice in terms of competitive ratio, especially when the memory size is logarithmic. Furthermore, an online version of the well-known Disjointness problem is constructed, which has been studied by many researchers from the perspective of communication complexity and query complexity.
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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available