What is the complexity of distinguishing a true Fourier spectra from a fake one?

Question

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

By the way, we know that even approximating a Fourier coefficient is not in PH. — Mirmojtaba Gharibi, Dec 07 '10 at 06:15
@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.) — Robin Kothari, Dec 07 '10 at 16:09
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 07 '10 at 22:55
@ Robin: I think you're right provided that the unknown Boolean function which the fake Fourier spectra belongs to ( call it y ), is chosen to be very close to f. However, what I mean is that y is also drawn from a uniform distribution (I am editing the question to make it clear). — Mirmojtaba Gharibi, Dec 08 '10 at 02:51
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 08 '10 at 05:23
@ Suresh: Nice question. I don't know the answer, but I think there should be a reasonable distance between valid fourier spectra's and our arbitrary function for Turing machine to be able distinguish them. Scott Aaronson in his paper "BQP vs. PH", was trying to prove something similar. He was trying (but still the problem is open) to prove that a PH machine cannot distinguish the uniform distribution from a function that contained the signs of the fourier coefficients of a given oracle (The setting is not exactly as I am explaining. I would refer you to that paper, if you're interested) — Mirmojtaba Gharibi, Dec 09 '10 at 03:21
Cross-post on MO: http://mathoverflow.net/questions/48721/what-is-the-complexity-of-distinguishing-a-true-fourier-spectra-from-a-fake-one — Hsien-Chih Chang 張顯之, Dec 09 '10 at 13:45
@Mirmojtaba, can you please point me to the Aaronson paper ? thanks ! — Suresh Venkat, Dec 12 '10 at 00:55
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: http://meta.cstheory.stackexchange.com/questions/673/changing-policy-on-crossposting — Suresh Venkat, Dec 12 '10 at 01:01
@Suresh: Here is the link : http://www.scottaaronson.com/papers/bqpph.pdf . You can skip all the parts related to Fourier Fishing and instead just look for materials related to Fourier checking. He has also some blog posts about Fourier Checking problem which you may find more abstract and easier to read: http://scottaaronson.com/blog/?p=381. Please note that the GLN conjecture-A generalization of Linial-Nisan conjecture) proved to be false (A conjecture that he used in his paper to prove Fourier Checking yield an oracle for BQP and PH separation.) — Mirmojtaba Gharibi, Dec 12 '10 at 04: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 02 '13 at 08:56
dont you have to specify (1) how the coefficients are specified on the input? since they are, aparently they must be rational. (2) it also seems like this question might be reformulated in terms of some error function/metric instead of probabilities where the error function approaches zero if the spectrum is "true" — vzn, Jan 03 '13 at 03:46
looked at aaronsons blog & paper, and frankly, dont understand how the above question is any different from the problem he poses as a key open problem and capable of separating BQP and PH. ie, isnt it just a virtually exact restatement of aaronsons problem? erdos-style, aaronson is offering up to $300 for related proof(s)... — vzn, Jan 03 '13 at 05:02

score 10 · Answer 1 · answered Jan 04 '13 at 01:05

10

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.

answered Jan 04 '13 at 01:05

Scott Aaronson

13,733
2
62
68

1

is the above statement of the question by Gharibi identical or slightly different? is it a relativized version of yours? – vzn Jan 04 '13 at 20:23
1

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 05 '13 at 20:43
1

Is more known when f is in P? – Gil Kalai Jan 05 '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

score 1 · Answer 2 · edited Jan 04 '13 at 01:13

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 03 '13 at 15:54

What is the complexity of distinguishing a true Fourier spectra from a fake one?

2 Answers2