Share Email Print

Proceedings Paper • new

Two-way quantum and classical machines with small memory for online minimization problems
Author(s): Kamil Khadiev; Aliya Khadieva
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

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

Paper Details

Date Published: 15 March 2019
PDF: 9 pages
Proc. SPIE 11022, International Conference on Micro- and Nano-Electronics 2018, 110222T (15 March 2019); doi: 10.1117/12.2522462
Show Author Affiliations
Kamil Khadiev, Smart Quantum Technologies Ltd. (Russian Federation)
Kazan Federal Univ. (Russian Federation)
Aliya Khadieva, Kazan Federal Univ. (Russian Federation)
Univ. of Latvia (Latvia)

Published in SPIE Proceedings Vol. 11022:
International Conference on Micro- and Nano-Electronics 2018
Vladimir F. Lukichev; Konstantin V. Rudenko, Editor(s)

© SPIE. Terms of Use
Back to Top