UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Logic circuits from zero forcing

Burgarth, D; Giovannetti, V; Hogben, L; Severini, S; Young, M; (2014) Logic circuits from zero forcing. Natural Computing 10.1007/s11047-014-9438-5. (In press). Green open access


Download (502kB)


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.

Type: Article
Title: Logic circuits from zero forcing
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/s11047-014-9438-5
Publisher version: http://dx.doi.org/10.1007/s11047-014-9438-5
Additional information: �Copyright The Author(s) 2014. This article is published with open access at Springerlink.com This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
URI: http://discovery.ucl.ac.uk/id/eprint/1322008
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item