Desurvire E. Classical and Quantum Information Theory: An Introduction for the Telecom Scientist

Подождите немного. Документ загружается.

15.1 Maxwell’s demon and Landauer’s principle 287

with H(X) = k

I (X)=k

log

2 in the units of physics. According to Landauer’s prin-

ciple, clearing the memory, thus, corresponds to the conversion into energy of the mem-

ory’s average information, which corresponds to the heat Q = k

T I =k

T log

The cleared memory can be viewed as a single-event source X



{

}

with probabil-

ity p(0) = 1, corresponding to zero information (I (0) =−log

[p(0)] =−log

(1) = 0)

and zero entropy H



= k

I (0)=0. The difference in memory entropy before and

after erasure is, thus, H = H



− H =−k

log

2. This is the amount of entropy that

is communicated to the environment. These values represent a lower bound because the

physical erasure process must also generate some form of heat, for instance passing a

current through a memory transistor gate. The key conclusion of Landauer’s principle

can be summarized into the following statement:

Information is physical.

This means that the creation, erasure, manipulation, or processing of information

involves physical laws. This represents a new awareness, which contrasts with the classi-

cal background of Shannon’s information theory, and calls for more questions, answers,

and paradoxes. These are to be found in quantum information theory (QIT), which will

be addressed shortly. At this stage, we must at least be convinced that there is more to

information than a mere mathematical or ethereal deﬁnition, as we have been used and

trained through education to believe intuitively.

Landauer’s principle brings up another interesting question, which concerns com-

puting. When one performs hand calculations on a blackboard, one is obliged at some

point to erase it, while saving the last results and other useful parameters somewhere in

the corner of the blackboard. Very large blackboards, with different folding or sliding

panels, could ﬁt a full math course. But the information must be cleared for the next

course. This shows that processing information (computation) requires information era-

sure, because of the ﬁnite size of the memory. A computer that would keep and store

the information regarding all of its intermediate calculation steps (namely the memory

contents at each step, or the full record of the memory changes) would rapidly “choke on

its own garbage.” Such a necessary erasure yet obliterates the information of the com-

puting history, which makes the computation irreversible. For computation, the term

“irreversible” means that the computed information output cannot lead one to know the

information input to the computation.

The concept of computing irreversibility, however, seems to be in contradiction with

the laws of physics. Indeed, if one fully knows the state of a system at a given time

t, for instance, the distribution of molecules and their velocities inside a closed box,

For instance, the addition of two integer numbers a and b, given the fact that the input information (a, b)

is then erased, is irreversible: to any output c correspond c + 1 possible input pairs. If a and b are real

numbers, the number of input-pair possibilities is inﬁnite. Another example of irreversibility is the opera-

tion of functional derivation: given any input function f

= f (x), the output is f

out

= f



(x ). Reversing the

algorithm yields f

∗

(x ) =



(x )dx = f (x) + C where C =−f (x

) is an arbitrary constant. The knowl-

edge of f

out

= f



(x ), thus, makes it possible to know f

∗

= f (x) +C = f

(x ) +C. This may represent

useful information, but f

∗

and f

differ from each other by an inﬁnity of possible real constants C, which

illustrates the irreversibility of the computation algorithm.

288 Reversible computation

Memory

Instructions

Data

Control unit

Registers

In Out

ALU

Figure 15.2 Von Neumann’s generic computer architecture.

the laws of mechanics make it possible to compute the system at any time prior to t.

This is like playing a video of a billiard ball game in reverse. From this perspective, a

physicist should suspect that it is possible to effect reversible computations, without any

heat dissipation or entropy increase. This brings the issue of the existence of reversible

logic. In the next two sections, I shall describe logic gates, which are used in the heart of

computer microcircuits, and then show that it is possible to deﬁne reversible logic gates

and circuits.

15.2 From computer architecture to logic gates

According to the 1945 design of computer architecture by von Neumann (VN),

the core

of a standard computer is made of a memory, and of an algorithmic and logical unit

(ALU), as illustrated in Fig. 15.2. It is seen that the VN architecture is completed with a

control unit and the interfaces enabling the computer to communicate with the outside

word and its peripherals. The memory is a device containing the instructions to initialize

and run the computer with its interfaces and peripherals. It includes the program to be

performed, in the form of a stack of instructions, and the data before, during, and after

See, for instance, http://en.wikipedia.org/wiki/Von_Neumann_architecture.

15.2 From computer architecture to logic gates 289

computation. As the ﬁgure shows, the ALU works with two dedicated memory buffers,

called registers, or sometimes “accumulators.” The two registers (A and B) are input

from the memory with binary data words a

