  The $k$'th frequency moment of a sequence of integers is defined as $F_k =
\sum_j n_j^k$, where $n_j$ is the number of times that $j$ 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 $F_k$ up to
relative error $\epsilon$. 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 $F_k$. We describe quantum algorithms for $F_0$, $F_2$ and
$F_\infty$ in this model which substantially outperform the best possible
classical algorithms in certain parameter regimes.
