Sign problem in tensor network contraction

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.

accepted version

References in corpus (24)

• Many body localization and thermalization in quantum statistical mechanics
• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Theory of the phase transition in random unitary circuits with measurements
• Measurement-induced criticality in random quantum circuits
• Holographic duality from random tensor networks
• Accurate determination of tensor network state of quantum lattice models in two dimensions
• Unitary-projective entanglement dynamics
• Entropy scaling and simulability by Matrix Product States
• Tensor Network Renormalization
• Aspects of generic entanglement
• The computational complexity of PEPS
• Entanglement phase transitions in measurement-only dynamics
• Entanglement Transitions from Holographic Random Tensor Networks
• Efficient classical simulation of random shallow 2D quantum circuits
• Quantum Hamiltonian Complexity
• Easing the Monte Carlo sign problem
• On some properties of orthogonal Weingarten functions
• The computational difficulty of finding MPS ground states
• Entanglement thresholds for random induced states
• Computational Difficulty of Global Variations in the Density Matrix Renormalization Group
• Entanglement and the Sign Structure of Quantum States
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry

Cited by in corpus (6)

• Tensor networks for quantum computing
• Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits
• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
• Efficient optimization and conceptual barriers in variational finite Projected Entangled-Pair States
• Positive bias makes tensor-network contraction tractable
• Classical Neural Networks on Quantum Devices via Tensor Network Disentanglers: A Case Study in Image Classification