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. Tijk 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
δij=⎡⎢⎣100010001⎤⎥⎦
and is a tensor with two indices, each of bond dimension 3. Meanwhile the Levi-Civita symbol
εijk=⎧⎨⎩1 if (i,j,k) is an even permutation−1 if (i,j,k) is an odd permutation0 if i==j or j==k or i==k
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
Qikl=∑jAijkBjl
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
Ai=∑jBijj
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 ∑ 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, ijk, 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 i1...in 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 vF=(1,0) or vT=(0,1). These vectors can be contracted with tensors representing the various boolean gates. For instance
TORijk={1 if (i=1 or j=1) and k=10 otherwise
This has the property that
vFivTjTORijk=vTk
That is, TOR implements an OR gate. An AND gate can be similarly constructed:
TANDijk={1 if (i=1 and j=1) and k=10 otherwise
Note that an AND tensor can also be used to copy a wire, because
vF/TiTANDijk=vF/TjvF/Tk
Finally, NOT gates are just given by
TNOTij=[0110]
so that
vF/TiTNOTij=vT/Fi
In this way, we can construct a tensor network which, when contracted against the vectors representing its inputs, results in a vector representing its output.
#SAT
#SAT is the problem of counting the number of instances of a boolean circuit which output True. We can represent this problem in a tensor network as follows:
(1) Map the boolean circuit to a tensor network with input indices i1...in and output index o. The result might look like
If we contract some combination of vF/T against the input indices i1...i4 then the resulting tensor network will equal either vT (if the boolean circuit would have produced True with that input) or vF (otherwise).
(2) Contract an instance of vT against o. Because vF is orthogonal to vT, and both have unit norm, the resulting tensor network now produces the scalar 1 if the inputs are set to a combination of vF/T so that o=vT and the scalar 0 otherwise.
(3) Make a copy of this tensor network, with input indices i′1...i′n.
(4) Construct a new tensor network which specifies the contraction of the network and its copy, linking each ij with the corresponding i′j. This might look as follows:
This network has no free indices and so produces a scalar when contracted. The contraction can be written as a sum over all possible values of the indices i1...in, so that scalar equals the number of input instances satisfying the boolean circuit.
(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. Tijk 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
δij=⎡⎢⎣100010001⎤⎥⎦and is a tensor with two indices, each of bond dimension 3. Meanwhile the Levi-Civita symbol
εijk=⎧⎨⎩1 if (i,j,k) is an even permutation−1 if (i,j,k) is an odd permutation0 if i==j or j==k or i==kis 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
Qikl=∑jAijkBjlsays 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
Ai=∑jBijjsays 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 ∑ 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![](https://39669.cdn.cke-cs.com/rQvD3VnunXZu34m86e5f/images/c754aedda8214fcc6d89c42c22e7f7c536fa21bf1c9d9ede.png)
Here A has three indices, ijk, 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 i1...in 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 vF=(1,0) or vT=(0,1). These vectors can be contracted with tensors representing the various boolean gates. For instance
TORijk={1 if (i=1 or j=1) and k=10 otherwiseThis has the property that
vFivTjTORijk=vTkThat is, TOR implements an OR gate. An AND gate can be similarly constructed:
TANDijk={1 if (i=1 and j=1) and k=10 otherwiseNote that an AND tensor can also be used to copy a wire, because
vF/TiTANDijk=vF/TjvF/TkFinally, NOT gates are just given by
TNOTij=[0110]so that
vF/TiTNOTij=vT/FiIn this way, we can construct a tensor network which, when contracted against the vectors representing its inputs, results in a vector representing its output.
#SAT
#SAT is the problem of counting the number of instances of a boolean circuit which output True. We can represent this problem in a tensor network as follows:
(1) Map the boolean circuit to a tensor network with input indices i1...in and output index o. The result might look like
If we contract some combination of vF/T against the input indices i1...i4 then the resulting tensor network will equal either vT (if the boolean circuit would have produced True with that input) or vF (otherwise).
(2) Contract an instance of vT against o. Because vF is orthogonal to vT, and both have unit norm, the resulting tensor network now produces the scalar 1 if the inputs are set to a combination of vF/T so that o=vT and the scalar 0 otherwise.
(3) Make a copy of this tensor network, with input indices i′1...i′n.
(4) Construct a new tensor network which specifies the contraction of the network and its copy, linking each ij with the corresponding i′j. This might look as follows:
This network has no free indices and so produces a scalar when contracted. The contraction can be written as a sum over all possible values of the indices i1...in, so that scalar equals the number of input instances satisfying the boolean circuit.