Siddhant Midha

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.