Translator Disclaimer
Paper
15 March 2019 Two-way quantum and classical machines with small memory for online minimization problems
Kamil Khadiev, Aliya Khadieva
Author Affiliations +
Proceedings Volume 11022, International Conference on Micro- and Nano-Electronics 2018; 110222T (2019) https://doi.org/10.1117/12.2522462
Event: The International Conference on Micro- and Nano-Electronics 2018, 2018, Zvenigorod, Russian Federation
Abstract
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).
© (2019) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Kamil Khadiev and Aliya Khadieva "Two-way quantum and classical machines with small memory for online minimization problems", Proc. SPIE 11022, International Conference on Micro- and Nano-Electronics 2018, 110222T (15 March 2019); https://doi.org/10.1117/12.2522462
PROCEEDINGS
9 PAGES


SHARE
Lens.org Logo
CITATIONS
Cited by 5 scholarly publications.
Advertisement
Advertisement
Back to Top