Limits...
Logic circuits from zero forcing.

Burgarth D, Giovannetti V, Hogben L, Severini S, Young M - Nat Comput (2015)

Bottom Line: Finally, we show that zero forcing can be also used to implement reversible computation.The model introduced here provides a potentially new tool in the analysis of Boolean functions, with particular attention to monotonicity.It is an open technical problem to verify whether there is a link between zero forcing and computation with contact circuits.

View Article: PubMed Central - PubMed

Affiliation: Department of Mathematics and Physics, Aberystwyth University, Aberystwyth, SY23 3BZ UK.

ABSTRACT

We design logic circuits based on the notion of zero forcing on graphs; each gate of the circuits is a gadget in which zero forcing is performed. We show that such circuits can evaluate every monotone Boolean function. By using two vertices to encode each logical bit, we obtain universal computation. We also highlight a phenomenon of "back forcing" as a property of each function. Such a phenomenon occurs in a circuit when the input of gates which have been already used at a given time step is further modified by a computation actually performed at a later stage. Finally, we show that zero forcing can be also used to implement reversible computation. The model introduced here provides a potentially new tool in the analysis of Boolean functions, with particular attention to monotonicity. Moreover, in the light of applications of zero forcing in quantum mechanics, the link with Boolean functions may suggest a new directions in quantum control theory and in the study of engineered quantum spin systems. It is an open technical problem to verify whether there is a link between zero forcing and computation with contact circuits.

No MeSH data available.


Physical bits for  and  in a dual rail encoding
© Copyright Policy - OpenAccess
Related In: Results  -  Collection


getmorefigures.php?uid=PMC4541710&req=5

Fig9: Physical bits for and in a dual rail encoding

Mentions: The idea is to adopt a dual rail strategy, where two vertices are employed to encode a single logical bit. Specifically, as shown in Fig. 9, in this scheme we associate the logical bit 0 to a configuration in which (say) the first vertex is colored in black while the second is kept white, and the logical 1 to the opposite configuration (i.e. the first vertex being left white and the second one being colored black). With such encoding we can now design the gate NOT by simply drawing a graph in which the nodes are exchanged at the output (see Fig. 10). Also a dual rail AND gate can be easily realized. Universal computation is hence achieved by constructing a NAND gate via concatenation of AND with NOT and by observing that the COPY gate for the dual rail encoding is simply obtained by just applying to both the nodes that form a bit the transformation of Fig. 5. Once universal computation has been achieved, we can easily turn it into a reversible one, e.g., by building a Toffoli gate (Toffoli 1980). This to remark that even if zero forcing is an irreversible process, it can still be used to induce a reversible computational dynamics.Fig. 9


Logic circuits from zero forcing.

Burgarth D, Giovannetti V, Hogben L, Severini S, Young M - Nat Comput (2015)

Physical bits for  and  in a dual rail encoding
© Copyright Policy - OpenAccess
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC4541710&req=5

Fig9: Physical bits for and in a dual rail encoding
Mentions: The idea is to adopt a dual rail strategy, where two vertices are employed to encode a single logical bit. Specifically, as shown in Fig. 9, in this scheme we associate the logical bit 0 to a configuration in which (say) the first vertex is colored in black while the second is kept white, and the logical 1 to the opposite configuration (i.e. the first vertex being left white and the second one being colored black). With such encoding we can now design the gate NOT by simply drawing a graph in which the nodes are exchanged at the output (see Fig. 10). Also a dual rail AND gate can be easily realized. Universal computation is hence achieved by constructing a NAND gate via concatenation of AND with NOT and by observing that the COPY gate for the dual rail encoding is simply obtained by just applying to both the nodes that form a bit the transformation of Fig. 5. Once universal computation has been achieved, we can easily turn it into a reversible one, e.g., by building a Toffoli gate (Toffoli 1980). This to remark that even if zero forcing is an irreversible process, it can still be used to induce a reversible computational dynamics.Fig. 9

Bottom Line: Finally, we show that zero forcing can be also used to implement reversible computation.The model introduced here provides a potentially new tool in the analysis of Boolean functions, with particular attention to monotonicity.It is an open technical problem to verify whether there is a link between zero forcing and computation with contact circuits.

View Article: PubMed Central - PubMed

Affiliation: Department of Mathematics and Physics, Aberystwyth University, Aberystwyth, SY23 3BZ UK.

ABSTRACT

We design logic circuits based on the notion of zero forcing on graphs; each gate of the circuits is a gadget in which zero forcing is performed. We show that such circuits can evaluate every monotone Boolean function. By using two vertices to encode each logical bit, we obtain universal computation. We also highlight a phenomenon of "back forcing" as a property of each function. Such a phenomenon occurs in a circuit when the input of gates which have been already used at a given time step is further modified by a computation actually performed at a later stage. Finally, we show that zero forcing can be also used to implement reversible computation. The model introduced here provides a potentially new tool in the analysis of Boolean functions, with particular attention to monotonicity. Moreover, in the light of applications of zero forcing in quantum mechanics, the link with Boolean functions may suggest a new directions in quantum control theory and in the study of engineered quantum spin systems. It is an open technical problem to verify whether there is a link between zero forcing and computation with contact circuits.

No MeSH data available.