Tensor network non-zero testing
arXiv:1406.5279
Abstract
Tensor networks are a central tool in condensed matter physics. In this paper, we study the task of tensor network non-zero testing (TNZ): Given a tensor network T, does T represent a non-zero vector? We show that TNZ is not in the Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among other results) that the special cases of TNZ on non-negative and injective tensor networks are in NP. Using this, we make a simple observation: The commuting variant of the MA-complete stoquastic k-SAT problem on D-dimensional qudits is in NP for logarithmic k and constant D. This reveals the first class of quantum Hamiltonians whose commuting variant is known to be in NP for all (1) logarithmic k, (2) constant D, and (3) for arbitrary interaction graphs.
15 pages, 4 figures. v2: Published version (QIC)
References in corpus (9)
- Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
- A class of quantum many-body states that can be efficiently simulated
- DMRG and periodic boundary conditions: a quantum information perspective
- Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
- Matrix product operators and states: NP-hardness and undecidability
- Tensor Network Contractions for #SAT
- Merlin-Arthur Games and Stoquastic Complexity
- Solving search problems by strongly simulating quantum circuits
- Undecidability in Tensor Network States