The “JVG algorithm” only wins on tiny numbers

MathMonkeyMan

The title of this post changed as I was reading it. "It looks like the 'JVG algorithm' only wins on tiny numbers" is a charitable description. The article is Scott Aaronson lambasting the paper and shaming its authors as intellectual hooligans.

RcouF1uZ4gsC

Scott References the top comment on this previous HN discussion https://news.ycombinator.com/item?id=47246295

kmeisthax

I mean, considering that no quantum computer has ever actually factored a number, a speedup on tiny numbers is still impressive :P

guy4261

> (yes, the authors named it after themselves) The same way the AVL tree is named after its inventors - Georgy Adelson-Velsky and Evgenii Landis... Nothing peculiar about this imh

kittikitti

While I think the idea that claiming one can "precompute the xr mod N’s on a classical computer" sounds impractical there are a subset of problems where this might be valid. According to computational complexity theory, there's a class of algorithms called BQP (bounded-error quantum polynomial time). Shor's algorithm is part of BQP. Is the JVC algorithm part of BQP, even though it utilizes classical components? I think so. I believe that the precomputational step is the leading factor in the algorithm's time complexity, so it isn't technically a lower complexity than Shor's. If I had to speculate, there will be another class in quantum computational complexity theory that accommodates precomputation utilizing classical computing. I welcome the work, and after a quick scroll through the original paper, I think there is a great amount of additional research that could be done in this computational complexity class.