Sign problem in tensor network contraction

• URL: http://arxiv.org/abs/2404.19023v1
• Date: Mon, 29 Apr 2024 18:06:38 GMT
• Title: Sign problem in tensor network contraction
• Authors: Jielun Chen, Jiaqing Jiang, Dominik Hangleiter, Norbert Schuch,
• Abstract summary: We study how the difficulty of contracting tensor networks depends on the sign structure of the tensor entries. We find that the transition from hard to easy occurs when the entries become predominantly positive. We also investigate the computational difficulty of computing expectation values of tensor network wavefunctions.
• Score: 0.5437298646956507
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 complexity. This raises the question how this transition in computational complexity manifests itself in the hardness of different contraction schemes. We pursue this question by studying random tensor networks with varying bias towards positive entries. First, we consider contraction via Monte Carlo sampling, and find that the transition from hard to easy occurs when the entries become predominantly positive; this can be seen as a tensor network manifestation of the Quantum Monte Carlo sign problem. Second, we analyze the commonly used contraction based on boundary tensor networks. Its performance is governed by the amount of correlations (entanglement) in the tensor network. Remarkably, we find that the transition from hard to easy (i.e., from a volume law to a boundary law scaling of entanglement) occurs already for a slight bias towards a positive mean, and the earlier the larger the bond dimension is. This is in contrast to both expectations and the behavior found in Monte Carlo contraction. We gain further insight into this early transition from the study of an effective statmech model. Finally, we investigate the computational difficulty of computing expectation values of tensor network wavefunctions, i.e., PEPS, where we find that the complexity of entanglement-based contraction always remains low. We explain this by providing a local transformation which 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 towards PEPS contraction based on positive decompositions.

Related papers

• Positive bias makes tensor-network contraction tractable [0.5437298646956507]
  tensor network contraction is a powerful computational tool in quantum many-body physics, quantum information and quantum chemistry. Here, we study how the complexity of tensor-network contraction depends on a different notion of quantumness, namely, the sign structure of its entries.
  arXiv  Detail & Related papers  (2024-10-07T18:27:23Z)
• Tensor Network Computations That Capture Strict Variationality, Volume Law Behavior, and the Efficient Representation of Neural Network States [0.6148049086034199]
  We introduce a change of perspective on tensor network states that is defined by the computational graph of the contraction of an amplitude. The resulting class of states, which we refer to as tensor network functions, inherit the conceptual advantages of tensor network states while removing computational restrictions arising from the need to converge approximate contractions. We use tensor network functions to compute strict variational estimates of the energy on loopy graphs, analyze their expressive power for ground-states, show that we can capture aspects of volume law time evolution, and provide a mapping of general feed-forward neural nets onto efficient tensor network functions.
  arXiv  Detail & Related papers  (2024-05-06T19:04:13Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Error Analysis of Tensor-Train Cross Approximation [88.83467216606778]
  We provide accuracy guarantees in terms of the entire tensor for both exact and noisy measurements. Results are verified by numerical experiments, and may have important implications for the usefulness of cross approximations for high-order tensors.
  arXiv  Detail & Related papers  (2022-07-09T19:33:59Z)
• Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks [83.58049517083138]
  We consider a two-layer ReLU network trained via gradient descent. We show that SGD is biased towards a simple solution. We also provide empirical evidence that knots at locations distinct from the data points might occur.
  arXiv  Detail & Related papers  (2021-11-03T15:14:20Z)
• On Convergence of Training Loss Without Reaching Stationary Points [62.41370821014218]
  We show that Neural Network weight variables do not converge to stationary points where the gradient the loss function vanishes. We propose a new perspective based on ergodic theory dynamical systems.
  arXiv  Detail & Related papers  (2021-10-12T18:12:23Z)
• What training reveals about neural network complexity [80.87515604428346]
  This work explores the hypothesis that the complexity of the function a deep neural network (NN) is learning can be deduced by how fast its weights change during training. Our results support the hypothesis that good training behavior can be a useful bias towards good generalization.
  arXiv  Detail & Related papers  (2021-06-08T08:58:00Z)
• Alternating linear scheme in a Bayesian framework for low-rank tensor approximation [5.833272638548154]
  We find a low-rank representation for a given tensor by solving a Bayesian inference problem. We present an algorithm that performs the unscented transform in tensor train format.
  arXiv  Detail & Related papers  (2020-12-21T10:15:30Z)
• Mean-field entanglement transitions in random tree tensor networks [0.0]
  Entanglement phase transitions in quantum chaotic systems have emerged as a new class of critical points separating phases with different entanglement scaling. We propose a mean-field theory of such transitions by studying the entanglement properties of random tree tensor networks.
  arXiv  Detail & Related papers  (2020-03-02T19:00:19Z)
• Understanding Generalization in Deep Learning via Tensor Methods [53.808840694241]
  We advance the understanding of the relations between the network's architecture and its generalizability from the compression perspective. We propose a series of intuitive, data-dependent and easily-measurable properties that tightly characterize the compressibility and generalizability of neural networks.
  arXiv  Detail & Related papers  (2020-01-14T22:26:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.