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.