Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1406.5279

Tensor network non-zero testing

Sevag Gharibian, Zeph A. Landau, Seung Woo Shin, Guo‐Ming Wang

Published Jun 20, 2014• 12 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.1406.5279

Related papers

Tensor network non-zero testing

Tensor networks are an important tool in condensed matter physics. In this paper, we study the task of tensor network non-zero testing (\tnit): Given a tensor network $T$, does $T$ represent a non-zero vector? We show that \tnit~is not in the Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among other results) that the special cases of \tnit~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 $k\in O(\log n)$ and $D\in O(1)$. 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.

Quantum Information and Computation•Jul 1, 2015•7 citations

Matrix-Product Operators and States: NP-Hardness and Undecidability

Martin Kliesch, D. Gross, Jens Eisert

Tensor network states constitute an important variational set of quantum states for numerical studies of strongly correlated systems in condensed-matter physics, as well as in mathematical physics. This is specifically true for finitely correlated states or matrix-product operators, designed to capture mixed states of one-dimensional quantum systems. It is a well-known open problem to find an efficient algorithm that decides whether a given matrix-product operator actually represents a physical state that in particular has no negative eigenvalues. We address and answer this question by showing that the problem is provably undecidable in the thermodynamic limit and that the bounded version of the problem is NP-hard (nondeterministic-polynomial-time hard) in the system size. Furthermore, we discuss numerous connections between tensor network methods and (seemingly) different concepts treated before in the literature, such as hidden Markov models and tensor trains.

arXiv:1404.4466•Physical Review Letters•Oct 16, 2014•80 citations

Exact tensor network ansatz for strongly interacting systems

Michael P. Zaletel

It appears that the tensor network ansatz, while not quite complete, is an efficient coordinate system for the tiny subset of a many-body Hilbert space which can be realized as a low energy state of a local Hamiltonian.However, we don't fully understand precisely which phases are captured by the tensor network ansatz, how to compute their physical observables (even numerically), or how to compute a tensor network representation for a ground state given a microscopic Hamiltonian. These questions are algorithmic in nature, but their resolution is intimately related to understanding the nature of quantum entanglement in many-body systems.For this reason it is useful to compute the tensor network representation of various `model' wavefunctions representative of different phases of matter; this allows us to understand how the entanglement properties of each phase are expressed in the tensor network ansatz, and can serve as test cases for algorithm development.Condensed matter physics has many illuminating model wavefunctions, such as Laughlin's celebrated wave function for the fractional quantum Hall effect, the Bardeen-Cooper-Schrieffer wave function for superconductivity, and Anderson's resonating valence bond ansatz for spin liquids.This thesis presents some results on exact tensor network representations of these model wavefunctions. In addition, a tensor network representation is given for the time evolution operator of a long-range one-dimensional Hamiltonian, which allows one to numerically simulate the time evolution of power-law interacting spin chains as well as two-dimensional strips and cylinders.

•Jan 1, 2014•0 citations

An exact tensor network for the 3SAT problem

Artur García-Sáez, José Ignacio Latorre

We construct a tensor network that delivers an unnormalized quantum state whose coefficients are the solutions to a given instance of 3SAT, an NP-complete problem. The tensor network contraction that corresponds to the norm of the state counts the number of solutions to the instance. It follows that exact contractions of this tensor network are in the #P-complete computational complexity class, thus believed to be a hard task. Furthermore, we show that for a 3SAT instance with n bits, it is enough to perform a polynomial number of contractions of the tensor network structure associated to the computation of local observables to obtain one of the explicit solutions to the problem, if any. Physical realization of a state described by a generic tensor network is equivalent to finding the satisfying assignment of a 3SAT instance and, consequently, this experimental task is expected to be hard.

•Mar 1, 2012•8 citations

An exact tensor network for the 3SAT problem

A. Garcia-Saez, J. I. Latorre

We construct a tensor network that delivers an unnormalized quantum state whose coefficients are the solutions to a given instance of 3SAT, an NP-complete problem. The tensor network contraction that corresponds to the norm of the state counts the number of solutions to the instance. It follows that exact contractions of this tensor network are in the #P-complete computational complexity class, thus believed to be a hard task. Furthermore, we show that for a 3SAT instance with n bits, it is enough to perform a polynomial number of contractions of the tensor network structure associated to the computation of local observables to obtain one of the explicit solutions to the problem, if any. Physical realization of a state described by a generic tensor network is equivalent to finding the satisfying assignment of a 3SAT instance and, consequently, this experimental task is expected to be hard.

arXiv:1105.3201•May 16, 2011•5 citations

Some Effective Results on the Invariant Theory of Tensor Networks

Jacob Turner, Jason Morton

In several applications including computational complexity and condensed matter physics, regular tensor networks arise in which vertex tensors and edge vector spaces are repeated. These have many internal edges, each with a label $i\in\{1,\dots,n\}$ and corresponding to an $t_i$-dimensional complex vector space. We have a local adjoint action on the vertex tensors by $G_{\textbf{t}}= \times_{i=1}^n{GL(t_i,\mathbb{C})}$ which amounts to a change of basis on each internal edge. Such networks are overparameterized in the sense that this action does not change the tensor represented by the entire network, although it may change the tensor associated to a given vertex. When $G_{\textbf{t}}$ acts nontrivially only on wires which are internal (perhaps after connecting copies of a network with dangling wires), the value of the network is of course a $G_{\textbf{t}}$ invariant. We explain how to use some tools from invariant theory to work modulo such an internal local $GL$ symmetry and apply them to a problem in complexity theory.

