<p>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 <a href="http://www.scottaaronson.com/papers/bqpph.pdf">BQP vs. PH</a> 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, <a href="http://www.scottaaronson.com/papers/glnfalse.pdf">that conjecture turned out to be false</a>, 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 <a href="http://users.cms.caltech.edu/~umans/papers/FSUV10.pdf">nice followup paper by Fefferman, Shaltiel, Umans, and Viola</a>.</p>

CC BY-SA 3.0
2013-01-04T20:23:36.263Z
is the above statement of the question by Gharibi identical or slightly different? is it a relativized version of yours?
vzn
CC BY-SA 3.0
2013-01-05T20:43:30.107Z
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
CC BY-SA 3.0
2013-01-05T21:58:36.047Z
Is more known when f is in P?
Gil Kalai
CC BY-SA 3.0
2013-01-13T22:25:55.413Z
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
CC BY-SA 3.0
2013-01-04T01:05:23.587Z
2013-01-04T01:05:23.587Z
Scott Aaronson
<p>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 <em>fourier checking problem</em> (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).</p>

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

<p><a href="http://qip2011.quantumlah.org/scientificprogramme/abstract/1010.3654.pdf" rel="nofollow">Exponential Speedups are Generic</a> by Fernando G.S.L. Brandão and Michał Horodecki</p>

<blockquote>
  <p>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 <em>any</em> (possibly non-abelian) finite group and <em>almost any</em> sufficiently long quantum circuit from a natural distribution on the set of quantum circuits. We obtain <em>exponential</em> separations of quantum and postselected classical query complexities for all such circuits.</p>
</blockquote>

CC BY-SA 3.0
2013-01-03T15:54:46.397Z
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
CC BY-SA 3.0
2013-01-03T06:06:15.713Z
2013-01-04T01:13:47.547Z
2013-01-04T01:13:47.547Z
vzn
<p>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$. </p>

<p>The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^n \to R$:</p>

<p>$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x)$
</p>

<p>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.</p>

<p>It is not hard to show that a $PH$ machine, cannot even approximate $F(s)$ for any $s$.</p>

<p>What is the query complexity of deciding with high success probability which one is the true one ?</p>

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

CC BY-SA 3.0
2013-01-02T08:56:11.737Z
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
CC BY-SA 3.0
2013-01-03T03:46:23.150Z
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
CC BY-SA 3.0
2013-01-03T05:02:23.887Z
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
CC BY-SA 2.5
2010-12-07T06:15:00.343Z
By the way, we know that even approximating a Fourier coefficient is not in PH.
Mirmojtaba Gharibi
CC BY-SA 2.5
2010-12-07T16:09:05.183Z
@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
CC BY-SA 2.5
2010-12-07T21:32:20.367Z
Thanks Kaveh and Robin. I edited my question accordingly.
Mirmojtaba Gharibi
CC BY-SA 2.5
2010-12-07T22:55:18.983Z
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
CC BY-SA 2.5
2010-12-08T02:51:19.247Z
@ 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
CC BY-SA 2.5
2010-12-08T05:23:49.927Z
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
CC BY-SA 2.5
2010-12-09T03:21:19.217Z
@ 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
CC BY-SA 2.5
2010-12-09T13:45:04.017Z
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 張顯之
CC BY-SA 2.5
2010-12-12T00:55:14.930Z
@Mirmojtaba, can you please point me to the Aaronson paper ? thanks !
Suresh Venkat
CC BY-SA 2.5
2010-12-12T01:01:23.113Z
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
CC BY-SA 2.5
2010-12-12T04:01:38.890Z
@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
<cc.complexity-theory><lg.learning><boolean-functions><fourier-analysis>
What is the complexity of distinguishing a true Fourier spectra from a fake one?
Mirmojtaba Gharibi
# What is the complexity of distinguishing a true Fourier spectra from a fake one?

(Asked by: username_0 on 2010-12-07)

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

**Tags:** cc.complexity-theory, lg.learning, boolean-functions, fourier-analysis

> **Comments:**
> **username_0**: By the way, we know that even approximating a Fourier coefficient is not in PH.  
> **username_3**: @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.)  
> **username_0**: Thanks Kaveh and Robin. I edited my question accordingly.  
> **username_3**: 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?  
> **username_0**: @ 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).  
> **username_4**: 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 ?  
> **username_0**: @ 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. username_6 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)  
> **username_5**: Cross-post on MO: http://mathoverflow.net/questions/48721/what-is-the-complexity-of-distinguishing-a-true-fourier-spectra-from-a-fake-one  
> **username_4**: @Mirmojtaba, can you please point me to the Aaronson paper ? thanks !  
> **username_4**: 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  
> **username_0**: @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.)  
> **username_1**: 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.  
> **username_2**: 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"  
> **username_2**: 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)...  

---

## 2 answers

### Answer by username_6 on 2013-01-04. Score: 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](http://www.scottaaronson.com/papers/bqpph.pdf) 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](http://www.scottaaronson.com/papers/glnfalse.pdf), 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](http://users.cms.caltech.edu/~umans/papers/FSUV10.pdf).

> **Comments:**
> **username_2**: is the above statement of the question by Gharibi identical or slightly different? is it a relativized version of yours?  
> **username_6**: 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.  
> **username_7**: Is more known when f is in P?  
> **username_6**: 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.)  

---

### Answer by username_2 on 2013-01-03. Score: 1

username_6 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](http://qip2011.quantumlah.org/scientificprogramme/abstract/1010.3654.pdf) 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.

> **Comments:**
> **username_2**: 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.  

---

