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 ) Alon, Matias and Szegedy gave an @math single-pass streaming algorithm @cite_35 , and also showed an @math lower bound. An @math lower bound for single-pass streaming algorithms was proven by Woodruff @cite_37 , which was similarly extended to an @math lower bound for @math -pass streaming algorithms by Chakrabarti and Regev @cite_39 .
@cite_35 @cite_37 @cite_39
2064379477 2160681854 1985526537
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. We prove that any one-pass streaming algorithm which (e, Δ)-approximates the kth frequency moment F k , for any real k ≠ 1 and any e = Ω(1 √m), must use Ω(1 e²) bits of space, where m is the size of the universe. This is optimal in terms of e, resolves the open questions of Bar- in [3, 4], and extends the Ω(1 e²) lower bound for F 0 in [11] to much smaller e by applying novel techniques. Along the way we lower bound the one-way communication complexity of approximating the Hamming distance and the number of bipartite graphs with minimum maximum degree constraints. We prove an optimal @math lower bound on the randomized communication complexity of the much-studied gap-hamming-distance problem. As a consequence, we obtain essentially optimal multipass space lower bounds in the data stream model for a number of fundamental problems, including the estimation of frequency moments. The gap-hamming-distance problem is a communication problem, wherein Alice and Bob receive @math -bit strings @math and @math , respectively. They are promised that the Hamming distance between @math and @math is either at least @math or at most @math , and their goal is to decide which of these is the case. Since the formal presentation of the problem by Indyk and Woodruff [Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 283--289], it had been conjectured that the naive protocol, which uses @math bits of communication, is asymptotically optimal. The conjecture was shown to be true in several special cases, e.g., when the communication is de...