Quantum Online Algorithms with Respect to Space and Advice Complexity
- Authors: Khadiev K.1,2, Khadieva A.2,3, Mannapov I.2
-
Affiliations:
- Smart Quantum Technologies Ltd.
- Kazan (Volga region) Federal University
- Faculty of Computing
- Issue: Vol 39, No 9 (2018)
- Pages: 1377-1387
- Section: Part 2. Special issue “Actual Problems of Algebra and Analysis” Editors: A. M. Elizarov and E. K. Lipachev
- URL: https://journals.rcsi.science/1995-0802/article/view/203375
- DOI: https://doi.org/10.1134/S1995080218090421
- ID: 203375
Cite item
Abstract
Online computation is a well-known area of computer science. We introduce quantum online algorithms and investigate them with respect to a competitive ratio in two points of view: space complexity and advice complexity. We start with exploring a model with restricted memory and show that quantum online algorithms can be better than classical ones (deterministic or randomized) for sublogarithmic space (memory), and they can be better than deterministic online algorithms without restriction for memory. Additionally, we consider the polylogarithmic space case and show that in this case, quantum online algorithms can be better than deterministic ones as well. Another point of view to the online algorithms model is advice complexity. So, we introduce quantum online algorithms with a quantum channel with an adviser. Firstly, we show that quantum algorithms have at least the same computational power as classical ones have. We give some examples of quantum online algorithms with advice. Secondly, we show that if we allow to use shared entangled qubits (EPR-pairs), then a quantum online algorithm can use half as many advise qubits compared to a classical one. We apply this approach to the well-known Paging Problem.
About the authors
K. Khadiev
Smart Quantum Technologies Ltd.; Kazan (Volga region) Federal University
Author for correspondence.
Email: kamilhadi@gmail.com
Russian Federation, ul. K. Marksa 5, Kazan, 420111; Kremlevskaya ul. 18, Kazan, Tatarstan, 420008
A. Khadieva
Kazan (Volga region) Federal University; Faculty of Computing
Email: kamilhadi@gmail.com
Russian Federation, Kremlevskaya ul. 18, Kazan, Tatarstan, 420008; Raina bulv. 19, Riga, LV-1586
I. Mannapov
Kazan (Volga region) Federal University
Email: kamilhadi@gmail.com
Russian Federation, Kremlevskaya ul. 18, Kazan, Tatarstan, 420008