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.