arXiv:1310.0370•Oct 1, 2013•1 citation
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.
Tensor networks are an important tool in condensed matter physics. In this paper, we study the task of tensor network non-zero testing (\tnit): Given a tensor network TTT, does TTT represent a non-zero vector? We show that \tnit~is not in the Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among other results) that the special cases of \tnit~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 kkk-SAT problem on DDD-dimensional qudits is in NP for k∈O(log⁡n)k\in O(\log n)k∈O(logn) and D∈O(1)D\in O(1)D∈O(1). This reveals the first class of quantum Hamiltonians whose commuting variant is known to be in NP for all (1) logarithmic kkk, (2) constant DDD, and (3) for arbitrary interaction graphs.
Tensor network states constitute an important variational set of quantum states for numerical studies of strongly correlated systems in condensed-matter physics, as well as in mathematical physics. This is specifically true for finitely correlated states or matrix-product operators, designed to capture mixed states of one-dimensional quantum systems. It is a well-known open problem to find an efficient algorithm that decides whether a given matrix-product operator actually represents a physical state that in particular has no negative eigenvalues. We address and answer this question by showing that the problem is provably undecidable in the thermodynamic limit and that the bounded version of the problem is NP-hard (nondeterministic-polynomial-time hard) in the system size. Furthermore, we discuss numerous connections between tensor network methods and (seemingly) different concepts treated before in the literature, such as hidden Markov models and tensor trains.
It appears that the tensor network ansatz, while not quite complete, is an efficient coordinate system for the tiny subset of a many-body Hilbert space which can be realized as a low energy state of a local Hamiltonian.However, we don't fully understand precisely which phases are captured by the tensor network ansatz, how to compute their physical observables (even numerically), or how to compute a tensor network representation for a ground state given a microscopic Hamiltonian. These questions are algorithmic in nature, but their resolution is intimately related to understanding the nature of quantum entanglement in many-body systems.For this reason it is useful to compute the tensor network representation of various `model' wavefunctions representative of different phases of matter; this allows us to understand how the entanglement properties of each phase are expressed in the tensor network ansatz, and can serve as test cases for algorithm development.Condensed matter physics has many illuminating model wavefunctions, such as Laughlin's celebrated wave function for the fractional quantum Hall effect, the Bardeen-Cooper-Schrieffer wave function for superconductivity, and Anderson's resonating valence bond ansatz for spin liquids.This thesis presents some results on exact tensor network representations of these model wavefunctions. In addition, a tensor network representation is given for the time evolution operator of a long-range one-dimensional Hamiltonian, which allows one to numerically simulate the time evolution of power-law interacting spin chains as well as two-dimensional strips and cylinders.
We construct a tensor network that delivers an unnormalized quantum state whose coefficients are the solutions to a given instance of 3SAT, an NP-complete problem. The tensor network contraction that corresponds to the norm of the state counts the number of solutions to the instance. It follows that exact contractions of this tensor network are in the #P-complete computational complexity class, thus believed to be a hard task. Furthermore, we show that for a 3SAT instance with n bits, it is enough to perform a polynomial number of contractions of the tensor network structure associated to the computation of local observables to obtain one of the explicit solutions to the problem, if any. Physical realization of a state described by a generic tensor network is equivalent to finding the satisfying assignment of a 3SAT instance and, consequently, this experimental task is expected to be hard.
We construct a tensor network that delivers an unnormalized quantum state whose coefficients are the solutions to a given instance of 3SAT, an NP-complete problem. The tensor network contraction that corresponds to the norm of the state counts the number of solutions to the instance. It follows that exact contractions of this tensor network are in the #P-complete computational complexity class, thus believed to be a hard task. Furthermore, we show that for a 3SAT instance with n bits, it is enough to perform a polynomial number of contractions of the tensor network structure associated to the computation of local observables to obtain one of the explicit solutions to the problem, if any. Physical realization of a state described by a generic tensor network is equivalent to finding the satisfying assignment of a 3SAT instance and, consequently, this experimental task is expected to be hard.
In several applications including computational complexity and condensed matter physics, regular tensor networks arise in which vertex tensors and edge vector spaces are repeated. These have many internal edges, each with a label i∈{1,…,n}i\in\{1,\dots,n\}i∈{1,…,n} and corresponding to an tit_iti​-dimensional complex vector space. We have a local adjoint action on the vertex tensors by Gt=×i=1nGL(ti,C)G_{\textbf{t}}= \times_{i=1}^n{GL(t_i,\mathbb{C})}Gt​=×i=1n​GL(ti​,C) which amounts to a change of basis on each internal edge. Such networks are overparameterized in the sense that this action does not change the tensor represented by the entire network, although it may change the tensor associated to a given vertex. When GtG_{\textbf{t}}Gt​ acts nontrivially only on wires which are internal (perhaps after connecting copies of a network with dangling wires), the value of the network is of course a GtG_{\textbf{t}}Gt​ invariant. We explain how to use some tools from invariant theory to work modulo such an internal local GLGLGL symmetry and apply them to a problem in complexity theory.