One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P.
Here and below when I talk about sampling the Fourier transform I mean choosing x according to $|\hat f(x)|^2$. (Normalized if necessary and approximately).
Can we describe the complexity class, that we can call P-FOURIER SAMPLING, of approximate sampling Boolean functions of P? Are there problems which are complete for this class?
Given a class X of Boolean functions what can be said about the the computational complexity, that we can refer to as SAMPLING-X of approximating sampling the Fourier transform of functions in X. (I suppose that if X is BQP then X-SAMPLING is still within the power of quantum computers.)
What are the examples of X where SAMPLING-X is in P? Are there interesting examples where SAMPLING-X is NP-hard?
There are several variants of this problem that can also be interesting. On the Fourier side, rather than approximate-sample we can talk about a decision problem enabled (probabilistically) by approximate sampling. On the primal side, we can start with a class X of probability distributions and ask what is the relation between the ability to approximately sample a distribution D in X and approximately sample the (normalized) Fourier transform.
In short, what is known about this question.
Update: Martin Schwarz pointed out that if all the Fourier coefficients themselves are concentrated only on a polynomial number of entries then it is possible in BPP to approximate these large coefficients (and thus also to approximately sample.) This goes back to Goldreich-Levin, and Kushilevitz-Mansour. Are there interesting classes of functions where there is a probabilistic polynomial algorithm for approximately sampling the Fourier side, where the Fourier coefficients are spread over more than polynomially many coefficients?
Added Later: Let me mention a few concrete problems.
1) How hard is it to approximately sample the Fourier transform of Boolean functions in P.
a) One question that Scott Aaronson mentioned in a comment below is to show that this is not in BPP. Or something weaker along the lines that if this task is in BPP some collapse is happening. (Scot Conjectures that this is the case.)
b) Another question is to show that this task is hard with respect to some quantum-based complexity class. E.g, to show that if you can perform this task you can solve decision problems in BPP assisted with log-depth quantum computers, or something like that.
2) What are classes of Boolean functions such that approximately sampling their Fourler transform is in P. What we know is that this is the case when the Fourier coefficients are concentrated on polynomial many coefficients, but this seems very restricted.
3) Is there some complexity class X high up in the PH that an X-machine can approximately sample the Fourier transform of every function that an X-machine can compute.
4) I was especially interested in the problem of sampling the Fourier transform of the crossing event for percolation on an n by n hexagonal grid.