Perfect sampling with unitary tensor networks

Tensor network states are powerful variational Ansätze for many-body ground states of quantum lattice models. The use of Monte Carlo sampling techniques in tensor network approaches significantly reduces the cost of tensor contractions, potentially leading to a substantial increase in computational efficiency. Previous proposals are based on a Markov chain Monte Carlo scheme generated by locally updating configurations and, as such, must deal with equilibration and autocorrelation times, which result in a reduction of efficiency. Here we propose perfect sampling schemes, with vanishing equilibration and autocorrelation times, for unitary tensor networks, namely, tensor networks based on efficiently contractible, unitary quantum circuits, such as unitary versions of the matrix product state (MPS) and tree tensor network (TTN), and the multiscale entanglement renormalization Ansatz (MERA). Configurations are directly sampled according to their probabilities in the wave function, without resorting to a Markov chain process. We consider both complete sampling, involving all the relevant sites of the system, and incomplete sampling, which only involves a subset of those sites and which can result in a dramatic (basis-dependent) reduction of sampling error.

Figure 1

Contraction of a tensor network. (a) Tensor network corresponding to the expectation value $\langle \Psi \left|\widehat{A}\right|\Psi \rangle$, with a sum over (or exact contraction of) indices $s_1,s_2,\cdots ,s_6$ (exact contraction). Contracting this tensor network has a cost that scales as $O\left({\chi }^p\right)$ with the bond index $\chi$ for some power $p$. (b) Tensor networks corresponding to $\langle \Psi |\mathbf{s}\rangle \langle \mathbf{s}\left|\widehat{A}\right|\Psi \rangle$ for a given configuration $\mathbf{s}$, corresponding to a single sample. The cost of contracting these two networks scales as $O\left({\chi }^q\right)$ with the bond index $\chi$, where power $q$ is smaller than power $p$. (c) Tensor network corresponding to $\langle \Psi |{\mathbf{s}}^{\diamond }\rangle \langle {\mathbf{s}}^{\diamond }|\widehat{A}|\Psi \rangle$ for a given incomplete configuration ${\mathbf{s}}^{\diamond }\equiv (s_1,s_2,s_3)$ (these three indices are being sampled), where in addition there is a sum over (or exact contraction of) indices $s_4,s_5$, and $s_6$. The cost of contracting this tensor network scales as $O\left({\chi }^{q^{\prime }}\right)$, with $q^{\prime }$ somewhere between $q$ and $p$.

Figure 2

Sampling in a unitary matrix product state (uMPS). (a) uMPS for a state $|\Psi \rangle$ of lattice $\mathcal{L}$. Notice the (fictitious) time direction, which provides each tensor with a sense of which indices are incoming and which are outgoing. (b) The past causal cone $\mathcal{C}$ of a local operator $\widehat{A}$ acting on a single site of $\mathcal{L}$ (denoted by a discontinuous circle) defines an effective lattice ${\mathcal{L}}^{\mathcal{C}}$, which is found in state $|{\Psi }^{\mathcal{C}}\rangle$. Notice that the effective lattice ${\mathcal{L}}^{\mathcal{C}}$ is made of two types of sites, namely, sites already present in the original lattice $\mathcal{L}$ and one site not present in $\mathcal{L}$, with $d$-dimensional and $\chi$-dimensional vector spaces, respectively. (c) Tensor networks representing $\langle \Psi \left|\widehat{A}\right|\Psi \rangle$ and $\langle {\Psi }^{\mathcal{C}}\left|\widehat{A}\right|{\Psi }^{\mathcal{C}}\rangle$. The inset shows unitarity reductions [Eq. (17)] used to transform $\langle \Psi \left|\widehat{A}\right|\Psi \rangle$ into $\langle {\Psi }^{\mathcal{C}}\left|\widehat{A}\right|{\Psi }^{\mathcal{C}}\rangle$.

Figure 3

Sampling in a unitary tree tensor network (uTTN). (a) uTTN for a state $|\Psi \rangle$ of lattice $\mathcal{L}$. (b) Effective lattice ${\mathcal{L}}^{\mathcal{C}}$. (c) Tensor networks for $\langle \Psi \left|O\right|\Psi \rangle$ and $\langle {\Psi }^{\mathcal{C}}\left|\mathcal{A}\right|{\Psi }^{\mathcal{C}}\rangle$. The inset shows a reduction due to the unitary constrain of tensors in the uTTN.

Figure 4

