Does the recent result on BQP not being in PH relative to an oracle do anything to your priors about the power of quantum computers relative to classical computers? If you had to distill why that oracle separation works, what would you say is the main trick from the perspective of "where does the power of quantum computers come from"?
Honestly, almost all of the technical innovation in this breakthrough had to do with classical circuit complexity—-once you know my Forrelation problem, there’s almost no further input you need about quantum computation. (Well, a slight amount, since Raz and Tal had to modify Forrelation a bit to get their proof to go through.)
For an attempt at a popular summary of what the circuit lower bound innovations consisted of, see my blog post:
No, this doesn’t much change my priors about the power of quantum computation—for one thing, because we all (or at least I :-) ) were already pretty damn confident that Forrelation was not in PH. On the other hand, I was not expecting that the separation could be proved right now—certainly, not without first proving some weaker separations like BQP vs. AM.
