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

EasyChair Preprint 1521

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

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