title: Logic circuits from zero forcing.
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.
authors: Department of Mathematics and Physics, Aberystwyth University, Aberystwyth, SY23 3BZ UK.
authors: Daniel
authors: D
authors: Burgarth
authors: NEST, Scuola Normale Superiore and Istituto Nanoscienze-CNR, Piazza dei Cavalieri 7, 56126 Pisa, Italy.
authors: Vittorio
authors: V
authors: Giovannetti
authors: Department of Mathematics, Iowa State University, Ames, IA 50011 USA ; American Institute of Mathematics, 360 Portage Ave, Palo Alto, CA 94306 USA.
authors: Leslie
authors: L
authors: Hogben
authors: Department of Computer Science, University College London, London, WC1E 6BT UK ; Department of Physics and Astronomy, University College London, London, WC1E 6BT UK.
authors: Simone
authors: S
authors: Severini
authors: Department of Mathematics, Iowa State University, Ames, IA 50011 USA.
authors: Michael
authors: M
authors: Young
keywords: Adiabatic quantum computation; Logic circuits; Zero forcing