5 ms·
The “JVG algorithm” only wins on tiny numbers
- MathMonkeyMan 7mo agoThe 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.
- measurablefunc 7mo agoScott Aaronson is the guy who keeps claiming quantum supremacy is here every year so he's like the proverbial pot calling the kettle black.
- adgjlsfhk1 7mo agothe 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
- measurablefunc 7mo agoAll I know is he keeps being wrong about quantum supremacy but maybe this is the year he finally gets his wish.
- adgjlsfhk1 7mo agohe's been right about it. quantum supremacy was achieved in 2023 (but only for incredibly useless problems)
- gsf_emergency_7 7mo agoYeah I think GP might now prefer his statement(s) to have been about "quantum _advantage_". Which is the modish term after all.
- Strilanc 7mo agoWhat do you mean? The original 2019 supremacy experiment was eventually simulated, as better classical methods were found, but the followups are still holding strong (for example [4] and [5]). There was recently a series of blog posts by Dominik Hangleiter summarizing the situation: [1][2][3]. [1]: https://quantumfrontiers.com/2026/01/06/has-quantum-advantage-been-achieved/ https://quantumfrontiers.com/2026/01/06/has-quantum-advantag... [2]: https://quantumfrontiers.com/2026/01/25/has-quantum-advantage-been-achieved-part-2-considering-the-evidence/ https://quantumfrontiers.com/2026/01/25/has-quantum-advantag... [3]: https://quantumfrontiers.com/2026/02/28/what-is-next-in-quantum-advantage/ https://quantumfrontiers.com/2026/02/28/what-is-next-in-quan... [4]: https://arxiv.org/abs/2303.04792 https://arxiv.org/abs/2303.04792 [5]: https://arxiv.org/abs/2406.02501 https://arxiv.org/abs/2406.02501
- gsf_emergency_7 7mo ago[dead]
- Strilanc 7mo agoMinor update: Dominik condensed the blog posts into a pre-print: https://arxiv.org/abs/2603.09901 https://arxiv.org/abs/2603.09901
- Strilanc 7mo agoAgree. Scott is exactly correct when he just straight calls it crap. It's inaccurate to say it wins on small numbers because on small numbers you would use classical computers. By the time you get to numbers that take more than a minute to factor classically, and start dreaming of quantum computers, you're well beyond the size where you could tractably do the proposed state preparation.
- amelius 7mo agoWell, the reviewers missed it too.
- bawolff 7mo agoHonestly i think he was remarkably polite given the sort of crap we are talking about.
- pseudohadamard 7mo agoI believe the appropriate technical term is "bollocks" rather than "crap", see https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf.
- Strilanc 7mo agoThat slide deck is complaining that correct work on quantum attacks should be seen as negligible priority or as distractions. TFA is complaining that JVG isn't even correct. They are pretty different concerns. To be clear, I think that slide deck will be looked back upon as naive. In particular, it makes the classic mistake of assuming the size of number factored should be growing smoothly. That's naive because 15 is such a huge cost outlier and because quantum error correction has frontloaded costs. See [1] and [2] for details. [1]: https://algassert.com/post/2500 https://algassert.com/post/2500 [2]: https://algassert.com/post/2503 https://algassert.com/post/2503
- RcouF1uZ4gsC 7mo agoScott References the top comment on this previous HN discussion https://news.ycombinator.com/item?id=47246295 https://news.ycombinator.com/item?id=47246295
- kmeisthax 7mo agoI mean, considering that no quantum computer has ever actually factored a number, a speedup on tiny numbers is still impressive :P
- Tyr42 7mo agoHey hey, 15 = 3*5 is factoring.
- scuppernong 7mo agomy understanding is that they factored 15 using a modular exponentiation circuit that presumes that the modulus is 3. factoring 15 with knowledge of 3 is not so impressive. Shor's algorithm has never been run with a full modular exponentiation circuit.
- Strilanc 7mo agoThe very first demonstration of factoring 15 with a quantum computer, back in 2001, used a valid modular exponentiation circuit [1]. The trickiest part of the circuit is they compile conditional multiplication by 4 (mod 15) into two controlled swaps. That's a very elegant way to do the multiplication, but most modular multiplication circuits are much more complex. 15 is a huge outlier on the difficulty of actually doing the modular exponentiation. Which is why so far 15 is the only number that's been factored by a quantum computer while meeting the bar of "yes you have to actually do the modular exponentiation required by Shor's algorithm". [1]: https://arxiv.org/pdf/quant-ph/0112176#page=15 https://arxiv.org/pdf/quant-ph/0112176#page=15
- adgjlsfhk1 7mo agowould other mersenne numbers admit the same trick? if so, factoring 2047 would be really interesting to see. it's still well within the toy range, but it's big enough that it would be a lot easier to believe that the quantum computer was doing something (15 is so small that picking an odd number less than sqrt(15) is guaranteed to be a correct factorization)
- guy4261 7mo ago> (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
- abound 7mo agoSame with RSA and other things, I think the author's point is that slapping your name on an algorithm is a pretty big move (since practically, you can only do it a few times max in your life before it would get too confusing), and so it's a gaudy thing to do, especially for something illegitimate.
- johncarlosbaez 7mo ago
- coolcoder9520 7mo ago[flagged]
- deleted 7mo ago[deleted]
- kittikitti 7mo agoWhile 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.
- adgjlsfhk1 7mo agoJVC 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
- amluto 7mo agoThere 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.
- deleted 7mo ago[deleted]