The @math 'th frequency moment of a sequence of integers is defined as @math , where @math is the number of times that @math occurs in the sequence. Here we study the quantum complexity of approximately computing the frequency moments in two settings. In the query complexity setting, we wish to minimise the number of queries to the input used to approximate @math up to relative error @math . We give quantum algorithms which outperform the best possible classical algorithms up to quadratically. In the multiple-pass streaming setting, we see the elements of the input one at a time, and seek to minimise the amount of storage space, or passes over the data, used to approximate @math . We describe quantum algorithms for @math , @math and @math in this model which outperform the best possible classical algorithms almost quadratically.
( @math , @math ) Alon, Matias and Szegedy gave single-pass streaming algorithms using space @math @cite_35 . An almost-optimal @math algorithm was later given by Indyk and Woodruff for any @math @cite_11 . This was simplified by , who also improved the dependence on @math @cite_22 . Very recently, gave an @math algorithm for @math and @math @cite_18 . This effectively matches the tightest known general space lower bound on @math -pass streaming algorithms, @math shown by Woodruff and Zhang @cite_32 .
@cite_35 @cite_18 @cite_22 @cite_32 @cite_11
2064379477 2075567379 2950318219 2069414131
The frequency moments of a sequence containing mi elements of type i, for 1 i n, are the numbers Fk = P n=1 m k . We consider the space complexity of randomized algorithms that approximate the numbers Fk, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F0;F1 and F2 can be approximated in logarithmic space, whereas the approximation of Fk for k 6 requires n (1) space. Applications to data bases are mentioned as well. The problem of estimating the kth frequency moment F k over a data stream by looking at the items exactly once as they arrive was posed in [1, 2]. A succession of algorithms have been proposed for this problem [1, 2, 6, 8, 7]. Recently, Indyk and Woodruff [11] have presented the first algorithm for estimating F k , for k > 2, using space O(n1-2 k), matching the space lower bound (up to poly-logarithmic factors) for this problem [1, 2, 3, 4, 13] (n is the number of distinct items occurring in the stream.) In this paper, we present a simpler 1-pass algorithm for estimating F k. We resolve several fundamental questions in the area of distributed functional monitoring, initiated by Cormode, Muthukrishnan, and Yi (SODA, 2008). In this model there are @math sites each tracking their input and communicating with a central coordinator that continuously maintain an approximate output to a function @math computed over the union of the inputs. The goal is to minimize the communication. We show the randomized communication complexity of estimating the number of distinct elements up to a @math factor is @math , improving the previous @math bound and matching known upper bounds up to a logarithmic factor. For the @math -th frequency moment @math , @math , we improve the previous @math communication bound to @math . We obtain similar improvements for heavy hitters, empirical entropy, and other problems. We also show that we can estimate @math , for any @math , using @math communication. This greatly improves upon the previous @math bound of Cormode, Muthukrishnan, and Yi for general @math , and their @math bound for @math . For @math , our bound resolves their main open question. Our lower bounds are based on new direct sum theorems for approximate majority, and yield significant improvements to problems in the data stream model, improving the bound for estimating @math in @math passes from @math to @math , giving the first bound for estimating @math in @math passes of @math bits of space that does not use the gap-hamming problem. We give a 1-pass O(m1-2⁄k)-space algorithm for computing the k-th frequency moment of a data stream for any real k > 2. Together with the lower bounds of [1, 2, 4], this resolves the main problem left open by in 1996 [1]. Our algorithm also works for streams with deletions and thus gives an O(m 1-2⁄p) space algorithm for the L p difference problem for any p > 2. This essentially matches the known Ω(m1-2⁄p-o(1)) lower bound of [12, 2]. Finally the update time of our algorithms is O(1).