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

Fig. 15.14. Edward Fredkin devised a set
of logic gates that are reversible in the
sense that the output signal from the
gate fully determines the input signal. (a)
A classical NOT gate and its truth table,
and (b) a controlled NOT or CNOT gate
and its truth table.

(a)

a NOT a

a a ′ 0 1

1 0

(b)

a ′ b ′ a b

a a ′

0 0 0 0

0 1 0 1

1 0 1 1

b b ′

1 1 1 0

these strange quantum probability waves. A wave traveling in one direction
along a string, for example, can just as easily travel in the reverse direction.
This reversibility property of quantum mechanics means that if we wish to con-
struct a quantum computer, we have to use computational elements that are
reversible.
We can now write down the essential ingredients of a quantum computer.
There must be a physical system in which information can be stored as qubits
on individual quantum objects such as electrons, atoms, or photons. The infor-
mation can be not only the familiar digital 1s and 0s but also quantum super-
positions of 1 and 0. A quantum computer must have mechanisms by which
these qubits can be made to interact so that we can perform Fredkin's revers-
ible logic operations. Note that because we could choose to start off our quan-
tum computer in a quantum superposition of all the possible initial states, in
principle the quantum computer would calculate results for all the possible
logical paths at the same time. David Deutsch, who first proved that quantum
computers can be more powerful than conventional computers, called this
property quantum parallelism . But how to exploit this property is not so obvious.
According to standard quantum theory, making a measurement on a quantum
superposition will result in only one of the possible states being selected, so
how can quantum parallelism actually be useful? Shor's great contribution
was to find a way to extract just a little information from all these quantum
paths.
There is a second key feature of quantum mechanics that we must now
explain, called quantum entanglement . Entanglement is a feature of certain types
of two-particle quantum states that we can think of as having some invisible
wiring to share information between the two particles ( Fig. 15.15 ). We can illus-
trate the strange nature of entanglement by considering a thought experiment
from particle physics. There is an unstable particle called a neutral pion that
most of the time spontaneously decays into two photons (a photon being a par-
ticle-like bundle of light energy). On some occasions, however, the pion decays
into an electron (e - ) and its antiparticle, a positron (e + ), instead of two photons.
This is a rare occurrence for the pion, but it gives us the simplest experiment
to illustrate what is meant by quantum entanglement. As in classical physics,
angular momentum must be conserved in any quantum mechanical process. The