QUANTUM COMPUTATION AND THE EVALUATION OF TENSOR NETWORKS

We present a quantum algorithm that additively approximates the value of a tensor network to a certain scale. When combined with existing results, this provides a complete problem for quantum computation. The result is a simple new way of looking at quantum computation in which unitary gates are replaced by tensors and time is replaced by the order in which the tensor network is "swallowed." We use this result to derive new quantum algorithms that approximate the partition function of a variety of classical statistical mechanical models, including the Potts model.