This conversion O(2^n) -> O(2^n/2) only applies to Grover's algorithm which can be used to break symmetric crypto (AES etc.). This is not the usual concern in the context of quantum computers because it just corresponds to halving the key space (in bits) which you can protect against by doubling the key size. So use AES-256 instead of AES-128. And the benefit by Grovers can only be had once. And as the paper you link to point out, maybe even that benefit is in question.

However, the main concern with quantum computers vs cryptography is Shor's algorithm which works on RSA and ECC. Shor's has the potential to take the problem from exponential (or at least close to exponential but sub, in the case of RSA) to polynomial O(n^3) which is much more powerful (essentially taking a log of the running time!). That is still assuming, of course, that workable quantum computers of required since will appear and that all the associated problems with that (noisy qbits etc.) are solved. Other challenges could also show up (difficulties scaling for longer computations, more passes through quantum gates, larger super-positions or even that the quantum laws governing e.g. probability amplitudes don't hold with full accuracy at such scales).