Google recently announced that they have achieved "Quantum Supremacy": "that would be practically impossible for a classical machine."
Does this mean that they have definitely proved that BQP ≠ BPP ? And if that is the case, what are the implications for P ≠ NP ?
Google's paper and results are kind of sideways to questions in computational complexity about the relation between $\mathrm{BPP}$ and $\mathrm{BQP}$ (and even further from questions about whether $\mathrm{P}\ne\mathrm{NP}$). It's more as if Google relies on the hypothesis that $\mathrm{BPP}\ne\mathrm{BQP}$ as evidence that their quantum computer performs a task many orders of magnitude faster than a classical computer could.
Google performed a sampling task on their quantum computer, that they had strong theoretical reasons to believe is not easily performed on a classical computer. If we say that these complexity classes live in some idealized platonic universe, then Google's results don't shed any light about the difficulty of proving whether or not they are equal to one another - because Google's paper assumes that they are not equal to one another.
What Google's paper does do is provide evidence that the hypothesis that "a probabilistic Turing machine can efficiently simulate any realistic model of computation" is incorrect. They have prepared and maintained coherence of a state of their choosing in a Hilbert space of dimension $2^{53}$. As Aaronson argues, this is akin to the Wright Flyer providing evidence that "heavier-than-air human-controlled powered flight is impossible" is incorrect.
Paraphrasing some tweets on the matter earlier, the result is rather underwhelming because it plays on a discrepancy between what they mean by quantum supremacy (QS) and what people tend to think QS means.
What I find most people think QS is supposed to mean, and what I assumed it meant until a month or so ago, was that there exists a computable problem (in the CTT sense of computation) and an actual quantum computer, such that, at some scales, the problem is tractable on the quantum computer but intractable on all classical computers.
The problem the Google QC folks have demonstrated is not computation in the CTT sense. It is a physical process of sampling that involves computations as part of the process, and as with any physical process, it can be simulated approximately by computation. They have good reason to believe (proof? I'm not sure but it should reasonably be assumed true by default anyway) that computation to similate the process is going to be intractably slow. This is not surprising at all. It's a fundamental consequence of quantum mechanics that lots of physical processes will have that property.
That's not to say it's entirely uninteresting. There are likely useful applications of the sampling problem they implemented, and as I understand it, it provides examples of large classes of physical systems which are not amenable to efficient computational simulation. But it has nothing to do with whether or how soon a QC will be able to compete with a (classical, CTT) computer solving computable problems.
This has already been mentioned in a few comments, but for permanence:
There's the (somewhat technical) wrinkle that BQP and BPP apply to decision problems, while Google's quantum computer solved a sampling problem. So Google's result does not directly tell us anything about BQP or BPP. (Not that a real-world experiment would be able to rigorously prove a separation between abstract complexity classes anyway.)
