(Thanks to Mark Xu for comments on these notes.)

These are some notes on tensor networks, the mapping from boolean circuits to tensor networks, and how #SAT can be written as a tensor network contraction.

Definitions and Notation

What is a tensor?

A rank- $d$ tensor is an array of numbers with $d$ integer indices, e.g. $T_{i j k}$ is a rank-3 tensor. The range of each index is called its bond dimension. So for instance the Kronecker delta tensor used in physics is given by

δ_{i j} = ⎡ ⎢ ⎣ \begin{matrix} 100010001 \end{matrix} ⎤ ⎥ ⎦

and is a tensor with two indices, each of bond dimension 3. Meanwhile the Levi-Civita symbol

ε_{i j k} = ⎧ ⎨ ⎩ \begin{matrix} 1 if (i,j,k) is an even permutation - 1 if (i,j,k) is an odd permutation 0 if i==j or j==k or i==k \end{matrix}

is a tensor with three indices each of dimension 3.

What is a tensor contraction?

A contraction is a specification of dot products to perform between tensors. For instance

Q_{i k l} = \sum j A_{i j k} B_{j l}

says to form the tensor $Q$ by contracting $A$ with $B$ along the second index of $A$ and the first index of $B$ .

A tensor can also be contracted with itself, forming a trace. For instance

A_{i} = \sum j B_{i j j}

says that we trace over the second and third indices of $B$ to form $A$ .

Often times the summation is written just with indices and no $\sum$ symbol using Einstein summation notation. In this notation, indices are summed over if they appear in an expression exactly twice. This notation is unambiguous because contraction is only defined over pairs of indices.

What is a tensor network?

A tensor network is a specification of which contractions are desired between one or more tensors. They are often drawn diagrammatically in penrose notation as

Here $A$ has three indices, $i j k$ , two of which are free (meaning they are not involved in any contraction) and one of which is linked to an index of $B$ , which itself has a further free index $l$ .

Representing Boolean Circuits

A boolean circuit with inputs $i_{1} . . . i_{n}$ can be written as a tensor network as follows. For further references see here.

First, each input is mapped from False/True to a vector which is either $v^{F} = (1, 0)$ or $v^{T} = (0, 1)$ . These vectors can be contracted with tensors representing the various boolean gates. For instance

T_{i j k}^{O R} = {\begin{matrix} 1 if (i=1 or j=1) and k=1 0 otherwise \end{matrix}

This has the property that

v_{i}^{F} v_{j}^{T} T_{i j k}^{O R} = v_{k}^{T}

That is, $T^{O R}$ implements an OR ...

Tensor Networks