=Paper=
{{Paper
|id=Vol-2850/paper1
|storemode=property
|title=Quantum request-answer game with buffer model for online algorithms. Application for The Most Frequent Keyword Problem
|pdfUrl=https://ceur-ws.org/Vol-2850/paper1.pdf
|volume=Vol-2850
|authors=Kamil Khadiev
|dblpUrl=https://dblp.org/rec/conf/doors/Khadiev21
}}
==Quantum request-answer game with buffer model for online algorithms. Application for The Most Frequent Keyword Problem==
https://ceur-ws.org/Vol-2850/paper1.pdf
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