[sgt101]

We need PQC about 20 years before practical, scalable gate quantum computers appear (if they can do all the right gates).

I think that this will be signaled when someone factors a 32 bit integer on one. At that point I guess it'll be about 20 years before someone can factor a 2048 bit integer, and I'll get twitchy about what I am sending over the wire with PKI. My feeling is that all my secrets from 20 years ago are irrelevant to life now so I feel 20 years of warning is quite sufficient.

[adastra22]

We are within 20 years of scalable quantum computers already.

[adrianN]

The record for integer factoring on quantum computers was on the order of factoring fifteen into three times five the last time I checked. Can we do three digits now?

[eigenket]

Significantly larger numbers than 15 have been factored [1] but not using Shor's algorithm. Shor's algorithm is particularly sensitive to noise/errors in your quantum computer and isn't going to be useful unless we get a properly error corrected machine working. The algorithms used in [1] are considerably less fancy (with worse asymptomatic performance) but are more resilient to noise.

[1] https://arxiv.org/abs/2012.07825

[tsimionescu]

I couldn't quickly find any info, but does this algorithm show the kind of exponential quantum speed up needed to break RSA? Because if it's just slightly faster than the best known classical algorithms, then it's enitely irrelevant to the question of when we need to switch our encryption schemes (even though it may be a significant advancement in the area of quantum algorithms research).

[eigenket]

I think its unknown, but my feeling is that the answer is almost certainly no.

These sort of variational algorithms are appealing (to some people) because they're potentially usable on the sort of noisy small quantum computers we have today and in the near term future, but they aren't very fancy. I think in general what you'd expect to get out of them is a sort of Grover's algorithm-like square root speedup.

[adgjlsfhk1]

it's generally believed that the algorithm is somewhere in between ecm and quadratic sieve (so slower by a super-polynomial factor than NFS which is the best classical algorithm)

[adgjlsfhk1]

that paper is factoring with an algorithm that almost certainly isn't polynomial time. That paper is only slightly better than the quantum factoring algorithm of making a quantum computer perform trial division.

[eigenket]

I agree

[adastra22]

And to extend off this comment, there are methods being worked on for building qubits that are intrinsically noise-free and don’t need the exponential number of error correcting operations. When those are available, you’ll see a step function increase in capabilities.

[s1dev]

For a circuit of size C, the size of a fault tolerant circuit to compute the same thing is O(C polylog C)

https://arxiv.org/abs/quant-ph/9906129

[adastra22]

Technically correct is the best kind of correct.

[andrepd]

>When those are available

Pretty big if

[adastra22]

We’re working on it.

[sgt101]

Interesting - why is Shor's sensitive to noise? Is that the Rphase gates?

[eigenket]

Yeah, for Shor's algorithm to factor an integer of order 2^k you need controlled phase gates with phases roughly order 2^{-k} (very roughly, with some caveats, but lets just say you need some small ones) these very small phase gates are susceptible to even very small errors.

This is a gross oversimplification. For the true version see here

https://arxiv.org/abs/2306.10072

[sgt101]

Took me a while to read it - seems to be a pretty significant take down of anything that uses a QFT - basically reality won't permit it.

[ziofill]

This is a minority point of view on quantum computing, as I understand.

[sgt101]

thank you

[vikramkr]

I'm not sure that's the right question. It's more, is there a chance at all of anyone figuring it out, and given the enormous scale of the security risk that poses, we should start proactively mitigating those threats. If fusion energy goes from perpetually 10 years away to suddenly here, that's pretty much just a white swan. If quantum computers happen, that's a global security risk before it's a civilizational upgrade.

[baby]

The last time I checked they even cheated to factor fifteen

[WJW]

You should check again. Numbers like 1099551473989 have been factored successfully by now. The arxiv link in the sibling post is a good start.

[adgjlsfhk1]

biggest number factored by a quantum computer isn't the right question. the right question is biggest number factored using a polynomial time algorithm. the answer to that as far as I know of still 15 (although I would be interested in papers that show more progress)

[sgt101]

This is one of the things I really resent about QC as a field - there's so much chaff where one paper will say "we can do x" and the reality is that x does not mean what everyone thought that they meant. Number of Qbits is another thing - also what gates are implemented in the devices; how long they can run for etc etc etc.

[adastra22]

Application of Shor's algorithm is currently limited by available error correction. Long-lived qubits would eliminate that need and drastically increase capabilities.