Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The “JVG algorithm” only wins on tiny numbers

scottaaronson.blog

Post reply on HN
Print view View original

51–56 of 56 posts

Re: The “JVG algorithm” only wins on tiny numbers

#51

Post by Strilanc »

adgjlsfhk1 wrote: post #47
Strilanc wrote: post #34

Earlier quoted context omitted.

The 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 do…

would 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)

No, 15 is unique in that all multiplications by a known constant coprime to 15 correspond to bit rotations and/or bit flips. For 2047 that only occurs for a teeny tiny fraction of the selectable multipliers.

Shor's algorithm specifies that you should pick the base (which determines the multipliers) at random. Somehow picking a rare base that is cheap to do really does start overlapping with knowing the factors as part of making the circuit. By far the biggest cheat you can do is to "somehow" pick a number g such that g^2=1 (mod n) but g isn't 1 or N-1. Because that's exactly the number that Shor's algorithm is looking for, and the whole thing collapses into triviality.

Re: The “JVG algorithm” only wins on tiny numbers

#52

Post by omoikane »

Tyr42 wrote: post #7
kmeisthax wrote: post #4

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

Hey hey, 15 = 3*5 is factoring.

You can also get a dog to factor 15, see pages 9-11 of this paper:

https://news.ycombinator.com/item?id=44608622 - Replication of Quantum Factorisation Records with a VIC-20, an Abacus, and a Dog (2025-07-18, 25 comments)

Re: The “JVG algorithm” only wins on tiny numbers

#53

Post by adrian_b »

jerf wrote: post #50
dehrmann wrote: post #16

Earlier quoted context omitted.

I didn't get the quantum hype last year. At least with AI, you can see it do some impressive things with caveats, and there are bull and bear cases that are both reasonable. The quantum hype training is promising the world, but compared to AI, it's at the linear regression stage.

The only things I'm aware of that I consider actual problems it solves are "it breaks classical encryption" and "you may be able to use it to directly model other quantum systems like for protein folding and such". Everything else I consider pretty silly. "It can improve logistics" - I'm fairly sure computers are already as good as they can be, what dominates logistics calculations isn't an inability to optimize but…

It does not even break classical encryption (though classical encryption needs higher security margins if attacks using quantum computers are possible).

It breaks only classical public-key encryption.

Public-key encryption is not necessary within a closed organization, e.g. for the personal use of an individual or group of individuals, or within a spy agency or for military applications, though it can make slightly simpler the process of key distribution, which otherwise needs an initial physical pairing between devices.

The most important application of public-key encryption is for allowing relations between parties who have never met in person, by the use of digital signatures and of Diffie-Hellman key establishment protocols.

This has been essential to enable online shopping and online banking, but not for the more traditional uses of cryptography.

Re: The “JVG algorithm” only wins on tiny numbers

#54

Post by pseudohadamard »

Strilanc wrote: post #35
MathMonkeyMan wrote: post #2

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.

Agree. 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.

I believe the appropriate technical term is "bollocks" rather than "crap", see https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf.

Re: The “JVG algorithm” only wins on tiny numbers

#55

Post by Strilanc »

pseudohadamard wrote: post #54
Strilanc wrote: post #35

Earlier quoted context omitted.

Agree. 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.

I believe the appropriate technical term is "bollocks" rather than "crap", see https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf .

That 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

[2]: https://algassert.com/post/2503

Re: The “JVG algorithm” only wins on tiny numbers

#56

Post by Strilanc »

Strilanc wrote: post #41
measurablefunc wrote: post #14

Earlier 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.

What 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-advantag... [2]: https://quantumfrontiers.com/2026/01/25/has-quantum…

Minor update: Dominik condensed the blog posts into a pre-print: https://arxiv.org/abs/2603.09901
Post reply on HN