1.1 Preliminaries
We order the two elements of a set \(\Sigma =\{0,1\}\) such that \(0<1\). This extends to a partial ordering on the set \(\Sigma ^{n}=\{0,1\}^{n}\) by comparing words coordinate-wise. Let \(x=x_{1},\ldots ,x_{n}\) and \(y=y_{1},\ldots ,y_{n}\). Here, \(x\succeq y\) means that \(x_{i}\ge y_{i}\), for every \(i=1,\ldots ,n\). A Boolean function \(f:\Sigma ^{n}\longrightarrow \Sigma \) is monotone when \(f\left( x\right) \ge\, f\left( y\right) \) if \(x\succeq y\), for every \(x,y\in \Sigma ^{n}\). Clearly, because of this, the symbol “\(\succeq \)” has a different meaning than majorization as a preorder of vectors.
Counted by the Dedekind numbers, monotone Boolean functions have an important role for proving lower bounds of circuit complexity (see, e.g., Leeuwen
1990, Chapter 14.4). Remarkably, any function obtained by composition of monotone Boolean functions is itself monotone. Examples of monotone Boolean functions are the conjunction AND and the disjunction OR. Indeed, every monotone Boolean function can be realized by AND and OR operations (but without NOT). Monotone Boolean functions are important in applications, for example, in the implementation of a class of non-linear digital filters called stack filters (Astola et al.
1997), in voting schemes, reliability theory, stability of hypergraphs, etc. Important methods for obtaining non-trivial bounds on specific monotone Boolean functions have been studied (see, e.g., the seminal work of Razborov
1985, and Alon and Boppana
1986).
The central topic of this paper is a connection between monotone Boolean function and zero forcing. The concept of
zero forcing on graphs is a recent idea that is part of a program studying minimum ranks of matrices with specific combinatorial constraints (American Institute of Mathematics
2008). Zero forcing has been also called graph infection and graph propagation in the areas related to quantum dynamics and control theory of quantum mechanical systems (Burgarth and Giovannetti
2007; Severini
2008).
In quantum mechanics, zero forcing is a technique for determining the algebraic controllability of a many-body quantum system by operating on the particles of a proper subsystem only. The technique is important because it does not require the knowledge of the spectral properties of the physical operator governing the system, but only topological information about the interactions, i.e., the graph of the interactions.
Notice that, in the context described here, the term “zero forcing” seems to be unfortunate, because we are forcing ones, not zeros. However, we keep the term given that this is now the most commonly used in the literature. We will skip alternative definitions of zero forcing. The interested reader may see the references American Institute of Mathematics (
2008), Burgarth et al. (
2009), Burgarth and Giovannetti (
2007).
For the purpose of formally describing zero forcing, we first need to define a color-change rule: if \(G=(V,E)\) is a graph with each vertex colored either white or black, \(u\) is a black vertex of \(G\), and exactly one neighbor \(v\) of \(u\) is white, then change the color of \(v\) to black. Given a coloring of \(G\), the final coloring is the result of applying the color-change rule until no more changes are possible. Of course, the final coloring can include different vertices depending on the initial configuration. A zero forcing set for \(G\) is a set \(Z\subseteq V\left( G\right) \) such that if the elements of \(Z\) are initially colored black and the elements of \(V(G)\backslash Z\) are colored white, the final coloring of \(G\) is all black.
In linear algebraic terms, zero forcing is related to certain minimum rank/maximum nullity problems of matrices associated to graphs (see American Institute of Mathematics
2008). As it usually happens for rank related questions, minimizing the size of zero forcing sets is a difficult combinatorial optimization problem, which turns out to be hard whose solution is hard even to approximate. (The PhD thesis of Aazami
2008, presents a detailed analysis.)
1.2 Results
In the next section, we prove that zero forcing on graphs realizes all monotone Boolean functions, and highlight some simple related facts. The connection between zero forcing and circuits is obtained by associating a graph to each logic gate. We will show that the functions AND and OR are indeed easily realized by two different gadgets with a few vertices. This is not the first work observing that monotone Boolean functions can be realized in a combinatorial setting. For example, Demaine et al. (
2012) have used the movements of a collections of simple interlocked polygons for the same purpose. Realizing general Boolean functions, or even some special classes, in non-standard computational models, has the potential of uncovering new mathematical ideas. These may help in practice for reformulating optimization problems, and more abstractly to establish lower bounds and to quantify resources. On the other side, we know that zero forcing can be directly used in the laboratory to optimize control operations on spin systems. For this reason, observing that the associated dynamical process is a computational primitive can be important to introduce parameters to quantify complexity of the physical evolution. With this aspects in mind, links between zero forcing and the abstract notion of computation are useful.
In Sect.
3, we describe the phenomenon of
back forcing in the circuit. The phenomenon occurs when the color-change rule acts to modify the color of a vertex which has been already used during the computation. In some cases, back forcing implies that the information about the output of a Boolean circuit can be read not just by looking at the color of a
target vertex corresponding to the final output of the process, but at the color of the vertices in certain intermediate or initial gadgets. The idea opens a simple but intriguing scenario consisting of many parties that perform computation in a distributed way: each party holds a subset of the gates and is able to read certain information about the input of other parties, since the color of its gates may have been modified by back forcing. Back forcing can be avoided by including some extra gadget acting as a filter. While we will not explore this idea in detail, we do believe that it is interesting and that it deserves further attention.
In Sect.
4, we show that zero forcing becomes
universal, i.e., it can realize any Boolean function, if we apply a proper encoding. Specifically the
dual rail encoding, where two vertices are assigned to each logical bit, is a method to construct the NOT gate and therefore to obtain universal computation. In this way, we can implement reversible computation. It is interesting to remark that while the dynamics of zero forcing is irreversible, the “higher level” process can also be used in a reversible manner. Conclusions are in Sect.
5.