I think it also has to be a problem that is able to be constructed in a way where incorrect solutions destructively interfere with each other while correct ones don't.
Think of it as being able to simultaneously calculate a bunch of inputs but only being able to report the "sum" of those calculations to you. So to make it useful you'd need to be able to reconstruct problems such that the incorrect answers when computed cancel each other out. Otherwise your desired answer would just be mixed in with garbage and you won't be able to get anything useful out.
It's not actually that easy to make useful quantum algorithms that work and there's only a handful of them around...
yes, and that is a solved problem for all encryption already, you need that to find any key in encryption.
what makes that hard now is the search takes so much time.
In a theortical post quantum world that search wont take much time.
So the only way I see that post quantum encryption can be secure is if it is impossible to guess a solution and test it for correctness - which for whatever reason... never seems to get addressed.
Think of it as being able to simultaneously calculate a bunch of inputs but only being able to report the "sum" of those calculations to you. So to make it useful you'd need to be able to reconstruct problems such that the incorrect answers when computed cancel each other out. Otherwise your desired answer would just be mixed in with garbage and you won't be able to get anything useful out.
It's not actually that easy to make useful quantum algorithms that work and there's only a handful of them around...