Quantum computation has also attracted commercial interest. At current rates of progress, big, code-breaking quantum computers are at least a decade away, so the private sector is focusing on two types of quantum computation that are easier. The first nontrivial type of quantum computing was proposed by the Nobel laureate Richard Feynman in 1981. Feynman was studying how quantum processes in high-energy physics could be simulated. He noted that classical computers were bad at the job, for the same reason that human beings find quantum mechanics counterintuitive: there is no easy way for either to represent a bit that registers 0 and 1 at the same time. Feynman suggested that if the computer were quantum-mechanical, it might have an easier time dealing with quantum processes. In 1996, I showed that Feynman was correct and created algorithms that would allow a quantum computer to simulate solid-state, chemical, and high-energy systems. Such a simulator would require only a hundred qubits or so to be able to surpass all conventional supercomputers.
A second type of quantum computing, known as adiabatic quantum computing, is not only easier than code breaking but potentially far more powerful. Adiabatic quantum computing is a particularly physical way of trying to solve hard problems.
Like all physical systems, electrons would rather inhabit lower energy states than higher energy states, particularly at low temperatures. The energy of a physical system such as an electron depends on the states of its neighbors. One electron might tell its spinning neighbors, “For a lower energy, spin clockwise.” Another electron might say, “For a lower energy, spin counterclockwise.” The lowest energy state for the spinning electrons as a community is the one that minimizes the total number of conflicts between neighboring spins. For a group of electrons to find their communal lowest energy state, or “ground state,” they must find ways to agree on how to align their spins. In the same way that a complex computational problem can be broken down into flipping bits, it can be posed in terms of finding the ground state of a suitable physical system.
Adiabatic quantum computation attempts to represent problems as the disturbance of a quantum system, so that the answer is represented by the system’s assumption of a new ground state. Developed by Eddie Farhi and Jeffrey Goldstone at MIT and Sam Gutmann at Northeastern University, it works by initializing the quantum system to a simple ground state (all spins rotating clockwise, for example) and then gradually, or “adiabatically,” turning on the interactions that encode the problem. If this turning-on process is sufficiently slow, the system will gradually “ooze” from its simple initial state into the complex final state.
The most interesting aspect of adiabatic quantum computation is that no one knows for sure whether it works in practice. It may be that for any meaningful problem, the system would have to ooze so slowly that it would take the age of the universe to return an answer. Conversely, it may be that even the hardest problem will succumb to an adiabatic quantum computer. Despite the concerted attention of a bevy of physicists and mathematicians, the question of whether adiabatic quantum computing works remains open. Most experts suspect that it can’t solve the very hardest computational problems. But suspicion is not proof.