,...,a

and b

,...,b

of identical size,

typically k =32 bits, 64 bits, and, today, 128 bits. This size is the same as that of the cells

in the memory, and also of the address used to index the memory cells (the memory,

thus, has 2

different addresses). Registers are literally used as scratchpads for the ALU

to perform various logical operations between the two data words {a

} and {b

}, such as

addition, subtraction, multiplication, division, comparison, complementation, rotational

permutation, overﬂow test, and zero-divide test, for the main ones. These operations are

performed by an internal circuit of the ALU, which is formed of a complex network of

logic gates, whose functions can be switched at will through a set of control bits. A basic

example of a four-bit ALU circuit is provided later in this chapter (one may yet have a

look at Fig. 15.6 for a ﬂavor), which will come after I have described the principles of

the elementary logic gates themselves.

All logical operations between the register data and the ALU are instructed from a

“micromachine” program, which decodes the higher-level instructions fed by the com-

puter memory into micro-instructions making the ALU capable to handle the register

bits. The ALU is complete with an internal buffer register. Today, the integrated version

of the ALU, internal buffer, and micromachine decoder represents what is referred to as a

CPU, for central processing unit.

The CPU is, thus, a machine to “crunch bits” from the

higher-level instructions of the central memory, hence the popular name “computer,”

which today means far more than just a calculator, although the appellation remains

conceptually exact. Note that the VN architecture is not the only one possible. Indeed,

several VN machines, or CPUs can be set to work in parallel, each being dedicated

to an independent fraction of the computing algorithm, or more simply being assigned

a share of the number-crunching groundwork. This is referred to as parallel or multi-

processor architecture, to be viewed either as a magniﬁed VN master machine ruling

over many CPU slaves, or a “democratic” group of VN machines putting their effort

towards some common-interest goals. The VN architecture yet remains crucial to the

orchestration of the ensemble, whether the master is a ruling dictator or simply a discreet

facilitator.

Before taking a closer look at the characteristics of binary logic gates forming the

ALU circuitry, it is worth considering the Turing machine (TM), which was described

in Chapter 7. To recall, the generic TM architecture, which is illustrated in Fig. 7.1,

consists of a bidirectional tape of inﬁnite length, and a head, which is able to read and

write bits or symbols onto the tape. The TM is set into motion according to a stack of

instructions, called an “action table.” This action table is the program from which the

tape input data are processed bit by bit (or symbol by symbol), resulting in the generation

of output data, which are recorded on the tape. It includes a “halting instruction,” which

forces the machine to halt on completion of the task. The tape is a memory of inﬁnite

size, which puts no restriction as to the complexity of the task, the corresponding

computing algorithm and the amount of data to be processed. Finally, a universal Turing

See http://en.wikipedia.org/wiki/Central_processing_unit.

290 Reversible computation

machine (UTM) belongs to a class of TMs, which, through a minimal set of action table

instructions, are able to emulate any other TM, which is achieved by means of a tape

program. The most important conclusion about TMs (and for that matter, UTMs) is that

they can compute “anything that a real computer can compute.” Namely, any problem

that can be solved through some form of computing process or algorithm devised by

a mathematician can be solved by a TM. This stunning statement is referred to as the

Church–Turing thesis. Thus, TMs, and more so UTMs, represent the most elementary

form of computing machine ever conceivable. In this view, why are modern computers

based on VN architecture instead of that of a TM? As discussed in Chapter 7,theTM

implementation is comparatively impractical, for two main reasons. First, as we have

seen, the TM requires an inﬁnite memory space, which is not physically possible. Second,

the ﬁnite size of a realistic computer memory puts a constraint on the management

of the memory space, which in turn impacts on the program structure and algorithms.

The TM algorithms may be more general or universal, but their implementation in a

computing machine of ﬁnite memory size may in some cases be intractable, if not

physically impossible. We can now see some key differences and similarities between

TM and VN computers. While the UTM represents the most universal and elementary

computer architecture, the VN machine represents its conceptual approximation in the

real world. Both have programs based on man-thought algorithms, and physical input–

output interfaces. We may think of the ALU as a TM that uses parts of its memory as an

input–output tape, and the other part as the place where the action table is located. But

this does not resolve the problem of memory ﬁniteness. Finally, another key difference

is that the VN machine is not subject to the “halting problem,” whereby a TM could

run forever. As discussed in Chapter 7, the halting problem is generally “undecidable,”

meaning that given an action table and an input tape, there exists no formal proof that a

TM will necessarily halt! In contrast, a VN machine does not have a halting problem. We

may not attempt to prove the point here, but simply stated, the ﬁnite size of the memory

