Blog

Quantum Computing? Really?

We just had an interesting discussion here about quantum computing, quantum cryptography and post-quantum cryptographic algorithms. I’m afraid that I might have wasted a few people’s time with a rant about why I’m not impressed by the possibilities for quantum computing.

I started by noting my thoughts on how hard it is going to be to build a large-scale quantum computer. Keeping quantum coherence long enough to do significant calculations with quantum computers may turn out to be really hard. As in so hard that we’ll need to create a new level above NP-hard to describe how hard it is.

This thinking might be a bit out of date. I haven’t had a lab where I’ve had equipment that let me play with quantum effects for over 20 years. Things might have become much easier since then, but I still think that it’s going to turn out to be extremely hard to build large-scale quantum computers. Perhaps even impossible. If I had to bet, I’d bet on impossible.

But I also rambled on about why I think that quantum computers are incredibly sloppy because they might be able to accomplish so little with so much.

If you have a register comprising n classical bits, that register can hold any one of 2n possible values. If you replace those classical bits with quantum bits (qubits), that register can hold all possible 2n values at once. An eight-bit register can hold any one of 256 possible values, while a register of eight qubits can hold all 256 of them at once. A 64-bit register can hold any one of 264 possible values, while a register of 64 qubits can hold all 264 of those values at once.

If you’re going to use Shor’s algorithm to factor an n-bit RSA modulus, you roughly need a register comprising 2n qubits. Today, most RSA moduli are of the 2,048-bit variety, so to use Shor’s algorithm to factor one you’d need 4,096 qubits. That’s a lot. Those 4,096 qubits are holding 24,096 values at once. We have that 24,096 is about 101,233. In either form, that’s a very big number.

How big?

There are about 1080 atoms in the visible universe. You can get this number two ways. One involves a SWAG (Scientific-Sounding Guess) of the number of galaxies in the visible universe, the number of stars in the typical galaxy, the mass of a typical star, etc. Or you can derive the number from precise observations made by astronomers. The results are about the same.

I personally find this to be more than slightly annoying. It reminds me more than a little of when I used to work in finance, where we had roughly two types of analysts: quants and cowboys. The quants (like me) were generally introverts who favored their computers over people and who would spend weeks in dimly lit rooms carefully building mathematical models to use to value deals. The cowboys were generally extroverts who drank a lot and just used their intuition to value deals. Annoyingly, there seemed to be absolutely no difference in how well either type of analyst did. So in addition to learning a lot about finance in this particular job, I also learned that life isn’t even close to being fair.

In any event, if you had a quantum computer that holds way more states than the number of atoms in the visible universe, you could use it to crack a 2,048-bit RSA encryption key. You’d think that with that many states you could end hunger, cure cancer, reverse global warning and bring back the TV show Firefly. But you can’t. That’s why I’m not impressed.

End of rant.