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

Fig. 15.13. A superconducting Josephson
Junction qubit device made by research-
ers at Delft University of Technology.

system therefore requires a new name, a quantum bit or qubit ( Fig. 15.13 ). This
superposition property of quantum states is one of the two key properties of
quantum mechanics that give quantum computers their remarkable power. In
a conventional computer, a bit can have a value of either 0 or 1. In a quantum
computer, a qubit can also be in a quantum superposition and so can be both 0
and 1 at the same time. A system with two qubits can hold four values simulta-
neously - 00, 01, 10, and 11.
When MIT computer scientist Edward Fredkin ( B.15.11 ) visited Feynman
at Caltech in 1974, Fredkin was researching the seemingly strange problem of
how to build a reversible computer. This is a type of computer that would be
able to reverse calculations - “uncalculating” - as well as being able to calcu-
late forward in the usual way. In conventional computers, logical operations
are performed by logic gates implemented in silicon. The familiar “AND” gate is
shown in Figure 2.8 with its two inputs and one output. All the possible inputs
and outputs for an AND gate are summarized in the accompanying truth table.
From this truth table, we see that an AND gate outputs a 1 only if both its inputs
are 1; for the other three possible input combinations, the gate outputs a 0. The
AND gate is therefore not reversible in the sense that it is impossible to deduce
a unique input signal from just the output signal. Fredkin devised a new set of
logic gates that are reversible - that is, gates such that the output signal from
the gate uniquely determines the input signal. The simplest example of one
of Fredkin's gates is the “Controlled NOT” or CNOT gate. This gate is shown
in Figure 15.14 together with a conventional NOT gate and the corresponding
truth tables. From the truth table for the CNOT gate, we see that the bottom
input either “does nothing” or acts as a conventional NOT gate, reversing a 1 to
a 0 and vice versa. Which action is chosen is determined by the signal on the
upper input, which acts as a control line. If the upper input is a 0, the lower line
does nothing. If it is a 1, the lower line acts as a NOT gate. Fredkin showed that
it was possible to perform every logical operation using a complete set of such
reversible gates (more than just the CNOT gate).
Why do we need to bother about reversible gates? Such gates are relevant
for quantum computing because the laws of quantum mechanics are revers-
ible in time. Reversibility is a property of conventional physical waves, not just

B.15.11. At the age of nineteen, Ed
Fredkin left Caltech and joined the
U.S. Air Force to serve as a fighter
pilot. He became a professor at MIT
in 1968 and was director of project
MAC from 1971 to 1974. He was a
close friend of Richard Feynman's
and introduced him to the concept
of reversible computing. Fredkin's
research interests are wide-ranging
and include the physics of computa-
tion and cellular automata.