Hacker News Reader

Comment by m3kw9 | Hacker News Reader

I’ve tried many quantum 101 read up’s and e-books, im gonna take yet another shot of finally understanding even the basics.

View on HN

But why? I don't think it's worth it. Shor's algorithm is great, but 1. it's not clear we'll ever have quantum computers capable of implementing it for any meaninful number of bits 2. it can't be generalized to other encryption schemes and 3. we don't use RSA anymore. The other algorithms that can benefit from quantum computers don't provide an exponential speedup like Shor's algorithm, but rather speed up from quadratic to linear. That's not a good enough reason to start using a completely new paradigm.

By the way, I took a graduate course in quantum computation more than 20 years ago. People were equally gung-ho about quantum computation then. Not much has changed in the meantime. Quantum computation remains equally "just around the corner" now as it was then.

Shor's algorithm can break RSA, Diffie-Hellman, and elliptic curve DH. Some researchers believe it can be generalized to break lattice-based crypto.

QCs also useful for quantum simulations.

> The other algorithms that can benefit from quantum computers don't provide an exponential speedup like Shor's algorithm, but rather speed up from quadratic to linear. That's not a good enough reason to start using a completely new paradigm.

That entirely depends on how big N is.

There's also the point that we only know about quantum algorithms that have already been discovered despite the almost complete absence of working quantum computers.

I don't think too many classical algorithms were discovered before we had access to classical computing either. (I could be wrong).

Many classical algorithms were discovered before we had access to classical computers, but that's because we were doing classical computing by hand, and that made them useful and thus people looked out for them.

Quantum computers are different, because we have reason to think that they can scale exponentially faster than "follow these steps on pen and paper, but more faster", unlike classical computers.

>...we don't use RSA anymore.

This very website is using RSA for TLS authentication. There are lots of applications where the longer key generation time and longer keys of RSA are not an issue. RSA is pretty common. Which is a good thing. We don't want to put all our eggs in one basket.

Forget breaking cryptography, that's what the media cares about but there is no social value in it. (Although it's worth noting it breaks every public key cryptosystem used today, not just RSA)

The real applications are in simulating other quantum systems for drug discovery etc.

Shor's algorithm is actually very generalizable, it applies to any crypto based on the hidden Abelian subgroup problem, and it is believed by many that analogous algorithms exist for most promising asymetric crypto we are planning on using.

quantum computers provide exponential speedup on all asymmetric crypto currently in use (and the quantum resistant algorithms being finalized by nist are very likely broken).

The way I see it is that in the future, we will need a quantum computer to run Slack, instead of a quad-core classical cpu to run Slack. Any performance gains will be negated by bad programming.

Reply on news.ycombinator.com