What is the complexity of distinguishing a true Fourier spectra from a fake one? A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$. 

The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^n \to R$:

$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x)$

One of $g$ or $h$ is the true Fourier spectra of $f$ and the other one is just a fake Fourier spectra belonging to an unknown random Boolean function.

It is not hard to show that a $PH$ machine, cannot even approximate $F(s)$ for any $s$.

What is the query complexity of deciding with high success probability which one is the true one ?

It is interesting to me, since if this problem is not in $PH$, then one can show that there exists an oracle relative to which $BQP$ in not a subset of $PH$.
Sorry I'm late -- it's a wonderful question!  As others have already pointed out, that's exactly why I asked the question in my BQP vs. PH paper, and why I spent 4 or 5 months working on it without success back in 2008.  One way to answer the question would have been to prove a much more general statement that I called the "Generalized Linial-Nisan Conjecture"---but unfortunately, that conjecture turned out to be false, at least for circuits of depth 3 and higher.  (I still think it's probably true for depth-2 circuits, which would at least yield an oracle separation between BQP and AM.)  For more recent ideas (the latest, as far as I know) toward an oracle separation between BQP and PH, see the nice followup paper by Fefferman, Shaltiel, Umans, and Viola.