Comment by jerf
1 day ago
In addition to the other fine answers, I personally find the additional operations that quantum computers enable to be surprisingly inapplicable to a lot of real problems. It's really kind of unimpressive when you dig down into it. It is not a revolution of computing as we know it, it's a very, very expensive accelerator card for a few niche problems. Neat for people who have those problems. But if "cracking cryptography" wasn't one of those problems I'm not sure it would have the popular attention it does.
I think there is a sense in which we have a historical accident that has make quantum computers sound bigger than they are, in that we ended up with "factoring prime numbers" being the first thing we had to make practical encryption out of, and by what is from a human perspective mostly a coincidence, it so happens that quantum computers may be really good at that. But the problem is that quantum computers happen to be good at factorizing that is the problem, not that quantum computers are somehow "good at breaking encryption". It seams to me that in some sense "post-quantum computing" is actually "all practical encryption schemes except those based on factoring large numbers". Breaking large prime number-based schemes is the exception that QC happens to be good at, not the rule.
this is broadly true. I've heard some criticisms of industrial QC research along these lines, namely that it runs into the issue that its entire TAM ends up being some combination of
1. defense contracting, which can definitely be lucrative, but (hopefully) will dry up quickly after the PQ transition (and especially will if we successfully transition before QCs are advanced enough, which is the goal), and
2. theft, with things like e.g. stealing bitcoins or whatever.
The second is plausibly a large market. It may be difficult to put it on a quarterly report though. So the economic basis industrial QC research may not end up panning out.
it's not just factoring, but general discrete log over abelian groups
Yes, sorry, I didn't mean to imply they could only "factor". But the things they can do that they get the big advantage over classical computing I find underwhelming when considered against the entire scope of computing problems. Again, great for the people who have those problems, but I still am not sure that they are "worth" what are being poured into them in terms of any real economic impact they have. I do wonder if I could trace back all the money in the sector to their original source just how much of it would end up being the intelligence sector who wants their crackz, and how valuable it'll end up being to them in the end if they can't get a decent crack before we all go post-quantum encryption anyhow.
> But if "cracking cryptography" wasn't one of those problems I'm not sure it would have the popular attention it does.
I think it's very funny to consider that if you were a time traveler tasked with making sure that humanity had the economic incentive to develop quantum computers, the most efficient way to ensure that in a single stroke would be by suggesting the use of prime factorization as a trapdoor function to Rivest, Shamir, or Adleman.