Two-way quantum and classical machines with small memory for online minimization problems

Kamil Khadiev; Aliya Khadieva

doi:10.1117/12.2522462

15 March 2019 Two-way quantum and classical machines with small memory for online minimization problems

Kamil Khadiev, Aliya Khadieva

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).

Citation Download Citation

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

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available