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$.
