If I understand the problem correctly it involves generating random strings. If so, then it seems like cheating since quantum effects are random and classical computing isn't.
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.