This is essentially the realm of computational complexity classes. For example, the class BQP may crudely described as the set of all problems that can be efficiently solved on a quantum computer. The difficulty with complexity classes is that it's hard to prove separations between many classes, i.e. the existence of problems which are in one class but not another.
In a sense, it is sufficient to be able to say "if this quantum algorithm cannot break it, it is safe", you just have to use the right algorithm. You need a BQP-complete algorithm such as finding roots of the Jones polynomial - any quantum algorithm can be cast as an instance of a BQP-complete algorithm. However, how that algorithm might be used for the cracking is completely unclear and non-trivial. It's not enough to see that you can't directly brute force things. So, that approach is probably not so helpful.
What do we want from a post-quantum crypto scenario? We need:
- a function $y=f(x)$ that we can easily compute for the purposes of encryption.
- for which the inverse, $f^{-1}(y)$ cannot easily be computed on a quantum computer, i.e. the problem class is outside BQP.
- given some secret, $z$, there is a classically efficiently computable function $g(y,z)=x$, i.e. with the supplementary information, the function $f(x)$ can be inverted. This is so that the right person (who has the private key, $z$) can decrypt the message.
This last bullet is (essentially) the definition of the complexity class NP: the problems for which it may be hard to find a solution, but for which a solution is easily verified when given a proof (corresponding to the private key in our case).
So, what we're after are problems in NP but not in BQP. Since we don't know if NP=BQP, we don't know that such things exist. However, there's a good route for looking at solutions: we consider NP-complete problems. These are the hardest instances of problems in NP, so if BQP$\neq$ NP (which is widely believed to be the case), NP-complete problems are certainly not in BQP. (If a problem is complete for a complexity class, it means that if you can solve it efficiently, you can solve all instances of the class efficiently.) So, this is kind of the guidance for where one might look for post-quantum algorithms.
The additional subtlety that complicates matters, however, is roughly (I'm not an expert) that complexity classes talk about worst case complexity, i.e. for a given problem size, it's about how hard the hardest possible instance of the problem is. But there could be only one such problem instance, which would mean that if we fix the problem size (as is standard, e.g. you might talk about 1024 bit RSA; the 1024 bits is the problem size), there's only be one private key. If we know that, an eavesdropper can just use that private key to decrypt messages. So, we actually need that this computational complexity reasoning applies for a large proportion of possible inputs. This gets you into the world of average-case complexity where, as I understand it, it becomes much harder to make such statements.
It may help to make a comparison to RSA, a public key crypto-system, and ignoring the existence of quantum computers. It is based on the difficulty of factoring large composite numbers. This problem is not (believed to be) in P, so it is believed to be difficult for a hacker with a classical computer to get at the answer. Meanwhile, it is in NP because the solution is readily verified (if you're given one factor, you can easily check it's a factor). That means it can be decrypted using a classical computer by the rightful recipient.
