The end of Moore’s law - The Computing Universe: A Journey through a Revolution - page 306

of computer, one that might be able to do calculations that conventional com-
puters cannot do. Feynman was referring specifically to simulations of quan-
tum systems to calculate quantum wave functions and quantum probabilities.
After Feynman's lecture, David Deutsch ( B.15.9 ), a physicist at the University
of Oxford, took the next step. In 1985, Deutsch proved that a quantum com-
puter could indeed do some calculations faster than a conventional computer.
But it was not until 1994 that interest in quantum computing really exploded
when Peter Shor ( B.15.10 ) of Bell Laboratories discovered a quantum algorithm
that could potentially solve certain mathematical problems much faster than
the best algorithm running on a conventional computer.
What are the key elements of a quantum computer? First, we are only
allowed to use quantum objects, like electrons or atoms, to input and store
information, and to perform logical operations on this information. Quantum
algorithms are executed using these fundamental logical operations. Finally,
we need to be able to read out the answer to our quantum calculation. In his
talk in 1981, Feynman speculated about the possibility of storing a single bit
of information using the quantum states of a single electron. As we discussed
in Chapter 7 , electrons possess a property called spin . In quantum mechanics,
an electron can exist in one of two possible spin states, which we call spin up ↑
and spin down ↓. To represent digital information, we can use the spin up state
↑ to represent a 1 and the spin down state ↓ to represent a 0. But this is not the
whole story: in quantum mechanics, the electron can be in a quantum superposi-
tion of both these states. The electron's state is described by a probability ampli-
tude . Using the traditional symbol ψ to represent the probability amplitude,
this quantum superposition can be written:

B.15.9. David Deutsch developed
the theory of a universal quantum
Turing machine. In a famous paper
published in1985, he argued that if a
quantum computer could be built, it
would have some remarkable prop-
erties due to quantum parallelism.

Ψ = α ↑ + β ↓

where α and β are the amplitudes of the two possible spin states. What hap-
pens if we make a measurement of the spin of an electron in such a quantum
superposition? According to standard quantum mechanics, we must observe
the electron in either a spin up state or a spin down state, but for any given
electron in the state ψ it is impossible to predict with certainty which spin state
we will see. However, if we were to prepare an ensemble collection of many dif-
ferent electrons in exactly the same way, so that each of them is in the same
state ψ, then quantum mechanics does make a definite prediction. If we make
measurements of the spin state of all of the electrons in this collection, quan-
tum mechanics predicts that we will obtain the spin up result with probability
α 2 and the spin down result with probability β 2 . The total probability to get any
of the possible results must always add up to one, so the sum of these two prob-
abilities must add up to one.
In some sense, we can say that the electron in superposition state ψ is in
both spin states at the same time. So now we see that if we use an electron to
represent digital information, in addition to being in one of the 1 and 0 states,
the electron could also be in a superposition of both the 1 and 0 states with
probabilities determined by α and β. After more than half a century studying
the fundamentals of computation, physicists had discovered something new
about information at the quantum level. Information stored in a quantum

B.15.10. Peter Shor received a PhD
in applied mathematics from MIT
in 1985. While working at Bell Labs
he became famous for his quantum
factorization algorithm that he
discovered in 1994. Shor has been a
professor at MIT since 2003.