Answer to 1), 2) & 3):
- Complexity theory works with asymptotic and probabilistic cases, not the space and time consumption of specific examples of a given problem type. So it is not a mathematically precise concept like the NP or QP problem classes. We know certain problems can be solved in polynomial time on a quantum computer that take exponential time on a classical computer. It is in that mathematically precise sense that Shor's algorithm is superior to any classical algorithm to do the same. But that is not what quantum supremacy means. Quantum supremacy would require an implementation of Shor's algorithm on a quantum computer that can factor a prime number that no existing implementation of a classical computer can. This makes it very hard to make mathematically precise because it would depend on the quantum computer being a perfectly precise (or with bounded, modelable error) implementation of an abstract quantum computer and the same with the classical computer. The incredible amount of engineering details necessary are not something we can easily make a mathematical model for. And in the end, quantum supremacy might come and go from time to time as classical computers get better along with quantum computers.
General note on the paper:
- Their work was quite impressive in terms of the difficulty of setting up the physical system (they truly made a step forward in terms of that alone) and there is a sense in which it is true quantum supremacy but it is not what we were hoping for in an intuitive sense. It is almost as if someone said a pile of sand settling is a complex computing system that can outperform current classical computers and then proved it by showing that it can compute where a piece of sand in the pile falls in less time than a classical computer. The paper isn't quite as bad as that. But it just doesn't feel like true supremacy even though it technically is.
They essentially set up a quantum system of 53 entangled qubits and then sampled the system to determine the statistics of the quantum system. To determine the same statistics with a classical system you would have to model 2^53 superimposed states, calculate each of their hamiltonian evolutions and then sample the model. That is not currently possible for 53 qubits on a classical computer. But it doesn't really excite one about quantum supremacy.