Re:I'm Scott Aaronson, quantum computing/computational compl...
by ScottAaronson on Saturday June 30, 2018 @08:11PM
(#17433376)
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.
For an attempt at a popular summary of what the circuit lower bound innovations consisted of, see my blog post:
https://www.scottaaronson.com/blog/?p=3827
or, of course, their paper.
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.