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.
Very recent independent work of @cite_7 has considered a related problem to approximating @math : testing the image size of a function. The quantum algorithm of @cite_7 is based in the setting of property testing, and has subtly different parameters to the algorithm for @math presented here. Given oracle access to a function @math , their algorithm distinguishes between two cases: a) the image of @math is of size at most @math ; b) an @math fraction of the output values of @math need to be changed to reduce its image to size at most @math . The algorithm uses @math quantum queries.
@cite_7
1465613978
In the k-junta testing problem, a tester has to efficiently decide whether a given function f: 0, 1 n → 0, 1 is a k-junta (i.e., depends on at most fc of its input bits) or is e-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity O([EQUATION]) and time complexity O(n[EQUATION]). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1 3) queries for junta-testing (for constant e).