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

-
 crosspost from cstheory: cstheory.stackexchange.com/questions/3612/… – Suresh Venkat Dec 12 2010 at 0:55