Download PDFOpen PDF in browser

Two-Way Quantum and Classical Automata with Advice for Online Minimization Problems

EasyChair Preprint 1521

12 pagesDate: September 14, 2019

Abstract

We consider online algorithms. Typically the model is investigated with respect to competitive ratio. In this paper, we explore two-way automata as a model for online algorithms. We focus on quantum and classical online algorithms. We show that there are problems that can be solved more efficiently by two-way automata with quantum and classical states than classical two-way automata in the case of sublogarithmic memory (sublinear size) even if classical automata get advice bits.

Keyphrases: advice complexity, automata, competitive ratio, online algorithms, online minimization problems, quantum computation, quantum online streaming algorithm, streaming algorithms, two-way automata

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@booklet{EasyChair:1521,
  author    = {Kamil Khadiev and Aliya Khadieva},
  title     = {Two-Way Quantum and Classical Automata with Advice for Online Minimization Problems},
  howpublished = {EasyChair Preprint 1521},
  year      = {EasyChair, 2019}}
Download PDFOpen PDF in browser