Tensor Networks

Abstract: Tensor network contraction on arbitrary graphs is a fundamental computational challenge with applications ranging from quantum simulation to quantum error correction. Belief propagation (BP) offers a powerful and scalable approximation method for this task, yet its accuracy limitations remain poorly understood and systematic improvements have been lacking. In this work, we present a rigorous theoretical framework for BP in tensor networks that resolves these issues. By importing ideas from statistical mechanics, we construct a convergent cluster expansion that systematically corrects BP and yields rigorous error bounds. This addresses two fundamental questions in BP algorithm: - It clarifies when BP approximates ground truth well and provides a rigorous error bound - It gives a polynomial-time algorithm to improve the BP algorithm to having inverse polynomial error. Put together, our results lay the groundwork for a principled and extensible theory of BP-based tensor network contraction.

Abstract: How the detailed entanglement structure emerges from quantum dynamics remains a fundamental challenge, motivated by recent advances in quantum simulators and information processing. As a central milestone, the Small-Incremental-Entangling (SIE) theorem bounds the entanglement-entropy growth rate, but does not control the entanglement spectrum itself. In this work, we define the spectral-entangling strength, which quantifies how strongly an operator can reshape the distribution of Schmidt coefficients across a bipartition. We then prove a spectral SIE theorem: for R\'enyi index $\alpha \ge 1/2$, the growth rate of R\'enyi entanglement entropies admits a universal bound. Remarkably, our bound at $\alpha=1/2$ is both qualitatively and quantitatively optimal; below this threshold ($\alpha<1/2$), no universal speed limit on entanglement growth can exist. This result yields a sharp $1/s^2$ threshold in the tail of the ordered Schmidt coefficients (with $s$ the Schmidt index), enabling rigorous truncation-based error control and establishing a quantitative link between entanglement-spectrum structure and computational complexity. As a practical highlight, for one-dimensional power-law interactions $1/r^{\eta}$ with $\eta>2$, this implies matrix-product-state approximations with bond dimension polynomial in $(n/\varepsilon)$ for ground states, real-time evolved states, and Gibbs states, thereby closing the quasi-polynomial gap. By controlling R\'enyi entanglement, we further obtain a rigorous \emph{a priori} bound on truncation error for time-dependent DMRG/TEBD-type simulations. Overall, we extend the SIE paradigm from bounding entanglement entropies to constraining the entanglement spectrum itself.