# Tensor network method for reversible classical computation. (arXiv:1708.08932v2 [cond-mat.stat-mech] UPDATED)

We develop a tensor network technique that can solve universal reversible

classical computational problems, formulated as vertex models on a square

lattice [Nat. Commun. 8, 15303 (2017)]. By encoding the truth table of each

vertex constraint in a tensor, the total number of solutions compatible with

partial inputs/outputs at the boundary can be represented as the full

contraction of a tensor network. We introduce an iterative

compression-decimation (ICD) scheme that performs this contraction efficiently.

The ICD algorithm first propagates local constraints to longer ranges via

repeated contraction-decomposition sweeps over all lattice bonds, thus

achieving compression on a given length scale. It then decimates the lattice

via coarse-graining tensor contractions. Repeated iterations of these two steps

gradually collapse the tensor network and ultimately yield the exact tensor

trace for large systems, without the need for manual control of tensor

dimensions. Our protocol allows us to obtain the exact number of solutions for

computations where a naive enumeration would take astronomically long times.