01206nas a2200169 4500008004100000245003600041210003500077260001500112300001200127490000700139520077800146100002100924700001700945700002100962700001800983856003501001 2015 eng d00aTensor network non-zero testing0 aTensor network nonzero testing c2015/07/01 a885-8990 v153 aTensor networks are a central tool in condensed matter physics. In this paper, we initiate the study 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.1 aGharibian, Sevag1 aLandau, Zeph1 aShin, Seung, Woo1 aWang, Guoming uhttp://arxiv.org/abs/1406.5279