Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations

We present a general method for approximately contracting tensor networks with an arbitrary connectivity. This enables us to release the computational power of tensor networks to wide use in inference and learning problems defined on general graphs. We show applications of our algorithm in graphical models, specifically on estimating free energy of spin glasses defined on various of graphs, where our method largely outperforms existing algorithms, including the mean-field methods and the recently proposed neural-network-based methods. We further apply our method to the simulation of random quantum circuits and demonstrate that, with a trade-off of negligible truncation errors, our method is able to simulate large quantum circuits that are out of reach of the state-of-the-art simulation methods.

Figure 1

Illustration of connectivity graph of the tensor networks we aim to contract: two-dimensional lattices, random graphs, fully connected graphs, and those defined by the quantum circuits.

Figure 2

Pictorial representation of our algorithm in contracting a tensor network with five tensors; see descriptions in main text.

Figure 3

Illustration of the (a) swap, (b) contract, and (c) merge operations. The scissor symbol indicates truncation of the singular values.

Figure 4

Relative errors of the free energy to exact solutions obtained by different methods on various models. Insets: illustrations of the underlying connectivity graph with smaller sizes. (a) Ferromagnetic Ising model on a $16\times 16$ square lattice; the exact solutions are given by [30], and the vertical dashed line represents the phase transition of an infinite system. (b) Ising spin glass model on random regular graphs of 80 nodes with degree $k=3$; couplings $J_{ij}$ are drawn from normal distribution with zero mean and unit variance. (c) Ising spin glass model on the Watts-Strogatz graphs of 70 nodes with average degree $c=4$ and rewiring probability $p=0.4$. The exact solutions are given by enumerating all configurations of feedback set of graphs [31]. (d) The Sherrington-Kirkpatrick model with $n=20$ spins; exact solutions are given by enumerating $2^n$ configurations. Data points are averaged over 10 random instances.

Figure 5

Computational time and memory usage of our algorithm in simulating random quantum circuits with depth $d=8$, comparing with the exact tensor network method of Guo et al. [24]. We ran our algorithm on a workstation with 64 GB memory (as indicated by the red dashed line). The blue lines with formulas in the figure represent the precise time and space complexity of the exact algorithm [24]. The memory usage is calculated based on double precision complex number. Each red point in the left panel is averaged over 10 random circuits, and the error bars are much smaller than the symbol size.