26
$\begingroup$

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

Improve this question
$\endgroup$
14
  • 5
    $\begingroup$ @Mirmojtaba: While I know the problem and motivation, it would be nice if you could edit your question and define "Fourier spectra" and explain the motivation for readers who are not familiar with this problem (or just the terminology you have used). You might get more answers from people that way. Also, it is usually preferred if you edit the question to add additional comments, instead of posting them in the comments thread. (So that readers only need to read your question and not the comments.) $\endgroup$
    – Robin Kothari
    Commented Dec 7, 2010 at 16:09
  • 4
    $\begingroup$ 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? $\endgroup$
    – Robin Kothari
    Commented Dec 7, 2010 at 22:55
  • 7
    $\begingroup$ 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 ? $\endgroup$
    – Suresh Venkat
    Commented Dec 8, 2010 at 5:23
  • 4
    $\begingroup$ 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/… $\endgroup$
    – Suresh Venkat
    Commented Dec 12, 2010 at 1:01
  • 2
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Commented Jan 2, 2013 at 8:56

2 Answers 2

Reset to default
10
+50
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ is the above statement of the question by Gharibi identical or slightly different? is it a relativized version of yours? $\endgroup$
    – vzn
    Commented Jan 4, 2013 at 20:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Scott Aaronson
    Commented Jan 5, 2013 at 20:43
  • 1
    $\begingroup$ Is more known when f is in P? $\endgroup$
    – Gil Kalai
    Commented Jan 5, 2013 at 21:58
  • $\begingroup$ 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.) $\endgroup$
    – Scott Aaronson
    Commented Jan 13, 2013 at 22:25
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Jan 3, 2013 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.