Graphical representation of $\langle {\Psi }^{\mathcal{C}}|\widehat{A}|{\Psi }^{\mathcal{C}}\rangle ={\sum }_{\mathbf{r}\in \mathcal{R}}\langle {\Psi }^{\mathcal{C}}|\mathbf{r}\rangle \langle \mathbf{r}|\widehat{A}|{\Psi }^{\mathcal{C}}\rangle$. In (a), the original state $|\Psi \rangle$ was represented with a uMPS; see Fig. 2. In (b), the original state $|\Psi \rangle$ was represented with a uTTN; see Fig. 3. However, in both cases the state $|{\Psi }^{\mathcal{C}}\rangle$ is represented by a uMPS that runs through the causal cone.

Figure 5

Perfect sampling with a uMPS. A sequence of the tensor networks corresponding (up to a proportionality constant) to ${\rho }_1$, $P\left(r_1\right)$, ${\rho }_2\left(r_2\right)$, $P\left(r_2\right|r_1)$, and so on is shown; see Eqs. (21, 22, 23, 24, 25, 26, 27, 28). Importantly, all these tensor networks can be contracted with a cost that scales as $O\left({\chi }^2\right)$ with the bond dimension $\chi$, and they are therefore computationally less expensive than an exact contraction, which has cost $O\left({\chi }^3\right)$.

Figure 6

Sampling of the ground state of the critical transverse Ising model in the $z$ basis. Comparison between configurations obtained using (a) the presented perfect sampling scheme and (b) a Markov chain scheme (single sweep) on 50 sites. Blue sites represent spin up and yellow represent spin down. The correlations between configurations obtained using a Markov chain scheme are evidenced by the appearance of domains of well-defined color that extend vertically. In (c) we have calculated the expected statistical error on the estimate of $\langle {\widehat{\sigma }}^z\rangle$ for the perfect sampling (blue line) and Markov chain sampling (blue dots). While with perfect sampling the error decreases with the usual $N^{-1/2}$ factor, correlations between subsequent samples increase the error on the estimate in the Markov chain scheme. In (d) we plot the same for $\langle {\widehat{\sigma }}^x\rangle$ by projecting all the spins into the $x$ basis. In this case the Markov scheme used utilizes a two-site update so as to be compatible with the wave-function symmetry.[32] In (e) we present the correlations on the center site (in the $z$ basis) after $j$ Markov chain sweeps using ${10}^6$ samples for 50 sites (blue dots) and 250 sites (black crosses). In the perfect sampling scheme (blue line), there are no correlations between configurations. In (f) we plot the estimated autocorrelation time for different system sizes.

Figure 7

Graphical representation of $\langle {\Psi }^{\mathcal{C}}|\widehat{A}|{\Psi }^{\mathcal{C}}\rangle ={\sum }_{{\mathbf{r}}^{\diamond }\in {\mathcal{R}}^{\diamond }}\langle {\Psi }^{\mathcal{C}}|\mathbf{r}\rangle \langle {\mathbf{r}}^{\diamond }|\widehat{A}|{\Psi }^{\mathcal{C}}\rangle$ for a uMPS; compare with Fig. 4a. Notice that sampling does not affect two of the indices, over which an exact contraction is still performed.

Figure 8

Incomplete perfect sampling with a uMPS. A complete sequence of the tensor networks corresponding (up to a proportionality constant) to ${\rho }_1$, $P\left(r_1\right)$, ${\rho }_2\left(r_2\right)$, $P\left(r_2\right|r_1)$, ${\rho }_3(r_1,r_2)$, and $P(r_1,r_2,r_3)$ necessary in order to generate a configuration ${\mathbf{r}}^{\diamond }=(r_1,r_2,r_3)$ with probability $P\left({\mathbf{r}}^{\diamond }\right)={\left|\langle {\Psi }^{\mathcal{C}}|{\mathbf{r}}^{\diamond }\rangle \right|}^2$. Notice that the cost still scales as $O\left({\chi }^2\right)$, as in the complete (perfect) sampling scheme.

Figure 9

Sampling errors with the incomplete perfect sampling scheme for a 50-site critical Ising chain, using both perfect sampling (solid lines) and Markov chain Monte Carlo sampling (dots). (a) Sampling errors in the computation of $\langle \Psi \left|{\widehat{\sigma }}_{25}^z\right|\Psi \rangle$. With perfect sampling, errors in the incomplete perfect sampling scheme are upper bounded by the errors in a complete sampling scheme, as proven in the Appendix. Interestingly, for estimates of $\langle {\widehat{\sigma }}_z\rangle$ the incomplete perfect sampling scheme obtains an error ${10}^{-7}$ times smaller by measuring in the $x$ basis on sites $1,2,\cdots ,L^{\diamond }$. (b) Sampling errors in the computation of $\langle \Psi \left|{\widehat{\sigma }}_{25}^x\right|\Psi \rangle$. Again, the errors with incomplete perfect sampling are smaller than those with complete perfect sampling and depend on the choice of product basis.