论文标题
带有缓冲模型用于在线算法的量子请求答案游戏
Quantum Request-Answer Game with Buffer Model for Online Algorithms
论文作者
论文摘要
我们将在线算法视为请求 - 答案游戏。生成输入请求的对手和在线算法答案。我们考虑了游戏的广义版本，该版本的尺寸有限。对手将数据加载到缓冲区，并且该算法随机访问缓冲区的元素。我们考虑模型的量子和经典（确定性或随机）算法。 在本文中，我们提供了一个特定的问题（最常见的关键字问题）和一种量子算法，其在竞争比率方面比任何经典（确定性或随机）算法都更好。同时，对于问题，标准模型中的经典在线算法等同于带有缓冲区模型的请求 - 答案游戏中的经典算法。
We consider online algorithms as a request-answer game. An adversary that generates input requests, and an online algorithm answers. We consider a generalized version of the game that has a buffer of limited size. The adversary loads data to the buffer, and the algorithm has random access to elements of the buffer. We consider quantum and classical (deterministic or randomized) algorithms for the model. In the paper, we provide a specific problem (The Most Frequent Keyword Problem) and a quantum algorithm that works better than any classical (deterministic or randomized) algorithm in terms of competitive ratio. At the same time, for the problem, classical online algorithms in the standard model are equivalent to the classical algorithms in the request-answer game with buffer model.
