Fast Classical and Quantum Algorithms for Online k-server Problem on Trees ? ?? Ruslan Kapralov1 , Kamil Khadiev1,2 , Joshua Mokut1 , Yixin Shen3 , and Maxim Yagafarov1 1 Kazan Federal University, Kazan, Russia 2 Zavoisky Physical-Technical Institute, FRC Kazan Scientific Center of RAS, Kazan, Russia 3 Université de Paris, CNRS, IRIF, F-75006 Paris, France Abstract. 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 imple- mentation of their algorithm has time complexity O(n) to process each request, where n is the number of nodes. We propose a new time-efficient implementation of this algorithm thathas O(n log n) time complexity for preprocessing and O k2 + k · log n time for processing a request. 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 2√ is needed, and the time complexity for each request is O(k n log n). √ When the number of requests is o k2n , 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 el- ement 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 query √ complexity O( m). In the particular case of one-sided errors on the in- √ put, it has expected query complexity O( x) where x is the position of the first marked element. Compared with previous work, our algorithm can handle errors in the input oracle. Keywords: online algorithms· k-server problem on trees · quantum computing · binary search. ? Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) ?? This work on Quantum algorithm for k-server problem was supported by Russian Science Foundation Grant 19-19-00656. The research in Section 4 is funded by the subsidy allocated to Kazan Federal University for the state assignment in the sphere of scientific activities, project No. 0671-2020-0065; supported by the Kazan Federal University Strategic Academic Leadership Program. The research is also supported in part by the ERA-NET Cofund in Quantum Technologies project QuantAlgo and the French ANR Blanc project RDAM. 1 Introduction Online optimization is a field of optimization theory that deals with optimization problems having no knowledge of the future [27]. An online algorithm reads an input piece by piece and returns an answer piece by piece immediately, even if the answer can depend on future pieces of the input. The goal is to return an answer that minimizes an objective function (the cost of the output). The most standard method to define the effectiveness of an online algorithm is the competitive ratio [20]. The competitive ratio is the approximation ratio achieved by the algorithm. That is the worst-case ratio between the cost of the solution found by the algorithm and the cost of an optimal solution. If the ratio is c, then the online algorithm is called c-competitive. In the general setting, online algorithms have unlimited computational power. Nevertheless, many papers consider them with different restrictions. Some of them are restrictions on memory [6, 9, 24, 2, 5, 18, 23, 21, 26, 25, 22], others are restrictions on time complexity [15, 31]. In this paper, we focus on efficient online algorithms in terms of time com- plexity. We consider the k-server problem on trees. Chrobak and Larmore [11] proposed a k-competitive algorithm for this problem where the competitive ratio k is the best possible for deterministic algorithms for this problem. The existing implementation of their algorithm has O(n) time complexity for each request, where n is the number of nodes in the tree. For general graphs, there exists a time-efficient algorithm for the k-server problem [31] that uses min-cost-max- flow algorithms. However, in the special case of a tree, this algorithm is not optimal. We propose a new time-efficient implementation of the algorithm from [11]. It has O (n log n) time complexity for preprocessing and O k 2 + k log n for processing a request. It is based on fast algorithms for computing Lowest Common Ancestor (LCA) [7] and the binary lifting technique [8]. We also revisit the problem of finding the first marked element in√a collection of m objects. It is well-known that it can be solved in expected O( √m) queries when given quantum oracle access to the input, and expected O( x) queires where x is the position of the first √ marked element [13],[29, Theorem 10] and [28, Theorem 6]. We give a O( m) queries algorithm that works even in the presence √ of two-sided bounded errors in the input. We also provide an expected O( x) queries algorithm in the case where the input has one-sided errors only. Note that contrary to the previous results, we assume that the oracle can have errors whereas [13, 29, 28] assume that the oracle is perfect. We then consider the k-server problem in the case where the description of the tree is given by string paths. The string path of a node in a rooted tree is a sequence of length h, where h is the height of the node, describing the path from the root to the node. Such a way of representing the trees is useful, for example, as a path to a file in file systems. Assuming oracle access to the length of the string path of each node and to each element on the string path with √time complexity O(1), we obtain a quantum algorithm for this problem with O(k 2 n log(n)) running time to process each request and without preprocessing. This algorithm is based on our improved quantum search algorithm. When the 2 √  number of requests is o k2n , the total runtime of our quantum algorithm is smaller than the classical one. The structure of the paper is the following. Section 2 contains preliminaries. The classical algorithm is described in Section 3. Section 4 contains our improved quantum search algorithm. The quantum algorithm for the k-server problem is described in Section 5. 2 Preliminaries 2.1 Online algorithms An online minimization problem consists of a set I of inputs and a cost func- tion. Each input I = (x1 , . . . , xn ) is a sequence of requests, where n is the length of the input |I| = n. Furthermore, a set of feasible outputs (or solutions) O(I) e is associated with each I; an output is a sequence of answers O = (y1 , . . . , yn ). The cost function assigns a positive real value cost(I, O) to I ∈ I and O ∈ O(I). e An optimal solution for I ∈ I is Oopt (I) = arg minO∈O(I) e cost(I, O). Let us define an online algorithm for this problem. A deterministic online algorithm A computes the output sequence A(I) = (y1 , . . . , yn ) such that yi is computed based on x1 , . . . , xi . We say that A is c-competitive if there exists a constant α ≥ 0 such that, for every n and for any input I of size n, we have: cost(I, A(I)) ≤ c · cost(I, OOpt (I)) + α. The minimal c that satisfies the previous condition is called the competitive ratio of A. 2.2 Rooted Trees Consider a rooted tree G = (V, E), where V is the set of nodes/vertices, and E is the set of edges. Let n = |V | be the number of nodes, or equivalently the size of the tree. We denote by 1 the root of the tree. A path P is a sequence of nodes (v1 , . . . , vh ) that are connected by edges, i.e. (vi , vi+1 ) ∈ E for all i ∈ {1, . . . , h − 1}, such that there are no duplicates among v1 , . . . , vh . Here h is a length of the path. Between any two nodes v and u on the tree, there is a unique path. The distance dist(v, u) is the length of this path. For each node v we can define a parent node Parent(v) which is the first node on the unique path from v to root 1. We have dist (1, Parent(v))+1 = dist(1, v). Additionally, we can define the set of children Children(v) = {u : Parent(u) = v}. Any node y on the unique path from root 1 to node v is an ancestor of node v. Lowest Common Ancestor (LCA). Given two nodes u and v of a rooted tree, the Lowest Common Ancestor is the node w such that w is an ancestor of both u and v, and w is the closest one to u and v among all such ancestors. The following result is well-known. Lemma 1 ([7]). There is an algorithm for the LCA problem with the following properties: (i) The time complexity of the preprocessing step is O(n); (ii)The time complexity of computing LCA for two vertices is O(1). 3 We call LCA Preprocessing() the subroutine that does the preprocessing for the algorithm and LCA(u, v) that computes the LCA of two nodes u and v. Binary Lifting Technique. This technique from [8] allows us to obtain a vertex v 0 that is at distance z from a vertex v with O(log n) time complexity. There are two procedures: • BL Preprocessing() prepares the required data structures. The time complexity is O(n log n). • MoveUp(v, z) returns a vertex v 0 on the path from v to the root and at distance dist(v 0 , v) = z. The time complexity is O(log n). The technique is well documented in the literature. We present an implemen- tation in the arxiv version [19] for completeness. 2.3 k-server Problem on Trees Let G = (V, E) be a rooted tree, and we are given k servers that can move among nodes of G. At each time slot, a request q ∈ V appears. We have to “serve” this request, that is, to choose one of the k servers and move it to q. The other servers are also allowed to move. The cost function is the distance by which we move the servers. In other words, if before the request, the servers are at positions v1 , . . . , vk and after the request they are at v10 , . . . , vk0 , then q ∈ {v10 , . . . , vk0 } and Pk the cost of the move is i=1 dist(vi , vi0 ). The cost of a sequence of requests is the sum of the costs of serving each requests. The problem is to design a strategy that minimizes the cost of servicing a sequence of requests given online. 2.4 Quantum query model We use the standard form of the quantum query model. Let f : D → {0, 1}, D ⊆ {0, 1}m be an m variable function. We wish to compute on an input x ∈ D. We are given an oracle access to the input x, i.e. it is realized by a specific unitary transformation usually defined as |ii |zi |wi → |ii |z + xi (mod 2)i |wi where the |ii register indicates the index of the variable we are querying, |zi is the output register, and |wi is some auxiliary work-space. An algorithm in the query model consists of alternating applications of arbitrary unitaries independent of the input and the query unitary, and a measurement in the end. The smallest number of queries for an algorithm that outputs f (x) with probability ≥ 32 on all x is called the quantum query complexity of the function f and is denoted by Q(f ). We refer the readers to [30, 3, 1] for more details on quantum computing. Definition 1 (Search problem). Suppose we have a set of objects named {1, 2, . . . , m}, of which some are targets. Suppose O is an oracle that identi- fies the targets. The goal of a search problem is to find a target i ∈ {1, 2, . . . , m} by making queries to the oracle O. In search problems, one will try to minimize the number of queries to the oracle. In the classical setting, one needs O(m) queries to solve such a problem. Grover, on the other hand, constructed a quantum algorithm that solves the 4 √ search problem with only O( m) queries [16], provided that there is a unique target. When the number of targets is unknown, Brassard et pal. designed a modi- fied Grover algorithm that solves the search problem with O( m/λ) queries [10], where λ is the number of targets, which is of the same order as the query com- plexity of the Grover search. 3 A Fast Online Algorithm for k-server Problem on Trees with Preprocessing We first describe Chrobak-Larmore’s k-competitive algorithm for k-server prob- lem on trees from [11]. Assume that we have a request on a vertex q, and the servers are on the vertices v1 , . . . , vk . We say that a server i is active if there are no other servers on the path from vi to q. In each phase, we move every active server one step towards the vertex q. After each phase, the set of active servers can change. We repeat this phase (moving of the active servers) until one of the servers reaches the queried vertex q. The naive implementation of this algorithm has time complexity O(n) for each request. First, we run a depth-first search with time labels [12], whose result allows us to check in constant time whether a vertex u is an ancestor of a vertex v. Recall that time labels record the first timestamp f (v) when the depth-first search enters a node v, and the last timestamp `(v) when the depth- first search finishes processing the last child of node v; the timestamp increases every time a new node is visited. A node u is then an ancestor of v if and only if the interval [f (v), `(v)] is contained in [f (u), `(u)]. After that, we can move each active server towards the queried vertex, step by step. Together all active servers cannot visit more than O(n) vertices. In the following, we present an effective implementation of Chrobak-Larmore’s algorithm with preprocessing. The preprocessing part is done once and has O(n log n) time complexity (Theorem 1). The request processing part is done for each request and has O k 2 + k · log n time complexity (Theorem 2). 3.1 Preprocessing We do the following steps for the preprocessing : 1. We do required preprocessing for LCA algorithm (Section 2.2) 2. We do required preprocessing for Binary lifting technique (Section 2.2) 3. Additionally, for each vertex v we compute the distance from the root to v, i.e. dist(1, v). This can be done using a depth-first search algorithm [12]. We store all the distances in an array. See the arxiv version [19] for an implementation of ComputeDistance(u). Theorem 1. The preprocessing has time complexity O(n log n). Proof. The time complexity of the preprocessing phase is O(n) for LCA, O(n log n) for the binary lifting technique and O(n) for ComputeDistance(1). Therefore, the total time complexity is O(n log n). 5 Algorithm 1 Preprocessing. The preprocessing procedure. LCA Preprocessing() BL Preprocessing() dist(1, 1) ← 0 ComputeDistance(1) 3.2 Request Processing Assume that we have a request on a vertex q, and the servers are on the vertices v1 , . . . , vk . We do the following steps, implemented in Algorithms 2 and 4. Step 1. We sort all the servers by their distance to the node q. The distance dist(v, q) between a node v and the node q can be computed in the following way. Let l = LCA(v, q) be the lowest common ancestor of v and q, then dist(v, q) = dist(1, q) + dist(1, v) − 2 · dist(1, l). Using the prepocessing, this quantity can be computed in constant time. We denote by Sort(q, v1 , . . . , vk ) this sorting procedure. In the following steps we assume that dist(vi , q) ≤ dist(vi+1 , q) for i ∈ {1, . . . , k − 1}. Step 2. The first server on v1 processes the request. We move it to the node q. Step 3. For i ∈ {2, . . . k} we consider the server on vi . It will be inactive when some other server with a smaller index arrives on the path between vi and q. Section 3.3 contains the different cases that can happen and how to compute the distance d traveled by vi before it becomes inactive. We then move the i-th server d steps towards the request q. The new position of the i-th server is vi0 . Algorithm 2 Request(q). Request processing procedure. Sort(q, v1 , . . . , vk ) v10 ← q for i ∈ {2, . . . , k} do d ← DistanceToInactive(q, i) . see Algorithm 3 vi0 ← Move(vi , d) . see Algorithm 4 3.3 Distance to Inactive State When processing a request, all servers except one will eventually become inactive. The crucial part of the optimization is to compute when a server becomes inactive quickly. For the purpose of computing this time, we claim that we can pretend that servers “never go inactive”. Formally, let q be a request, i be a server, and j another server with smaller index. We know that i will become inactive because it is not the closest to the target. However it is possible that this particular server j is not the one that will render i inactive. Nevertheless, we can pretend that j will never become inactive and compute the distance i will travel before going inactive because of j, call this distance dqi,j (the index i is fixed in this reasoning). We claim the following: Lemma 2. For any request q and server i > 1 ( i.e. a server that will become inactive), the distance Diq travelled by i before it becomes inactive is equal to minj dist(l, v) then z ← z − dist(l, v) Result ← MoveUp(q, dist(l, q) − z) return Result 8 Lemma 4. The time complexity of Move is O (log n). Proof. The time complexity of MoveUp is O(log n) using the binary lifting technique from Section 2.2 and LCA is in O(1) by Section 2.2. Furthermore, we can compute the distance between any two nodes in O(1) thanks to the preprocessing. Therefore, the total complexity is O(log n).  Theorem 2. The time complexity of the request processing phase is O k 2 + k log n . Proof. The complexity of sorting the servers by distance is O(k log k). For each server, we compute the distance traveled before being inactive in O(1) by Lemma 3. We then move each server by that distance in time O(log n) by Lemma 4. There- fore, the complexity of processing one server is O(k + log n), and there are k servers. 4 Binary Search for a Function with Errors Consider a search space S = {1, . . . , m} and a subset M ⊆ S of marked elements. Define the indicator function gM : S 2 → {0, 1} by gM (`, r) = 1 if {`, . . . , r} ∩ M 6= ∅, and 0 otherwise. In other words, gM (`, r) indicates whether there is a marked element from M in the interval [`, r]. Now assume that we do not know M but have access to a two-sided probabilistic approximation g̃ of gM . Formally, there is a probability p < 1/2 such that for any `, r ∈ S, g̃(`, r) = gM (`, r) with probability at least 1 − p and 1 − gM (`, r) otherwise. Intuitively, g̃ behaves like gM with probability at least 1 − p. However, sometimes it makes mistakes and returns a completely wrong answer. Note that g̃ has two-sided error: it can return 0 even if the interval [`, r] contains a marked element, but more importantly, it can also return 1 even though the interval does not contain any marked element. We further assume that a call to g̃(`, r) takes time T (r − `) where T is some nondecreasing function. Typically, we assume that T (m) = o(m), i.e. T is strictly better than a linear search. We now consider the problem of finding the first marked element in S, with probability at least, say, 1/2. A trivial algorithm is to perform a linear search in O(m) until g̃ returns 1. If g̃ had no errors, we could perform a binary search in O(T (m)). This does not work very well in the presence of errors because decisions made are irreversible, and errors accumulate quickly. Our observation is that if we modify the binary search to boost the success probability of certain calls to g̃, we can still solve the problem in time in O (T (m)). 4.1 Algorithm The idea is inspired by [4] and very similar to [14] except that the calls to g̃ (the “comparisons”) do not necessarily have unit cost. The difference with [14] is apparent in the complexity since we can avoid the extra log factor when the cost of each comparison becomes high enough. For reasons that become clear in the proof, we need to boost some calls’ success probability. We do so by repeating 9 Algorithm 5 Binary search for a function with two-sided errors ` ← 1, r ← m + 1 . search interval d←1 . depth of the search while ` < r do mid ← b(` + r)/2c vl ← g̃(`, mid) . repeat d times and take the majority if vl = 0 then ` ← mid + 1 else r ← mid d←d+1 them several times and taking the majority: by this we mean that we take the most common answer, and return an error in the case of a tie. Proposition 1. Assume that T satisfies T (m/k) = O(T (m)/k α ) for some α > 0 and every m and k, then with probability more than 0.5, Algorithm 5 returns the position of the first marked element, or m + 1 if none exists. The running time is O(T (m)). Proof. The correctness of the algorithm, when there are no errors, is clear. We need to argue about the complexity and error probability. At the uth iteration of the loop, the algorithm considers a segment [`, r] of length at most m ·2−(u−1) . The complexity of g̃(`, mid) is at most O(T (r − `)) = O T (m · 2−(u−1) ) but we repeat it 2u times, so the total complexity of the uth iteration is O uT m · 2−(u−1) . The number of iterations is at most log2 m.  Hence, the total complexity is     log2 m log2 m ∞ ! X   X X −(u−1)  −αu  −αu O  uT m · 2 =O  T (m) 2 u = O T (m) 2 u u=1 u=1 u=1 α   2 = O T (m) = O (T (m)) . (2α − 1)2 Finally, we need to analyze the success probability of the algorithm: at the uth iteration, the algorithm will run each test 2u times and each test has a constant probability of failure p. Hence for the algorithm to fail at iteration u, at least half of  the 2u runs must fail: this happens with probability at most 2u u 2ue u u u u p 6 u p 6 (2ep) , where e = exp(1). Hence, the probability that the log 2m P∞ 2ep (2ep)u 6 u=1 (2ep)u 6 1−2ep P algorithm fails is bounded by . By taking p u=1 small enough (say 2ep < 13 ), which is always possible by repeating the calls to g̃ a constant number of times to boost the probability, we can ensure that the algorithm fails less than half of the time. Remark 1. The condition T (m/k) = O(T (m)/k α ) for some α > 0 and every m and k is clearly satisfied by any function of the form T (m) = mα logβ m logγ log m. 10 4.2 Application to Quantum Search A particularly useful application of the previous section is for quantum search, particularly √ when g̃ is a Grover-like search. Indeed, Grover’s search can decide in O( m) queries if a marked element exists in an array of size m, with a constant probability of error. More precisely, assume that we have a function f : {1, . . . m} → {0, 1} and the task is to find the minimal x ∈ {1, . . . , m} such that f (x) =√1. If we let g̃(`, r) = GROVER(`, r, f ) then g̃ has query complexity T (m) = m and fails with constant probability. Hence, we can apply Proposition 1 and obtain an √ al- gorithm to find the first marked element with query complexity T (m) = O( m) and constant probability of error. In fact, note that we are not making use of Proposition 1 to its full strength because g̃ really has one-sided error: it will never return 1 if there are no marked element. We will make use of this observation later. Proposition 2. There is a quantum √ algorithm that finds the first marked ele- ment in an array of size m in O( m) queries and error probability < 0.5. As observed above, we are not really using Proposition 1 to its full strength because Grover’s search has one-sided error. This suggests that there is room for improvement. Suppose that we now only have access to a two-sided probabilistic approximation f˜ of f . In other words, f can now make mistakes: it can return 1 for an unmarked element or 0 for a marked element with some small probability. Formally, f˜(x) = f (x) with probability at least 1 − p and 1 − f (x) otherwise, for some probability p < 1/2. We cannot apply Grover’s search directly in this case, but some variants have been developed that can handle bounded errors [17]. Using this result, we can build a two-sided √ error function g̃ with high probability of success and time complexity O( m). Applying Proposition 1 again, we obtain the following improvement: Proposition 3. There exists a quantum algorithm √ FindFirst that finds the first marked element in an array of size m in O( m) queries and error prob- ability less than 0.5; even when the oracle access to the array has a two-sided error. In quantum computing, f rarely has two-sided errors. For instance, Grover’s search has a one-sided error only. If we assume that f˜ has one-sided error only, we can obtain a slightly better version of Proposition 3. Formally, we assume that f˜(x) = f (x) with probability at least 1 − p and 0 otherwise. Proposition 4. There exists a quantum algorithm √ that finds the first marked element in an array of size m in expected O( x) queries and with error proba- √ bility less than 0.5, where x is the position of the first marked element, or O( m) queries if none is marked. Furthermore, it works even when the oracle access to the array √ has one-sided error. Additionally, it has a worst-case query complexity of O( m) in all cases. 11 Proof. Let FindFirst denote the algorithm from Proposition 3 and GroverTwoSided denote the variant of Grover’s algorithm of [17] that works with two-sided error oracles. Recall that we assume that f˜ has one-sided error, i.e. it may return 0 instead of 1 with small probability but not the other way around. Consider the following algorithm: Algorithm 6 FindFirstAdvanced(m, f ). Find the first marked element in an array. r←1 . size of the search space while r ≤ n and GroverTwoSided(1, r, f˜) = 0 do r ← min(m, 2r) return FindFirst(r, f˜) We now show that this algorithm satisfies the requirements of Proposition 4. To simplify the proof, we assume that the array always contains a marked ele- ment; this is without loss of generality because we can add an extra object at the end that is always marked. Furthermore, we assume that n is a power 2, this is again without loss of generality because we can add dummy object at the end at the cost of doubling the array size at most. Recall that f˜ has a one-sided error, and the same applies to GroverTwoSided in this case. Therefore the test GroverTwoSided(1, r, f˜) = 0 can only fail if there actually is a marked element in the interval [1, r]. Of course, the problem is that it can succeed even though there is a marked element in this interval. Let p be the probability that this happens (i.e. GroverTwoSided fails), we know that this is < 1/2 by [17, Theorem 10]. Let x be the position of the first marked element and let `x be such that 2`x 6 x < 2`x +1 . Let R be the value of r after the loop, it is a random variable and always a power of 2. By the above reasoning, it is always the case that R > x. Furthermore, for any `x 6 ` < log2 n, the prob- ` `−`x ability √ that R = 2 is at most p (1 − p). The call to FindFirst takes time O( R) by Proposition 3. Hence, the expected time complexity of this algorithm is log Xn ∞ ! ! √ √ X √ `−`x ` O p (1 − p) 2` = O 2`x p 2` `=`x `=0 √  1 =O 2`x √ 1− 2p √  =O x where we assume that p is small enough. This is always possible by repeating the calls to FindFirst a constant number of times to reduce the failure probability p. Finally, we note that the only way this algorithm can fail is if the (unique) call to FindFirst fails and this only happen with constant probability. 12 5 A Fast Quantum Implementation of Online Algorithm for k-server Problem on Trees We consider a special way of storing a rooted tree. Assume that for each vertex v we have access to a sequence av = (av1 , . . . , avd ) for d = dist(1, v) + 1. Here av is a path from the root (the vertex 1) to the vertex v, av1 = 1, avd = v. Such a way of describing a tree is not uncommon, for example when the tree represents a file system. A file path “c:\Users\MyUser\newdoc.txt” is exactly such a path in the file system tree. Here “c”, “Users”, “MyUser” are ancestors of “newdoc.txt”, “c” is the root and “newdoc.txt” is the node itself. We assume that we have access to the following two oracles in time O(1): (i) given a vertex u, a (classical) oracle that returns the length of the string path au ; (ii) given a vertex u and an index i, a quantum oracle that returns the ith vertex aui of the sequence au . We can solve the k-server problem on trees using the same algorithm as in Section 3 with the following modifications: (i) The function LCA(u, v) becomes LCP(au , av ) where LCP(au , av ) is a longest common prefix of two sequences au and av . (ii) MoveUp(v, z) is the vertex avd−z where av is the sequence for v and d = |av |; (iii) We can compute dist(u, v) if u is the ancestor of v: it is d0 − d00 , where d0 is a length of au and d00 is a length of av . Note that the invocations of dist in Algorithms 4 and 2 are always this form. The only exception is dist(u, v) in Sort in which the function uses LCA as a subroutine. The complexity of Sort is thus the same as the complexity of LCA or LCP in our case. By doing so, we do not need any preprocessing. We now replace the LCP(au , av ) function by a quantum subroutine QLCP(au , av ), presented √ in Section 5.1, and keep everything else as is. This subroutine runs in time O( n log n) with O n13 error probability. This allows us to obtain the following result. Theorem √ 3. There is a quantum algorithm that processes a request in time O k 2 n log n with probability of error O n1 . It does not require any prepro- cessing. Proof. The complexity Move is the complexity of LCA that is QLCP in our implementation, √ plus the complexity of MoveUp. The former has complexity is O( n log n) by Lemma 5, and √ the latter O(1) by the oracle. Therefore, the total running time of Move is O( n log n). The complexity of Request is O(k 2 ) times the cost of LCA that is QLCP in our implementation, and then a call to Move. Additionally, the Sort func- tion invokes √ LCA to compute distances. Hence, the complexity √  of Sort is O (k log k · n · log n), and the total complexity is O k 2 n · log n . We invoke, QLCP at most 4k 2 times so the success probability is at least 4k2 4n2 1 − n13 ≥ 1 − n13 ≥ 1 − Ω n1 for enough big n. Therefore, the error  probability is O n1 . Note that we do not need any preprocessing. 13 5.1 Quantum Algorithm for Longest Common Prefix of Two Sequences Let us consider the Longest Common Prefix (LCP) problem. Given two se- quences (q1 , . . . , qd ) and (b1 , . . . , bs ), the problem is to find t such that q1 = b1 , . . . , qt = bt and qi 6= bi for t + 1 ≤ i ≤ m, where m = min(d, s). Consider a function f : {1, . . . , m} → {0, 1} such that f (i) = 1 iff qi 6= bi . Assume that x is the minimal argument such that f (x) = 1, then t = x − 1. The LCP problem is equivalent to finding the first marked element. It can be solved as follows. Algorithm 7 QLCP(q, b). Quantum algorithm for the longest common prefix. m ← min(d, s) x ← FindFirst(m, f ) . Repeat 3 log m times and take the majority vote if x = N U LL then x←m+1 return x − 1 Lemma √ 5. Algorithm 7 finds the LCP of two sequences of length m in time O( m log m) and with probability of error O m13 .  Proof. The correctness of the √algorithm follows from the definition of f . The complexity √ of FindFirst is O( m) by Proposition 2. The total running time is O( m log m) because of the repetitions. References 1. Ablayev, F., Ablayev, M., Huang, J.Z., Khadiev, K., Salikhova, N., Wu, D.: On quantum methods for machine learning problems part i: Quantum tools. Big Data Mining and Analytics 3(1), 41–55 (2019) 2. Ablayev, F., Ablayev, M., Khadiev, K., Vasiliev, A.: Classical and quantum com- putations with restricted memory. LNCS 11011, 129–155 (2018) 3. Ambainis, A.: Understanding quantum algorithms via query complexity. In: Proc. Int. Conf. of Math. 2018. vol. 4, pp. 3283–3304 (2018) 4. Ambainis, A., Balodis, K., Iraids, J., Khadiev, K., Klevickis, V., Prusis, K., Shen, Y., Smotrovs, J., Vihrovs, J.: Quantum lower and upper bounds for 2d-grid and Dyck language. In: Proceedings of MFCS 2020. LIPIcs, vol. 170, pp. 8:1–8:14 (2020) 5. Baliga, G.R., Shende, A.M.: On space bounded server algorithms. In: Proceedings of ICCI’93. pp. 77–81. IEEE (1993) 6. Becchetti, L., Koutsoupias, E.: Competitive analysis of aggregate max in windowed streaming. In: ICALP. LNCS, vol. 5555, pp. 156–170 (2009) 7. Bender, M.A., Farach-Colton, M.: The lca problem revisited. In: Latin American Symposium on Theoretical Informatics. pp. 88–94. Springer (2000) 8. Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theoret- ical Computer Science 321(1), 5–12 (2004) 9. Boyar, J., Larsen, K.S., Maiti, A.: The frequent items problem in online stream- ing under various performance measures. International Journal of Foundations of Computer Science 26(4), 413–439 (2015) 14 10. Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik 46(4-5), 493–505 (1998) 11. Chrobak, M., Larmore, L.L.: An optimal on-line algorithm for k servers on trees. SIAM Journal on Computing 20(1), 144–148 (1991) 12. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. McGraw-Hill (2001) 13. Dürr, C., Høyer, P.: A quantum algorithm for finding the minimum. arXiv:quant- ph/9607014 (1996) 14. Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM Journal on Computing 23(5), 1001–1018 (1994) 15. Flammini, M., Navarra, A., Nicosia, G.: Efficient offline algorithms for the bicriteria k-server problem and online applications. Journal of Discrete Algorithms 4(3), 414– 432 (2006) 16. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Pro- ceedings of STOC96. pp. 212–219. ACM (1996) 17. Høyer, P., Mosca, M., de Wolf, R.: Quantum search on bounded-error inputs. In: Automata, Languages and Programming (2003) 18. Hughes, S.: A new bound for space bounded server algorithms. In: Proceedings of the 33rd annual on Southeast regional conference. pp. 165–169 (1995) 19. Kapralov, R., Khadiev, K., Mokut, J., Shen, Y., Yagafarov, M.: Fast classical and quantum algorithms for online k-server problem on trees. arXiv preprint arXiv:2008.00270 (2021) 20. Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. In: FOCS, 1986., 27th Annual Symposium on. pp. 244–254. IEEE (1986) 21. Khadiev, K.: Quantum request-answer game with buffer model for online algo- rithms. application for the most frequent keyword problem. In: CEUR Workshop Proceedings. vol. 2850, pp. 16–27 (2021) 22. Khadiev, K., Khadieva, A.: Two-way quantum and classical machines with small memory for online minimization problems. In: International Conference on Micro- and Nano-Electronics 2018. Proc. SPIE, vol. 11022, p. 110222T (2019) 23. Khadiev, K., Khadieva, A.: Quantum online streaming algorithms with logarithmic memory. International Journal of Theoretical Physics 60, 608–616 (2021) 24. Khadiev, K., Khadieva, A., Mannapov, I.: Quantum online algorithms with respect to space and advice complexity. Lobachevskii J. of Math. 39(9), 1210–1220 (2018) 25. Khadiev, K., Khadieva, A.: Two-way quantum and classical automata with advice for online minimization problems. In: Reversibility in Programming, Languages, and Automata (RPLA 2019) procceedings. LNCS, Springer (2020) 26. Khadiev, K., Lin, D.: Quantum online algorithms for a model of the request-answer game with a buffer. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko- Matematicheskie Nauki 162(3), 367–382 (2020) 27. Komm, D.: An Introduction to Online Computation: Determinism, Randomiza- tion, Advice. Springer (2016) 28. Kothari, R.: An optimal quantum algorithm for the oracle identification problem. In: Proceedings of STACS 2014. p. 482 (2014) 29. Lin, C.Y.Y., Lin, H.H.: Upper bounds on quantum query complexity inspired by the elitzur-vaidman bomb tester. In: Proceedings of CCC 2015 (2015) 30. Nielsen, M.A., Chuang, I.L.: Quantum computation and quantum information. Cambridge univ. press (2010) 31. Rudec, T., Baumgartner, A., Manger, R.: A fast work function algorithm for solving the k-server problem. Cent Eur J Oper Res 21(1), 187–205 (2013) 15