[flagged]
The “JVG algorithm” only wins on tiny numbers
21–30 of 56 posts
Re: The “JVG algorithm” only wins on tiny numbers
#22While 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.
Re: The “JVG algorithm” only wins on tiny numbers
#23[deleted]
Re: The “JVG algorithm” only wins on tiny numbers
#24The 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.
Scott Aaronson is the guy who keeps claiming quantum supremacy is here every year so he's like the proverbial pot calling the kettle black.
the reason people pay attention to him is that he does a good job publicizing both positive and negative results, and accurately categorizing which are bullshit
Re: The “JVG algorithm” only wins on tiny numbers
#25While 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 thi…
JVC isn't BQP. it's exp time (I.e. worse than factoring without a quantum computer at all). it takes the only step of shors algorithm that is faster to run on a quantum computer and moves it to a classical computer
Re: The “JVG algorithm” only wins on tiny numbers
#26While 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 thi…
There is a genuinely interesting complexity class called BQP/poly, which is pronounced something like “bounded-error quantum polynomial time with classical advice” (add some more syllables for a complete pronunciation).
The JVG algorithm is not a high quality example of this or really anything else. If you think of it as “classical advice”, then it fails, because the advice depends on the input and not just the size of the input. If you think of it as precomputation, it’s useless, because the precomputation involved already fully solves the discrete log problem. And the JVG paper doesn’t even explain how to run their circuit at respectable sizes without the sheer size of the circuit making the algorithm fail.
It’s a bit like saying that one could optimize Stockfish to run 1000x faster by giving it an endgame table covering all 16-or-fewer-piece-positions. Sure, maybe you could, but you also already solved chess by the time you finish making that table.
Re: The “JVG algorithm” only wins on tiny numbers
#27> (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
Adelson-Velsky and Evgenii Landis were not the ones who named their tree the "AVL tree". In my "crackpot index", item 20 says: 20 points for naming something after yourself. (E.g., talking about the "The Evans Field Equation" when your name happens to be Evans.)
https://math.ucr.edu/home/baez/crackpot.html for the curious (on that version it's item 25 though :o )
Re: The “JVG algorithm” only wins on tiny numbers
#28[flagged]
[deleted]
Re: The “JVG algorithm” only wins on tiny numbers
#29Earlier quoted context omitted.
Scott Aaronson is the guy who keeps claiming quantum supremacy is here every year so he's like the proverbial pot calling the kettle black.
the reason people pay attention to him is that he does a good job publicizing both positive and negative results, and accurately categorizing which are bullshit
All I know is he keeps being wrong about quantum supremacy but maybe this is the year he finally gets his wish.
Re: The “JVG algorithm” only wins on tiny numbers
#30Earlier quoted context omitted.
the reason people pay attention to him is that he does a good job publicizing both positive and negative results, and accurately categorizing which are bullshit
All I know is he keeps being wrong about quantum supremacy but maybe this is the year he finally gets his wish.
he's been right about it. quantum supremacy was achieved in 2023 (but only for incredibly useless problems)