Remix clone Hacker News

What's the rough bit count of the largest numbers anyone's quantum computer can factor today? Breaking RSA2048 would be a huge breakthrough, but I'm wondering if they can even factor `221 = 13*17` yet (RSA8).

And as I've mentioned elsewhere, the other QC problems I've seen sure seem like simulating a noisy circuit with a noisy circuit. But I know I don't know enough to say that with confidence.

▲

Strilanc 2 days ago | parent [-]

Like I said above, the size of number that can be factored will sit still for years while error correction spins up. It'll be a good metric for progress later; it's a terrible metric for progress now. Too coarse.

▲

xscott 2 days ago | parent [-]

Heh, that seems evasive. Good metric or not, it makes me think they aren't at the point where they can factor `15 = 3*5`.

I'm not trying to disparage quantum computing. I think the topic is fascinating. At one point I even considered going back to school for a physics degree so I would have the background to understand it.

▲

Strilanc 2 days ago | parent [-]

I'm not trying to be evasive. I'm directly saying quantum computers won't factor interesting numbers for years. That's more typically described as biting the bullet.

There are several experiments that claim to factor 15 with a quantum computer (e.g. [1][2]). But beware these experiments cheat to various degrees (e.g. instead of performing period finding against multiplication mod 15 they do some simpler process known to have the same period). Even without cheating, 15 is a huge outlier in the simplicity of the modular arithmetic. For example, I think 15 is the only odd semiprime where you can implement modular multiplication by a constant using nothing but bit flips and bit swaps. Being so close to a power of 2 also doesn't hurt.

Beware there's a constant annoying trickle of claims of factoring numbers larger than 15 with quantum computers, but using completely irrelevant methods where there's no reason to expect the costs to scale subexponentially. For example, Zapata (the quantum startup that recently went bankrupt) had one of those [3].

[1]: https://www.nature.com/articles/414883a

[2]: https://arxiv.org/abs/1202.5707

[3]: https://scottaaronson.blog/?p=4447

	▲	xscott 2 days ago \| parent [-]
		Thank you for the reply and links. Good stuff.