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

• Maybe I misunderstood the problem, but it seems like this problem is too hard. If g and h are very close (say they differ at only 1 bit), how does a BQP machine decide which one is the correct Fourier spectrum of f? Shouldn't the lower bound on the search problem imply that this is hard for quantum computers? – Robin Kothari Dec 7 '10 at 22:55
• I have a more basic question. given an arbitrary function, is it easy to tell if it is indeed the fourier spectrum of a boolean function ? – Suresh Venkat Dec 8 '10 at 5:23
• as an aside, since he waited two days before crossposting, and that too after receiving no answer here, I think it's perfectly fine to do so. See also the resolution reached here: meta.cstheory.stackexchange.com/questions/673/… – Suresh Venkat Dec 12 '10 at 1:01
• What is a PH machine? In fact, this seems irrelevant if you are only interested in query complexity, right? In this case the problem seems to boil down to a simple linear algebra problem, which probably gives an exponential query complexity. – domotorp Jan 2 '13 at 8:56

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.

• is the above statement of the question by Gharibi identical or slightly different? is it a relativized version of yours? – vzn Jan 4 '13 at 20:23
• It's a slight variant, but I believe it's not hard to prove equivalent. First, certainly if you can solve Fourier Checking then you can also solve Gharibi's problem (just run the FC algorithm separately for g and h). For the converse, if you can solve Gharibi's problem, then given an instance of FC, name the second FC function either "g" or "h" uniformly at random, and set the other of the two (respectively h or g) to be a random function. If the Gharibi algorithm always picks the original function from the FC instance, that's evidence that the instance was forrelated rather than random. – Scott Aaronson Jan 5 '13 at 20:43
• Is more known when f is in P? – Gil Kalai Jan 5 '13 at 21:58
• Gil: Not really! You then get an unrelativized promise problem in BQP, which we don't know to be in PH. Certainly, you could simulate the "random" case of the oracle problem by replacing f and g by pseudorandom functions (computed in time that's a larger polynomial than the PH machine has available). The hard part is, how do you simulate the "forrelated" case of the oracle problem (where f is close to the Fourier transform of g)? I.e., how do you provide small circuits for such f and g that don't "give the entire game away"? (A similar issue occurs with Simon's problem.) – Scott Aaronson Jan 13 '13 at 22:25

Scott Aaronson may be the best person in the world to answer this question, maybe he will have a better answer after this one is posted. he proposed the original problem which this posted question seems to be a very slight variant on, the so-called fourier checking problem (more refs on that in the comments). the problem is closely related/nearly equivalent to separating two important complexity classes PH and BQP which is a key open problem of QM complexity theory, and it is presumably very hard. it does not appear that a lot of direct/further research on it has been done on the problem so far by anyone other than Aaronson and maybe not even him (its apparently only a little more than 2 years old).

however here is at least one paper by someone other than Aaronson that focuses/builds on the conjecture/problem with some new results.

Exponential Speedups are Generic by Fernando G.S.L. Brandão and Michał Horodecki

In our paper [4] we generalize the Fourier Checking problem [1] and show that the Fourier transform, both in the definition of the problem and in the quantum algorithm solving it, can be replaced by a large class of quantum circuits. These include both the Fourier transform over any (possibly non-abelian) finite group and almost any sufficiently long quantum circuit from a natural distribution on the set of quantum circuits. We obtain exponential separations of quantum and postselected classical query complexities for all such circuits.

• addendum: Aaronson formulated the Fourier checking problem specifically as a possible/plausible route to resolving $BQP\nsubseteq PH$ in ref [1] of the Branda~o paper. – vzn Jan 3 '13 at 15:54