Live data from Hacker News

The “JVG algorithm” only wins on tiny numbers

scottaaronson.blog

31–40 of 56 posts

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

#31
post #5

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

This might not be something entirely obvious to people outside of academia, but the vast majority (which I'm only weakening a claim of "totality" in order to guard against unknown instances) of entities that bear the name of humans in the sciences do so because other people decided to call them by that name.

From another view, Adelson-Velsky and Landis called their tree algorithm "an algorithm for the organization of information" (or, rather, they did so in Russian --- that's the English translation). RSA was called "a method" by Rivest, Shamir, and Adleman. Methods/algorithms/numbers/theorems/etc. generally are not given overly specific names in research papers, in part for practical reasons: researchers will develop many algorithms or theorems, but a very small proportion of these are actually relevant or interesting. Naming all of them would be a waste of time, so the names tend to be attached well after publication.

To name something after oneself requires a degree of hubris that is looked down upon in the general academic community; the reason for this is that there is at least a facade (if not an actual belief) that one's involvement in the sciences should be for the pursuit of truth, not for the pursuit of fame. Naming something after yourself is, intrinsically, an action taken in the seeking of fame.

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

#32
post #15
post #6

Earlier quoted context omitted.

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

Leonhard Euler has entered the chat: https://en.wikipedia.org/wiki/List_of_topics_named_after_Leo...

[deleted]

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

#33

Earlier quoted context omitted.

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)

Yeah I think GP might now prefer his statement(s) to have been about "quantum _advantage_". Which is the modish term after all.

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

#34
post #7

Earlier quoted context omitted.

Hey hey, 15 = 3*5 is factoring.

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

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

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

#35

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.

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

#36
post #11
post #5

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

Named after != named by

> Named after != named by

But also note that naming an algorithm, in and of itself, is fine; it's naming it after yoursel(f,ves) in the initial paper that's a sign of crackpottery.

* Named by: Probably fine but heavily weighted on the grandiosity of the title.

* Named after: Almost certainly fine (unless it's something like "X's Absolute Drivel Faced Garbage That Never Works Because X Kidnapped My Dog And Is A Moral Degenerate Algorithm", obvs.)

* Named by yoursel(f,ves) after yoursel(f,ves): In the initial paper? Heavy likelihood of crackpottery. Years later? Egotistical but strong likelihood of being a useful algorithm.

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

#37

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.

Well, the reviewers missed it too.

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

#38
post #37

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.

Well, the reviewers missed it too.

What reviewers? It's not a peer reviewed article.

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

#39
post #37

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.

Well, the reviewers missed it too.

[deleted]

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

#40
post #6
post #5

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

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

The RSA authors didn’t name the algorithm after themselves.
Post reply on HN