Classical simulation of quantum many-body systems with a tree tensor network

We show how to efficiently simulate a quantum many-body system with tree structure when its entanglement (Schmidt number) is small for any bipartite split along an edge of the tree. As an application, we show that any one-way quantum computation on a tree graph can be efficiently simulated with a classical computer.

Figure 1

(Color online) (i) A tree TN for state $\mid \Psi ⟩$ of $n=7$ qudits. Each open index labels an orthonormal single-qudit basis [see Eq. (1)]. Each vertex has three edges and corresponds to a tensor with three indices. Pairs of tensors are connected in the network through a shared index, over which there is an implicit summation. (ii) Canonical form of the previous tree TN. For each bipartition, subtrees $\mathcal{A}$ and $\mathcal{B}$ describe Schmidt bases [see Eq. (2)]. An empty circle on top of an edge represents a set of Schmidt coefficients weighting the corresponding index.

Figure 2

(Color online) (i) Initial decomposition Eq. (3). (ii) Insertion of ${\left(X^T\right)}^{-1}{X}^T$ and $Y{Y}^{-1}$, projectors onto the subspaces generated by $\left\{\mid {\widehat{e}}_{\tau }⟩\right\}$ and $\left\{\mid {\widehat{f}}_{\eta }⟩\right\}$. (iii) $X^{T}Y$ is replaced with its singular value decomposition $U\Lambda V$, computed in $O\left({\chi }^3\right)$ time. (iv) The Schmidt decomposition Eq. (2) is obtained after contracting some indices [$O\left({\chi }^4\right)$ time].

Figure 3

(Color online) A single-qudit reduced density matrix is computed by contracting the TN in (i), which represents $\mid \Psi ⟩⟨\Psi \mid$ with a partial trace over all qudits but one. This TN reduces to the TN in (ii) thanks to the orthogonality of the Schmidt bases. In (iii) the weights have been absorbed into the three-index tensors [$O\left(d{\chi }^2\right)$ operations] and in (iv) the remaining shared indices have been contracted [$O\left(d^2{\chi }^2\right)$ operations].

Figure 4

(Color online) The reduced density matrix for two qudits separated by $m=3$ tensors is computed by contracting the TN in (i). This reduces to the TN in (ii) thanks to the orthogonality of the Schmidt bases. In (iii) the Schmidt weights have been absorbed into the tensors [$O\left(d{\chi }^2\right)$ operations], which in turn are reorganized on a line made of $m=3$ columns. Networks (iv)–(vi) illustrate how to reduce by one the number of columns [$O\left(d^2{\chi }^4\right)$ operations]. By iteration, a single tensor (vii) with four open indices is obtained.

Figure 5

(Color online) In order to exchange the positions of indices $\beta$ and $\gamma$ in (i), we contract the corresponding tensors (including all neighboring weights) into the four-legged tensor in (ii). After swapping the two indices, we split the resulting tensor (iii) through a SVD (of a matrix of the dimension $d\chi \times d\chi$ or $d\chi \times {\chi }^2$) that costs $O\left(d^2{\chi }^4\right)$ basic operations. The singular values define the new weights of the central index, whose initial rank $\chi$ may have increased to at most $d\chi$. The old weights for lateral indices are detached from the two tensors to leave the resulting tree TN in the canonical form.

Figure 6

(Color online) The tensor subnetwork in (i) is contracted into the four-legged tensor in (ii), which is then decomposed into (iii) by using a SVD (of a $d\chi \times d\chi$ matrix) that takes $O\left(d^3{\chi }^3\right)$ basic operations. Notice that, as in Fig. 5, special attention is paid to first absorbing and then detaching the weights of the lateral indices. This guarantees that the resulting tree TN is in its canonical form.

Figure 7

(Color online) (i) Tree TN for a system with a genuine tree structure, such as a dendrimer. The red circles represent atoms, whose interaction pattern has a tree structure, represented by the red dotted lines. (ii), (iii) Two random qudits in a binary tree TN are connected through $O\mathbf{\left(}\log \left(n\right)\mathbf{\right)}$ tensors, while in a linear TN (or MPS) they are connected through $O\left(n\right)$ tensors. Therefore, the time required to simulate a gate between two qudits is on average a factor $\log \left(n\right)∕n$ lower when using a tree TN. This is a substantial gain in simulations involving long-range interactions. On the other hand, a generic binary tree TN with rank $\chi$ can be replaced with a MPS with a Schmidt rank ${\chi }^{\prime }=O\left({\chi }^{\log \left(n\right)}\right)=O\left(n^{\log \left(\chi \right)}\right)$. Thus, for constant $\chi$ (independent of $n$) the use of the binary tree TN is markedly more convenient. For $\chi =\mathrm{poly}\left(n\right)$, using the binary tree TN requires polynomial resources, while the cost of using a MPS is superpolynomial, namely, $O\left(n^{\log \left(n\right)}\right)$.