What is recursive Fourier sampling and how does it prove separations between BQP and NP in the black-box model?

Question

Context:

I was going through John Watrous' lecture Quantum Complexity Theory (Part 1) - CSSQI 2012. Around 48 minutes into the lecture, he presents the following:

No relationship is known between $\mathsf{BQP}$ and $\mathsf{NP}$...they are conjectured to be incomparable.

So far so good. Then I came across Scott Aaronson's answer to Can a parallel computer simulate a quantum computer? Is BQP inside NP? He mentions these points:

• Suppose you insist on talking about decision problems only ("total" ones, which have to be defined for every input), as people traditionally do when defining complexity classes like P, NP, and BQP. Then we have proven separations between BQP and NP in the "black-box model" (i.e., the model where both the BQP machine and the NP machine get access to an oracle), as mmc alluded to.

• And to reiterate, all of these separations are in the black-box model only. It remains completely unclear, even at a conjectural level, whether or not these translate into separations in the "real" world (i.e., the world without oracles). We don't have any clear examples analogous to factoring, of real decision problems in BQP that are plausibly not in NP. After years thinking about the problem, I still don't have a strong intuition either that BQP should be contained in NP in the "real" world or that it shouldn't be.

According to his answer, it seems that in the "black-box model" we can show some relationship (as in non-overlapping) between $\mathsf{BQP}$ and $\mathsf{NP}$. He cites @mmc's answer, which says:

There is no definitive answer due to the fact that no problem is known to be inside PSPACE and outside P. But recursive Fourier sampling is conjectured to be outside MA (the probabilistic generalization of NP) and has an efficient quantum algorithm. Check page 3 of this survey by Vazirani for more details.

Question:

It's not clear from @mmc's answer as to how the recursive Fourier sampling algorithm is related to the $\mathsf{BQP}$ class and how (or whether at all) it proves separations between $\mathsf{BQP}$ and $\mathsf{NP}$ in the "black-box model". In fact, I'm not even sure what "black-box model" means in this context, although I suspect that it refers to some kind of computation model involving quantum oracles.

It would be great if someone could provide a brief and digestible summary of what the recursive Fourier sampling algorithm is and how it proves separations between $\mathsf{BQP}$ and $\mathsf{NP}$. Even a rough sketch of the idea behind the proof would be okay. I'm hoping this will give me a head start in understanding the papers linked by @mmc, which are otherwise rather dense for me at present.

Answer 1

Initially I'll admit that I find the linked papers to be dense as well.

However, to make some headway, a complete problem in $\mathrm{NP}$ can be phrased as "given a $\mathsf{3SAT}$ instance, does there exist a solution?" A complete problem in $\mathrm{coNP}$ is "given $\mathsf{3SAT}$ instance, do all inputs satisfy the $\mathsf{3SAT}$? Problems in the polynomial hierarchy $\mathrm{PH}$ alternate "there exists" with "for alls," with a constant number of iterations of $\exists$ and $\forall$. For me, the easiest problem in $\mathrm{PH}$ to think about is "is there a mate in $n$ for this board position?" because this is just "does there exist a move by white such that for all moves by black, there is a counter-move by white such that... white wins."

Ponder the difficulty of such $\forall x_1,\exists x_2\cdots$ problems as compared to factoring, which is in $\mathrm{NP}\cap\mathrm{coNP}$.

Turning to Recursive Fourier Sampling (RFS), much as in Simon's problem, with RFS we are only given oracle access to a function $A$. However, RFS involves a promise having just such an alternation of $\exists$ and $\forall$. By going up to a small-enough height (number of iterations of $\exists$ and $\forall$,) the problem can be shown to be likely difficult for a classical computer to efficiently solve but definitely easy for a quantum computer to solve.

Comparing RFS to the "forrelation" problem that I think is a little easier to understand but somewhat more difficult to see the connection to $\forall x_1,\exists x_2\cdots$. Forrelation is as simple as asking if, given two black-box (oracle) functions $f$ and $g$, is there a correlation between $f$ and the Fourier transform of $g$? Here, we can simply Fourier transform $g$ and find the inner product with $f$.

Forrelation is likely even completely outside the polynomial hierarchy. Here the relation to the $\forall, \exists$ is less clear to me right now but effectively involves translating a tree of alternating $\mathsf{AND's}$ and $\mathsf{OR's}$ that are capable of solving forrelation to a sequence of alternating $\forall$ and $\exists$.

Here $f$ and $g$ are simply black-box, without any structure. As far as I know, we don't know a good instantiation of $f$ or $g$ "in the real world" yet, with $f$ and/or $g$ have a particular structure.