How Classical Cryptography Will Survive Quantum Computers

Justin Trudeau, the Canadian prime minister, certainly raised the profile of quantum computing a few notches last year, when he gamely—if vaguely1—described it for a press conference. But we’ve heard a lot about quantum computers in the past few years, as Google, I.B.M., and N.A.S.A., as well as many, many universities, have all been working on, or putting money into, quantum computers for various ends. The N.S.A., for instance, as the Snowden documents revealed, wants to build one for codebreaking, and it seems to be a common belief that if a full-scale, practical quantum computer is built, it could be really useful in that regard. A New Yorker article early this year, for example, stated that a quantum computer “would, on its first day of operation, be capable of cracking the Internet’s most widely used codes.” But maybe they won’t be as useful as we have been led to believe.

Quantum computation is based on the superposition principle of quantum physics. Bits in a normal computer are either 0 or 1. Quantum physics allows bits to be in a superposition of 0 and 1, in the same way Schrödinger’s cat can be in a superposition of “alive” and “dead.” This sometimes lets quantum computers explore possibilities more quickly than normal computers. For a general search problem, such as trying to find the key to a secret code by trying all of them, quantum computers are expected to have quadratic speed-up. For example, the Advanced Encryption Standard, approved by the United States government, has up to 2256—or about a 1 followed by 77 zeros—keys. A quantum computer could make that same search as if there were only 2128 keys—about a 3 followed by 38 zeros. On the one hand, that’s a lot faster. On the other hand, it’s still an awful lot of searching to do.