Positive bias makes tensor-network contraction tractable
arXiv:2410.05414 · doi:10.1145/3717823.3718105
Abstract
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.
45 pages, 7 figures
References in corpus (25)
- Measurement-Induced Phase Transitions in the Dynamics of Entanglement
- Tensor networks for complex quantum systems
- Theory of the phase transition in random unitary circuits with measurements
- Holographic duality from random tensor networks
- Simulating quantum computation by contracting tensor networks
- Tensor Network Renormalization
- The computational complexity of PEPS
- Variational study of hard-core bosons in a 2-D optical lattice using Projected Entangled Pair States (PEPS)
- Variational optimization with infinite projected entangled-pair states
- Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code
- Gradient methods for variational optimization of projected entangled-pair states
- Renormalization of tensor-network states
- Tensor Network Algorithms: a Route Map
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Tensor Networks and Quantum Error Correction
- General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
- Rigorous RG algorithms and area laws for low energy eigenstates in 1D
- Entanglement phase transitions in random stabilizer tensor networks
- Contracting projected entangled pair states is average-case hard
- Simulation of three-dimensional quantum systems with projected entangled-pair states
- Finite-time teleportation phase transition in random quantum circuits
- Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
- Efficient Algorithms for Approximating Quantum Partition Functions
- Approximating local observables on projected entangled pair states
- Sign problem in tensor network contraction