Quantum request-answer game with buffer model for online algorithms. Application for The Most Frequent Keyword Problem Kamil Khadiev Kazan Federal University, 18 Kremlyovskaya str, Kazan, Tatarstan, 420008, Russia Abstract 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 al- gorithm that works better than any classical (deterministic or randomized) algorithm in terms of com- petitive 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. Keywords quantum computation, online algorithm, request-answer game, online minimization problem, buffer, keywords search 1. Introduction One of the applications for online algorithms is optimization problems [1]. The peculiarity is the following. An algorithm reads an input piece by piece and returns an answer piece by piece immediately, even if an answer can depend on future pieces of the input. The algorithm should return an answer for minimizing an objective function (the cost of an output). The most standard method to define the effectiveness is the competitive ratio [2, 3]. One of the possible point of view to online algorithms is a request-answer game [4]. Here we consider a game of an online algorithm and Adversary that holds input. Adversary requests and the algorithm returns answers. We suggest a reversed version of the game. The algorithm asks an input variable and Adversary returns an answer, but as a price for the answer, Adversary asks to return an output variable. The new version of the game is equivalent to the original one, but we can generalize it. We provide the new model for online algorithms that is called “Request-answer Game with Buffer”. The model is a game of three players that are an online algorithm, Adversary and Buffer of limited size. The algorithm can do a request of one of two QuaInT 2021: Workshop on the Quantum Information Technologies, April 11, 2021, Zhytomyr, Ukraine doors 2021: Edge Computing Workshop, April 11, 2021, Zhytomyr, Ukraine " kamilhadi@gmail.com (K. Khadiev) ~ https://kpfu.ru/Kamil.Hadiev?p_lang=2 (K. Khadiev)  0000-0002-5151-9908 (K. Khadiev) © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) types: • asking Adversary to load the next block of input variables to the Buffer; • request Buffer for one of the holding variables. For some integer parameter 𝑅, after each 𝑅 requests Adversary asks an output variable. If the size of Buffer is 1 and 𝑅 = 1, then the model is equivalent to the original one. Motivation. Online algorithms have different applications. One of them is making a decision in current time with no knowledge about future data. Another one is processing a data stream and output a result data stream in online fashion, for example, streaming video on web sites and others. Many programming languages like Java, C++ [5, 6] and others use buffered data streams that store data in a fast buffer first, and then an algorithm reads data from the buffer. So, our model is like usage of buffered data streams. Additionally, we have asynchronous processing with online output. In other words, we focus on online behavior of the output stream, but when an algorithm reads an input stream, it can skip some data. Quantum model. In the paper, we consider a quantum version of “Request-answer Game with Buffer” model. Quantum computing itself [7, 8, 9] is one of the hot topics in computer science. There are many problems where quantum algorithms outperform the best known clas- sical algorithms [10, 11, 12, 13, 14]. Superior of quantum over classical was shown for different computational models like query model, streaming processing models, communication models and others [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]. Different versions of online quantum algorithms were considered in [21, 20] including quan- tum streaming algorithms as online algorithms [29, 30], quantum online algorithms with re- stricted memory [31, 32], quantum online algorithms with repeated test [33]. In these papers, authors show examples of problems that have quantum online algorithms with better compet- itive ratio comparing to classical online algorithms. Our results. Here we provide a specific problem and a quantum online algorithm in “Request- answer Game with Buffer” model for it. We show that the quantum online algorithm has better competitive ratio than any classical (deterministic or randomized) counterpart. The problem is “The Most Frequent Keyword Problem”. Questions are strings of length 𝑘; the problem is searching the most frequent keyword among words of a text and returning it after each word of the text immediately. The problem [34] is one of the most well-studied ones in the area of data streams [35, 36, 37]. Many applications in packet routing, telecommunication logging, and tracking keyword queries in search machines are critically based upon such routines. The similar problem in online fashion was considered in [38]. The paper is organized in the following way. Definitions are in Section 2. A description of the most frequent question problem and the quantum algorithm for the problem are described in Section 3. Section 4 contains lower bounds for classical algorithms. 17 2. Preliminaries An online minimization problem consists of a set  of inputs and a cost function. Each input 𝐼 = (𝑥1 , … , 𝑥𝑛 ) is a sequence of requests, where 𝑛 is a length of the input |𝐼 | = 𝑛. Furthermore, a set of feasible outputs (or solutions) (𝐼 ) is associated with each 𝐼 ; an output is a sequence of answers 𝑂 = (𝑦1 , … , 𝑦𝑛 ). The cost function assigns a positive real value 𝑐𝑜𝑠𝑡(𝐼 , 𝑂) to 𝐼 ∈  and 𝑂 ∈ (𝐼 ). An optimal solution for 𝐼 ∈  is 𝑂𝑜𝑝𝑡 (𝐼 ) = 𝑎𝑟𝑔𝑚𝑖𝑛𝑂∈(𝐼 ) 𝑐𝑜𝑠𝑡(𝐼 , 𝑂). Let us define an online algorithm for this problem. A deterministic online algorithm 𝐴 computes the output sequence 𝐴(𝐼 ) = (𝑦1 , … , 𝑦𝑛 ) such that 𝑦𝑖 is computed by 𝑥1 , … , 𝑥𝑖 . We say that 𝐴 is 𝑐-competitive if there exists a constant 𝛼 ≥ 0 such that, for every 𝑛 and for any input 𝐼 of size 𝑛, we have: 𝑐𝑜𝑠𝑡(𝐼 , 𝐴(𝐼 )) ≤ 𝑐 ⋅ 𝑐𝑜𝑠𝑡(𝐼 , 𝑂𝑂𝑝𝑡 (𝐼 )) + 𝛼, where 𝑐 is the minimal number that satisfies the inequality. Also we call 𝑐 the competitive ratio of 𝐴. If 𝛼 = 0, 𝑐 = 1, then 𝐴 is optimal. A randomized online algorithm 𝑅 computes an output sequence 𝑅 𝜓 (𝐼 ) = (𝑦1 , … , 𝑦𝑛 ) such that 𝑦𝑖 is computed from 𝜓 , 𝑥1 , … , 𝑥𝑖 , where 𝜓 is the content of the random tape, i. e., an infinite binary sequence, where every bit is chosen uniformly at random and independently of all the others. By 𝑐𝑜𝑠𝑡(𝐼 , 𝑅 𝜓 (𝐼 )) we denote the random variable expressing the cost of the solution computed by 𝑅 on 𝐼 . 𝑅 is 𝑐-competitive in expectation if there exists a constant 𝛼 > 0 such that, for every 𝐼 , 𝔼 [𝑐𝑜𝑠𝑡(𝐼 , 𝑅 𝜓 (𝐼 ))] ≤ 𝑐 ⋅ 𝑐𝑜𝑠𝑡(𝐼 , 𝑂𝑂𝑝𝑡 (𝐼 )) + 𝛼. We can say that 𝑐 is expected competitive ratio for the algorithm. 2.1. Request-answer game with buffer model The standard model for online algorithms can be considered as a request-answer game [4]. Adversary holds an input, it sends request 𝑥𝑖 to an algorithm, and the algorithm sends answer 𝑦𝑖 . Here Adversary is an “active” player that rules the game and the algorithm is a “passive” player that answers on each response. Let us change the point of view to this game. Both are “active” players in some sense. Round 1. The algorithm asks an input variable 𝑥1 . (The algorithm is active on this round). Round 2. Adversary asks an output variable 𝑦1 . (Adversary is active on this round). ... Round 2𝑖 − 1. The algorithm asks an input variable 𝑥𝑖 . (The algorithm is active on this round). Round 2𝑖. Adversary asks an output variable 𝑦𝑖 . (Adversary is active on this round). It is easy to see that the new game is equivalent to the original game and the standard model. Let us consider the modification of the game that has a buffer. Assume that we have a buffer between the algorithm and Adversary. Let a positive integer 𝐾 be a size of the buffer. Additionally, there is an integer parameter 𝑅 ≤ 𝐾 . The algorithm will ask to load data to the buffer by blocks of 𝐾 variables. Let 𝑖 be a number of the loading block. The algorithm can do the following actions if it is active on some round: 18 • The algorithm asks to erase the buffer and load the next 𝐾 input variables 𝑥𝑖⋅𝐾 +1 , … , 𝑥𝑖⋅𝐾 +𝐾 to the buffer. After that, 𝑖 is increased by 1. (𝑖 ← 𝑖 + 1) • The algorithm requests any variable from the buffer. We consider a query model (decision tree model) for the algorithm that queries variables from the buffer. The game has the following scenario: Round 0. We initialize 𝑖 ← 0 Round 1. The algorithm is active and it does the possible actions that were described before. Round 2. The algorithm is active and it does the possible actions that were described before. ... Round 𝑅. The algorithm is active and it does the possible actions that were described before. Round 𝑅 + 1. Adversary is active. He asks output variables 𝑦1 , … , 𝑦𝑅 . ... Round (𝑅 + 1) ⋅ 𝑗 + 1. The algorithm is active and it does the possible actions that were described before. Round (𝑅 + 1) ⋅ 𝑗 + 2. The algorithm is active and it does the possible actions that were described before. ... Round (𝑅 + 1) ⋅ 𝑗 + 𝑅. The algorithm is active and it does the possible actions that were described before. Round (𝑅 + 1) ⋅ 𝑗 + 𝑅 + 1. Adversary is active. He asks output variables 𝑦𝑗⋅𝑅+1 , … , 𝑦𝑗⋅𝑅+𝑅 . Comment. In the case of 𝐾 = 1 and 𝑅 = 1, the new model is equivalent to the standard online algorithms model. In the randomized case, an algorithm that requests data from the buffer can be randomized, and we use a randomized query model in that case. We consider an expected competitive ratio for the model as for the standard model of randomized online algorithms. At the same time, the loading the next block to the buffer is deterministic action. In the quantum case, an algorithm that requests data from the buffer can be quantum, and we use a quantum query model in that case. Because of the probabilistic behavior of quantum algorithms, we also consider an expected competitive ratio for the model. At the same time, the loading the next block to the buffer is deterministic action. We skip details of the quantum model and quantum algorithms here because we use them as quantum subroutines and the rest part is classical. More details on quantum query model and quantum algorithms can be found in [7, 8, 9] 19 3. A quantum algorithm for The Most Frequent Keyword Problem Let us present the problem formally. Problem. For some positive integers 𝑚, 𝑑 and 𝑘, the input is 𝐼 = (𝑠 1 , … , 𝑠 𝑑 , 𝑥 1 , … , 𝑥 𝑚 ). Here (𝑠 1 , … , 𝑠 𝑑 ) is a sequence of strings that are interesting keywords for us in the input, 𝑠 𝑗 = (𝑠1𝑗 , … , 𝑠𝑘𝑗 ) ∈ {0, 1}𝑘 , for 𝑗 ∈ {1, … , 𝑑}. Strings 𝑥 1 , … , 𝑥 𝑚 are words of a text, 𝑥 𝑗 = (𝑥1𝑗 , … , 𝑥𝑘𝑗 ) ∈ {0, 1}𝑘 , for 𝑗 ∈ {1, … , 𝑚}. The input length is 𝑛 = (𝑚 + 𝑑) ⋅ 𝑘. A frequency of a string 𝑡 ∈ {0, 1}𝑘 is 𝑓 (𝑡) = #(𝑡) 𝑖 𝑚 , where #(𝑡) = |{𝑖 ∶ 𝑡 = 𝑥 , 𝑖 ∈ {1, … , 𝑚}}| is a number of occurrence of 𝑡 in (𝑥 , … , 𝑥 ). The index 𝑖0 of the most frequent string 𝑠 𝑖0 is such that 𝑓 (𝑠 𝑖0 ) = max 𝑓 (𝑠 𝑖 ) and 1 𝑚 𝑖∈{1,…,𝑑} 𝑖0 is minimal. We should return index 𝑖0 after reading each string 𝑥 𝑗 . So, the right answer that returns offline algorithm is (𝑧1 , … , 𝑧𝑛 ) where 𝑧(𝑗+𝑑)⋅𝑘 = 𝑖0 for 𝑗 ∈ {1, … , 𝑚} and other output variables are not considered. The cost of an output 𝑂 = (𝑦1 , … , 𝑦𝑛 ) is 𝑚 𝑐𝑜𝑠𝑡(𝐼 , 𝑂) = 1 + 𝑚 − ∑ 𝛿(𝑦(𝑗+𝑑)⋅𝑙 , 𝑖0 ) 𝑗=1 Here 𝛿(𝑎, 𝑏) = 1 if 𝑎 = 𝑏 and 𝛿(𝑎, 𝑏) = 0 if 𝑎 ≠ 𝑏 3.1. Quantum algorithm Firstly, we discuss a quantum subroutine that compares two strings of length 𝑙 for some integer 𝑙 > 0. 3.1.1. The quantum algorithm for two strings comparing Assume that the subroutine is Compare_strings(𝑠, 𝑡) and it compares 𝑠 and 𝑡 in lexicographical order. It returns: • −1 if 𝑠 < 𝑡; • 0 if 𝑠 = 𝑡; • 1 if 𝑠 > 𝑡. As a base for our algorithm, we will use the algorithm of finding the minimal argument with 1-result of a Boolean-value function. Formally, we have: Lemma 1. [39] Suppose, we have a function 𝑓 ∶ {1, … , 𝑁 } → {0, 1} for some integer 𝑁 . There is a quantum algorithm√for finding 𝑗0 = min{𝑗 ∈ {1, … , 𝑁 } ∶ 𝑓 (𝑗) = 1}. The algorithm finds 𝑗0 with query complexity 𝑁 and error probability that is at most 12 . 20 Let us choose the function 𝑓 (𝑗) = (𝑠𝑗 ≠ 𝑡𝑗 ). So, we search 𝑗0 that is the index of the first unequal symbol of the strings. We search 𝑗0 among indexes 1, … min(|𝑠|, |𝑡|), where |𝑠| is a length of 𝑠. Then, we can claim that 𝑠 precedes 𝑡 in lexicographical order iff 𝑠𝑗0 precedes 𝑡𝑗0 in the alphabet for strings. If there are no unequal symbols, then we have one of three options: • if |𝑠| < |𝑡|, then 𝑠 < 𝑡; • if |𝑠| > |𝑡|, then 𝑠 > 𝑡; • if |𝑠| = |𝑡|, then 𝑠 = 𝑡. We use The_first_one_search(𝑓 , 𝑁 ) as a subroutine from Lemma 1, where 𝑓 (𝑗) = (𝑠𝑗 ≠ 𝑡𝑗 ). Assume that this subroutine returns 𝑁 + 1 if it does not find any solution. We apply the standard technique of boosting success probability that was used, for example, in [12]. So, we repeat the algorithm 3 log2 𝑚 times and return the minimal answer, where 𝑚 is 1 a number of strings in the sequence (𝑥 1 , … 𝑥 𝑚 ). In that case, the error probability is 𝑂 ( 23 log 𝑚) = 𝑂 ( 𝑚13 ). Let us present the algorithm. Algorithm 1 Compare_strings(𝑠, 𝑡, 𝑘). The quantum algorithm for two strings comparing. 𝑁 ← 𝑚𝑖𝑛(|𝑠|, |𝑡|) 𝑗0 The_first_one_search(𝑓 , 𝑁 ) ⊳ The initial value for 𝑖 ∈ {1, … , 3 log2 𝑚} do 𝑗 ← The_first_one_search(𝑓 , 𝑁 ) if 𝑗 ≤ 𝑘 and 𝑠𝑗 ≠ 𝑠𝑡 then 𝑗0 ← min(𝑗0 , 𝑗) end if end for if 𝑗0 = 𝑁 + 1 and |𝑠| = |𝑡| then 𝑟𝑒𝑠𝑢𝑙𝑡 ← 0 ⊳ The strings are equal. end if if ((𝑗0 ≠ 𝑁 + 1) and (𝑠𝑗0 < 𝑡𝑗0 )) or ((𝑗0 = 𝑁 + 1) and (|𝑠| < |𝑡|)) then 𝑟𝑒𝑠𝑢𝑙𝑡 ← −1 ⊳ 𝑠 precedes 𝑡. end if if ((𝑗0 ≠ 𝑁 + 1) and (𝑠𝑗0 > 𝑡𝑗0 )) or ((𝑗0 = 𝑁 + 1) and (|𝑠| > |𝑡|)) then 𝑟𝑒𝑠𝑢𝑙𝑡 ← 1 ⊳ 𝑡 succeeds 𝑠. end if return 𝑟𝑒𝑠𝑢𝑙𝑡 Let us discuss the property of the algorithm: Lemma 2.√ Algorithm 1 compares two strings 𝑠 and 𝑡 in lexicographical order with query com- plexity 𝑂( min(|𝑠|, |𝑡|) log 𝑚) and error probability 𝑂 ( 𝑚13 ). Proof. The correctness of the algorithm follows from description and lexicographical order. 21 Let us discuss the error probability. The algorithm has error iff there are error in all 3 log2 𝑚 invocations of The_first_one_search algorithm. The probability of such event is at most 0.53 log2 𝑚 = 𝑂 ( 𝑚13 ). □ 3.1.2. A quantum algorithm in request-answer game with buffer model Firstly, we present an idea of the algorithm. We use the well-known data structure a self-balancing binary search tree. As an implemen- tation of the data structure, we can use the AVL tree [40, 41] or the Red-Black tree [42, 41]. Both data structures allow us to find and add elements in 𝑂(log 𝑁 ) running time, where 𝑁 is a size of the tree. The idea of the algorithm is the following. We store a triple (𝑖, 𝑠, 𝑐) in a vertex of the tree, where 𝑖 is the minimal index of a string from {𝑠 1 , … , 𝑠 𝑑 } such that 𝑠 = 𝑠 𝑖 and 𝑐 is a number of occurrences of the string 𝑠 among {𝑥 1 , … , 𝑥 𝑚 }. We assume that a triple (𝑖, 𝑠, 𝑐) is less than a pair (𝑖 ′ , 𝑠 ′ , 𝑐 ′ ) iff 𝑠 precedes 𝑠 ′ in the lexicographical order. So, we use Compare_strings(𝑠, 𝑠 ′ , 𝑘) subroutine as the comparator of the vertexes. The tree represents a set of unique strings from {𝑠 1 , … , 𝑠 𝑑 } with a number of occurrences among (𝑥 1 , … , 𝑥 𝑚 ). Firstly, we load all strings 𝑠 1 , … , 𝑠 𝑑 one by one to Buffer and add a vertex 𝑣 = (𝑗, 𝑠 𝑗 , 0) for each string 𝑠 𝑗 to the tree, here 𝑗 ∈ {1, … , 𝑑}. We add only one node for each duplicate strings from 𝑠 1 , … , 𝑠 𝑑 if they exist. The index 𝑗 in 𝑣 stores the index of 𝑠 𝑗 and if there is no a vertex that corresponds to 𝑠 𝑗 , then 𝑗 is a minimal index from all possible indexes. 0 in 𝑣 means that initially we assume that 𝑠 𝑗 does not occurs among (𝑥 1 , … , 𝑥 𝑚 ). Secondly, we load questions (strings) from 𝑥 1 to 𝑥 𝑚 one by one to Buffer and search them in our tree. We increase the number of occurrences. If the string was not found in the tree, then it is not a keyword, i.e. it does not belong to 𝑠 1 , … 𝑠 𝑑 and we skip it. At the same time, we store (𝑖𝑚𝑎𝑥 , 𝑠, 𝑐𝑚𝑎𝑥 ) = 𝑎𝑟𝑔𝑚𝑎𝑥(𝑖,𝑡,𝑐) in the tree 𝑐 and recalculate it in each step. When Adversary requests an output variable, then we return 𝑖𝑚𝑎𝑥 . Let us present the algorithm formally. Let 𝐵𝑆𝑇 be a self-balancing binary search tree such that: • Find(𝐵𝑆𝑇 , 𝑥 𝑖 ) finds a vertex (𝑗, 𝑠, 𝑐) such that 𝑠 = 𝑥 𝑖 , or 𝑁 𝑈 𝐿𝐿 if 𝑥 𝑖 was not found. The standard algorithm for searching 𝑥 𝑖 in the tree is comparing with elements of vertexes and moving by the tree according to the result of the comparison. When we invoke the Compare_strings subroutine, we request a variable from Buffer for checking a symbol of 𝑥 𝑖 and request to memory when we check a symbol of a string that is stored in a vertex. • Add(𝐵𝑆𝑇 , 𝑗, 𝑠 𝑗 ) adds a vertex (𝑗, 𝑠 𝑗 , 0) to the tree if a vertex with 𝑠 𝑗 does not exist; and does nothing otherwise. • Init(𝐵𝑆𝑇 ) initializes an empty tree. Let us discuss the property of the algorithm. 22 Algorithm 2 A quantum algorithm for The Most Frequent Keyword Problem. Init(𝐵𝑆𝑇 ) ⊳ The initialization of the tree. 𝑐𝑚𝑎𝑥 ← 1 ⊳ The maximal number of occurrences. 𝑖𝑚𝑎𝑥 ← 1 ⊳ The index of most frequent question. 𝑠𝑡𝑒𝑝 ← 0 for 𝑗 ∈ {1, … , 𝑑} do Load_To_Buffer ⊳ Load 𝑠 𝑗 to Buffer 𝑡 ← }} ′′ ⊳ Initially 𝑡 is an empty string for 𝑞 ∈ {1, … , 𝑘} do ⊳ Reading the string 𝑡 𝑡 ← 𝑡 + Request(𝑞) ⊳ Requesting 𝑞-th variable from Buffer and appending the variable to 𝑡 end for Add(𝐵𝑆𝑇 , 𝑗, 𝑡) ⊳ Adding the string 𝑡 = 𝑠 𝑗 to the tree as a vertex (𝑁 𝑈 𝐿𝐿, 𝑡, 0) end for for 𝑗 ∈ {1, … , 𝑚} do Load_To_Buffer ⊳ Load 𝑥 𝑖 to Buffer 𝑣 = (𝑖, 𝑡, 𝑐) ← Find(𝐵𝑆𝑇 , 𝑥 𝑗 ) ⊳ Searching 𝑥 𝑖 in the tree. if 𝑣 ≠ 𝑁 𝑈 𝐿𝐿 then ⊳ If 𝑥 𝑖 belongs to (𝑠 1 , … , 𝑠 𝑑 ) 𝑐 ←𝑐+1 ⊳ Updating the vertex by increasing the number of occurrences. 𝑣 ← (𝑖, 𝑡, 𝑐) ⊳ Updating the vertex by the new values if 𝑐 > 𝑐𝑚𝑎𝑥 then ⊳ Updating the maximal value. 𝑐𝑚𝑎𝑥 ← 𝑐 𝑖𝑚𝑎𝑥 ← 𝑖 end if end if end for if Adversary request an output variable then return 𝑖𝑚𝑎𝑥 end if Theorem 3. The expected competitive ratio 𝑐 for Algorithm 2 is at most 𝑄 where (𝑚 log 𝑚) ⋅ (log 𝑑) 𝑄 = 𝑂 1 + √ . ( 𝑘 ) Proof. The correctness of the algorithm follows from the description. Let us discuss the query complexity of Find(𝐵𝑆𝑇 , 𝑥 𝑗 ). The procedure requires 𝑂(log 𝑑) comparing operations √ ′ Compare_strings(𝑥 𝑗 , 𝑠 𝑖 , 𝑘). Due to Lemma 2, each comparing operation √ requires 𝑂( 𝑘 log 𝑚) queries. The total query complexity of the Find procedure is 𝑂 ( 𝑘(log 𝑚) ⋅ (log 𝑑)). So, the al- √ gorithm checks all 𝑥 1 , … , 𝑥 𝑚 in𝑂 (𝑚 𝑘(log 𝑚) ⋅ (log 𝑑)) rounds and after that returns right an- √ swers for the requests of Adversary. Therefore, the first 𝑂 ( 𝑚 𝑘(log𝑘𝑚)⋅(log 𝑑) ) = 𝑂 ( 𝑚(log 𝑚)⋅(log √ 𝑘 𝑑) ) “significant” output variables can be wrong and others are right. We call output variable 𝑦(𝑗+𝑑)⋅𝑘 , for 𝑗 ∈ {1, … , 𝑚}, as “significant” because the cost depends on these variables. Hence, the cost is at most 1 + 𝑂 ( 𝑚(log 𝑚)⋅(log √ 𝑘 𝑑) ). 23 Let us discuss the error probability. Events of error in the algorithm are independent. So, all events should be correct. Due to Lemma 2, the probability of correctness of one event is 1 − (1 − 𝑚13 ). Hence, the probability of correctness of all 𝑂(𝑚 log 𝑚) events is at least 1 − 1 𝛾 ⋅𝑚 log 𝑚 (1 − 𝑚 3 ) for some constant 𝛾 . Note that 1 𝛾 ⋅𝑚 log 𝑚 (1 − 𝑚3 ) lim < 1; 𝑛→∞ 1/𝑚 Hence, the total error probability is at most 𝑂 ( 𝑚1 ). In a case of an error, all “significant” output variables can be wrong. Therefore, the expected competitive ratio of the algorithm is at most 𝑚(log 𝑚)⋅(log 𝑑) 𝑂( 𝑚−1 𝑚 ) ⋅ (1 + 𝑂 ( √ 𝑘 1 )) + 𝑂 (𝑚 ⋅ 𝑚 ) 𝑚(log 𝑚) ⋅ (log 𝑑) 𝑄 = =𝑂 1+ √ . 1 ( 𝑘 ) □ 4. Lower bounds for classical algorithms for The Most Frequent Keyword Problem There is an input 𝐼𝐵 such that any classical (deterministic or randomized) algorithm returns output with the cost at least 𝑂(𝑚). Theorem 4. Any randomized algorithm for √ the problem has competitive ratio 𝑐 at least 𝑅 = 𝑂(𝑚) > 𝑄 in a case of (log2 𝑚) ⋅ (log2 𝑑) = 𝑜( 𝑘). Proof. Let us show that the problem is equivalent to unstructured search problem. Assume that 𝑚 = 2𝑡 for some integer 𝑡. Then, let 𝑥 𝑡+1 , … , 𝑥 2𝑡 = 0𝑘 where 0𝑘 is a string of 𝑘 zeros. We have two cases for other string: • case 1: 𝑥 1 , … , 𝑥 𝑡 = 1𝑘 ; • case 2: there are 𝑧 ∈ {1, … , 𝑡} and 𝑢 ∈ {1, … , 𝑘} such that 𝑥𝑢𝑧 = 0 and 𝑥𝑢𝑧′ = 1 for all ′ 𝑢 ′ ∈ {1, … , 𝑢 − 1, 𝑢 + 1, … , 𝑘}, 𝑥 𝑧 = 1𝑘 for 𝑧 ′ ∈ {1, … , 𝑡}⧵{𝑧}. Let 𝑑 = 2, 𝑠 1 = 0𝑘 and 𝑠 2 = 1𝑘 . In the first case, the answer is 1𝑘 . In the second case, the answer is 0𝑘 . Therefore, the problem is equivalent to search 0 among the first 𝑡𝑘 = 𝑚𝑘/2 variables. Due to [43], the randomized query complexity of unstructed search among 𝑚𝑘/2 is Ω(𝑚𝑘). In a case of odd 𝑚, we assign 𝑥 𝑚 = 1𝑘/2 0𝑘/2 , and it is not used in the search. Then, we can consider only 𝑚 − 1 strings. So, 𝑚 − 1 is even. Suppose, we have a randomized algorithm 𝐴 for finding the most frequent question that uses 𝑜(𝑚𝑘) queries to buffer when it reads 𝑥 1 , … , 𝑥 𝑚 . Then, Adversary can construct the input 𝐼𝐵 such that 𝐴 obtains a wrong answer. 24 Therefore, all “significant” output variables will be wrong and 𝑐𝑜𝑠𝑡(𝐼𝐵 , 𝐴(𝐼𝐵 )) = 1 + 𝑚. The competitive ratio in that case is 𝑅 = 𝑚 + 1. If the algorithm do 𝑂(𝑚𝑘) queries to Buffer for computing answer, then 𝑂(𝑚) “significant” output variables should be returned before getting a right answer. Therefore, 𝑐𝑜𝑠𝑡(𝐼𝐵 , 𝐴(𝐼𝐵 )) = 𝑂(𝑚) and 𝑅 = 𝑂(𝑚). √ In the case of (log2 𝑚) ⋅ (log2 𝑑) = 𝑜( 𝑘) we have 𝑚(log2 𝑚) ⋅ (log2 𝑑) 𝑄 = 𝑂 1 + √ = 𝑜(𝑚) < 𝑂(𝑚) = 𝑅 . ( 𝑘 ) □ 5. Conclusion We consider a new setting or new model for online algorithms √ that is useful for real world problems. We show that in the case of (log2 𝑚) ⋅ (log2 𝑑) = 𝑜( 𝑘) the quantum algorithm shows a better competitive ratio than any classical (deterministic or randomized) algorithm. Note that this setting is reasonable. Acknowledgments The research was funded by the subsidy allocated to Kazan Federal University for the state assignment in the sphere of scientific activities, project No. 0671-2020-0065. We thank Farid Ablayev and Aliya Khadieva from Kazan Federal University for helpful dis- cussions and support. References [1] D. Komm, An Introduction to Online Computation: Determinism, Randomization, Advice, Springer, 2016. [2] D. D. Sleator, R. E. Tarjan, Amortized efficiency of list update and paging rules, Commu- nications of the ACM 28 (1985) 202–208. [3] A. R. Karlin, M. S. Manasse, L. Rudolph, D. D. Sleator, Competitive snoopy caching, in: FOCS, 1986., 27th Annual Symposium on, IEEE, 1986, pp. 244–254. [4] S. Albers, BRICS, Mini-Course on Competitive Online Algorithms, Aarhus University, 1996. [5] Oracle, Java Platform SE 8 documentation, 2021. URL: https://docs.oracle.com/javase/8/ docs/api/java/io/BufferedReader.html. [6] S. B. Lippman, J. Lajoie, C++ Primer, third ed., Massachusetts: Addison-Wesley, 1998. [7] M. A. Nielsen, I. L. Chuang, Quantum computation and quantum information, Cambridge univ. press, 2010. [8] A. Ambainis, Understanding quantum algorithms via query complexity, in: Proc. Int. Conf. of Math. 2018, volume 4, 2018, pp. 3283–3304. 25 [9] F. Ablayev, M. Ablayev, J. Z. Huang, K. Khadiev, N. Salikhova, D. Wu, On quantum meth- ods for machine learning problems part i: Quantum tools, Big Data Mining and Analytics 3 (2019) 41–55. [10] R. de Wolf, Quantum computing and communication complexity, Ph.D. thesis, 2001. [11] S. Jordan, Quantum algorithms zoo, 2021. URL: http://quantumalgorithmzoo.org/. [12] K. Khadiev, L. Safina, Quantum algorithm for dynamic programming approach for dags. applications for zhegalkin polynomial evaluation and some problems on dags, in: Pro- ceedings of UCNC 2019, volume 4362 of LNCS, 2019, pp. 150–163. [13] K. Khadiev, D. Kravchenko, D. Serov, On the quantum and classical complexity of solving subtraction games, in: Proceedings of CSR 2019, volume 11532 of LNCS, 2019, pp. 228–236. [14] K. Khadiev, I. Mannapov, L. Safina, The quantum version of classification decision tree constructing algorithm c5. 0, CEUR Workshop Proceedings 2500 (2019). [15] A. Ambainis, N. Nahimovs, Improved constructions of quantum automata, Theoretical Computer Science 410 (2009) 1916–1922. [16] F. Ablayev, A. Vasiliev, On quantum realisation of boolean functions by the fingerprinting technique, Discrete Mathematics and Applications 19 (2009) 555–572. [17] F. Ablayev, A. Gainutdinova, K. Khadiev, A. Yakaryılmaz, Very narrow quantum OBDDs and width hierarchies for classical OBDDs, in: DCFS, volume 8614 of LNCS, Springer, 2014, pp. 53–64. [18] F. Ablayev, A. Gainutdinova, K. Khadiev, A. Yakaryılmaz, Very narrow quantum OBDDs and width hierarchies for classical OBDDs, Lobachevskii Journal of Mathematics 37 (2016) 670–682. [19] F. Ablayev, A. Ambainis, K. Khadiev, A. Khadieva, Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test, In SOFSEM 2018, LNCS 10706 (2018) 197–211. [20] F. Ablayev, M. Ablayev, K. Khadiev, A. Vasiliev, Classical and quantum computations with restricted memory, LNCS 11011 (2018) 129–155. [21] K. Khadiev, A. Khadieva, I. Mannapov, Quantum online algorithms with respect to space and advice complexity, Lobachevskii Journal of Mathematics 39 (2018) 1210–1220. [22] K. Khadiev, A. Khadieva, Reordering method and hierarchies for quantum and classical ordered binary decision diagrams, in: CSR 2017, volume 10304 of LNCS, Springer, 2017, pp. 162–175. [23] R. Ibrahimov, K. Khadiev, K. Prūsis, A. Yakaryılmaz, Error-free affine, unitary, and prob- abilistic OBDDs, Lecture Notes in Computer Science 10952 LNCS (2018) 175–187. [24] F. Le Gall, Exponential separation of quantum and classical online space complexity, Theory of Computing Systems 45 (2009) 188–202. [25] K. Khadiev, A. Ilikaev, Quantum algorithms for the most frequently string search, in- tersection of two string sequences and sorting of strings problems, in: International Conference on Theory and Practice of Natural Computing, 2019, pp. 234–245. [26] D. Kravchenko, K. Khadiev, D. Serov, R. Kapralov, Quantum-over-classical advantage in solving multiplayer games, Lecture Notes in Computer Science 12448 (2020) 83–98. [27] A. Glos, N. Nahimovs, K. Balakirev, K. Khadiev, Upperbounds on the probability of finding marked connected components using quantum walks, Quantum Information Processing 20 (2021) 1–23. 26 [28] A. Ambainis, K. Balodis, J. Iraids, K. Khadiev, V. Kl, evickis, K. Prūsis, Y. Shen, J. Smotrovs, J. Vihrovs, Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language, in: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), 2020, pp. 8:1– 8:14. [29] K. Khadiev, A. Khadieva, D. Kravchenko, A. Rivosh, R. Yamilov, I. Mannapov, Quan- tum versus classical online streaming algorithms with logarithmic size of memory, Lobachevskii Journal of Mathematics (2019). (in print). arXiv:1710.09595. [30] K. Khadiev, A. Khadieva, Quantum online streaming algorithms with logarith- mic memory, International Journal of Theoretical Physics (2019). doi:10.1007/ s10773-019-04209-1. [31] K. Khadiev, A. Khadieva, Two-way quantum and classical machines with small mem- ory for online minimization problems, in: International Conference on Micro- and Nano-Electronics 2018, volume 11022 of Proc. SPIE, 2019, p. 110222T. doi:10.1117/12. 2522462. [32] K. Khadiev, A. Khadieva, Two-way quantum and classical automata with advice for online minimization problems, in: Formal Methods. FM 2019 International Workshops, 2020, pp. 428–442. [33] Q. Yuan, Quantum online algorithms, Ph.D. thesis, University of California, Santa Barbara, 2009. [34] G. Cormode, M. Hadjieleftheriou, Finding frequent items in data streams, Proceedings of the VLDB Endowment 1 (2008) 1530–1541. [35] S. Muthukrishnan, Data streams: Algorithms and applications, Foundations and Trends in Theoretical Computer Science 1 (2005) 117–236. [36] C. C. Aggarwal, Data streams: models and algorithms, volume 31, Springer Science & Business Media, 2007. [37] L. Becchetti, I. Chatzigiannakis, Y. Giannakopoulos, Streaming techniques and data ag- gregation in networks of tiny artefacts, Computer Science Review 5 (2011) 27–46. [38] J. Boyar, K. S. Larsen, A. Maiti, The frequent items problem in online streaming under various performance measures, International Journal of Foundations of Computer Science 26 (2015) 413–439. [39] R. Kapralov, K. Khadiev, J. Mokut, Y. Shen, M. Yagafarov, Fast classical and quantum algorithms for online 𝑘-server problem on trees, arXiv preprint arXiv:2008.00270 (2020). [40] G. M. Adel’son-Vel’skii, E. M. Landis, An algorithm for organization of information, in: Doklady Akademii Nauk, volume 146, Russian Academy of Sciences, 1962, pp. 263–266. [41] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, McGraw- Hill, 2001. [42] L. J. Guibas, R. Sedgewick, A dichromatic framework for balanced trees, in: Proceedings of SFCS 1978, IEEE, 1978, pp. 8–21. [43] C. H. Bennett, E. Bernstein, G. Brassard, U. Vazirani, Strengths and weaknesses of quan- tum computing, SIAM journal on Computing 26 (1997) 1510–1523. 27