That we could have quantum computing "accelerators" in our computers and maybe even smartphones by 2030, just like we're starting to see machine learning accelerators now (or GPUs for graphics processing in the 90's).

You can't just casually assume we'll suddenly figure out how to run qubits at room temperature in 13 years.

For clarification for other readers, the authors of the paper here do not make any claim towards that. They assume a setup where

> the complete structure is maintained at cryogenic temperatures (∼1 K or less) inside an electron spin resonance (ESR) system, which will be used to apply qubit control pulses.

The authors don’t, but the previous post (apparently) implicitly assumes it (or fails to understand what maintaining quantum coherence entails, or both).

Uh finally! Thanks for explicating this so succinctly and adroitly. I'm driven spare by the “quantum computers everywhere [because] Moore's Law bla bla bla” attitude.

So what kind of stuff can we do with that?

Nothing significant until we have many more qubits. With 128 qubits you could crack 128 bit RSA encryption in a few mins.

I've thought for a long time that this explains why the NSA is recording so much encrypted data. When QCs are available they will be able to decrypt all the things. Imagine what they'll learn.

That’s a bit conspiracy-theorist-ish but unfortunately in the present climate and given that has transpired from the Snowden leaks not at all implausible.

Either they have made a breakthrough in number theory that allows factorisation over finite fields, or they have a quantum computer already, or they are banking on having one soon. In any case, storage is so cheap that it makes sense to just record the traffic (which is useful for sigint anyway) and refer back to it “if and when”.

Of course, much of what we consider “public-key encrypted” traffic is actually encrypted with a symmetric cipher whose encryption is impervious to Shor’s Algorithm… it is the key-exchange process that really uses the textbook public-key encryption algorithms. So much of the traffic is technically impervious to whatever advances they have made, but of course once you have captured the key-exchange “handshake” that sets up the session and exchanges the symmetric cipher keys, you’re all set to retrieve the plaintext from the intercept.

There are public-key algorithms (particularly those based on lattices) that we currently hold to be secure against attack by quantum computers. I am surprised these are not seeing more adoption amongst the “enlightened paranoid cypherpunk elite”. Here is a primer on such “post-quantum cryptography” approaches, courtesy of the good folks at Wikipedia: https://en.wikipedia.org/wiki/Post-quantum_cryptography

In the process they'd get key exchanges too and it's easy to correlate traffic.

I thought it was a really straightforward obvious idea. I'd do it if I were them and had such deep pockets.

QC is clearly coming. Lots of news lately.

I was agreeing with you, of course if they have intercepted all traffic they have both public-key encryption key exchange and the resulting symmetrically encrypted traffic and that they could correlate it... I’m sorry if I was a bit longwinded and pedantic in my reply, I didn’t realise I was talking to virtual Hacker News nobility (with ten times the karma I do!).

Hacker News nobility is a dubious title haha.

Btw on post quantum crypto: the problem is that most of it has not yet had enough conventional cryptanalysis. Makes no sense to use an algorithm immune to quantum speedup if it's conventionally vulnerable.

Yeah I know, I’m no expert, but I studied applied mathematics.

What would be nice book / video / web link that will give a decent intro to a novice like me?

citation? A theoretical understanding of bits in quantum superposition would support the notion of traversing all combinatorially related possibilities however that is not the case for any realizable quantum computer. Realizable machines are based on specific quantum logic gates. otherwise you would have to design at the electron level, a new processor for every problem.

Here's the citation: https://en.wikipedia.org/wiki/Shor%27s_algorithm

You do need to update yourself. There are standard gates, complete computation theories, and algorithms for lots of interesting problems. Those aren't even new.

aes isn't broken by factorization of composites of prime. if the op had said rsa, sure, but they said aes (it was changed you can tell because there was never such a thing as 128bit rsa), but thanks for telling me about that "new" shor's algorithm devised in 1994.

Yes, comment edition sometimes leads to misunderstanding. But there was 128bit RSA, it was in use up to the middle of the 00's.

One claim is the near instant factoring of large integers...breaking a class of encryption that's widely used currently.

Quantum computers can be used to simulate quantum physics and approximate solutions to optimization problems.

Honest question: Why would the average person want/need to do that with their smartphone or computer?

Why would someone want more than 640k of RAM?

My thoughts exactly.. We don't know we need it till its to indispensable to remove. Only god knows what we could do with quantum computers. There are some low hanging fruit with encryption and quantum simulation.. but hey maybe it can be used in random world generation for games like minecraft.

The average person would probably not find a lot of use from those applications; but researchers will.

They wouldn't.

That's what Ballmer thought about iPhone.

not all that much unless you're in the field, in which case it's pretty cool.