The running time of attacks hasn't suddenly become O(n^4.5). The latter figure describe the noise ratio for which the LWE assumption becomes broken in quantum polynomial time.
The proposed post-quantum encryption schemes use a much smaller noise ratio which (at the moment) is not affected by these attacks.
I didn’t say the runtime did I? The approximation ratio went from exponential to polynomial noise ratio. This just went from 2^n to n^4.5 and everyone seems to say “oh this is fine”.
The attackable noise ratio did not go from exponential to polynomial either. It went from classically subexponential to quantumly polynomial.
Yes sub exponential which is splitting hairs. Exp(O(n log log n / log n)). Thanks for the acknowledgment that I didn’t say runtime.
An analogy would be something like this. Factoring is hard. We base RSA on the hardness of this problem and there we use numbers that are the product of two primes. Someone just found an algorithm that doesn’t work to find the product of two primes, but can take a product of four primes and return two products of two primes. Do you feel safe with RSA?
Anyway the paper could be wrong or it could be right, it will take a while for those in the field to dig through this. As a cautionary tale, there have been a few extra good quantum people who have proposed quantum attacks on lattice problems that have later been shown to have bugs.