--- _id: '8168' abstract: - lang: eng text: "Tensor 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.\r\n" article_type: original author: - first_name: Sevag full_name: Gharibian, Sevag id: '71541' last_name: Gharibian orcid: 0000-0002-9992-3379 - first_name: Zeph full_name: Landau, Zeph last_name: Landau - first_name: Seung full_name: Woo Shin, Seung last_name: Woo Shin - first_name: Guoming full_name: Wang, Guoming last_name: Wang citation: ama: Gharibian S, Landau Z, Woo Shin S, Wang G. Tensor network non-zero testing. Quantum Information & Computation. 2015;15(9{\ & }10):885-899. apa: Gharibian, S., Landau, Z., Woo Shin, S., & Wang, G. (2015). Tensor network non-zero testing. Quantum Information & Computation, 15(9{\ & }10), 885–899. bibtex: '@article{Gharibian_Landau_Woo Shin_Wang_2015, title={Tensor network non-zero testing}, volume={15}, number={9{\ & }10}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Landau, Zeph and Woo Shin, Seung and Wang, Guoming}, year={2015}, pages={885–899} }' chicago: 'Gharibian, Sevag, Zeph Landau, Seung Woo Shin, and Guoming Wang. “Tensor Network Non-Zero Testing.” Quantum Information & Computation 15, no. 9{\ & }10 (2015): 885–99.' ieee: S. Gharibian, Z. Landau, S. Woo Shin, and G. Wang, “Tensor network non-zero testing,” Quantum Information & Computation, vol. 15, no. 9{\ & }10, pp. 885–899, 2015. mla: Gharibian, Sevag, et al. “Tensor Network Non-Zero Testing.” Quantum Information & Computation, vol. 15, no. 9{\ & }10, 2015, pp. 885–99. short: S. Gharibian, Z. Landau, S. Woo Shin, G. Wang, Quantum Information & Computation 15 (2015) 885–899. date_created: 2019-03-01T11:53:08Z date_updated: 2023-02-28T11:02:35Z department: - _id: '623' - _id: '7' extern: '1' external_id: arxiv: - '1406.5279' intvolume: ' 15' issue: 9{\&}10 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1406.5279 oa: '1' page: 885-899 publication: Quantum Information & Computation publication_status: published status: public title: Tensor network non-zero testing type: journal_article user_id: '71541' volume: 15 year: '2015' ...