Why haven't quantum computers factored 21 yet?

It’s worth noting that the reason we are deploying PQ crypto is not that we are 100% convinced QC is coming soon. It may or may not depending on how development goes.

The goal of cryptography is to make something as close to theoretically unbreakable as possible. That means even theoretical vulnerabilities are taken seriously.

For ECC and RSA and related algorithms we have a theoretical and physically plausible pathway toward a practical machine that could break them. That means many cryptographers consider them theoretically broken even if such a machine does not exist and may not exist for a long time. The math works even if we can’t build it yet.

So it’s considered prudent to go ahead and upgrade now while no QC exists. That way if some major advance does arrive we are ready.

Nobody’s talking seriously about replacing SHA2, AES, ChaCha, etc because there is no physically plausible theoretically valid path to a machine that can break these in, say, less than many millions of years. AFAIK there is no proof that such a path does not exist but nobody has found one, hence they are considered unbroken.

Note that cryptography is not the only or even the most useful application of QC. Things like physical stimulation of quantum systems, protein folding, machine learning, etc. could be more useful. Like digital computers there’s probably a ton of uses we don’t know about because we need to tinker with the machine to figure them out.

> Things like physical stimulation of quantum systems, protein folding, machine learning, etc. could be more useful

is there still more to do in protein folding after AlphaFold?

https://www.isomorphiclabs.com/articles/alphafold-3-predicts...

There’s a difference between good AI predictions and theoretically perfect QC computations. The AI estimates while the QC will give you the answer, full stop. The latter could be relied upon more strongly. It could also generate infinite training data to make much better models.

QC might be directly applicable to AI training too. It may be possible to compute the optimal model over a data set in linear time. It could allow training that is faster and consumes a tiny fraction of the energy current brute force methods need.

For the symmetric cryptography (so obviously AES and ChaCha, but also in effect the SHA-2 family) we can hand wave the quantum attacks as halving key length by enabling a sort of meet-in-the-middle attack (this attack is why it was 3DES not 2DES when they strengthened DES). There's a lot of hand waving involved. Your real Quantum Computer won't in fact be equivalent cost to the non-quantum computer, or as fast, or as small, the speed-ups aren't quite halving, and so on. But it's enough to say OK, what if AES-128 was as weak as a hypothetical AES-64, and that's fine because we have AES-256 anyway.

However, the main focus is on Key Exchange. Why? Well, Key Exchange is the clever bit where we don't say our secrets out loud. Using a KEX two parties Alice and Bob agree a secret but neither of them utters it. Break that and you can learn the secret, which was used to encrypt everything else - for any conversation, including conversations which you recorded any time in the past, such as today.

If future bad guys did have a Quantum Computer the Key Exchange lets them read existing conversations they've tapped but today can't read, whereas breaking say the signing algorithm wouldn't let them somehow go back in time and sign things now because that's not how time works. So that's why the focus on KEX. Once such a thing exists or clearly is soon to deliver it's important to solve a lot of other problems such as signing, but for KEX that's already too late.

Is there any known quantum exponential speedup for gradient descent?

The predictions don't tell us anything about why the answer is what it is. There is probably important (useful) fundamental scientific knowledge in being able to know that vs. just being able to predict the result.

There have in fact been some results on quantum speedups for machine learning: https://www.quantamagazine.org/ai-gets-a-quantum-computing-s...

I would expect this to become relevant later than crypto, though, because you need larger data sizes for things to get interesting.