[tialaramex]

> which seems probable, as we are progressing fast in the number of qubits we can keep together

Are we? Every so often I check back to see how well they're doing with actually running Shor's algorithm. In 2012 they managed to find that 21 = 3 x 7. And today... 21 = 3 x 7. That doesn't sound like progressing fast.

Quantum annealing is doing well for itself, but it isn't any sort of threat to encryption.

[krastanov]

We definitely are getting closer. Look at any graph of "qubit lifetime" and you will see how we have orders of magnitude improvements. (a quick google search gives me page 9 of https://hpcuserforum.com/presentations/tuscon2018/QCOverview...). We still need a couple more orders of magnitude before the qubits are useful, but the signs of exponential progress are unmistakable.

I would not take any experiment performing Shor's algorithm today or in the past particularly seriously, since they would probably be showing something fine tuned for the particular instance of the problem (e.g. 21). We do not have anything that can be called an "error-corrected logical qubit", and we need this before we can make serious claims about running algorithms like Shor's.

[mlyle]

So if we extrapolate out the current curve 2 more orders of magnitude, it looks good. Therefore we can conclude it's looking possible? ;)

[beambot]

For historical precedence, see "Moore's Law"

Talking to experts in the field, we're doubling the number of functional qbits (ie accounting for error correcting requirements) about every 12 months right now. Looks like current number is 16-qbits, where many algos get "really interesting" around 1000 qbits (and functional even before that). So 5-6 years until a potential total transformation in computing paradigms. Quantum is in a similar place as deep learning in 2012.

[mlyle]

Exponents don't continue forever in the real world.

It's anyone's guess to how far we go, but generally extrapolating a curve far off the current reading is a case of innumeracy.

[beambot]

Obviously. However, Moore's Law held for 40+ years. We are at 16 qbits in quantum vs single silicon chips with 1.2Trillion transistors. Clearly some room for growth, especially given the $Billions in annual investment being poured into quantum.

[paggle]

There are some areas where 100x improvement is almost inevitable: self-driving cars, facial recognition, etc. You don’t need to be a genius to see it.

[mlyle]

?? Facial recognition is very good already; how would we define a 100x improvement? A 100x reduction in error rate? NIST benchmarked current implementations at a 0.2% error rate with massive databases--1 in 500-- you're saying that you're really confident we'll reach a 1 in 50,000 error rate?

More generally: nothing is inevitable, especially when we're talking about orders of magnitude. Maybe it happens as quickly as we'd hope, maybe it doesn't. Maybe it doesn't even happen in the near to intermediate future at all. That goes for self-driving cars, quantum computers, general artificial intelligence, or whatever.

Moore's law was inevitable, until it wasn't.

[krastanov]

Yes, two or more orders of magnitude of improvement are very much expected by most researchers in this field, simply because the current state of the hardware is infantile compared to what we know is possible (it just takes a lot of work to put all the different improvements in a single experiment).

[mlyle]

That's a completely different argument. "Researchers think we'll get two more orders of magnitude in a reasonable time" is quite different from saying "if we extrapolate this curve, we'll get there in 5 years". After all, exponents describe growth until they don't-- eventually we reach physical or economic limits (Moore's law has tapered off; bacteria in a dish of agar show exponential growth until they don't anymore, etc.)

I highly doubt we'll get there in 5 years, myself.

[Avamander]

We can conclude that if we're optimists.

[solveit]

We conclude it's looking possible because fundamental physics says it should be possible.

[sweeneyrod]

Damn, looks like I should stop using 21 as my PK then.

[nielsole]

Not sure what algorithm you use for encryption, but 21 doesn't look like a prime. Maybe run a Miller Rabin test on it? ;)

[sweeneyrod]

It's the modulus of my RSA PK, so the product of two large primes rather than a prime itself. Of course, I can't say what the factors are, otherwise anyone could crack it even if they don't have a quantum computer!

[neuralzen]

Just XOR 21 times, problem solved!

[myle]

Always with the same mask, to make sure it is applied well.