COMPUTING SCIENCE

# The Square Root of NOT

# Reversible Logic

The QCF gate demonstrates some principles of quantum computation, but it is not enough to build a complete quantum computer, any more than NOT gates are enough to build a classical computer. Performing useful calculations requires gates that process more than one bit (or qubit) at a time. For example, conventional computers make extensive use of and gates that accept two input bits and have a single output bit; the output is a 1 only if both input bits are 1's.

In designing gates for a quantum computer, certain constraints must be satisfied. In particular, the matrix of transition amplitudes must be unitary, which implies, roughly speaking, that it conserves probability: The sum of the probabilities of all possible outcomes must be exactly 1. A consequence of this requirement is that any quantum computing operation must be reversible: You must be able to take the results of an operation and put them back through the machine in the opposite direction to recover the original inputs. and gates do not obey this rule, since information is irretrievably lost when two input bits are condensed into a single output bit. Reversible gates must have the same number of inputs and outputs.

As it happens, the study of reversible computing has gotten a lot of attention lately, largely because of the discovery by Charles H. Bennett and Rolf Landauer of IBM that a reversible computer can perform any computation and can do so with arbitrarily low energy consumption *(10)*. A reversible gate devised by Tommaso Toffoli of MIT is a "universal" classical gate: A computer could be built out of copies of this gate alone *(11)*. Deutsch has shown that a similar gate is universal for quantum computers *(12)*. Both the Toffoli and the Deutsch gates have three inputs and three outputs, but more recently two-qubit gates have also proved universal for quantum computations *(13)*.

Practical quantum technologies are surely years or decades away, and yet a few implementation schemes are already under discussion. The idea closest to existing electronic technology relies on "quantum dots," which are isolated conductive regions within a semiconductor substrate *(14)*. Each quantum dot can hold a single electron, whose presence or absence represents one qubit of information. Another proposal is based on a hypothetical polymeric molecule in which the individual subunits could be toggled between the ground state and an excited state *(15)*. And David P. DiVincenzo of IBM has described a mechanism by which isolated nuclear spins would interact—and thereby compute—when they are brought together by the meshing of microscopic gears *(13)*.

EMAIL TO A FRIEND :