{"id":4050,"date":"2024-09-21T12:19:42","date_gmt":"2024-09-21T12:19:42","guid":{"rendered":"https:\/\/workhouse.sweetdishy.com\/?p=4050"},"modified":"2024-09-21T12:19:42","modified_gmt":"2024-09-21T12:19:42","slug":"the-circuit-model-and-universal-gates","status":"publish","type":"post","link":"https:\/\/workhouse.sweetdishy.com\/index.php\/2024\/09\/21\/the-circuit-model-and-universal-gates\/","title":{"rendered":"The Circuit Model and Universal Gates"},"content":{"rendered":"\n<p>Classical computation using binary variables works on Boolean logic, and<\/p>\n\n\n\n<p>implementation of basic logical operations are done through logic gates that<\/p>\n\n\n\n<p>are well known. We will revise their behaviour and notation and express their<\/p>\n\n\n\n<p>action as matrix operators.<\/p>\n\n\n\n<p>We will think of a computation as e\ufb00ected by a circuit evaluating some<\/p>\n\n\n\n<p>Boolean function whose input is a binary n-bit number, and output may be<\/p>\n\n\n\n<p>an m-bit number:<\/p>\n\n\n\n<p>f : {0, 1}<\/p>\n\n\n\n<p>n<\/p>\n\n\n\n<p>7\u2192 {0, 1}<\/p>\n\n\n\n<p>m<\/p>\n\n\n\n<p>. (6.1)<\/p>\n\n\n\n<p>As a circuit this is represented in the following diagram:<\/p>\n\n\n\n<p>f<\/p>\n\n\n\n<p>n m<\/p>\n\n\n\n<p>\uf8fc<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8fd<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8fe<\/p>\n\n\n\n<p>\uf8f1<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8f2<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8f4<\/p>\n\n\n\n<p>\uf8f3<\/p>\n\n\n\n<p>The computation is e\ufb00ected by a combination of logic gates. One can<\/p>\n\n\n\n<p>represent an n-bit input to a gate as a 2<\/p>\n\n\n\n<p>n<\/p>\n\n\n\n<p>\u00d7 1 column vector and the output<\/p>\n\n\n\n<p>as a 2<\/p>\n\n\n\n<p>m<\/p>\n\n\n\n<p>\u00d7 1 column vector. The action of the gate is then represented by a<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>m<\/p>\n\n\n\n<p>\u00d7 2<\/p>\n\n\n\n<p>n<\/p>\n\n\n\n<p>matrix.<\/p>\n\n\n\n<p>A single classical bit takes two mutually exclusive logical values, that can<\/p>\n\n\n\n<p>be written as the two basis vectors:<\/p>\n\n\n\n<p>0 \u2261<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>, 1 \u2261<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>. (6.2)<\/p>\n\n\n\n<p>The logical operation NOT takes a bit and gives its complement: x \u2192 \u00afx. We<\/p>\n\n\n\n<p>can algebraically represent this operation of negation as x \u2192 1 \u2212x. Physically<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p>it ca nbe implemented by the NOT gate, which \ufb02ips the value of the input<\/p>\n\n\n\n<p>bit, as speci\ufb01ed by the truth table and operation<\/p>\n\n\n\n<p>Input Output<\/p>\n\n\n\n<p>0 1<\/p>\n\n\n\n<p>1 0<\/p>\n\n\n\n<p>,<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>\u2192<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>,<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>\u2192<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>. (6.3)<\/p>\n\n\n\n<p>This action can be executed by operation of the following 2 \u00d7 2 matrix on<\/p>\n\n\n\n<p>either of the bit values:<\/p>\n\n\n\n<p>NOT =<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>0 1<\/p>\n\n\n\n<p>1 0<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>. (6.4)<\/p>\n\n\n\n<p>There are more operations possible on two and higher bits. The two-bit num-<\/p>\n\n\n\n<p>bers are given by 4 column vectors<\/p>\n\n\n\n<p>00 \u2261<\/p>\n\n\n\n<p>\uf8ee<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8f0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>\uf8f9<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fb<\/p>\n\n\n\n<p>, 01 \u2261<\/p>\n\n\n\n<p>\uf8ee<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8f0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>\uf8f9<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fb<\/p>\n\n\n\n<p>, 10 \u2261<\/p>\n\n\n\n<p>\uf8ee<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8f0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>\uf8f9<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fb<\/p>\n\n\n\n<p>, 11 \u2261<\/p>\n\n\n\n<p>\uf8ee<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8f0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>\uf8f9<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fb<\/p>\n\n\n\n<p>. (6.5)<\/p>\n\n\n\n<p>A very useful two-bit operation is the AND, which gives an output 1 if an only<\/p>\n\n\n\n<p>if both input bits are 1. As a gate, it is given by the truth table and operation<\/p>\n\n\n\n<p>Input Output<\/p>\n\n\n\n<p>00 0<\/p>\n\n\n\n<p>01 0<\/p>\n\n\n\n<p>10 0<\/p>\n\n\n\n<p>11 1<\/p>\n\n\n\n<p>,<\/p>\n\n\n\n<p>\uf8ee<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8f0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>\uf8f9<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fb<\/p>\n\n\n\n<p>\u2192<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>,<\/p>\n\n\n\n<p>\uf8ee<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8f0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>\uf8f9<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fb<\/p>\n\n\n\n<p>\u2192<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>,<\/p>\n\n\n\n<p>\uf8ee<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8f0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>\uf8f9<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fb<\/p>\n\n\n\n<p>\u2192<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>,<\/p>\n\n\n\n<p>\uf8ee<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8ef<\/p>\n\n\n\n<p>\uf8f0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>\uf8f9<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fa<\/p>\n\n\n\n<p>\uf8fb<\/p>\n\n\n\n<p>\u2192<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>0<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>.(6.6)<\/p>\n\n\n\n<p>To represent this operation we need a 2<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>\u00d7 2 matrix:<\/p>\n\n\n\n<p>AND =<\/p>\n\n\n\n<p>&#8220;<\/p>\n\n\n\n<p>1 1 1 0<\/p>\n\n\n\n<p>0 0 0 1<\/p>\n\n\n\n<p>#<\/p>\n\n\n\n<p>(6.7)<\/p>\n\n\n\n<p>Algebraically, AND can be executed by (x, y) \u2192 x \u2227 y = xy.<\/p>\n\n\n\n<p>Various other logical operations on two bits are possible, such as the OR,<\/p>\n\n\n\n<p>the complements of AND and OR called NAND and NOR respectively, and<\/p>\n\n\n\n<p>the exclusive-OR or XOR. These along with their symbols and algebraic equiv-<\/p>\n\n\n\n<p>alents are listed in Table 6.1.<\/p>\n\n\n\n<p>Exercise 6.2. Find the matrix representations of the OR and XOR gates.<\/p>\n\n\n\n<p>In classical computations, we often assume that we work on copies of a<\/p>\n\n\n\n<p><img loading=\"lazy\" decoding=\"async\" alt=\"\" src=\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bg84.png\" width=\"608\" height=\"777\"><\/p>\n\n\n\n<p>Computation Models and Computational Complexity 107<\/p>\n\n\n\n<p>TABLE 6.1: Basic classical gates and their symbols.<\/p>\n\n\n\n<p>Gate Logical Symbol Arithmetic Equivalent Circuit Symbol<\/p>\n\n\n\n<p>NOT: \u00afx 1 \u2212 x<\/p>\n\n\n\n<p>AND: x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>\u2227 x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>OR: x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>\u2228 x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>+ x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>\u2212 x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>XOR: x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>\u2295 x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>+ x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>\u2212 2x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>NOR: x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>\u2193 x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>1 \u2212 x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>\u2212 x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>+ x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>NAND: x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>\u2191 x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>1 \u2212 x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>COPY: (fanout) x \u2212\u2192 x, x<\/p>\n\n\n\n<p>SWAP: (crossover) x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>, x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>\u2212\u2192 x<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>, x<\/p>\n\n\n\n<p>1<\/p>\n\n\n\n<p>certain input bit, and sometimes inputs are switched. These are included ex-<\/p>\n\n\n\n<p>plicitly among the logic gates, as actions we need to perform though we may<\/p>\n\n\n\n<p>ignore them at times. This becomes especially important when we map clas-<\/p>\n\n\n\n<p>sical functions to quantum ones, because in manipulating qubits, copy can no<\/p>\n\n\n\n<p>longer be implemented, and swap is non-trivial.<\/p>\n\n\n\n<p>We can concatenate gates in series to obtain an e\ufb00ective action by multi-<\/p>\n\n\n\n<p>plying the matrices representing the gates:<\/p>\n\n\n\n<p>A B<\/p>\n\n\n\n<p>\u2261<\/p>\n\n\n\n<p>BA<\/p>\n\n\n\n<p>.<\/p>\n\n\n\n<p>Further, gates could act in parallel in which case the e\ufb00ective action is<\/p>\n\n\n\n<p>obtained by taking the tensor product of the corresponding matrices.<\/p>\n\n\n\n<p>A<\/p>\n\n\n\n<p>\u2261<\/p>\n\n\n\n<p>B<\/p>\n\n\n\n<p>A \u2297 B<\/p>\n\n\n\n<p>In general, the evaluation of a function can be converted to an algorithm<\/p>\n\n\n\n<p>involving logic gates acting on the input bits, and a corresponding circuit can<\/p>\n\n\n\n<p>be constructed. Now an n \u2192 m function is equivalent to evaluating each of<\/p>\n\n\n\n<p>the m outputs as a {0, 1}<\/p>\n\n\n\n<p>n<\/p>\n\n\n\n<p>\u2192 {0, 1} function. We can therefore restrict our<\/p>\n\n\n\n<p>attention to n \u2192 1 functions. Note that for a given n there are 2<\/p>\n\n\n\n<p>2<\/p>\n\n\n\n<p>n<\/p>\n\n\n\n<p>such<\/p>\n\n\n\n<p>distinct functions.<\/p>\n\n\n\n<p>Now we show that any such function can be evaluated using a small subset<\/p>\n\n\n\n<p>of the above logic gates: a set of universal gates.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Classical computation using binary variables works on Boolean logic, and implementation of basic logical operations are done through logic gates that are well known. We will revise their behaviour and notation and express their action as matrix operators. We will think of a computation as e\ufb00ected by a circuit evaluating some Boolean function whose input [&hellip;]<\/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-4050","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\/4050","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=4050"}],"version-history":[{"count":1,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4050\/revisions"}],"predecessor-version":[{"id":4051,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4050\/revisions\/4051"}],"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=4050"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4050"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4050"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}