Universal logic gates

A set G of logic gates is universal if an arbitrary ri-variable Boolean function T can be written as a composition of the logic gates in G a universal set of gates 9u- - dm is. sometimes also said to gorm a basis set for T. It is easy to show that the set consisting of the Boolean operators AND, OR and NOT, for example, is universal.  

Consider an arbitrary set of Boolean input values, Xi. Xn- Using only the Boolean operators AND and NOT, we can write down an expre.ssion which takes the value 1 if and only if a particular configuration of O s and I s appears in the input. Suppose that n = 6 and we want to construct an expression that equals one if and only if xi = X3 = X4 = X5 = 1 and. X2 = xe = 0. A little thought will show that the required expression is given by joining the string of six Boolean variables with the AND operator, substituting NOT(xi) for all values x)i that are required to equal zero  

In order to construct an expression representing an arbitrary Boolean function J-, we must therefore j)erform two simple steps (1) construct expressions of the above form for each occurrence of a 1 in J- s truth table, and (2) join each such expression by the OR operator. Since each term is explicitly constructed so as to pick out a particular input configuration yielding the value 1 under J-, no more than one such term in the resulting OR expansion can yield the value 1 for a given input. All other configurations are identically zero. 

Note that while the set AND, OR, NOT forms a complete basis, it is not a minimal basis i.e. a basis set such that no subset of the set is itself a complete basis. It is easy to show, however, that the subset consisting of the AND and NOT operators is a minimal basis. Similarly, there also exist individual gates, such as the NAND and NOR gates (see figure 6.6), that are universal by themselves. 

Consider the NAND gate. The NAND gate yields a T unless both input values equal 1 . If the value of either one of input lines is fixed at 1 , the gate is equivalent to the NOT operator i.e. the gate yields an output of T if the free input-line equals 0 and a 0 if the free input-line equals T . If we now use the NOT operator to complement the NAND operator input line, we obtain the AND operator. Since we have already observed that the set AND, NOT is universal, we have thus also shown that the NAND operator is, by itself, universal.  

---

Having demonstrated, by construction, that each of the computational elements required of a conventional digital computer for its own computation - namely, (1) digital bit-stream signals, (2) wires, (3) redirection circuits, (4) an internal system clock, (5) a (potentially infinite) memory, and (6) a set of universal logic gates... 

Yadav C, Roy S. Ultrafast all-optical universal logic gates with graphene and graphene-oxide metal porphyrin composites. J Comput Electron 2014 14 209-13. 

In classical computation, any logical operation can be done from combinations of the logic gate nand (NOT-AND). The similar is true in quantum computing any quantum operation can be implemented using a set of universal logic gates. Such a set is composed of the Hadamard (H), controlled NOT (CNOT), phase (S) and jr/8 (T). 

The only ingredient in the proof of Life s universality that we have not yet discussed is memory storage. While a finite memory is fairly easy to implement with wires and logic gates - for example, glider-stream-encoded information can be made to circulate around a memory circuit contained within the computer - the construction of an arbitrarily large memory requires a bit more work,... 

The question which Landauer failed to ask in 1961 [land61] and which was answered first by Bennett in 1973 [benu73] and later, independently, by Predkin [fredkiu82], is whether irreversible logic gates are essential to computation. Might it be possible to construct a universal set out of reversible gates ... 

Consider a logic gate with 3-iiiput and 3-output lines. Edward Fredkin, motivated by a deep conviction in a fundamental connection between a discrete, finite physics and reversible computation [wrightSS], discovered a simple universal 3-input/ 3-output logic function that now bears his name [fredkin82]. 

Figure 7.3 Schematic representation of the operations of some quantum logic gates acting on two qubits. In quantum computation, single qubit rotations (Figure 7.2) and CNOT (controlled-NOT) or INSWAP quantum gates are universal.

SLI is not specific to molecular eigenstates, but universal to the superposition of any eigenstates in a variety of quantum systems. It is thus expected as a new tool for quantum logic gates not only in MEIP but also for other systems such as atoms, ions, and quantum dots. SLI also provides a new method to manipulate WPs with fs laser pulses in general applications of coherent control. 

A. Credi, Molecular-level machines and logic gates , Ph. D. Dissertation, University of Bologna, 1998. 

Obviously that B and C can be recovered by applying the gate to B and C. Tha-efore, the gate is reversible. Fredkin gate can be used to built an universal set of classical logic gates. 

The ability of an experimental technique for preparing initial states and implementing an universal set of logic gates are two important features for its use in quantum information processing. Another equally important requirement is the characterization of the output state. In many cases we wish more than a simple readout, but a full characterization of the system state. This can achieved by determining all elements of the density matrix of the... 

When used together, the three gates NOT, CONTROLLED NOT and CONTROLLED CONTROLLED NOT constitute a universal reversible set, and can thus be used to construct an arbitrary logical circuit. 

Grote, J. G., Digital logic and reconiigurable interconnects using aluminum gallium arsenide electro-optic Fredkin gates, Ph.D. disseitation. University of Dayton, Dayton, OH, 1994. 

NAND logic is also in the universal gate category, according to electronic engineers. The current inability of molecular-level counterparts to inherit this mantle has been mentioned previously in Section 2.5. NAND logic means that the output achieves the state 0 only when the inputs are both simultaneously 1. 

---