Finding an sha-512 collision is not a problem that quantum computers can help with, even in theory.*
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.
"Extremely contrived" is a little bit misleading since they did in fact run random algorithms from a general set of algorithms. So it's rather the opposite of contrived.. but I understand what you mean :)
Contrived means "Deliberately created rather than arising naturally or spontaneously"
https://www.lexico.com/en/definition/contrived . I think the problems used to demonstrate quantum supremacy very literally meet that definition - they were largely created for the sole purpose of demonstrating supremacy; they are not problems we naturally want to know the answers to.
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.