FRESH

Hacker News

The “JVG algorithm” only wins on tiny numbers

71 points by jhalderm

by MathMonkeyMan

2 subcomments

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.

by RcouF1uZ4gsC

0 subcomment

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

0 subcomment

by kittikitti

2 subcomments

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.

by coolcoder9520

1 subcomments

by kmeisthax

3 subcomments

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

by guy4261

4 subcomments

> (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