Re:Quantum Algorithms for Lattice Problems
by da-bacon on Friday April 12, 2024 @04:02PM
(#40017054)
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”.
[ Parent
| on HN ]
Re:Quantum Algorithms for Lattice Problems
by Ar-Curunir on Friday April 12, 2024 @08:20PM
(#40019071)
The attackable noise ratio did not go from exponential to polynomial either. It went from classically subexponential to quantumly polynomial.