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.

Mar 1, 20128 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.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.

Quantum Information and ComputationMar 1, 201210 citations

Contracting projected entangled pair states is average-case hard

Jonas Haferkamp, Dominik Hangleiter, Jens Eisert +1 more

An accurate calculation of the properties of quantum many-body systems is one of the most important yet intricate challenges of modern physics and computer science. In recent years, the tensor network ansatz has established itself as one of the most promising approaches enabling striking efficiency of simulating static properties of one-dimensional systems and abounding numerical applications in condensed matter theory. In higher dimensions, however, a connection to the field of computational complexity theory has shown that the accurate normalization of the two-dimensional tensor networks called projected entangled pair states (PEPS) is #P-complete. Therefore an efficient algorithm for PEPS contraction would allow solving exceedingly difficult combinatorial counting problems, which is considered highly unlikely. Due to the importance of understanding two- and three-dimensional systems the question currently remains: Are the known constructions typical of states relevant for quantum many-body systems? In this work, we show that an accurate evaluation of normalization or expectation values of PEPS is as hard to compute for typical instances as for special configurations of highest computational hardness. We discuss the structural property of average-case hardness in relation to the current research on efficient algorithms attempting tensor network contraction, hinting at a wealth of possible further insights into the average-case hardness of important problems in quantum many-body theory.An accurate calculation of the properties of quantum many-body systems is one of the most important yet intricate challenges of modern physics and computer science. In recent years, the tensor network ansatz has established itself as one of the most promising approaches enabling striking efficiency of simulating static properties of one-dimensional systems and abounding numerical applications in condensed matter theory. In higher dimensions, however, a connection to the field of computational complexity theory has shown that the accurate normalization of the two-dimensional tensor networks called projected entangled pair states (PEPS) is #P-complete. Therefore an efficient algorithm for PEPS contraction would allow solving exceedingly difficult combinatorial counting problems, which is considered highly unlikely. Due to the importance of understanding two- and three-dimensional systems the question currently remains: Are the known constructions typical of states relevant for quantum many-body systems? In this work, we show that an accurate evaluation of normalization or expectation values of PEPS is as hard to compute for typical instances as for special configurations of highest computational hardness. We discuss the structural property of average-case hardness in relation to the current research on efficient algorithms attempting tensor network contraction, hinting at a wealth of possible further insights into the average-case hardness of important problems in quantum many-body theory.

Jan 1, 202044 citations

Toward bootstrapping tensor-network contractions

Seishiro Ono, Yanbai Zhang, Hoi Chun Po

Accurate contraction of tensor networks beyond one dimension is essential in various fields including quantum many-body physics. Existing approaches typically rely on approximate contraction schemes and do not provide certified error bars. We introduce a numerical bootstrap framework which casts the problem of tensor-network contractions into a convex optimization problem, thereby yielding certified lower and upper bounds on expectation values of physical observables. As a proof-of-principle, we construct such constraints explicitly for translationally invariant matrix product states and demonstrate that, assuming a canonical form, second-order-cone relaxation can provide tight bounds on the contraction result. We further demonstrate that when the requirement on canonical form is lifted, a more general semidefinite-programming approach could yield similar tight bounds at higher but still polynomial computational cost. Our work suggests numerical bootstrap could be a possible way forward for the rigorous contractions of tensor networks.Accurate contraction of tensor networks beyond one dimension is essential in various fields including quantum many-body physics. Existing approaches typically rely on approximate contraction schemes and do not provide certified error bars. We introduce a numerical bootstrap framework which casts the problem of tensor-network contractions into a convex optimization problem, thereby yielding certified lower and upper bounds on expectation values of physical observables. As a proof-of-principle, we construct such constraints explicitly for translationally invariant matrix product states and demonstrate that, assuming a canonical form, second-order-cone relaxation can provide tight bounds on the contraction result. We further demonstrate that when the requirement on canonical form is lifted, a more general semidefinite-programming approach could yield similar tight bounds at higher but still polynomial computational cost. Our work suggests numerical bootstrap could be a possible way forward for the rigorous contractions of tensor networks.

cond-mat.str-elCross-listedarXiv:2603.17856Mar 19, 20260 citations

Tensor Networks in a Nutshell

Jacob Biamonte, Ville Bergholm

