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

Kamil Khadiev and Aliya Khadieva
Additional contact information
Kamil Khadiev: Institute of Computational Mathematics and Information Technologies, Kazan Federal University, Kremlevskaya Str. 18, 420008 Kazan, Russia
Aliya Khadieva: Institute of Computational Mathematics and Information Technologies, Kazan Federal University, Kremlevskaya Str. 18, 420008 Kazan, Russia

Mathematics, 2022, vol. 10, issue 1, 1-21

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: quantum computation; online algorithms; streaming algorithms; online minimization problems; automata (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/1/143/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/1/143/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:1:p:143-:d:717385

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().