undefined | Better HN

0 pointsda-bacon1y ago0 comments

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”.

0 comments

Ar-Curunir1y ago

The attackable noise ratio did not go from exponential to polynomial either. It went from classically subexponential to quantumly polynomial.

da-baconOP1y ago

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.

j / k navigate · click thread line to collapse

0 pointsda-bacon1y ago0 comments

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”.

0 comments

Ar-Curunir1y ago

The attackable noise ratio did not go from exponential to polynomial either. It went from classically subexponential to quantumly polynomial.

da-baconOP1y ago

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.

j / k navigate · click thread line to collapse