Tensor network methods are taking a central role in modern quantum physics and beyond. They can provide an efficient approximation to certain classes of quantum states, and the associated graphical language makes it easy to describe and pictorially reason about quantum circuits, channels, protocols, open systems and more. Our goal is to explain tensor networks and some associated methods as quickly and as painlessly as possible. Beginning with the key definitions, the graphical tensor network language is presented through examples. We then provide an introduction to matrix product states. We conclude the tutorial with tensor contractions evaluating combinatorial counting problems. The first one counts the number of solutions for Boolean formulae, whereas the second is Penrose's tensor contraction algorithm, returning the number of $3$ -edge-colorings of $3$ -regular planar graphs.Tensor network methods are taking a central role in modern quantum physics and beyond. They can provide an efficient approximation to certain classes of quantum states, and the associated graphical language makes it easy to describe and pictorially reason about quantum circuits, channels, protocols, open systems and more. Our goal is to explain tensor networks and some associated methods as quickly and as painlessly as possible. Beginning with the key definitions, the graphical tensor network language is presented through examples. We then provide an introduction to matrix product states. We conclude the tutorial with tensor contractions evaluating combinatorial counting problems. The first one counts the number of solutions for Boolean formulae, whereas the second is Penrose's tensor contraction algorithm, returning the number of $3$-edge-colorings of $3$-regular planar graphs.

arXiv:1708.00006Jul 31, 2017113 citations

Positive Bias Makes Tensor-Network Contraction Tractable

Jiaqing Jiang, Jielun Chen, Norbert Schuch +1 more

Tensor network contraction is a powerful computational tool in quantum many-body physics, quantum information and quantum chemistry. The complexity of contracting a tensor network is thought to mainly depend on its entanglement properties, as reflected by the Schmidt rank across bipartite cuts. Here, we study how the complexity of tensor-network contraction depends on a different notion of quantumness, namely, the sign structure of its entries. We tackle this question rigorously by investigating the complexity of contracting tensor networks whose entries have a positive bias. We show that for intermediate bond dimension d>~n, a small positive mean value >~1/d of the tensor entries already dramatically decreases the computational complexity of approximately contracting random tensor networks, enabling a quasi-polynomial time algorithm for arbitrary 1/poly(n) multiplicative approximation. At the same time exactly contracting such tensor networks remains #P-hard, like for the zero-mean case [HHEG20]. The mean value 1/d matches the phase transition point observed in [CJHS24]. Our proof makes use of Barvinok's method for approximate counting and the technique of mapping random instances to statistical mechanical models. We further consider the worst-case complexity of approximate contraction of positive tensor networks, where all entries are non-negative. We first give a simple proof showing that a multiplicative approximation with error exponentially close to one is at least StoqMA-hard. We then show that when considering additive error in the matrix 1-norm, the contraction of positive tensor network is BPP-Complete. This result compares to Arad and Landau's [AL10] result, which shows that for general tensor networks, approximate contraction up to matrix 2-norm additive error is BQP-Complete.Tensor network contraction is a powerful computational tool in quantum many-body physics, quantum information and quantum chemistry. The complexity of contracting a tensor network is thought to mainly depend on its entanglement properties, as reflected by the Schmidt rank across bipartite cuts. Here, we study how the complexity of tensor-network contraction depends on a different notion of quantumness, namely, the sign structure of its entries. We tackle this question rigorously by investigating the complexity of contracting tensor networks whose entries have a positive bias. We show that for intermediate bond dimension d>~n, a small positive mean value >~1/d of the tensor entries already dramatically decreases the computational complexity of approximately contracting random tensor networks, enabling a quasi-polynomial time algorithm for arbitrary 1/poly(n) multiplicative approximation. At the same time exactly contracting such tensor networks remains #P-hard, like for the zero-mean case [HHEG20]. The mean value 1/d matches the phase transition point observed in [CJHS24]. Our proof makes use of Barvinok's method for approximate counting and the technique of mapping random instances to statistical mechanical models. We further consider the worst-case complexity of approximate contraction of positive tensor networks, where all entries are non-negative. We first give a simple proof showing that a multiplicative approximation with error exponentially close to one is at least StoqMA-hard. We then show that when considering additive error in the matrix 1-norm, the contraction of positive tensor network is BPP-Complete. This result compares to Arad and Landau's [AL10] result, which shows that for general tensor networks, approximate contraction up to matrix 2-norm additive error is BQP-Complete.

arXiv:2410.05414ACM Symposium on Theory of Computing (STOC)Jun 15, 20252 citations

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.

3

-edge-colorings of

3

-regular planar graphs.