must eventually cause the VN machine to “choke on its own garbage,” unlike the TM,

which may run indeﬁnitely! But unlike the idealized TM, the realistic VN computer

can be programmed to stop automatically if caught in an inﬁnite loop, or trespassing a

preset CPU time limit. As a matter of fact, modern VN computers are fully capable of

emulating any universal TM, and for this reason they are said to be Turing complete,

Turing equivalent,orcomputationally universal.

This does not mean that such a UTM

emulation would be any quicker, more efﬁcient, or easier; probably to the contrary

in most general cases. The key difference remains the ﬁniteness of the VN computer

memory.

We shall now focus on the VN computer and look in more detail at the ALU and

its elementary computing circuits. As we have seen, the ALU processes the codeword

bits that are loaded in the two registers A and B. The ALU is able to interpret high-

level instructions from the memory into basic micromachine operations. In short, a

high-level instruction may be stated in a form such as “c = a + b,” which the ALU

interprets as “load the operands a, b pointed by the corresponding memory addresses

See http://en.wikipedia.org/wiki/Turing-complete.

15.2 From computer architecture to logic gates 291

into the registers A and B, perform the addition of the two, and return the result c

to the dedicated memory address. Such an operation calls for a microprogram, which

must process the two binary operands a, b (a = a

,...,a

, b = b

,...,b

)ona

bit-by-bit (a

, b

) basis.

Another possible instruction may be “IF a > b, THEN.” Here,

the ALU is asked to verify indeed if a > b, so that in the event the answer is yes (or

TRUE, or 1 in logic language) the high-level program may jump to another instruction.

The ALU must then subtract b from a, and return TRUE, or 1, if z = a − b is identiﬁed

as being neither negative nor zero. It is clear that such a test requires a microprogram,

which sequentially compares every bit in the two registers A, B. The same is true for

operations such as multiplication and division, for which the ALU must also return

the extra information “overﬂow = TRUE/FALSE” and “zero divide = TRUE/FALSE.”

Here, we will not tarry on the micromachine programming concept and structure, but

rather focus on the bit-to-bit operations (a

↔ b

) in the registers A, B, which are per-

formed by a preset circuitry of logic gates, acting as a controlled network. As mentioned

earlier, a basic example of such a network is provided later in this chapter (Fig. 15.6).

But to understand how the network operates under any micro-instructions, it is essen-

tial to review the different types of logic gate, as well as their possible basic circuit

arrangements.

The three most elementary logic gates, which may have one or two input bits, but

have a single output bit, are called NOT, AND, and OR, as illustrated in Fig. 15.3.

Calling a, b the bit operands, these gates correspond to the three Boolean operators

noted, respectively and equivalently (see Chapter 1):

¬a,

a for NOT a,

a ∨ b, a + b for a OR b,

a ∧ b, a × b for a AND b.

The “truth tables” shown in the ﬁgure list all possible outcomes of any logical operation.

For instance, the output c = a ∧ b (AND gate) is nonzero only in the case a = b = 1.

The three other cases, (a, b) = (00), (10), (01) yield c = 0. Thus, the result c = 1 has

only one cause while the result c = 0 has three indistinguishable causes, illustrating that

the AND operation is effectively nonreversible. It is observed from the truth tables in

Fig. 15.3 that only the NOT gate performs a reversible computation (the output to input

bit correspondence being unique).

The three gates NOT, OR, and AND make it possible to build a second group of ele-

mentary logic gates, shown in Fig. 15.4, called NAND (NOT AND) and XOR (eXclusive

Let A = a

,...,a

and B = b

,...,b

be two binary numbers. Proceeding from the lowest-weight

bit (i = 0) to the highest-weight bit (i = n), a ﬁrst Boolean circuit computes both x

= a

⊕ b

and

(1)

= a

∧ b

. The output c

(1)

provides a “carry” bit, which is 1 if the two bits (a

, b

) are equal to 1, and

0 otherwise. A second circuit stage then computes y

= x

⊕ c

i−1

, c

(2)

= x

⊕ c

i−1

and c

= c

(1)

+ c

(2)

where c

i−1

is the carry bit resulting from the previous addition stage (by convention, c

−1

= 0). The result y

represents the ith bit of A + B and the result c

is the carry to use for the next computation stage i + 1. It is

left to the reader as an exercise to draw the Boolean circuits corresponding to these different computations

stages, as well as the circuit for a full k-bit binary adder.

292 Reversible computation

NOT

AND

11 1

10 0

01 0

00 0

11 1

10 1

01 1

00 0

NOT

AND

Figure 15.3 The three elementary logic gates: NOT, AND, and OR, along with their

corresponding truth tables.

NAND

XOR

ab a

NAND

11 0

10 1

01 1

00 1

11 0

10 1

01 1

00 0

XOR

Figure 15.4 Second group of elementary logic gates, NAND and XOR, along with their

corresponding truth tables, as built from the ﬁrst group shown in Fig. 15.3.

15.2 From computer architecture to logic gates 293

OR). In Boolean logic, the corresponding operators are:

