{"id":4056,"date":"2024-09-21T12:23:48","date_gmt":"2024-09-21T12:23:48","guid":{"rendered":"https:\/\/workhouse.sweetdishy.com\/?p=4056"},"modified":"2024-09-21T12:23:48","modified_gmt":"2024-09-21T12:23:48","slug":"classical-reversible-gates","status":"publish","type":"post","link":"https:\/\/workhouse.sweetdishy.com\/index.php\/2024\/09\/21\/classical-reversible-gates\/","title":{"rendered":"Classical reversible gates"},"content":{"rendered":"\n

In the early 1970s, this line of thinking prompted Bennett to come up<\/p>\n\n\n\n

with ways to beat the Landauer limit: by introducing reversible computation.<\/p>\n\n\n\n

The gates we have studied so far, such as AND and XOR, are intrinsically<\/p>\n\n\n\n

irreversible since they are two-one functions. An n \u2192 m function can, however,<\/p>\n\n\n\n

be implemented reversibly if it is embedded in a reversible n + m \u2192 m + n<\/p>\n\n\n\n

function.<\/p>\n\n\n\n

The additional m inputs take certain \ufb01xed values, and are referred to<\/p>\n\n\n\n

as ancilla bits, while the extra n outputs are ignored. These are sometimes<\/p>\n\n\n\n

referred to as garbage bits.<\/p>\n\n\n\n

(x, 0) 7\u2212\u2192<\/p>\n\n\n\n

\ue000<\/p>\n\n\n\n

f(x), g(x)<\/p>\n\n\n\n

\ue001<\/p>\n\n\n\n

. (6.13)<\/p>\n\n\n\n

. \u2193 \u2193 &<\/p>\n\n\n\n

input ancilla output garbage<\/p>\n\n\n\n

The advantage of reversibility is that the entire process can be run in<\/p>\n\n\n\n

reverse after storing (copying) the answers, so that all the bits are returned<\/p>\n\n\n\n

to their original states. The garbage is thus e\ufb00ectively recycled! The circuit<\/p>\n\n\n\n

diagram for such a reversible implementation is given in Figure 6.5.<\/p>\n\n\n\n

f<\/p>\n\n\n\n

m bit output f(x)<\/p>\n\n\n\n

n bit input x<\/p>\n\n\n\n

\uf8fc<\/p>\n\n\n\n

\uf8fd<\/p>\n\n\n\n

\uf8fe<\/p>\n\n\n\n

\uf8f1<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8f2<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8f3<\/p>\n\n\n\n

\uf8f1<\/p>\n\n\n\n

\uf8f2<\/p>\n\n\n\n

\uf8f3<\/p>\n\n\n\n

0<\/p>\n\n\n\n

n (ignore)<\/p>\n\n\n\n

m ancillary bits 0<\/p>\n\n\n\n

\uf8fc<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8fd<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8f4<\/p>\n\n\n\n

\uf8fe<\/p>\n\n\n\n

0<\/p>\n\n\n\n

FIGURE 6.5: Reversible implementation of an irreversible function<\/p>\n\n\n\n

The function may be reversible only if the circuit to compute it is built<\/p>\n\n\n\n

out of reversible gates. NOT is a reversible 1-bit gate. A reversible 2-bit gate<\/p>\n\n\n\n

is the CNOT or controlled-NOT gate. This classic gate acts as NOT on the<\/p>\n\n\n\n

1<\/p>\n\n\n\n

k<\/p>\n\n\n\n

B<\/p>\n\n\n\n

= 1.38 \u00d7 10<\/p>\n\n\n\n

\u221223<\/p>\n\n\n\n

J\/K. This constant appears in the relationship between energy and<\/p>\n\n\n\n

temperature at the level of particle constituents of a thermodynamic system.<\/p>\n\n\n\n

\"\"<\/p>\n\n\n\n

112 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n

second (target) input bit if the \ufb01rst (control) bit is set to 1; otherwise it leaves<\/p>\n\n\n\n

it unchanged. The truth table and circuit representation is:<\/p>\n\n\n\n

CNOT:<\/p>\n\n\n\n

x y x<\/p>\n\n\n\n

0<\/p>\n\n\n\n

y<\/p>\n\n\n\n

0<\/p>\n\n\n\n

0 0 0 0<\/p>\n\n\n\n

0 1 0 1<\/p>\n\n\n\n

1 0 1 1<\/p>\n\n\n\n

1 1 1 0<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

y<\/p>\n\n\n\n

x \u2295 y<\/p>\n\n\n\n

(6.14)<\/p>\n\n\n\n

Here the top bit is the control bit. The \ufb01lled circle on the connecting wire<\/p>\n\n\n\n

between the two bits represents control by the value 1. The lower bit is the<\/p>\n\n\n\n

target bit.<\/p>\n\n\n\n

Exercise 6.3. Check that the matrix representation for the CNOT gate is<\/p>\n\n\n\n

C =<\/p>\n\n\n\n

\uf8ee<\/p>\n\n\n\n

\uf8ef<\/p>\n\n\n\n

\uf8ef<\/p>\n\n\n\n

\uf8ef<\/p>\n\n\n\n

\uf8f0<\/p>\n\n\n\n

1 0 0 0<\/p>\n\n\n\n

0 1 0 0<\/p>\n\n\n\n

0 0 0 1<\/p>\n\n\n\n

0 0 1 0<\/p>\n\n\n\n

\uf8f9<\/p>\n\n\n\n

\uf8fa<\/p>\n\n\n\n

\uf8fa<\/p>\n\n\n\n

\uf8fa<\/p>\n\n\n\n

\uf8fb<\/p>\n\n\n\n

.<\/p>\n\n\n\n

Now the CNOT gate is a reversible implementation of the XOR gate. You<\/p>\n\n\n\n

can see that the second output y<\/p>\n\n\n\n

0<\/p>\n\n\n\n

represents the XOR of the inputs. So if we<\/p>\n\n\n\n

ignore the \ufb01rst output, we have here a reversible XOR gate:<\/p>\n\n\n\n

XOR : (x, y) 7\u2192 (x, x \u2295 y). (6.15)<\/p>\n\n\n\n

This is re\ufb02ected in the circuit symbol for CNOT, where the target bit is shown<\/p>\n\n\n\n

with an \u2295 symbol acting on it, controlled by the \ufb01rst bit.<\/p>\n\n\n\n

It is easy to see that this gate is the inverse of itself: if a second CNOT<\/p>\n\n\n\n

acts on the outputs of one CNOT, we get back the inputs to the \ufb01rst CNOT.<\/p>\n\n\n\n

(Note however that a reversible gate is not necessarily its self-inverse.)<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

y<\/p>\n\n\n\n

x \u2295 y<\/p>\n\n\n\n

x \u2295 x \u2295 y = y<\/p>\n\n\n\n

The CNOT gate can be used to reversibly embed several other useful gates<\/p>\n\n\n\n

such as the COPY gate and the SWAP gate:<\/p>\n\n\n\n

COP Y : (x, 0) 7\u2192 (x, x)<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

0<\/p>\n\n\n\n

x<\/p>\n\n\n\n

(6.16)<\/p>\n\n\n\n

SW AP : (x, y) 7\u2192 (y, x)<\/p>\n\n\n\n

x<\/p>\n\n\n\n

S<\/p>\n\n\n\n

y<\/p>\n\n\n\n

y<\/p>\n\n\n\n

x<\/p>\n\n\n\n

(6.17)<\/p>\n\n\n\n

\"\"<\/p>\n\n\n\n

Computation Models and Computational Complexity 113<\/p>\n\n\n\n

\u00d7<\/p>\n\n\n\n

\u2261<\/p>\n\n\n\n

\u00d7<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022 \u2022<\/p>\n\n\n\n

y<\/p>\n\n\n\n

y<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

where (x, y)<\/p>\n\n\n\n

CN OT<\/p>\n\n\n\n

12<\/p>\n\n\n\n

\u2212\u2212\u2212\u2212\u2212\u2212\u2192 (x, x \u2295 y)<\/p>\n\n\n\n

CN OT<\/p>\n\n\n\n

21<\/p>\n\n\n\n

\u2212\u2212\u2212\u2212\u2212\u2212\u2192 (y, x \u2295 y)<\/p>\n\n\n\n

CN OT<\/p>\n\n\n\n

12<\/p>\n\n\n\n

\u2212\u2212\u2212\u2212\u2212\u2212\u2192 (y, x).<\/p>\n\n\n\n

6.3.2 Universal reversible gates<\/p>\n\n\n\n

The classical universal sets obtained earlier, including AND, NOR, etc.<\/p>\n\n\n\n

are not reversible. The question now is whether our pet CNOT is universal.<\/p>\n\n\n\n

One way to see why it is not, is given by Preskill [57]. It turns out that the<\/p>\n\n\n\n

CNOT gate, as in fact, all 2-bit reversible gates, is an a\ufb03ne transformation.<\/p>\n\n\n\n

Any 2-bit gate whose output is a permutation of the input bits is of the form<\/p>\n\n\n\n

“<\/p>\n\n\n\n

x<\/p>\n\n\n\n

y<\/p>\n\n\n\n

#<\/p>\n\n\n\n

7\u2192 M<\/p>\n\n\n\n

“<\/p>\n\n\n\n

x<\/p>\n\n\n\n

y<\/p>\n\n\n\n

#<\/p>\n\n\n\n

+<\/p>\n\n\n\n

“<\/p>\n\n\n\n

a<\/p>\n\n\n\n

b<\/p>\n\n\n\n

#<\/p>\n\n\n\n

(6.18)<\/p>\n\n\n\n

where M is an invertible matrix and a and b are constants. There are invert-<\/p>\n\n\n\n

ible functions that are non-a\ufb03ne, especially for n > 3. Therefore, 2-bit gates<\/p>\n\n\n\n

are insu\ufb03cient to generate such functions. Research has shown that certain<\/p>\n\n\n\n

conditional 3-bit gates are in fact universal. The most important for these are:<\/p>\n\n\n\n

\u2022 gate: T is a doubly controlled NOT gate. Two control bits have to be<\/p>\n\n\n\n

set to 1 for NOT to act on the third bit. Else nothing changes. The truth<\/p>\n\n\n\n

table and circuit representation are as follows:<\/p>\n\n\n\n

x y z x<\/p>\n\n\n\n

0<\/p>\n\n\n\n

y<\/p>\n\n\n\n

0<\/p>\n\n\n\n

z<\/p>\n\n\n\n

0<\/p>\n\n\n\n

0 0 0 0 0 0<\/p>\n\n\n\n

0 0 1 0 0 1<\/p>\n\n\n\n

0 1 0 0 1 0<\/p>\n\n\n\n

0 1 1 0 1 1<\/p>\n\n\n\n

1 0 0 1 0 0<\/p>\n\n\n\n

1 0 1 1 0 1<\/p>\n\n\n\n

1 1 0 1 1 1<\/p>\n\n\n\n

1 1 1 1 1 0<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

y<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

y<\/p>\n\n\n\n

z<\/p>\n\n\n\n

z \u2295xy<\/p>\n\n\n\n

(6.19)<\/p>\n\n\n\n

\"\"<\/p>\n\n\n\n

114 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n

\u2022 Fredkin gate: F is a controlled swap gate. If the control bit is set, then<\/p>\n\n\n\n

the other two bits are swapped.<\/p>\n\n\n\n

x y z x<\/p>\n\n\n\n

0<\/p>\n\n\n\n

y<\/p>\n\n\n\n

0<\/p>\n\n\n\n

z<\/p>\n\n\n\n

0<\/p>\n\n\n\n

0 0 0 0 0 0<\/p>\n\n\n\n

0 0 1 0 0 1<\/p>\n\n\n\n

0 1 0 0 1 0<\/p>\n\n\n\n

0 1 1 0 1 1<\/p>\n\n\n\n

1 0 0 1 0 0<\/p>\n\n\n\n

1 0 1 1 1 0<\/p>\n\n\n\n

1 1 0 1 0 1<\/p>\n\n\n\n

1 1 1 1 1 1<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

y<\/p>\n\n\n\n

\u00d7<\/p>\n\n\n\n

xy + \u00afxz<\/p>\n\n\n\n

z<\/p>\n\n\n\n

\u00d7<\/p>\n\n\n\n

xz + \u00afxy<\/p>\n\n\n\n

(6.20)<\/p>\n\n\n\n

Exercise 6.4. Find out the matrix representations for the T and F gates.<\/p>\n\n\n\n

Box 6.1: Billiard Ball Reversible Computer<\/p>\n\n\n\n

The Fredkin gate has an interesting origin. It arose out of a mechanical<\/p>\n\n\n\n

model for reversible computation based on elastic collisions of a system of<\/p>\n\n\n\n

billiard balls and re\ufb02ecting walls in a frictionless environment, proposed in<\/p>\n\n\n\n

1982 by Fredkin and To\ufb00oli [35]. A ball appearing at a port represents a<\/p>\n\n\n\n

logical 1 at that port, while the absence of a ball at a port represents a logical<\/p>\n\n\n\n

0. The movement is restricted to a grid with unit distance, and the balls have<\/p>\n\n\n\n

radius 1\/<\/p>\n\n\n\n

\u221a<\/p>\n\n\n\n

2 to capture discrete time steps. Inside the \u201ccomputer\u201d, a billiard<\/p>\n\n\n\n

ball shot forward in a direction 45<\/p>\n\n\n\n

\u25e6<\/p>\n\n\n\n

up could collide with another ball or with<\/p>\n\n\n\n

horizontal re\ufb02ecting walls, so that it always stays on the grid. At the output<\/p>\n\n\n\n

ports one obtains a readout of the process based on which ports are occupied<\/p>\n\n\n\n

and which are not. A series of well-placed re\ufb02ectors would achieve a circuit<\/p>\n\n\n\n

built out of Fredkin gates. Since the collisions of the balls with the re\ufb02ectors<\/p>\n\n\n\n

are nearly perfectly elastic, no energy is lost and we have an energy-conserving<\/p>\n\n\n\n

implementation of a reversible computation. A further property of the Fredkin<\/p>\n\n\n\n

gate, re\ufb02ected by the billiard ball model, is that it is conservative, that is, the<\/p>\n\n\n\n

number of 1\u2019s in the input is preserved in the output. This just translates<\/p>\n\n\n\n

into no ball being lost in the computer. Conservativeness is also a concern of<\/p>\n\n\n\n

physical implementations of computation.<\/p>\n\n\n\n

One way to see how such a 3-bit gate may be universal is to show how<\/p>\n\n\n\n

to implement the (irreversible) universal set {AND, NOT, OR, COPY} using<\/p>\n\n\n\n

only this gate.<\/p>\n\n\n\n

\"\"<\/p>\n\n\n\n

Computation Models and Computational Complexity 115<\/p>\n\n\n\n

Example 6.3.1. The universality of the Fredkin gate can be demonstrated by<\/p>\n\n\n\n

using it to implement the four universal logic gates:<\/p>\n\n\n\n

AND OR NOT and COPY<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

y<\/p>\n\n\n\n

\u00d7<\/p>\n\n\n\n

0<\/p>\n\n\n\n

\u00d7<\/p>\n\n\n\n

xy<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

y<\/p>\n\n\n\n

\u00d7<\/p>\n\n\n\n

x \u2227 y<\/p>\n\n\n\n

1<\/p>\n\n\n\n

\u00d7<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

0<\/p>\n\n\n\n

\u00d7<\/p>\n\n\n\n

x<\/p>\n\n\n\n

1<\/p>\n\n\n\n

\u00d7<\/p>\n\n\n\n

\u00afx<\/p>\n\n\n\n

For the output of the OR gate, we have used<\/p>\n\n\n\n

x + \u00afxy = x + (1 \u2212 x)y = x + y \u2212 xy = x \u2227 y.<\/p>\n\n\n\n

Also note how the required output appears at one port and the other ports<\/p>\n\n\n\n

are ignored. This is a common feature in implementing irreversible gates em-<\/p>\n\n\n\n

bedded in bigger, reversible ones.<\/p>\n\n\n\n

Exercise 6.5. Show how {AND, NOT, OR, COPY} can be implemented by Tof-<\/p>\n\n\n\n

foli gates alone.<\/p>\n\n\n\n

Thus, these classical universal gates can implement any function, provided<\/p>\n\n\n\n

some of the inputs are chosen to take \ufb01xed values, and some of the outputs<\/p>\n\n\n\n

are ignored, as in Figure 6.5.<\/p>\n\n\n\n

Example 6.3.2. A reversible half-adder:<\/p>\n\n\n\n

Let\u2019s see how to build a simple reversible circuit, for example a 1-bit adder,<\/p>\n\n\n\n

using To\ufb00oli gates alone. The function we need must calculate the sum which<\/p>\n\n\n\n

is addition mod 2 of the inputs: s = x \u2295 y, and the carry which is the AND<\/p>\n\n\n\n

of the inputs: c = xy.<\/p>\n\n\n\n

f<\/p>\n\n\n\n

add<\/p>\n\n\n\n

(x, y . . .) = (x, y, x \u2295 y, xy).<\/p>\n\n\n\n

Check that the following circuit does what we need:<\/p>\n\n\n\n

1<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

\u2022 \u2022<\/p>\n\n\n\n

x<\/p>\n\n\n\n

y<\/p>\n\n\n\n

\u2022<\/p>\n\n\n\n

s = x \u2295 y<\/p>\n\n\n\n

0<\/p>\n\n\n\n

c = xy<\/p>\n\n\n\n

Exercise 6.6. Construct a half-adder using Fredkin gates alone.<\/p>\n","protected":false},"excerpt":{"rendered":"

In the early 1970s, this line of thinking prompted Bennett to come up with ways to beat the Landauer limit: by introducing reversible computation. The gates we have studied so far, such as AND and XOR, are intrinsically irreversible since they are two-one functions. An n \u2192 m function can, however, be implemented reversibly if […]<\/p>\n","protected":false},"author":1,"featured_media":4040,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[495],"tags":[],"class_list":["post-4056","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computation-models-and-computational-complexity"],"jetpack_featured_media_url":"https:\/\/workhouse.sweetdishy.com\/wp-content\/uploads\/2024\/09\/download-1.png","_links":{"self":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4056","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/comments?post=4056"}],"version-history":[{"count":1,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4056\/revisions"}],"predecessor-version":[{"id":4057,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4056\/revisions\/4057"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media\/4040"}],"wp:attachment":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media?parent=4056"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4056"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4056"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}