https://www.scottaaronson.com/blog/?p=4317

I feel like Scott's FAQ needs its own FAQ

Q. So, I heard on twitter there was some big news about quantum computing. Is that for bullshit?

A. Until now I've basically assumed all big announcements about quantum computing are bullshit and haven't been proved wrong yet.

Q. And this one?

A. Scott Aaronson thinks its for real and he's generally right about this sort of thing and not prone to quantum bullshit.

Q. So... wtf is "quantum supremacy"

A. This sounded like super bullshit to me, but according to wikipedia, it's a term for a quantum computer which can solve a problem no existing non-quantum computer can.

Q. So... that happened?

A. Scott Aaronson thinks so. The official publication hasn't happened yet.

Q. And this is... out of nowhere?

A. It sounds like no, actually, just that the number of qubits in quantum computers was slowly growing until through some engineering brilliance they reached the point of being able to do non-trivial calculations. But having a quantum computer which is actually better than a classical computer at SOMETHING is still pretty impressive.

Q. So... better at what?

A. Um... some contrived problem made up to specifically show that there's something quantum computers can do and classic computers can't.

Q. Oh. But, like, it really is, a problem you can try and solve on a classic computer and fail and try on a quantum computer and succeed?

A. Apparently so.

Q. Apparently?

A. That's basically the situation. No-one can PROVE you can't do it on a classical computer: no-one's even proved large travelling salesman problems or other NP-complete/NP-hard problems are impossible for classical computers yet. But no-one expects otherwise.

Q. Any other big caveats?

A. Apparently this particular problem is probabilistic, you sample the result N times and show it's more-likely-than-chance in the right answer.

Q. And how do you know what the right answer is? Is this a hard-to-find-each-to-check thing?

A. That's what everyone hopes to reach in future, but sadly no, apparently this is a "solve it in seconds on a quantum computer, then simulate the quantum algorithm in months of giant compute clusters on classical processors, check the results match"

Q. But then you CAN do it on a non-quantum computer. Wasn't the point to find a problem you can't?

A. Yeah. But (a) with this method, if they build a quantum computer even slightly bigger, it would be unmatchable, but then they wouldn't have any way of checking the answer and (b) if the method works and it is seconds vs months, everyone agrees that is quantum computers doing something useful.

Q. So, does this break crypto?

A. Not for a while yet. They'll need a fair bit bigger quantum computers to make that practical.

Q. But those are coming?

A. I don't know, but it sounds like it.

Q. And that breaks all crypto?

A. Of course not.

Q. It breaks all crypto we use in real life at the moment?

A. No.

Q. But?

A. It would break MOST crypto we use at the moment. Anything that lets you set up secure crypto without secretly sharing a key in advance.

Q. Wait, not just RSA, other systems too?

A. Apparently the same factoring works there too?

Q. But someone will come up with some crypto which quantum computers don't help against?

A. As I understand it, we expect that from a theoretical point of view, but people haven't actually got round to it yet.

Q. Do the NSA have a bigger quantum computer?

A. I really don't know. I think installing spyware everywhere is probably easier. But they're filled with ethics-flexible maths nerds who'd probably WANT to build a big quantum computer.

Q. So what are the next steps after this?

A. Quantum computer with more bits. Solving a less contrived problem or finding a problem to solve that can actually be checked. Working out how many extra quantum bits you need to account for errors from losing the coherence of your qubits (10% more? 1000000% more? somewhere between?). Eventually, getting a computer that can run Shur's factoring algorithm, and breaking existing cryptosystems in practice. Find a problem that's actually useful -- not sure what that is, but modelling some physical processes?

You can also comment at https://jack.dreamwidth.org/1112208.html using OpenID. comments so far.