It's 2020, and I'm still waiting to see an impressive proof of work out out of a quantum computer that I can easily verify on my traditional computer (two different files with identical SHA-512, for example?).
Maybe a few years from now?
Maybe a few years from now?
Anyways, if you want something that can be verified on a classical computer but cannot be done on a classical computer, see google's recent Quantum supremacy experiment. However it is extremely contrived. I think the most likely non contrived thing will be simulating simpilish quantum systems (to help with chemistry experiments and the like), but its probably still going to be a while before we start seeing that i think (IANA quantum scientist).
*Edit: to clarify, quantum computers can speed the process up of finding a collision in theory, just not enough to help. Normally you would need O(2^256) operations to find sha512 collision (Birthday paradox), quantum (BHT) gets you down to O(2^170), which is better, but still way to high. Most crypto assumes anything greater than 2^128 is secure by a comfortable margin.
Now, instead of the random string, you have a random circuit. And the output is the goal. The random circuit is as useful to you as the random string. But using a quantum computer you can compute its state when operating. With a traditional computer it is very hard.
https://www.nature.com/articles/s41586-019-1666-5 https://www.scottaaronson.com/blog/?p=4317