MY AMERICAN SCIENTIST
SEARCH

COMPUTING SCIENCE

The hardware doesn’t yet exist, but languages for quantum coding are ready to go.

# The Quantum Mystique

Abstraction barriers break down because computers are not abstractions. A computing machine is a physical object, which has to obey the laws of nature as well as any rules of logic or mathematics that the designer wants to impose. You can’t entirely ignore the physical substrate—and that goes double for a quantum computer.

The bits of a classical computer are just binary digits, with a value of either 0 or 1. Almost any device with two distinct states can serve to represent a classical bit: a switch, a valve, a magnet, a coin. Qubits, partaking of the quantum mystique, can occupy a superposition of 0 and 1 states. What does that mean? It’s not that the qubit can have an intermediate value, such as 0.63; when the state of the qubit is measured, the result is always 0 or 1. But in the course of a computation a qubit can act as if it were a mixture of states—say, 63 percent 0 and 37 percent 1. Only a few physical systems exhibit superposition clearly enough to function as qubits. Examples include photons with two directions of polarization, atomic nuclei with two spin orientations, and superconducting loops with clockwise and counterclockwise electric currents.

Another key aspect of qubit behavior is interference, a phenomenon well known in the physics of waves. When two waves overlap, they can either reinforce each other (if the peaks and valleys of the undulations coincide) or they can cancel (if the waves are out of phase). Mathematically, the intensity of the combined waves at any point is given by the square of the sum of the individual wave amplitudes. When the two amplitudes have the same sign, the interference is constructive; when one amplitude is positive and the other negative, the resulting destructive interference yields an intensity less than that of either wave alone.

Like waves, the 0 and 1 states of a qubit have amplitudes that can be either positive or negative. (Actually, the amplitudes are complex numbers, with real and imaginary parts, but that complication can be ignored here.) Depending on the signs of the amplitudes, quantum interference can either increase or decrease the probability that a specific state will be observed when the qubit is measured.

Interference plays a role in all the interesting algorithms for quantum computers—that is, the algorithms that might enable such a machine to outperform a classical computer. The general idea is to arrange the evolution of the quantum system so that wrong answers are suppressed by destructive interference and right answers are enhanced by constructive interference. In this way the algorithms exploit a form of parallelism that’s unique to quantum systems. In effect, a collection of n qubits can explore all of its 2n possible configurations at once; a classical system might have to look at the 2n bit patterns one at a time.

One last aspect of quantum weirdness is entanglement. When two or more qubits interact, they may form a fused state that cannot be teased apart to show the contributions of individual qubits. In other words, you cannot poke around inside a quantum register and alter one qubit while leaving the rest undisturbed. Entanglement is a prerequisite for at least some of the important quantum algorithms.

Among those algorithms, the best known is a procedure for finding the factors of integers, devised in 1994 by Peter W. Shor, now at MIT. When factoring an n-digit number, the fastest known classical algorithms take an amount of time that grows exponentially with n; Shor’s algorithm works in time proportional to n3. For large enough n, the quantum algorithm is far faster.