That's not really what's going on here. Typically when quantum computers are compared against classical computers, it's assumed that the latter have access to

That's not really what's going on here. Typically when quantum computers are compared against classical computers, it's assumed that the latter have access to a source of randomness. It's not the randomness by itself that should make this hard for a classical computer.