Computers process information by breaking it down into the smallest possible chunks, called “bits.” A bit represents the distinction between two possibilities: True and False, Yes and No, or, as they are conventionally represented, 1 and 0.
The end point of Moore’s Law (which holds that computers get faster by a factor of two every year and a half or so) is a computer so powerful that it uses individual atoms to store bits of information: one atom, one bit. If we were able to work at subatomic scales and store bits on electrons or quarks, we might go further. But let’s stick with what we know we can do.
If current rates of miniaturization persist, your PC will store one bit on one atom sometime around 2050. But it’s natural to ask whether we can, in fact, achieve a bit-to-atom correspondence. Remarkably, prototype computers that store bits on individual atoms already exist in the laboratory. These computers are called quantum computers, because they store and process information at scales where the laws of quantum mechanics hold sway.
Quantum mechanics is the branch of physics that governs what happens at very small scales. Its principles are famously weird, so it’s natural that quantum computers should be odd, too. A conventional electronic computer, in which each bit registers either 0 or 1, is enslaved by binary logic; but a quantum bit, or “qubit,” can register 0 and 1 at the same time, a phenomenon known as “superposition.” What does it mean for a quantum bit to simultaneously register 0 and 1? The accurate answer is, nobody knows for sure. The counterintuitive nature of quantum mechanics prevents our minds from grasping how quantum bits behave. Nonetheless, because the laws of quantum mechanics are precisely formulated, we can predict what quantum computers will do.
And what they do is remarkable. Since one qubit can simultaneously represent two different values, two qubits can simultaneously represent four (00, 01, 10, and 11, in binary notation); four qubits can represent 16 values; eight qubits 256 values; and so on. Even a relatively small quantum computer, one that had a few tens of thousands of qubits, could consider so many different values at once that it would be able to break all known codes commonly used for secure Internet communication. Quantum computers might also be used for faster database searches, or to tackle hard problems that classical computers couldn’t solve with all the time in the universe. My colleagues at MIT and I have been building simple quantum computers and executing quantum algorithms since 1996, as have other scientists around the world. Quantum computers work as promised. If they can be scaled up, to thousands or tens of thousands of qubits from their current size of a dozen or so, watch out!
Given their power to intercept and disrupt secret communications, it is not surprising that quantum computers have the attention of various U.S. government agencies. The National Security Agency, which supports research in quantum computing, candidly declares that given its interest in keeping U.S. government communications secure, it is loath to see quantum computers built. On the other hand, if they can be built, then it wants to have the first one.