The complexity of sampling (approximately) the Fourier transform of a Boolean function

Question

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.

Answer 1

The Kushilevitz-Mansour algorithm in learning theory establishes, that whenever $\hat{f}(x)$ is approximately sparse, i.e. there are only $O(poly(n))$-many large Fourier coefficients of absolute value $\Omega(1/poly(n))$, then we can find their locations and approximate their complex values in $\sf{BPP}$. Of course you can also efficiently sample from that list. To be precise, Kushilevitz-Mansour only talked about Fourier transforms over $\mathbb{Z}_2$, but generalization to FTs over general finite Abelian groups (see e.g. Akavia's thesis) are known.

As an application of this to quantum computing, one can show that the output state of quantum circuits structured in blocks of Hadamard-Toffoli-Hadamard gates can be efficiently approximated given the promise that the output state written in the computational basis is approximately sparse (see my QIP'2010 poster here, and the pre-print here). If the sparsity assumption is dropped, we could simulate Simon's algorithm (or Shor's), which is of exactly that structure, contradicting the $\Omega(2^{n/2})$ query lower-bound for Simon's problem.