Quantum Computers
The term quantum, from physics, originated in a breakthrough scientific discovery a century ago. It is, unfortunately, somewhat mysterious for some people who may need to use the term in a technical context. The following is a cursory glance into quantum computing from the viewpoint of a classic computer architect. Getting into physics is avoided on purpose.
Energy, a primal feature of the physical world, seems to “condense” or form matter in discrete definite amounts called quanta. Also, the resulting particles, the building blocks of matter, seem to behave similarly at a small scale, e.g., spin or acquire/release energy in fixed amounts. This quantum behavior, among many, was astonishing at first. There would be other even less familiar behaviors at the quantum scale. The physical world at the scale with which humans interact and above behaves very differently. It seems to change continuously at those scales. Our electronic computing machines also behave in ways consistent with the direct human experience of the world.
Conventional computers switch between two distinct and deterministically time-sequential states. In other words, the binary states are separate in time. They are always observable separately with certainty. These states usually derive from a large-scale physical behavior, such as the flow of electrons in a semiconducting material. Only two are considered, in a mostly ignored analog continuous behavior, to simplify the logical analysis of the system [Feynman Lectures on Computation, Westview Press 1996]. In a quantum computer, the focus shifts to more atomic (i.e., at the particle level) quantum properties like spin or position.
Quantum properties have physical states that are only distinguished probabilistically. Those states overlap in time in unfamiliar ways, not in line with how we experience the physical world. At times, the physical properties behind the quantum states may not be observable with certainty like those that non-quantum computers rely on. Hence, in addition to the familiar binary states encoded logically as 0 or 1, they effectively introduce a third physical state that is neither 0 nor 1 with certainty. The desired computation occurs at this quantum state. Maintaining it is not easy. It is a big challenge for the quantum machine.
Clearly, quantum computers demand very different technology. What may be less obvious but more important is the fundamental change in the underlying switching behavior of the physical machine. Rapidly changing states that overlap in time are naturally parallel at a level lower than a computation. Switching is much faster but also, unfortunately, much more difficult to predict and control.
Quantum switching promises to overcome the polynomial efficiency limitation of conventional computers. In those machines, the solution time must grow like a polynomial function of the input size to solve arbitrary instances of problems in a reasonable time. The new machines will need new algorithms to exploit different physics, however. Applications that suffer from the limitation should see significant advantages. Those who rely on it, most notably secure computing, will face a huge problem.
Some experts thought at times that quantum computers would be the next big thing, eventually replacing conventional computers, at least in main impact areas, and thus radically changing our computing experience. Some remain skeptical and, at best, think quantum computers may serve a limited specialized role, that is, if we can overcome significant technical software and hardware issues. Time will tell. As of this writing, quantum computing is no longer a futuristic thing. Major technology players are shipping production real-world machines. They continue to pour enormous resources into the field, with substantial, steady progress reported.