Condolences to the author, but this is a huge relief. A polytime quantum algorithm for LWE would have been a scary prospect for the future of asymmetric key crypto. (Not to mention all the other cool stuff people are building on top like fully homomorphic encryption.) Even if it wasn't quite fast enough to break the current schemes that NIST is standardizing, I (and I'm sure many others) would much prefer those problems to stay in exptime.
I love this, great work for science overall. This is exactly the type of approach/response one should take, and I hope he gets praise for doing the right thing.
Context, eg:
Quantum Algorithms for Lattice Problems,123 comments
https://news.ycombinator.com/item?id=39998396
and
A quick post on Chen's algorithm, 95 comments
His "comic slides" are fun :)
https://eurocrypt.iacr.org/2017/slides/A04-constraint-hiding...
I find it amazing someone can even read and follow all the formulas and find a bug
This is a very good reminder that we don't know for various problems whether there is an efficient algorithm. For problems studied for decades (eg travelling salesman) we feel fairly confident that there is no polynomial-time algorithm - but even then, we don't know for sure.
As far as I know, the problems underpinning post-quantum cryptography have not yet enjoyed such extensive scrutiny / search for efficient (regular or quantum) algorithms.
In other words: stuff that is hoped to be post-quantum might turn out to be quantum -- or even in a feasible non-quantum class. The latter seems unlikely barring p=np-alike breakthroughs, but even these cannot fully be ruled out.
[flagged]
[flagged]
[flagged]
I hope the author will post an official correction/amendment to the original paper and not just leave a short notice on their personal homepage.
I find that this is a great reaction to someone finding a bug in your paper. No trying to cover it up, but straight-up admitting a mistake. Also, the fact that he leaves the paper out because it does contain novel ideas that might be useful for further research is cool.