We consider online algorithms with respect to the competitive ratio. In this paper, we explore one-way automata as a model for online algorithms. We focus on quantum and classical online algorithms. For a specially constructed online minimization problem, we provide a quantum log-bounded automaton that is more effective (has less competitive ratio) than classical automata, even with advice, in the case of the logarithmic size of memory. We construct an online version of the well-known Disjointness problem as a problem. It was investigated by many researchers from a communication complexity and query complexity point of view.
We consider online algorithms with respect to the competitive ratio. In this paper, we explore one-way automata as a model for online algorithms. We focus on quantum and classical online algorithms. For a specially constructed online minimization problem, we provide a quantum log-bounded automaton that is more effective (has less competitive ratio) than classical automata, even with advice, in the case of the logarithmic size of memory. We construct an online version of the well-known Disjointness problem as a problem. It was investigated by many researchers from a communication complexity and query complexity point of view.
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in a case of logarithmic or sublogarithmic size of memory, even if classical online algorithms get advice bits. Furthermore, we show that a quantum online algorithm with a constant number of qubits can be better than any deterministic online algorithm with a constant number of advice bits and unlimited computational power.
In this paper, we consider online algorithms. Typically the model is investigated with respect to competitive ratio. We consider algorithms with restricted memory (space) and explore their power. We focus on quantum and classical online algorithms. We show that there are problems that can be better solved by quantum algorithms than classical ones in a case of logarithmic memory. Additionally, we show that quantum algorithm has an advantage, even if deterministic algorithm gets advice bits. We propose Black Hats Method. This method allows us to construct problems that can be effectively solved by quantum algorithms. At the same time, these problems are hard for classical algorithms. The separation between probabilistic and deterministic algorithms can be shown with a similar method.
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.
Online algorithm is a well-known computational model. 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 polylogarithmic space case and show that in this case, quantum online algorithms can be better than deterministic ones as well.
Fast Classical and Quantum Algorithms for Online k-server Problem on Trees
We consider online algorithms for the k-server problem on trees. Chrobak and Larmore proposed a k-competitive algorithm for this problem that has the optimal competitive ratio. However, a naive implementation of their algorithm has O(n) time complexity for processing each query, where n is the number of nodes in the tree. We propose a new time-efficient implementation of this algorithm that has O(nlogn) time complexity for preprocessing and O(k2+k⋅logn) time for processing a query. We also propose a quantum algorithm for the case where the nodes of the tree are presented using string paths. In this case, no preprocessing is needed, and the time complexity for each query is O(k2nlogn). When the number of queries is o(k2lognn), we obtain a quantum speed-up on the total runtime compared to our classical algorithm. We also give a simple quantum algorithm to find the first marked element in a collection of m objects, that works even in the presence of two-sided bounded errors on the input oracle. It has worst-case complexity O(m). In the particular case of one-sided errors on the input, it has expected time complexity O(x) where x is the position of the first marked element. Compare with previous work, our algorithm can handle errors in the input oracle.