Logic Decomposition of Networks

In the ink notes I have explained the basics of the idea. However, I didn’t derive an relation between the network connection coefficients and the logic unit coefficients.

We’ll only consider spin 1/2 nodes, hence Ising model but the spins could be fully connect.

Review of Ink Notes

Basically, the equation we need to solve is

$$ \begin{align} &\sum_{ij} J_{ij}s_is_j + \sum_i K_i s_i\\ =& \sum_{ij}A_{ij}(1+s_i s_j) \\ &+ \sum_{ijk} B_{ijk} \left( 3 + (-s_i -s_j + 2s_k) + s_i s_j - 2 s_i s_k -2 s_j s_k \right)\\ &+\sum_{ijk} C_{ijk} \left( 3 - (-s_i -s_j + 2s_k) + s_i s_j - 2 s_i s_k -2 s_j s_k \right) \end{align} $$

In this expression, $A_{ij}$ is the coefficient for NOT logic calculation, $B_{ijk}$ is the coefficient for AND logic calculation, and $C_{ijk}$ is the coefficient for OR logic calculation. The LHS is the original ‘Ising model’.

In fact this equation can be simplified to $$ \begin{align} &\sum_{ij} J_{ij}s_is_j \\ =& \sum_{ij}A_{ij}(1+s_i s_j) \\ &+ \sum_{ijk}\left[ (B_{ijk}+C_{ijk} ) ( 3 + s_i s_j - 2 s_i s_k -2 s_j s_k ) \right.\\ &\left.+ (B_{ijk}-C_{ijk}) (-s_i -s_j + 2s_k) \right] \end{align} $$

As we have proved in the ink notes, the coefficients have symmetry properties.

  1. The coefficient of and logic $B_{ijk}$ is invariant under exchange of $(i\leftrightarrow j)$, $(i\leftrightarrow k)$, $(j\leftrightarrow k)$;
  2. The coefficient of or logic $C_{ijk}$ is invariant under exchange of $(i\leftrightarrow j)$.

Relations Between Ising Model and Logic Calculation View

We’ll derive the relations between the coefficients of spin coupling $J_{ij}$, $K_i$ and the coefficients of logic units, $A_{ij}$, $B_{ijk}$, $C_{ijk}$.

Here we apply a trick of summations,

$$ \begin{align} &\sum_{ij}J_{ij}s_i s_j\\ =&\frac{1}{3}\left( \sum_{ij} J_{ij} s_i s_j + \sum_{ik} J_{ik} s_i s_k + \sum_{jk} J_{jk} s_js_k \right) \\ =& \frac{1}{3N} \sum_{ijk}\left( J_{ij} s_i s_j + J_{ik} s_i s_k + J_{jk} s_js_k \right) \end{align}, $$

where $N$ is the total number of spins. We also have

$$ \sum_i K_i s_i = \sum_{ijk} \frac{1}{3N^2} \left( K_i s_i + K_j s_j + K_k s_k \right). $$

Similar trick can be applied to the RHS, which leads to an equation

$$ \begin{align} &\sum_{ijk} \frac{1}{3N}\left( J_{ij} s_i s_j + J_{ik} s_i s_k + J_{jk} s_js_k \right) + \sum_{ijk} \frac{1}{3N^2} \left( K_i s_i + K_j s_j + K_k s_k \right) \\ =& \frac{1}{3N}\sum_{ijk} \left( A_{ij} (1 + s_i s_j) + A_{ik} (1+s_i s_k) + A_{jk} (1+s_js_k) \right) \\ &+ \sum_{ijk}\left[ (B_{ijk}+C_{ijk} ) ( 3 + s_i s_j - 2 s_i s_k -2 s_j s_k ) \right.\\ &\left.+ (B_{ijk}-C_{ijk}) (-s_i -s_j + 2s_k) \right] \end{align}. $$

Then we compare the coefficients with the same product of spins.

First of all, the constant term on the RHS should be 0,

$$ \begin{equation} \frac{1}{3N} (A_{ij} + A_{ik} + A_{jk}) + 3(B_{ijk}+C_{ijk}) = 0 \end{equation}. $$

The linear terms give us

$$ \begin{align} \frac{1}{3N^2} K_i=& C_{ijk}- B_{ijk}\\ \frac{1}{3N^2} K_j=& C_{ijk}- B_{ijk}\\ \frac{1}{3N^2} K_k=& 2 ( B_{ijk} - C_{ijk}) \end{align}. $$

The quadratic terms give us

$$ \begin{align} \frac{1}{3N} J_{ij} =& \frac{1}{3N} A_{ij} + B_{ijk} + C_{ijk} \\ \frac{1}{3N} J_{ik} =& \frac{1}{3N} A_{ik} -2(B_{ijk} + C_{ijk}) \\ \frac{1}{3N} J_{jk} =& \frac{1}{3N} A_{jk} -2(B_{ijk} + C_{ijk}) \\ \end{align}. $$

We have to also include the symmetry conditions

$$ \begin{align} B_{ijk}=&B_{jik}\\ B_{ijk}=&B_{kji}\\ B_{ijk}=&B_{ikj}\\ C_{ijk}=&C_{jik} \end{align}. $$

We have 11 sets of equations to solve the coefficients of logic units. However, some of the equations are obviously redundant. For example, equation

$$ \frac{1}{3N} J_{jk} = \frac{1}{3N} A_{jk} -2(B_{ijk} + C_{ijk}) $$

can be derived using

$$ \begin{align} \frac{1}{3N} J_{ik} =& \frac{1}{3N} A_{ik} -2(B_{ijk} + C_{ijk})\\ B_{ijk}=&B_{jik} \\ C_{ijk}=&C_{jik} \end{align}. $$

Solutions to The Equations

To solve the equations, I need to combine several of them to cancel some unknown coefficients.

I can combine

$$ \frac{1}{3N}(J_{ij}+J_{ik}+J_{jk})=\frac{1}{3N}( A_{ij}+A_{ik}+A_{jk} ) $$


$$ \frac{1}{3N}(A_{ij}+A_{ik}+A_{jk})+3(B_{ijk}+C_{ijk})=0 $$

to get the equation $$ -6(B_{ijk}+C_{ijk})=\frac{1}{3N}(J_{ij}+J_{jk}+J_{ik}), $$ which is combined with equation $$ \begin{equation} C_{ijk}-B_{ijk}=\frac{1}{3N^2}K_i \end{equation} $$ to get $$ C_{ijk}=-\frac{1}{36N}(J_{ij}+J_{ik}+J_{jk})+\frac{1}{6N^2}K_i. $$ Then we can find $B_{ijk}$ and $A_{ij}$ $$ \begin{align} B_{ijk}=&C_{ijk}-\frac{1}{3N^2}K_i\\ A_{ij}=&J_{ij}-2N(B_{ijk}+C_{ijk}). \end{align} $$

HOWEVER, I have no idea what the last equation means. What happened to the extra index $k$?


Here is a Mathematica Notebook.

Planted: by ;

Lei Ma (2020). 'Logic Decomposition of Networks', Intelligence, 10 April. Available at: https://intelligence.leima.is/toolbox/random-thoughts/logic-decomposition-of-networks/.