In the Nature paper published by Google, they say,
To demonstrate quantum supremacy, we compare our quantum processor against state-of-the-art classical computers in the task of sampling the output of a pseudo-random quantum circuit. Random circuits are a suitable choice for benchmarking because they do not possess structure and therefore allow for limited guarantees of computational hardness. We design the circuits to entangle a set of quantum bits (qubits) by repeated application of single-qubit and two-qubit logical operations. Sampling the quantum circuit’s output produces a set of bitstrings, for example {0000101, 1011100, …}. Owing to quantum interference, the probability distribution of the bitstrings resembles a speckled intensity pattern produced by light interference in laser scatter, such that some bitstrings are much more likely to occur than others. Classically computing this probability distribution becomes exponentially more difficult as the number of qubits (width) and number of gate cycles (depth) grow.
So, from what I can tell, they configure their qubits into a pseudo-randomly generated circuit, which, when run, puts the qubits into a state vector that represents a probability distribution over $2^{53}$ possible states of the qubits, but that distribution is intractable to calculate, or even estimate via sampling using a classical computer simulation. But they sample it by "looking" at the state of the qubits after running the circuit many times.
Isn't this just an example of creating a system whose output is intractable to calculate, and then "calculating" it by simply observing the output of the system?
It sounds similar to saying:
If I spill this pudding cup on the floor, the exact pattern it will form is very chaotic, and intractable for any supercomputer to calculate. But I just invented a new special type of computer: this pudding cup. And I'm going to do the calculation by spilling it on the floor and observing the result. I have achieved pudding supremacy.
which clearly is not impressive at all. In my example, I'm doing a "calculation" that's intractable for any classical computer, but there's no obvious way to extrapolate this method towards anything actually useful. Why is Google's experiment different?
EDIT: To elaborate on my intuition here, the thing I consider impressive about classical computers is their ability to simulate other systems, not just themselves. When setting up a classical circuit, the question we want to answer is not "which transistors will be lit up once we run a current through this?" We want to answer questions like "what's 4+1?" or "what happens when Andromeda collides with the Milky Way?" If I were shown a classical computer "predicting" which transistors will light up when a current is run through it, it wouldn't be obvious to me that we're any closer to answering the interesting questions.
Best Answer
There isn't a real distinction here. Both quantum and classical computers only do one thing: compute the result of some circuit. A classical computer does not fundamentally know what $4+1$ means. Instead current is made to flow through various transistors, as governed by the laws of physics. We then read off the final state of the output bits and interpret it as $5$.
The real distinction, which holds in both cases, is whether you can program it or not. For example, a simple four-function calculator is a classical system involving lots of transistors, but the specific things it can compute are completely fixed, which is why we don't regard it as a classical computer. And a pudding is a quantum system involving lots of qubits, but we can't make it do anything but be a pudding, so it's not a quantum computer.
Google can control the gates they apply in their quantum circuit, just like loading a different program can control the gates applied in a classical CPU. That's the difference.