No, the distribution is thought to be hard for any classical algorithm (this is still being worked on - there are still ongoing theory development for showing

No, the distribution is thought to be hard for any classical algorithm (this is still being worked on - there are still ongoing theory development for showing it is harder and harder), and by extension, any classical process. Yes, the problem is very contrived - the distribution being sampled is given by the distribution you get from sampling from a randomly sampled quantum circuit. Of course this is easy on a quantum computer because you can just throw on the randomly chosen gates and measure it. I don't think it will be very useful in a application sense. This problem was designed for the very purpose of showing a "quantum supremacy" as soon as possible. Also, from what I know, there is still a problem in the whole verification aspect for this problem. That is, even if it can sample from the distribution, it is difficult to verify that in fact the correct distribution was sampled. This is in contrast to the problem of factoring, where to verify the computation we just need to multiply the numbers together to check these are indeed the factors. A remedy I have heard of this (I think from Scott Aarsonson) is that we can modify the parameters so that the output is just within the limits of verifiability with a big supercomputer, and that should be good enough to show supremacy was achieved (EDIT: this is precisely what OP's article says it will do). I think this might be bending what is meant by the term "quantum supremacy" too much, but it's a pretty arbitrary point in computational power anyways , so I'm not too concerned. If you're interested in more about quantum supremacy, these two articles have a lot of information: 1. Quantum Computational Supremacy Aram W. Harror, Ashley Montanaro (2018) https://arxiv.org/pdf/1809.07442.pdf https://arxiv.org/pdf/1809.07442.pdf 2. Complexity-Theoretic Foundations of Quantum Supremacy Experiments Scott Aaronson, Lijie Chen (2016) https://arxiv.org/pdf/1612.05903.pdf https://arxiv.org/pdf/1612.05903.pdf