da-bacon parent
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.