Tensor networks represent the state-of-the-art in computational methods across many disciplines, including the classical simulation of quantum many-body systems and quantum circuits. Several applications of current interest give rise to tensor networks with irregular geometries. Finding the best possible contraction path for such networks is a central problem, with an exponential effect on computation time and memory footprint. In this work, we implement new randomized protocols that find very high quality contraction paths for arbitrary and large tensor networks. We test our methods on a variety of benchmarks, including the random quantum circuit instances recently implemented on Google quantum chips. We find that the paths obtained can be very close to optimal, and often many orders or magnitude better than the most established approaches. As different underlying geometries suit different methods, we also introduce a hyper-optimization approach, where both the method applied and its algorithmic parameters are tuned during the path finding. The increase in quality of contraction schemes found has significant practical implications for the simulation of quantum many-body systems and particularly for the benchmarking of new quantum chips. Concretely, we estimate a speed-up of over 10,000 × compared to the original expectation for the classical simulation of the Sycamore `supremacy' circuits.
Belief propagation is a well-studied algorithm for approximating local marginals of multivariate probability distribution over complex networks, while tensor network states are powerful tools for quantum and classical many-body problems. Building on a recent connection between the belief propagation algorithm and the problem of tensor network contraction, we propose a block belief propagation algorithm for contracting two-dimensional (2D) tensor networks and approximating the ground state of 2D systems. The advantages of our method are threefold: (1) the same algorithm works for both finite and infinite systems; (2) it allows natural and efficient parallelization; and (3) given its flexibility, it would allow us to deal with different unit cells. As applications, we use our algorithm to study the 2D Heisenberg and transverse Ising models, and show that the accuracy of the method is on par with state-of-the-art results.
We present several results relating to the contraction of generic tensor networks and discuss their application to the simulation of quantum many-body systems using variational approaches based upon tensor network states. Given a closed tensor network
T, we prove that if the environment of a single tensor from the network can be evaluated with computational cost $\ensuremath{\kappa}$, then the environment of any other tensor from
T can be evaluated with identical cost $\ensuremath{\kappa}$. Moreover, we describe how the set of all single tensor environments from
T can be simultaneously evaluated with fixed cost $3\ensuremath{\kappa}$. The usefulness of these results, which are applicable to a variety of tensor network methods, is demonstrated for the optimization of a multiscale entanglement renormalization Ansatz for the ground state of a one-dimensional quantum system, where they are shown to substantially reduce the computation time.