of as a restriction on measurements. Phenomena such as entanglement were considered part of “quantum foundations” or the philosophy of quantum mechanics, but were not considered operationally relevant until quantum computing and quantum cryptography were independently developed in the 1980s and 1970s, respectively.

Quantum computing (or more precisely, the idea of quantum advantage in computing) did not arise until 1982, when Richard Feynman suggested that since conventional computers appeared to require exponential overhead to simulate quantum mechanics, perhaps a quantum-mechanical computer could perform the task more efficiently. The model was formalized in 1985 by David Deutsch, who also showed, surprisingly, that a quantum-mechanical computer could be faster than a conventional computer for a problem that on its face had nothing to do with quantum mechanics ( computing the XOR of two bits). A series of stronger speedups followed, albeit for contrived problems, until Peter Shor’s 1994 quantum algorithm for factoring integers in polynomial time.

Much earlier (1970), then grad student Stephen Wiesner proposed using Heisenberg’s restrictions on measurements to prevent an adversary from learning a secret message. Thus quantum cryptography was born, although Wiesner’s paper was almost universally rejected from journals, and its ideas were largely unknown until Charles Bennett and Gilles Brassard published a scheme for quantum key distribution in 1984. Even the Bennett-Brassard proposal wasn’t taken seriously until they implemented it in 1991 (a much simpler task than building a general-purpose quantum computer).

The key conceptual shift enabling both quantum computing and quantum cryptography was to start thinking about the effects of quantum mechanics on information in operational terms instead of as a source of limitations, curiosities, and paradoxes. Once this shift was made, the technical aspects of quantum information were much simpler than earlier developments in quantum mechanics (e.g., the unification in the 1950s of quantum mechanics with special relativity).

Figure 1. This molecule was used in a 5-qubit nuclear magnetic resonance (NMR) quantum computer. While NMR was useful in the early QC implementations, it has limitations that make it unlikely to lead to a large-scale implementation.

Courtesy of Isaac Chung

COMPU TING WITH QUBI TS

One of the basic contributions of the computational approach to quantum mechanics is the idea of a “qubit” ( pronounced q-bit). In general, the state of a quantum system with d perfectly distinguishable states can be described as a unit vector in ℂ (where ℂ is the set of all complex numbers). The simplest interesting case is when d= 2, and the resulting vector is called a qubit:

x= xo x1

!

"

#

$ % &

 
This formalism includes the case of a
classical system, for which state j is rep-
resented by the vector ej with a 1 in po-
sition j and zeroes elsewhere. Since any
state can be written as a linear combi-
nation (also called a “superposition”)
of different ej, it is tempting to imagine
that the classical states are somehow
fundamental. But mathematically, one
basis is as good as any other.

The vector x describes the binary
quantum system in the sense that mea-
suring its state by means of an experi-
ment yields outcome j with probability
|xj| 2 for j=0, 1 (or 0, 1,…d- 1 in general);
hence x is indeed a unit vector. One
consequence of quantum measure-
ment is that upon outcome j, the state
of the system collapses to ej. Since any
external record of the quantum state
causes the same effect as a measure-
ment, this explains why most systems
look classical even though the underly-
ing physics is always quantum.