∧ y for x NAND y,

x ⊕ y for x XOR y,

respectively. Note the small open circle, or “bubble,” which indicates the logical com-

plementation at the gate’s output (in some cases, the bubble can be placed at the input to

complement some of the input data bits). The ﬁgure shows that the NAND gate is built

through a succession of AND and NOT gates. The XOR gate is an essential function for

performing modulo-2 addition of two binary numbers. This gate can be built in many

different ways. The ﬁgure shows one possible Boolean circuit utilizing AND, NAND,

and OR gates, according to the heuristic formula

a ⊕ b = (a

∧ b) ∧(a ∨ b). (15.1)

Here are three other possible ways to effect a XOR computation, which the reader can

check out using truth tables:

a ⊕ b = (a ∨ b) ∧ (

a ∨

= (a ∧

b) ∨(

a ∧ b)

= (a

∧

∧ (

∧ b).

(15.2)

It is seen that the last solution in this equation makes exclusive use of NAND (

∧) and

NOT (

x) operations. The NOT can also be realized with NAND, taking into account the

property

a = a

∧ a. Thus, we obtain from Eq. (15.2)

a ⊕ b =

[

∧ (b

∧ b)

]

∧ [(a

∧ a)

∧ b], (15.3)

which shows that an XOR gate can be built exclusively with a Boolean circuit of NAND

gates. It is easily established that the NAND gate can be used as a universal building block

in Boolean circuits to construct all elementary logic gates. This property is illustrated in

Fig. 15.5.

We have, thus, identiﬁed the basic constitutive elements of computation: logic gates

(NOT, AND, OR, XOR) with NAND representing a universal building block, and wires

to realize any Boolean circuit, from elementary to complex. We can then consider other

types of logic gates derived from these.

First, the XOR gate can also be used to perform yet another logical function called

controlled-NOT, corresponding to the CNOT gate. Given (a, x) as inputs, with a being

called the control bit, the output of CNOT is a ⊕ x.Fora = 0, we have a ⊕ x = x; and

for a = 1, we have a ⊕ x =

x. Thus the value of x is ﬂipped if the control bit is set to

a = 1 and is left unchanged otherwise, hence the name “controlled-NOT” gate.

Another Boolean-circuit component, which was only implicitly introduced, is the

wire splitter that enables one to use the same bit to feed different gate inputs. This

logical splitting function is referred to as FANOUT. Another logical function of interest

is CROSSOVER (also called SWAP), which consists of switching two bits (a, b)into

294 Reversible computation

XOR

AND

NOT

Figure 15.5 Construction of logic gates NOT, AND, OR, and XOR from Boolean circuits of

NAND gates.

(b, a), depending on the value of a control bit c. As we shall see later, the function

CROSSOVER is the key to building reversible logic gates. Here, we shall overlook

more complex logical-gate arrangements, whereby the wires can form circuit loops,

thus enabling output bits to be fed back into the circuit that computes them. Such

feedback loops are used to create “bistable” or two-state logical devices. The corre-

sponding devices are called FLIP-FLOP gates, and are activated by a clock signal. A

FLIP-FLOP gate can have different output possibilities, or states, depending on (a) the

input bits, and (b) the previous state in which it is found at each clock cycle. There

exist several types of elementary FLIP-FLOP gates,

which ﬁnd many applications for

data registers and counters, and computer memories. Finally, any single-port logic gate

whose output is equal to the input performs the function REPEAT, as does a “repeater”

in digital electronics. This is the case of the CNOT gate with the control bit set to

a = 0.

Having, now, an understanding of the various logic gates and functions, it is well

worthwhile to provide a basic example of ALU (algorithmic and logical unit) circuitry.

Figure 15.6 shows the impressive logical circuit of a four-bit ALU, an integrated circuit

from the TTL (transistor-transistor logic) family referred to as 74181.

The following does not represent any authoritative description of the ’181 (as profes-

sionals call it), but simply a brief academic overview. As may be counted from the ﬁgure,

this ALU network includes 67 logic gates (namely: 38 AND, 12 NOR, 4 XOR, 4 NAND,

and 9 NOT). The four-bit inputs

A = (

B = (

) (top) and output

See, for instance: http://en.wikipedia.org/wiki/Flip-ﬂop_(electronics), http://computer.howstuffworks.com/

boolean3.htm, www.eelab.usyd.edu.au/digital_tutorial/part3/ﬂ-types.htm.

See (in French): http://fr.wikipedia.org/wiki/Unit%C3%A9_arithm%C3%A9tique_et_logique. Also see

datasheet in (for instance):

www.ac-nancy-metz.fr/enseign/ssi/ressourcesP/Documentation/GE/TTL/74hc181.pdf.

15.2 From computer architecture to logic gates 295

0−3

GPC

Figure 15.6 Basic example of a four-bit ALU (inputs

, output

F = (

) (bottom) are shown in open circles (note that, here, the operands are

conventionally input in complemented logic). On top left, the “mode-control” input M

selects the type of computation to perform, namely logic with M = H (for high voltage

level) and arithmetic with M = L (for low voltage level). The logic mode (M = H)

performs individual bit–bit logical operations between the two inputs

B, with carry

inhibition. The arithmetic mode (M =L) transfers carries at each individual bit–bit oper-

ation to the higher bit level. For instance, this is the difference between performing the

operation A ⊕ B, which consists in logically XORing the two operands on an individual

bit-by-bit basis (without carry), and performing the operation A + B, which represents

the arithmetic addition (with carry transfer) of the two binary numbers A, B. The cir-

cuit can perform either 16 logical operations or 16 arithmetic operations. Shown at the

top right in Fig. 15.6 are four “mode select” bits S =

(

)

. These bits control

the 2

= 16 possible functions, which may be either logical or arithmetic, according

to the computational mode M. Also shown at the top left of the ﬁgure, an input c

and output c

n+4

(high or low values) are provisioned to enable the cascading of arith-

metic computations over larger word sizes, for instance to form a 16-bit ALU network.

Table 15.1 shows the 16 logical functions (M = H) performed by the ALU according to

the 16 different selection modes S.

296 Reversible computation

Table 15.1 Logical functions F = f (

B) performed from four-bit operands

B by the ALU network shown in

Fig. 15.6, as deﬁned by the 16 selection modes S = (S

),withS

= 0 for “low” and S

= 1 for “high” voltage

levels.

F = f (

B) S

F = f (

0000

A 1000

A ∧ B

0001

A ∧ B 1001 A ⊕ B

0010

A ∨ B 1010B

00111 1011A ∨ B

0100

A ∨ B 11000

0101

B 1101A ∧

0110

A ⊕

B 1110A ∧ B

0111A ∨

B 1111A

A detailed demonstration of the 74181-TTL and other higher-level network arrange-

ments (e.g., 16-bit ALU), which is animated through Java applets, is available on the

Internet.

This basic example only provides a hint of the computing capabilities of

logical circuits and more complex network arrangements. It just sufﬁces to illustrate that

the ALU can compute anything corresponding to a VN program, as decomposed into

a series of micro-instructions and bit processing through such complex logic networks.

We shall now move on to the core of the issue: the reversibility of computing and the

need to ﬁnd alternative ways to process information.

As we have learnt, the above description constitutes a basic inventory of classical logic

gates and circuit networks, which (except for NOT gate) we know perform nonreversible

operations. According to Landauer’s principle, which was described earlier, the infor-

mation erasure of each input bit corresponds to a minimum heat and entropy generation

of Q = k

T log 2 and H = k

log 2, respectively. The power consumption of the logic

gates and of the various electronic circuits (including digital ampliﬁers to compensate

for signal propagation or splitting loss) also represents a source of heat and entropy,

whose measures are orders of magnitude greater than Landauer’s bound. The heat dis-

sipation is estimated to be Q



= 500k

T log 2 ≡ 500Q for elementary logic gates, and



= 10

T ≈ 10

Q for the CPU in ordinary home computers.

Most of this heat,

of resistive origin, could be alleviated if computers would be run at ultra-low tempera-

tures (T → 0), using “superconducting” electronics. If such a computer could ever be

built, then one would reach the ultimate limits predicted by Landauer’s bound. The key

question, then, is whether or not it is possible to build computers with reversible logic.

As previously hinted, physicists, who are attached to the concept of reversible processes,

intuitively suspect that it should be possible to manipulate information in a reversible

See: http://tams-www.informatik.uni-hamburg.de/applets/hades/webdemos/20-arithmetic/50-74181/

demo-74181-ALU.html.

See (respectively): M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information

(Cambridge: Cambridge University Press, 2000) and V. Vedral and M. B. Plenio, Basics of quantum

computation. Prog. Quant. Electron., 22 (1998), 1–39.