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

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.if ( = 1 ) = NOT

**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.

Wed Aug 23 11:54:31 IDT 1995