Tensor Networks for Reversible Classical Computation and Time Evolution of Quantum Many-Body Systems

Motivated by statistical physics models connected to computational problems, we introduce an iterative compression-decimation scheme for tensor network optimization that is suited to problems without translation invariance and with arbitrary boundary conditions. When applied to tensor networks that encode generalized vertex models on regular lattices, our algorithm is able to propagate global constraints imposed at the boundary via repeated contraction-decomposition sweeps over all lattice bonds, followed by coarse-graining tensor contractions. We apply our algorithm to a recently proposed vertex model encoding universal reversible classical computations. Our protocol allows us to obtain the exact number of solutions for computations where a naive enumeration would take astronomically long times. We also gain insights into the hardness of a computation from an entanglement perspective. Finally, I will discuss how our algorithm can be applied to simulating unitary time evolutions in quantum many-body systems.