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.


The steps of back forcing
© Copyright Policy - OpenAccess
Related In: Results  -  Collection


getmorefigures.php?uid=PMC4541710&req=5

Fig7: The steps of back forcing

Mentions: The phenomenon will be called back forcing, because it is induced by the color-change rule acting backwards with respect to the direction from input to output in the whole circuit. The gadget exhibits back forcing conditionally on having input . The type of back forcing in can be called transmittal back forcing, because if something back forces its output black then the gate transmits the back force, i.e., it modifies the color of the output vertex in a gate used previously. Figure 7 clarifies the dynamics.Fig. 7


Logic circuits from zero forcing.

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

The steps of back forcing
© Copyright Policy - OpenAccess
Related In: Results  -  Collection

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

Fig7: The steps of back forcing
Mentions: The phenomenon will be called back forcing, because it is induced by the color-change rule acting backwards with respect to the direction from input to output in the whole circuit. The gadget exhibits back forcing conditionally on having input . The type of back forcing in can be called transmittal back forcing, because if something back forces its output black then the gate transmits the back force, i.e., it modifies the color of the output vertex in a gate used previously. Figure 7 clarifies the dynamics.Fig. 7

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.