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

Kamil Khadiev; Aliya Khadieva

doi:10.3390/math10010143

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

Kamil Khadiev
, Aliya Khadieva

Kazan Volga Region Federal University

Zinātniskās darbības rezultāts: Devums žurnālam › Zinātniskais raksts (žurnālā) › koleģiāli recenzēts

14 Atsauces (Scopus)

Kopsavilkums

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.

Oriģinālvaloda	Angļu
Raksta numurs	143
Žurnāls	Mathematics
Sējums	10
Izdevuma numurs	1
DOIs	https://doi.org/10.3390/math10010143
Publikācijas statuss	Publicēts - 1 janv. 2022

OECD Zinātnes nozare

1.1 Matemātika

Piekļuve Dokumentiem

10.3390/math10010143

Citi faili un saites

Citēt šo

@article{52dc723012ba42a6958b45aa514fa3d5,

title = "Quantum and Classical Log-Bounded Automata for the Online Disjointness Problem",

abstract = "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.",

keywords = "Automata, Online algorithms, Online minimization problems, Quantum computation, Streaming algorithms",

author = "Kamil Khadiev and Aliya Khadieva",

note = "Publisher Copyright: {\textcopyright} 2022 by the authors. Licensee MDPI, Basel, Switzerland.",

year = "2022",

month = jan,

day = "1",

doi = "10.3390/math10010143",

language = "English",

volume = "10",

journal = "Mathematics",

issn = "2227-7390",

publisher = "Multidisciplinary Digital Publishing Institute (MDPI)",

number = "1",

}

TY - JOUR

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

AU - Khadiev, Kamil

AU - Khadieva, Aliya

PY - 2022/1/1

Y1 - 2022/1/1

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

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

KW - Automata

KW - Online algorithms

KW - Online minimization problems

KW - Quantum computation

KW - Streaming algorithms

UR - https://www.mdpi.com/2227-7390/10/1/143

UR - https://www.scopus.com/pages/publications/85122177571

U2 - 10.3390/math10010143

DO - 10.3390/math10010143

M3 - Article

SN - 2227-7390

VL - 10

JO - Mathematics

JF - Mathematics

IS - 1

M1 - 143

ER -

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

Kopsavilkums

OECD Zinātnes nozare

Piekļuve Dokumentiem

Citi faili un saites

Nospiedums

Citēt šo