Algorithmic Locality via Provable Convergence in Quantum Tensor Networks

• URL: http://arxiv.org/abs/2604.21919v1
• Date: Thu, 23 Apr 2026 17:58:15 GMT
• Title: Algorithmic Locality via Provable Convergence in Quantum Tensor Networks
• Abstract summary: We develop the first end-to-end theory of tensor network belief propagation for a class of projected entangled pair states.<n>We show that when the injectivity parameter exceeds a constant threshold, BP fixed points can be found efficiently.<n>We identify a striking phenomenon we term emphalgorithmic locality: local perturbations of the tensor network affect the BP fixed point with an influence decaying rapidly with distance.
• Score: 0.005023988093549015
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Belief propagation has recently emerged as a powerful framework for evaluating tensor networks in higher dimensions, combining computational efficiency with provable analytical guarantees. In this work, we develop the first end-to-end theory of tensor network belief propagation for a class of projected entangled pair states satisfying \emph{strong injectivity}. We show that when the injectivity parameter exceeds a constant threshold, BP fixed points can be found efficiently, and a cluster-corrected BP algorithm computes physical quantities to $1/\mathrm{poly}(N)$ error in $\mathrm{poly}(N)$ time for an $N$ qubit system. We identify a striking phenomenon we term \emph{algorithmic locality}: local perturbations of the tensor network affect the BP fixed point with an influence decaying rapidly with distance. As a result, updates to the fixed point after a local perturbation can be carried out using only local recomputation. Moreover, through the cluster expansion, this locality extends to observables, implying that local expectation values can be approximated from local data with controlled accuracy. Our results provide the first rigorous guarantee for the effectiveness of tensor-network belief propagation on a wide class of many-body states, bridging a gap between widely used numerical practice and provable algorithmic performance.

Related papers

• Contracting Tensor Networks with Generalized Belief Propagation [0.0]
  We show how to apply belief propagation to approximate, but highly efficient, tensor network contraction.<n>We implement the belief propagation algorithm for a number of different region choices on a range of two- and three-dimensional, infinite and finite tensor networks.<n>Our examples include calculating the partition function of the fully frustrated Ising model, computing the ground state degeneracy of three-dimensional ice models, measuring observables on the deformed AKLT quantum state and evaluating the norm of randomly generated tensor network states.
  arXiv  Detail & Related papers  (2026-04-27T17:59:03Z)
• Belief Propagation and Tensor Network Expansions for Many-Body Quantum Systems: Rigorous Results and Fundamental Limits [0.005389965299678531]
  Belief propagation (BP) provides a scalable for contracting tensor networks on loopy graphs.<n>We rigorously study the applicability of BP to many-body quantum systems.<n>We show that loop-decay" emphnecessarily implies exponential decay of connected correlations.
  arXiv  Detail & Related papers  (2026-04-03T17:59:09Z)
• Partitioned Expansions for Approximate Tensor Network Contractions [0.0]
  We propose a method for approximating the contraction of a tensor network by partitioning the network into a sum of cheaper networks.<n>The flexibility of our approach is demonstrated through applications to a variety of example networks.<n> Benchmark numerical results for networks composed of Ising, AKLT, and random tensors typically show an improvement in accuracy over BP by several orders of magnitude.
  arXiv  Detail & Related papers  (2025-12-11T18:39:44Z)
• Beyond Belief Propagation: Cluster-Corrected Tensor Network Contraction with Exponential Convergence [0.0]
  We develop a rigorous theoretical framework for BP in tensor networks, leveraging insights from statistical mechanics.<n>We prove that the cluster expansion converges exponentially fast if an object called the emphloop contribution decays sufficiently fast with the loop size.<n>Our work opens the door to a systematic theory of BP for tensor networks and its applications in decoding classical and quantum error-correcting codes and simulating quantum systems.
  arXiv  Detail & Related papers  (2025-10-02T17:58:30Z)
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm [8.329034093208826]
  We introduce a method to efficiently approximate tensor network contractions using low-rank approximations.<n>The proposed algorithm has the flexibility to incorporate a large portion of the environment when performing low-rank approximations.
  arXiv  Detail & Related papers  (2024-06-14T07:13:52Z)
• Optimization Guarantees of Unfolded ISTA and ADMM Networks With Smooth Soft-Thresholding [57.71603937699949]
  We study optimization guarantees, i.e., achieving near-zero training loss with the increase in the number of learning epochs. We show that the threshold on the number of training samples increases with the increase in the network width.
  arXiv  Detail & Related papers  (2023-09-12T13:03:47Z)
• Binarizing Sparse Convolutional Networks for Efficient Point Cloud Analysis [93.55896765176414]
  We propose binary sparse convolutional networks called BSC-Net for efficient point cloud analysis. We employ the differentiable search strategies to discover the optimal opsitions for active site matching in the shifted sparse convolution. Our BSC-Net achieves significant improvement upon our srtong baseline and outperforms the state-of-the-art network binarization methods.
  arXiv  Detail & Related papers  (2023-03-27T13:47:06Z)
• On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks [91.3755431537592]
  We study how random pruning of the weights affects a neural network's neural kernel (NTK) In particular, this work establishes an equivalence of the NTKs between a fully-connected neural network and its randomly pruned version.
  arXiv  Detail & Related papers  (2022-03-27T15:22:19Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  We provide a framework for designing Generative Adversarial Networks (GANs) to solve high dimensional robust statistics problems. Our work extend these to robust mean estimation, second moment estimation, and robust linear regression. In terms of techniques, our proposed GAN losses can be viewed as a smoothed and generalized Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2022-02-02T20:11:33Z)
• Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds [99.23098204458336]
  Certified robustness is a desirable property for deep neural networks in safety-critical applications. We show that our method consistently outperforms state-of-the-art methods on MNIST and TinyNet datasets.
  arXiv  Detail & Related papers  (2021-11-02T06:44:10Z)
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks [56.084798078072396]
  We take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with quadratic widths in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size.
  arXiv  Detail & Related papers  (2021-01-12T00:40:45Z)
• Second-Order Provable Defenses against Adversarial Attacks [63.34032156196848]
  We show that if the eigenvalues of the network are bounded, we can compute a certificate in the $l$ norm efficiently using convex optimization. We achieve certified accuracy of 5.78%, and 44.96%, and 43.19% on 2,59% and 4BP-based methods respectively.
  arXiv  Detail & Related papers  (2020-06-01T05:55:18Z)

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.