Quantum Online Algorithms with Respect to Space and Advice Complexity
- 作者: Khadiev K.1,2, Khadieva A.2,3, Mannapov I.2
-
隶属关系:
- Smart Quantum Technologies Ltd.
- Kazan (Volga region) Federal University
- Faculty of Computing
- 期: 卷 39, 编号 9 (2018)
- 页面: 1377-1387
- 栏目: 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
如何引用文章
详细
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.
作者简介
K. Khadiev
Smart Quantum Technologies Ltd.; Kazan (Volga region) Federal University
编辑信件的主要联系方式.
Email: kamilhadi@gmail.com
俄罗斯联邦, 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
俄罗斯联邦, Kremlevskaya ul. 18, Kazan, Tatarstan, 420008; Raina bulv. 19, Riga, LV-1586
I. Mannapov
Kazan (Volga region) Federal University
Email: kamilhadi@gmail.com
俄罗斯联邦, Kremlevskaya ul. 18, Kazan, Tatarstan, 420008