Classical Information

The basic unit of classical deterministic information is the ``bit''. A bit is an abstract entity or ``system'' that can be in one of the two states symbolized by $\mathfrak{0}$ and $\mathfrak{1}$. At this point, the symbols for the two states have no numeric meaning. That is why we have used a font different from that for the numbers $0$ and $1$. By making a clear distinction between the bit and its states we emphasize that a bit should be physically realized as a system or device whose states correspond to the ideal bit's states. For example, if you are reading this primer on paper, the system used to realize a bit is a reserved location on the surface, and the state depends on the pattern of ink ($\mathfrak{0}$ or $\mathfrak{1}$) in that location. In a computer, the device realizing a bit can be a combination of transistors and other integrated circuit elements with the state of the bit determined by the distribution of charge.

In order to make use of information it must be possible to manipulate (or ``process'') the states of information units. The elementary operations that can be used for this purpose are called ``gates''. Two one-bit gates are the $\mathbf{not}$ and the $\mathbf{reset}$ gates. Applying the $\mathbf{not}$ gate to a bit has the effect of ``flipping'' the state of the bit. For example, if the initial state of the bit is $\mathfrak{0}$, then the state after applying $\mathbf{not}$ is $\mathbf{not}(\mathfrak{0})=\mathfrak{1}$. We can present the effect of the gate in the following form:

$$\begin{array}{ccc} \textrm{Initial State}&&\textrm{Final St... ...tarrow & \mathbf{not}(\mathfrak{1}) = \mathfrak{0}. \end{array}$$ (1)

The $\mathbf{reset}$ gate sets the state to $\mathfrak{0}$ regardless of the input:

$$\begin{array}{ccc} \textrm{Initial State}&&\textrm{Final St... ...rrow & \mathbf{reset}(\mathfrak{1}) = \mathfrak{0}. \end{array}$$ (2)

By applying a combination of $\mathbf{not}$ and $\mathbf{reset}$ gates one can transform the state of a bit in every possible way.

Information units can be combined to represent more information. Bits are typically combined into sequences. The states of such a sequence are symbolized by strings of state symbols for the constituent bits. For example a two-bit sequence can be in one of the following four states: $\mathfrak{0}\mathfrak{0},\mathfrak{0}\mathfrak{1},\mathfrak{1}\mathfrak{0}$ and $\mathfrak{1}\mathfrak{1}$. The different bits are distinguished by their position in the sequence.

The one-bit gates can be applied to any bit in a sequence. For example, the $\mathbf{not}$ gate applied to the second bit of a three-bit sequence in the state $\mathfrak{0}\mathfrak{1}\mathfrak{1}$ changes the state to $\mathfrak{0}\mathfrak{0}\mathfrak{1}$.

One-bit gates act independently on each bit. To compute with multiple bits, we need gates whose action can correlate the states of two or more bits. One such gate is the $\mathbf{nand}$ (``not and'') gate, which acts on two bits in a bit sequence. Its effect is to set the state of the first bit to $\mathfrak{0}$ if both the first and the second bit are $\mathfrak{1}$, otherwise it sets it to $\mathfrak{1}$. Here is what happens when $\mathbf{nand}$ is applied to two consecutive bits:

$$\begin{array}{ccc} \textrm{Initial State}&&\textrm{Final S... ...mathfrak{1}\mathfrak{1})=\mathfrak{0}\mathfrak{1}. \end{array}$$ (3)

The $\mathbf{nand}$ gate can be applied to any two bits in a sequence. For example, it can be applied to the fourth and second bits (in this order) of four bits, in which case the initial state $\mathfrak{1}\mathfrak{1}\mathfrak{0}\mathfrak{1}$ is transformed to $\mathfrak{1}\mathfrak{1}\mathfrak{0}\mathfrak{0}$, setting the fourth bit to $\mathfrak{0}$.

Other operations on bit sequences include adding a new bit to the beginning ( $\mathbf{prepend}$) or end ( $\mathbf{append}$) of a bit sequence. The new bit is always initialized to $\mathfrak{0}$. It is also possible to discard the first or last bit, regardless of its state. Versions of these operations that are conditional on the state of another bit may also be used. An example is the conditional append operation: ``if the $k$'th bit is in the state $\mathfrak{0}$ then append a bit.''

The gates just introduced suffice for implementing arbitrary state transformations of a given bit sequence. Instructions for applying gates in a particular order are called a ``circuit''. An important part of investigations in information processing is to determine the minimum resources required to perform information processing tasks. For a given circuit, the two primary resources are the number of gates and the total number of bits used. The ``circuit complexity'' of a desired transformation is the minimum number of gates needed to implement it.

The model of computation defined by the ability to apply gates in a fixed sequence is called the ``circuit model''. Classical computation extends the circuit model by providing a means for repeating blocks of instructions indefinitely or until a desired condition is achieved. In principle, it is possible to conceive of a general purpose computer as a device that repeatedly applies the same circuit to the beginnings of several bit sequences. In this introduction, we take for granted a traditional programmable computer based on classical information. Thus a ``quantum algorithm'' is a program written for such a computer with additional instructions for applying gates to quantum information. The computational power of this model is equivalent to that of other general purpose models of quantum computation, such as quantum Turing machines [7].

For an introduction to algorithms and their analysis, see [8]. A useful textbook on computational complexity with an introduction to classical computation and computational machine models is [9].