In the 1992 movie Sneakers, hackers discover a device that can break the encryption of virtually any computer system. At the time of release, the idea seemed far-fetched. But today, because of quantum computers, we may soon have a similar device.
Quantum theory is now approaching its 100th anniversary, with the central tenants of the theory having been well-established by the mid-1920s. Together with general relativity, quantum theory is one of the foundational theories of modern science. Our modern world would not be possible without quantum theory: It’s central to the design of semiconductors, lasers, MRIs, and even LEDs.
However, most of us have been able to ignore the strange implications of quantum physics. In one interpretation, conscious observation “collapses” probabilistic wave functions into concrete particles—suggesting that consciousness might somehow create reality. A competing and increasingly popular explanation for quantum behavior is that multiple universes are continuously being created whenever a quantum event occurs. This “many worlds” theory is the basis for the proliferation of “multiverse” movies such as the Academy Award-winning Everything Everywhere All at Once.
While quantum computing has been integral to computer hardware design, it has had little effect on software. But that will soon change. According to most experts, within 10 years or so, quantum computers will break existing encryption algorithms.
Most public key encryption schemes are based on the difficulty in factoring large numbers: that is, finding prime numbers that can be multiplied together to give that large number. Given a public key, you could deduce the corresponding private key if you could quickly find all the factors for the public key. However, for existing computers, that problem is computationally costly: The largest key “brute forced” in this manner was 829 bits, and that took 2,700 “core-years” (e.g., it would have taken 2,700 years for a single-core computer).
For traditional computers, the time taken to factor a public key increases exponentially with each bit added to the key. So even as CPU speeds increase, we can easily outpace that growth by using longer keys.
However, a quantum computer can theoretically factor large numbers very quickly. Existing quantum computers can do this only for very small keys. The number of “qubits” in a quantum computer (analogous to the number of bits in a traditional computer) limits the size of the numbers that can be factored. IBM’s Osprey quantum computer, for instance, has 433 qubits—about 1/10th of what would be needed to break existing encryption.
The challenges involved in building larger quantum computers are non-trivial. Quantum computers need to run at close to absolute zero temperature (-273° Celsius) and need to be kept isolated from vibration or other “noise” that can interfere with quantum processing.
Nevertheless, it seems reasonable to assume that within a decade or so, quantum computers will exist that can break existing encryption schemes.
Just because encryption-breaking quantum computers exist only in the future does not mean we don’t have a problem now. Most information being encrypted today will still need to be encrypted in the future. Therefore, the industry is working on quantum-safe encryption algorithms that can be adopted immediately. The National Institute of Science and Technology (NIST) has been working for some time on establishing standards for post-quantum algorithms, and it’s virtually certain that standards for post-quantum computing signatures will be available well before quantum computers are developed that can break existing keys.
In some respects, a quantum computer can be considered a sophisticated, highly parallelizable computational device.
However, the fact that quantum computers work at all is still mind-boggling. Under one of the dominant interpretations of quantum theory, a quantum computer works by performing calculations in parallel across multiple universes. If that doesn’t blow your mind, I don’t know what will!