Quantum computation and the evaluation of tensor networks
arXiv:0805.0040
Abstract
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 mechanics models, including the Potts model.
35 pages, 11 figures, 3rd version includes: the section presenting statistical mechanical algorithms has been changed to clarify the relationship to other recent work. To appear in SICOMP
References in corpus (8)
- Exponential algorithmic speedup by quantum walk
- Completeness of the classical 2D Ising model and universal quantum computation
- Trading inverses for an irrep in the Solovay-Kitaev theorem
- Quantum algorithms for spin models and simulable gate sets for quantum computation
- On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
- Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem
- Renormalization algorithm with graph enhancement
- A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs