We investigate how the computational difficulty of contracting tensor networks depends on the sign structure of the tensor entries. Using results from computational complexity, we observe that the approximate contraction of tensor networks with only positive entries has lower computational complexity as compared to tensor networks with general real or complex entries. This raises the question of how this transition in computational complexity manifests itself in the hardness of different tensor-network-contraction schemes. We pursue this question by studying random tensor networks with varying bias toward positive entries. First, we consider contraction via Monte Carlo sampling and find that the transition from hard to easy occurs when the tensor entries become predominantly positive; this can be understood as a tensor-network manifestation of the well-known negative-sign problem in quantum Monte Carlo. Second, we analyze the commonly used contraction based on boundary tensor networks. The performance of this scheme is governed by the number of correlations in contiguous parts of the tensor network (which by analogy can be thought of as entanglement). Remarkably, we find that the transition from hard to easy—i.e., from a volume-law to a boundary-law scaling of entanglement—already occurs for a slight bias of the tensor entries toward a positive mean, scaling inversely with the bond dimension D , and thus the problem becomes easy the earlier the larger D occurs. This is in contrast both to expectations and to the behavior found in Monte Carlo contraction, where the hardness at fixed bias increases with the bond dimension. To provide insight into this early breakdown of computational hardness and the accompanying entanglement transition, we construct an effective classical statistical-mechanical model that predicts a transition at a bias of the tensor entries of 1 / D , confirming our observations. We conclude by investigating the computational difficulty of computing expectation values of tensor-network wave functions (projected entangled-pair states, PEPSs) and find that in this setting, the complexity of entanglement-based contraction always remains low. We explain this by providing a local transformation that maps PEPS expectation values to a positive-valued tensor network. This not only provides insight into the origin of the observed boundary-law entanglement scaling but also suggests new approaches toward PEPS contraction based on positive decompositions.
We investigate how the computational difficulty of contracting tensor networks depends on the sign structure of the tensor entries. Using results from computational complexity, we observe that the approximate contraction of tensor networks with only positive entries has lower computational complexity as compared to tensor networks with general real or complex entries. This raises the question of how this transition in computational complexity manifests itself in the hardness of different tensor-network-contraction schemes. We pursue this question by studying random tensor networks with varying bias toward positive entries. First, we consider contraction via Monte Carlo sampling and find that the transition from hard to easy occurs when the tensor entries become predominantly positive; this can be understood as a tensor-network manifestation of the well-known negative-sign problem in quantum Monte Carlo. Second, we analyze the commonly used contraction based on boundary tensor networks. The performance of this scheme is governed by the number of correlations in contiguous parts of the tensor network (which by analogy can be thought of as entanglement). Remarkably, we find that the transition from hard to easy—i.e., from a volume-law to a boundary-law scaling of entanglement—already occurs for a slight bias of the tensor entries toward a positive mean, scaling inversely with the bond dimension D , and thus the problem becomes easy the earlier the larger D occurs. This is in contrast both to expectations and to the behavior found in Monte Carlo contraction, where the hardness at fixed bias increases with the bond dimension. To provide insight into this early breakdown of computational hardness and the accompanying entanglement transition, we construct an effective classical statistical-mechanical model that predicts a transition at a bias of the tensor entries of 1 / D , confirming our observations. We conclude by investigating the computational difficulty of computing expectation values of tensor-network wave functions (projected entangled-pair states, PEPSs) and find that in this setting, the complexity of entanglement-based contraction always remains low. We explain this by providing a local transformation that maps PEPS expectation values to a positive-valued tensor network. This not only provides insight into the origin of the observed boundary-law entanglement scaling but also suggests new approaches toward PEPS contraction based on positive decompositions.
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.
Projected entangled pair states (PEPS) constitute a variational family of quantum states with area-law entanglement. PEPS are particularly relevant and successful for studying ground states of spatially local Hamiltonians. However, computing local expectation values in these states is known to be \postBQP-hard. Injective PEPS, where all constituent tensors fulfil an injectivity constraint, are generally believed to be better behaved, because they are unique ground states of spatially local Hamiltonians. In this work, we therefore examine how the computational hardness of contraction depends on the injectivity. We establish that below a constant positive injectivity threshold, evaluating local observables remains \postBQP-complete, while above a different constant nontrivial threshold there exists an efficient classical algorithm for the task, resolving an open question from (Anshu et al., STOC `24). We do this by proving that noisy postselected quantum computation can be made fault-tolerant.
Projected entangled pair states (PEPS) offer memory-efficient representations of some quantum many-body states that obey an entanglement area law and are the basis for classical simulations of ground states in two-dimensional (2d) condensed matter systems. However, rigorous results show that exactly computing observables from a 2d PEPS state is generically a computationally hard problem. Yet approximation schemes for computing properties of 2d PEPS are regularly used, and empirically seen to succeed, for a large subclass of (``not too entangled'') condensed matter ground states. Adopting the philosophy of random matrix theory, in this work, we analyze the complexity of approximately contracting a 2d random PEPS by exploiting an analytic mapping to an effective replicated statistical mechanics model that permits a controlled analysis at a large bond dimension. Through this statistical-mechanics lens, we argue that (i) although approximately sampling wave-function amplitudes of random PEPS faces a computational-complexity phase transition above a critical bond dimension, and (ii) one can generically efficiently estimate the norm and correlation functions for any finite bond dimension. These results are supported numerically for various bond-dimension regimes. It is an important open question whether the above results for random PEPS apply more generally also to PEPS representing physically relevant ground states.
We have a strong interest in the interplay between geometrical frustrations and quantum fluctuations in the strongly correlated matter because it causes the emergence of new exotic quantum phases. For example, in the past decade, we have found a number of new Mott insulator materials on a triangular layer: Cs2CuCl4 [1] and organic charge transfer salts [2], such as κ-(BEDT-TTF)2 X and β-Z[Pd(dmit)2]2. There are geometrical frustrations and quantum fluctuations in these materials. Probably, the interplay has an important role for the disordered behaviors at very low temperatures in some materials. In order to study the low temperature property of strongly correlated matter in low-dimensional systems, we need a theoretical tool beyond the mean-field theory. The numerical approach is a candidate. Unfortunately, there are serious drawbacks in the conventional numerical methods. For example, quantum Monte Carlo (QMC) methods are powerful tools because they are unbiased. However, the weight of QMC samples can be negative in quantum frustrated magnets, leading to a cancellation in sign, and the accuracy of simulations fatally decreases (this is the so-called negative sign problem.) Exact diagonalization gives us the detail of a ground state, but it can only be applied to small systems. On the other hand, the variational method is flexible, and it is powerful if we choose the appropriate variational wave function. In the past decade, based on the study of entanglement, we discussed the new types of wave functions for quantum many-body systems. We define the probability amplitudes of these wave functions by the tensor contractions of small tensors. Since the tensor contractions can be drawn as a network, it is called a tensor network state. In this paper, we will report the performance of tensor network state for the variational study of quantum frustrated magnets. There are two major tensor network states: projected entangled pair state(PEPS) [3] and multiscale entanglement renormalization ansatz(MERA) [4]. In the following, we will focus on the MERA, and we will report the performance for S = 1/2 spatially anisotropic triangular antiferromagnets [5]. We organize this paper as follows: In Sec. 2, we will briefly introduce the tensor network. In addition, we will explain a MERA tensor network for triangular lattice models in detail. In Sec. 3, we will show the performance of MERA for the S = 1/2 antiferromagnetic Heisenberg model on a
We propose an approach to study the ground state of quantum many-body systems in which tensor network states, specifically projected entangled pair states (PEPSs), and Green's function Monte Carlo (GFMC) are combined. PEPSs, by design, encode the area law which governs the scaling of entanglement entropy in quantum systems with short-range interactions but are hindered by the high computational complexity scaling with bond dimension D. GFMC is a highly efficient method, but it usually suffers from the infamous negative sign problem which can be avoided by the fixed-node approximation in which a guiding wave function is utilized to modify the sampling process. The trade-off for the absence of the negative sign problem is the introduction of systematic error by the guiding wave function. In this work, we combine these two methods, PEPS and GFMC, to take advantage of both of them. PEPSs are very accurate variational wave functions, while at the same time, only contractions of the single-layer tensor network are necessary in GFMC, which reduces the cost substantially. Moreover, energy obtained in GFMC is guaranteed to be variational and lower than the variational energy of the guiding PEPS wave function. Benchmark results of the ${J}_{1}\ensuremath{-}{J}_{2}$ Heisenberg model on the square lattice are provided.
The approximate contraction of a tensor network of projected entangled pair states (PEPS) is a fundamental ingredient of any PEPS algorithm, required for the optimization of the tensors in ground state search or time evolution, as well as for the evaluation of expectation values. An exact contraction is in general impossible, and the choice of the approximating procedure determines the efficiency and accuracy of the algorithm. We analyze different previous proposals for this approximation, and show that they can be understood via the form of their environment, i.e. the operator that results from contracting part of the network. This provides physical insight into the limitation of various approaches, and allows us to introduce a new strategy, based on the idea of clusters, that unifies previous methods. The resulting contraction algorithm interpolates naturally between the cheapest and most imprecise and the most costly and most precise method. We benchmark the different algorithms with finite PEPS, and show how the cluster strategy can be used for both the tensor optimization and the calculation of expectation values. Additionally, we discuss its applicability to the parallelization of PEPS and to infinite systems.