Algorithmic Locality via Provable Convergence in Quantum Tensor Networks

Siddhant Midha, Yifan F. Zhang, Daniel Malz, Dmitry A. Abanin, Sarang Gopalakrishnan · 2026

Read Algorithmic Locality via Provable Convergence in Quantum Tensor Networks by Siddhant Midha, Yifan F. Zhang, Daniel Malz, Dmitry A. Abanin, Sarang Gopalakrishnan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21919.txt.

Introduction

Midha and four colleagues develop the first theory of tensor network belief propagation for projected entangled pair states with strong injectivity. Above an injectivity threshold, fixed points can be found fast, and a cluster-corrected algorithm computes quantities to 1/poly(N) error in poly(N) time for an N qubit system. The authors identify algorithmic locality: local perturbations affect the fixed point with influence fading with distance, so local updates need local recomputation. This locality extends to observables, so expectation values can be worked out from data.

Catalog record

CREATORSiddhant Midha, Yifan F. Zhang, Daniel Malz, Dmitry A. Abanin, Sarang Gopalakrishnan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE251590
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.21919

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Algorithmic Locality via Provable Convergence in Quantum Tensor Networks Siddhant Midha, Yifan F. Zhang, Daniel Malz, Dmitry A. Abanin, Sarang Gopalakrishnan 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 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 / poly ⁡ ( N ) 1/\mathrm{poly}(N) error in poly ⁡ ( N ) \mathrm{poly}(N) time for an N N qubit system. We identify a striking phenomenon we term 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. Introduction.— Tensor network states provide a powerful framework for encoding and manipulating quantum many-body wave functions 71 ; 72 ; 54 ; 43 ; 10 ; 65 ; 66 ; 64 ; 63 ; 48 ; 67 ; 68 . In particular, projected entangled pair states (PEPS) 63 generalize matrix product states 71 ; 72 ; 54 ; 64 to higher-dimensional lattices, offering a natural description of ground states of local Hamiltonians with area-law entanglement 43 ; 10 . While PEPS have been extensively studied numerically 23 ; 63 ; 42 ; 41 ; 63 ; 32 ; 39 ; 28 ; 14 ; 12 ; 73 and have yielded significant insights into the structure of quantum phases, establishing their rigorous properties on general graphs remains challenging. In particular, PEPS defined on graphs with loops lack the simple iterative structure enjoyed by matrix product states 71 ; 72 ; 54 ; 64 on one-dimensional chains. As a result, many analytical and computational tools available in one dimension do not directly generalize. (a) (b) Figure 1: (a) Algorithmic locality in tensor networks : The effect of a perturbation at the center of the network on the fixed-point messages living on edges of the graph decays exponentially with distance from perturbation. Loops (see Eq. (6) ) and clusters (see Eq. (7) ) built out of the fixed-point messages inherit the locality subsequently. (b) Phase diagram of injective PEPS : Theorem 1 shows existence (for all 0\leq\varepsilon<1 ) and uniqueness (for \varepsilon<\varepsilon_{*}=\order{1/\Delta} ) of fixed points, where \Delta is the degree of the graph. Theorem 2 shows convergence of cluster expansion for \varepsilon<\varepsilon_{**}=\order{\min\{1/D, (D/\Delta)^{\Delta/2}\}} leading to efficient classical simulation algorithms, with D being the bond dimension of the PEPS. Theorem 3 ties these results to prove algorithmic locality of tensor network belief propagation. The TN-BP algorithm performs well empirically in the intermediate regime. The hardness threshold for estimating local observables depicted \varepsilon_{h} is from Ref. 19 . A framework for reasoning about PEPS on arbitrary graphs has recently emerged in the form of belief propagation (BP) 50 ; 1 ; 53 ; 61 , a message-passing algorithm originally developed for inference on graphical models 17 ; 46 ; 34 ; 75 ; 74 deeply rooted in statistical physics 5 ; 47 ; 59 ; 35 ; 25 ; 24 ; 40 . While classical belief propagation has long been placed on a rigorous footing in certain regimes 69 ; 58 ; 21 ; 22 ; 38 ; 6 ; 57 , recent developments have extended this program to tensor networks through loop and cluster expansions 15 ; 37 ; 36 ; 18 ; 45 , which systematically account for the errors incurred by BP. In this picture, fixed points of the BP message-passing equations encode leading-order information about reduced density matrices of the PEPS on local regions 15 ; 61 , while the convergence properties of BP based expansions are closely tied to the decay of correlations in the underlying quantum state 36 . A key advance enabling this perspective is the use of cluster expansions from lattice statistical mechanics, which systematically decompose tensor network contractions into contributions from localized excitations or “clusters” built on top of the BP fixed points 37 ; 36 . Despite its empirical success in quantum many-body applications 62 ; 61 ; 52 ; 45 ; 29 ; 53 , the theoretical foundations of TN-BP remain incomplete. The cluster expansion technology only provides guarantees given the existence of a suitable BP fixed-point 37 . In practice, the BP message-passing equations used to compute fixed points of the tensor network are implemented as iterative updates, but their convergence is not guaranteed. Moreover, the cluster expansion framework yields controlled results when the contributions from loop tensors decay sufficiently rapidly with loop size—a condition called “decay of loops” that is expected to hold in physically relevant regimes (e.g., deep in a gapped phase) 36 , but has not yet been established rigorously. In this work we put tensor-network belief propagation (TN-BP) on fully rigorous ground by proving the following results. Working with PEPS on arbitrary graphs satisfying an injectivity condition, we prove that BP message-passing admits fixed points, and for a subclass of strongly injective PEPS the fixed point is unique. We further show that these PEPS satisfy a “decay of loops” property controlling corrections to BP. Using the cluster-expansion framework, we can then construct polynomial-time classical algorithms to compute properties such as local expectation values and connected correlation functions. Our convergence results, as a function of the injectivity strength \varepsilon (formally defined later), are summarized in Fig. 1 (b). \varepsilon=1 corresponds to non-injective PEPS and \varepsilon=0 correspond to the “maximally” injective PEPS where all singular values are equal. While we show that a BP fixed point exists for all \varepsilon<1 , it is known that contracting PEPS is \mathsf{postBQP} -hard 33 ; 19 when \varepsilon is above a constant threshold \varepsilon_{h} . Therefore, we do not expect BP to form a good approximation in this regime. On the other hand, we show two upper-bound thresholds \varepsilon_{*} and \varepsilon_{**} : below \varepsilon_{*} the fixed point is unique and can be efficiently found, and below \varepsilon_{**}\leq\varepsilon_{*} cluster-corrected BP can contract PEPS in polynomial-time, to inverse polynomial multiplicative error. Our proof methodology reveals a striking phenomenon, which we call algorithmic locality . Specifically, local perturbations of tensors affect BP messages only within a neighborhood, with influence that decays rapidly with distance Fig. 1 (a). This has both theoretical and practical consequences. On the theoretical side, algorithmic locality yields a clustering theorem analogous to exponential decay of correlations 20 . On the practical side, it enables significant computational speedups when contracting multiple tensor networks that differ only locally: it suffices to update messages within the neighborhood of the perturbation. To the best of our knowledge, this work provides

Read the complete text