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 bufer of limited size. The adversary loads data to the bufer, and the algorithm has random access to elements of the bufer. 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 bufer model.
• asking Adversary to load the next block of input variables to the Bufer; • request Bufer for one of the holding variables.
For some integer parameter , after each requests Adversary asks an output variable. If the
size of Bufer is 1 and = 1, then the model is equivalent to the original one.
Motivation. Online algorithms have diferent 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++ [
Quantum model. In the paper, we consider a quantum version of “Request-answer Game
with Bufer” model. Quantum computing itself [
Diferent versions of online quantum algorithms were considered in [
Our results. Here we provide a specific problem and a quantum online algorithm in
“Requestanswer Game with Bufer” 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 [
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.
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.
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 bufer. Assume that we have a bufer between the algorithm and Adversary. Let a positive integer be a size of the bufer. Additionally, there is an integer parameter ≤ . The algorithm will ask to load data to the bufer 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: • The algorithm asks to erase the bufer and load the next input variables ⋅ +1, … , ⋅ + to the bufer. After that, is increased by 1. ( ← + 1) • The algorithm requests any variable from the bufer. We consider a query model (decision tree model) for the algorithm that queries variables from the bufer.
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 bufer 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 bufer is deterministic action.
In the quantum case, an algorithm that requests data from the bufer 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 bufer 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 [
Problem. For some positive integers ,
and , the input is = ( 1, … , , 1, … , ). returns ofline algorithm is variables are not considered.
The cost of an output = ( 1, … , ) is {0, 1} , for
∈ {1, … , }. The input length is = ( + ) ⋅ . A frequency of a string 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} i(s 1,(…), = )#.( )T, hwehienrdeex#( 0) o=f t|h{e m∶o st frequent string 0 is such that ( 0 ) = = , ∈ {1, … , }}| is a number of occurrence of in ( ) and 0 is minimal. We should return index 0 after reading each string . So, the right answer that max ∈{1,…, } ( 1, … , ) where ( + )⋅ = 0 for ∈ {1, … , } and other output ( , ) = 1 + − ∑ ( ( + )⋅ , 0) Here (, ) = 1 if = and (, ) = 0 if ≠
> 0
.
Firstly, we discuss a quantum subroutine that compares two strings of length for some integer 3.1.1. The quantum algorithm for two strings comparing order. It returns: Assume that the subroutine is Compare_strings(, ) and it compares and in lexicographical • −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:
with query complexity √ and error probability that is at most 1 .
2
Lemma 1. [
Let us choose the function ( ) = ( ≠ ). So, we search 0 that is the index of the first unequal symbol of the strings. We search
among indexes 1, … min(| |, | |), where | | is a length of . for strings. If there are no unequal symbols, then we have one of three options: Then, we can claim that precedes in lexicographical order if 0 precedes 0 in the alphabet • if | | < | |, then < ; • if | | > | |, then > ; • if | | = | |, then = . (
13 ).
Assume that this subroutine returns + 1 if it does not find any solution.
We use The_first_one_search( , ) as a subroutine from Lemma 1, where ( ) = ( ≠ ).
We apply the standard technique of boosting success probability that was used, for example,
in [
(| |, | |) 0The_first_one_search( , ) for ∈ {1, … , 3 log2 } do if ≤ and ≠ then ← The_first_one_search( , ) end if
0 ← min( 0, ) end for if 0 = + 1 and | | = | | then end if
end if end if return if (( 0 ≠ + 1) and ( 0 < 0 )) or (( 0 = + 1) and (| | < | |)) then if (( 0 ≠ + 1) and ( 0 > 0 )) or (( 0 = + 1) and (| | > | |)) then Let us discuss the property of the algorithm: ⊳ The initial value ⊳ The strings are equal.
⊳ precedes . ⊳ succeeds .
√ plexity ( min(| |, | |) log ) and error probability ( 13 ).
Lemma 2. Algorithm 1 compares two strings and in lexicographical order with query comProof. The correctness of the algorithm follows from description and lexicographical order. that:
Let us discuss the error probability. The algorithm has error if 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 bufer model
We use the well-known data structure a self-balancing binary search tree. As an
implemensize of the tree.
tation of the data structure, we can use the AVL 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 occurrences of the string among { 1, … , } . We assume that a triple (, , pair ( ′, ′, ′) if 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 , ) = and is a number of ) is less than a { 1, … ,
} with a number of occurrences among ( 1, … , ).
Firstly, we load all strings 1, … , one by one to Bufer 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
Secondly, we load questions (strings) from initially we assume that does not occurs among ( 1, … , ).
1 to one by one to Bufer 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 nothing otherwise. • 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 Bufer 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 • Init(
) initializes an empty tree.
Init( for ∈ {1, … , } do
← }}′′ for ∈ {1, … , } do variable to end for
Add( , , end for for ∈ {1, … , } do
Load_To_Buffer if ≠ = (, , ) ← Find( ,
then ← + 1
← (, , ) if >
then ⊳ Adding the string = to the tree as a vertex ( , , 0) )
⊳ Load to Bufer ⊳ Searching in the tree. ⊳ If belongs to ( 1, … , ) ⊳ Updating the vertex by increasing the number of occurrences.
⊳ Updating the vertex by the new values ⊳ Updating the maximal value. ← + Request( ) ⊳ Requesting -th variable from Bufer and appending the
⊳ The initialization of the tree. ⊳ The maximal number of occurrences. ⊳ The index of most frequent question.
⊳ Initially is an empty string ⊳ Reading the string ⊳ Load to Bufer end if end for if Adversary request an output variable then return Theorem 3. The expected competitive ratio for Algorithm 2 is at most where queries. The total query complexity of the Find procedure is Proof. The correctness of the algorithm follows from the description. Let us discuss the query complexity of Find( , Compare_strings( , ′ .
) , ). Due to Lemma 2, each comparing operation requires ( log )
The procedure requires (log ) comparing operations √ ( (log ) ⋅ (log )). So, the algorithm checks all 1, … , in (
(log ) ⋅ (log ))rounds and after that returns right answers for the requests of Adversary. Therefore, the first “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 √ (log )⋅(log ) ( ) = ( is at most 1 + ( (log √)⋅(log ) .
)
1 ⋅ log for some constant .
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 − Hence, the total error probability is at most
lim →∞ (1 − 13 ) ⋅ log 1/ ( 4. Lower bounds for classical algorithms for The Most Frequent
output with the cost at least ( ).
There is an input such that any classical (deterministic or randomized) algorithm returns √ ( ) > in a case of (log2 ) ⋅ (log2 ) = ( ).
Theorem 4. Any randomized algorithm for the problem has competitive ratio at least = two cases for other string: 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 • case 1: 1, … , = 1 ;
′ ∈ {1, … , − 1, + 1, … , }, ′ = 1 for ′ ∈ {1, … , }⧵{ }.
• case 2: there are ∈ {1, … , } and ∈ {1, … , } such that = 0 and ′ = 1 for all 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 [
In a case of odd , we assign
= 1 /20 /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 such that obtains a wrong answer. ( ) queries to bufer when it reads 1, … , . Then, Adversary can construct the input for finding the most frequent question that uses
In the case of (log2 ) ⋅ (log2 ) = ( ) we have
√ Therefore, all “significant” output variables will be wrong and ( , ( )) = 1 + . The competitive ratio in that case is =
+ 1. output variables should be returned before getting a right answer. Therefore, If the algorithm do ( ) queries to Bufer for computing answer, then ( ) “significant” ( , ( )) = 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.
cussions and support.
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[1] D. Komm, An Introduction to Online Computation: Determinism, Randomization, Advice, [2] D. D. Sleator, R. E. Tarjan, Amortized eficiency of list update and paging rules, Communications of the ACM 28 (1985) 202–208. 1996. [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, [5] Oracle, Java Platform SE 8 documentation, 2021. URL: https://docs.oracle.com/javase/8/ univ. press, 2010.
Conf. of Math. 2018, volume 4, 2018, pp. 3283–3304. [8] A. Ambainis, Understanding quantum algorithms via query complexity, in: Proc. Int.