In this section we describe how arbitrary logic gates may be constructed for quantum bits. We start by considering various one-bit unitary operations and a single two-bit one---the XOR operation. Combinations of these are sufficient to construct a Toffoli gate for quantum bits or indeed any unitary operation on a finite number of bits.
Start with a single quantum bit. If we represent the states
and 
(i.e.,
and 
) as the vectors 
and
, respectively, then the most general unitary
transformation corresponds to a 
matrix of the form
where we typically take 
[14]. Using
this operator we can flip bits via:
The extraneous sign represents a phase factor that does not affect the logical operation of the gates and may be removed if we wish, now or at a later stage. Such one-bit computations are illustrated schematically as a quantum circuit in Fig. 5 [14,15].
Fig. 5 Schematic of the quantum circuit diagram for
a one-bit gate. The line represents a single quantum bit (such as a
spin-
particle). Initially, this bit has a state described by 
; after
it has ``passed'' through this circuit it comes out in the state
.
Another important one-bit gate is 
which maps a spin-down
particle
to an equal superposition of down and up. Consider a string of k
spin-
particles initially spin-down. If we apply this
gate independently to each particle we obtain a superposition of
every possible bit-string of length k:
where 
. Our computer is now in a superposition of an
exponentially large number of integers a from 0 to 
.
Suppose we could now construct a unitary operation which maps a pair
of bit-strings 
into the pair 
for some
function 
. Then such a unitary operator acting on the
superposition of states
would compute 
in parallel an exponentially large number of times
for the various inputs a.
To see how such unitary operators may be constructed from a few elementary ones we must also consider the XOR gate [14,15]. Writing the two-particle basis states as the vectors
we may represent the XOR gate as a unitary operator
Here the first particle acts as a conditional gate to flip the state of the second particle. It is easy to check that the state of the second particle corresponds to the action of the XOR gate given in Table 1. The quantum circuit for an XOR gate is illustrated in Fig. 6. This circuit is equivalent to the elementary instruction
if ( 
= 1 ) 
= NOT
which may be thought of as example of quantum computer code [22].
The ket-brackets 
are reminders that we are dealing
with quantum rather than classical bits. The XOR gate allows us to move
information around as is illustrated in Fig. 7.
Fig. 6 Quantum circuit diagram for an XOR gate. The
lower bit 
is flipped whenever the upper bit 
is set.
Fig. 7 Circuit for swapping a pair of bits.
How do we construct the Toffoli gate? One major problem with this
gate is that it requires three bits in and three out. Quantum
mechanically, this seems to correspond to a scattering
process involving three-particle collisions [16] calling
for a (possibly) unreasonable control of the particles [5].
Fortunately, the Toffoli gate may be constructed by two-particle
scattering processes alone [15,17,18,19,20].
In particular, we show a construction here involving the XOR
gate and some one-bit gates 
(Fig. 8) [14].
Not only is the XOR sufficient for all logic operations on a quantum
computer, but it can be used to construct arbitrary unitary transformations
on any finite set of bits. Numerous proposals for producing such gates
have been considered [2,6].
Fig. 8 Toffoli gate built from two-bit XOR gates plus some
one-bit gates [5,14]. This circuit introduces
some extra signs in the unitary matrix 
which may
be removed at a later stage.