6533b820fe1ef96bd127a349
RESEARCH PRODUCT
Two-way quantum and classical machines with small memory for online minimization problems
Aliya KhadievaAliya KhadievaKamil Khadievsubject
Theoretical computer scienceComputational complexity theoryCompetitive analysisSublinear functionComputer scienceOnline algorithmFocus (optics)QuantumAutomatonQuantum computerdescription
We consider online algorithms. Typically the model is investigated with respect to competitive ratio. In this paper, we explore algorithms with small memory. We investigate two-way automata as a model for online algorithms with restricted memory. We focus on quantum and classical online algorithms. We show that there are problems that can be better solved by two-way automata with quantum and classical states than classical two-way automata in the case of sublogarithmic memory (sublinear size).
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2019-03-15 | International Conference on Micro- and Nano-Electronics 2018 |