Google announced a breakthrough on the way to building usable and useful quantum computers.
Since I'm not a cryptographer, I wanted to ask when quantum computers will be able to break the crypto algorithms used today and whether this breakthrough has significantly changed the predictions.
Also, when will good post-quantum crypto libraries be available so that programmers can slowly begin replacing currently used crypto with post-quantum cryptography or go with a hybrid solution?
Since I'm not a cryptographer, I wanted to ask when quantum computers will be able to break the crypto algorithms used today and whether this breakthrough has significantly changed the predictions.
No, despite being on the front page of Nature, Google's result has no impact on cryptography for the foreseeable future.
The news about the (rather regrettable) term ‘quantum supremacy’ means that Google claims to have demonstrated ‘solving’ some problem on a quantum computer faster than anyone has been able to solve that problem on a classical computer. In one sense, this is a remarkable achievement, because nobody had been able to do it before. In another sense, it is the tiniest achievement imaginable: after decades of research, they found a problem, among all possible computational problems one might imagine whether or not solving it has any utility whatsoever, that they were able to demonstrate a quantum computer is better at than a classical computer. (Maybe ‘quantum non-uselessness’ would be a better term than ‘quantum supremacy’, or perhaps ‘quantum non-futility’ since the problem they found is not terribly useful itself.)
The ‘problem’, in this case, is, given a random quantum circuit of about 50 qubits chosen by a challenger, to apply it on an all-zero initial state, and measure the result in the $\{0,1\}$ basis. A choice of quantum circuit gives rise to a probability distribution on the outputs of this procedure—run the circuit on all zero inputs, measure the result in the $\{0,1\}$ basis—and nobody has shown a way to sample from this distribution as efficiently on a classical computer. The results are then verified by statistical tests computed using classical simulation with about $2^{50}$ computations (which puts a bit of a damper on the prospect of verifying results like these on, say, 100-qubit circuits).
What Google has not demonstrated is anything that is useful for running quantum circuits like Grover's algorithm or Shor's algorithm, which requires substantially larger numbers of qubits and error correction at a scale we're nowhere near. For more details, see Scott Aaronson's Supreme Quantum Supremacy FAQ.
To the best of my knowledge, no quantum computer has ever factored a number larger than 21 using Shor's algorithm, and there's no reason to suspect that other quantum factoring methods will meaningfully scale; see fgrieu's past answer on quantum factoring records (which I hope he will keep updated if the literature changes so I don't have to!). Scott Aaronson estimates that if configured to run Shor's algorithm, Google's quantum computer could maybe manage factoring a number ‘up to the hundreds, depending on how much precompilation and other classical trickery was allowed’
Also, when will good post-quantum crypto libraries be available so that programmers can slowly begin replacing currently used crypto with post-quantum cryptography or go with a hybrid solution?
Symmetric-key cryptography is not seriously threatened by quantum computers as long as you already meet a classical 128-bit security level by using ≫128-bit keys like 256-bit keys, which you're already doing, right?
There is an ongoing competition, NIST PQC, to settle on candidates for standardization of post-quantum public-key cryptography—encryption, key agreement, and signatures. Aside from the NIST PQC candidates' reference implementations, available via the NIST PQC web site and in SUPERCOP, there are also some prototype libraries of post-quantum cryptography candidates, such as liboqs (open quantum safe), and experiments in deployment in protocols such as SSH and TLS.
It's still probably going to be a while. That's for 53 qubits. For proper error handling they'd probably need somewhere between 2,500 and 3,000 qubits to break 2,048 bit RSA.
As for libraries, NIST is working on standardizing post quantum algos now. They think they'll have standards ready sometime between 2022 and 2024. Decent implementations will probably be ready concurrent with the standard and good implementations a year or two later. Absent some significant breakthrough, the algorithms and libraries should be ready before they're needed.
