Locality and Digital Quantum Simulation of Power-Law Interactions

The propagation of information in nonrelativistic quantum systems obeys a speed limit known as a Lieb-Robinson bound. We derive a new Lieb-Robinson bound for systems with interactions that decay with distance $r$ as a power law, $1/r^{\alpha }$. The bound implies an effective light cone tighter than all previous bounds. Our approach is based on a technique for approximating the time evolution of a system, which was first introduced as part of a quantum simulation algorithm by Haah et al., FOCS’18. To bound the error of the approximation, we use a known Lieb-Robinson bound that is weaker than the bound we establish. This result brings the analysis full circle, suggesting a deep connection between Lieb-Robinson bounds and digital quantum simulation. In addition to the new Lieb-Robinson bound, our analysis also gives an error bound for the Haah et al. quantum simulation algorithm when used to simulate power-law decaying interactions. In particular, we show that the gate count of the algorithm scales with the system size better than existing algorithms when $\alpha >3D$ (where $D$ is the number of dimensions).

Popular Summary

Quantum mechanics limits the speed at which information can propagate. Such speed limits have far-reaching implications, including theoretical bounds on entanglement in a system’s lowest-energy state. More concretely, they imply the existence of a “light cone,” a limited region of spacetime potentially affected by a given event. Here, we prove the existence of a new, tighter light cone for systems with long-range interactions. Such long-range interactions are ubiquitous in physics, including, for example, the Coulomb interaction that acts between electrons regardless of their separation. Compared with the best previously known bound, our proof is conceptually simpler and more flexible, enabling new calculations that would not have been possible before.

Our work builds upon a framework that was recently introduced for simulating quantum systems with short-range interactions on a quantum computer. This framework relies on the quantum speed limits mentioned above. Surprisingly, we show that for long-range interactions, the framework can be adapted to prove a tighter light cone, using an earlier, looser bound as a starting point. Additionally, we show that the previously proposed quantum simulation algorithm works even for long-range interactions.

This research opens the door to studying bounds on information propagation for a wide variety of physical quantities, including the out-of-time-order correlators considered in studies of quantum chaos. We also expect that the simulation framework could be adapted to simulate quantum systems more efficiently on a classical computer.

Figure 1

A demonstration of the unitary decomposition in Lemma 1. (a) The three disjoint regions $A$, $B$, $C$ in $D=1$ and $D=2$ dimensions with $A$ convex and compact. (b) Lemma 1 allows the evolution of the whole system to be approximated by a series of three evolutions of subsystems. The horizontal axis lists the sites in each of the three sets $A$, $B$, $C$ (not necessarily according to their geometrical arrangement, particularly in higher dimensions). Each box is an evolution for time $t$ of a Hamiltonian supported on the sites the box covers. These evolutions can be forward (white fill) or backward (orange fill, with dagger) in time.

Figure 2

A step-by-step construction of the unitary $\tilde{U}$ such that ${\tilde{U}}^{†}{O}_X\tilde{U}\approx U_T^{†}{O}_X{U}_T$. Each box represents an evolution of the subsystem covered by the width of the box for a fixed time. The colors of the boxes follow the same convention as in Fig. 1. In panel (a), the unitary $U_T$ is written as a product of evolutions of the same system in $M=5$ consecutive time slices. (b) The evolution in the last (bottom) time slice is decomposed using the method in Fig. 1, with the choice of subsystems $A$, $B$, $C$ such that $X$ is contained in $A$. The evolutions of the subsystems $B$ and $BC$ (hatched boxes) therefore commute with $O_X$ and cancel out with their counterparts from $U_T^{†}$, resulting in (c). In panel (d), we repeat the procedure for the second-from-bottom time slice, but note the different choice of $A$, $B$, $C$ from (b). This difference is necessary to ensure that the evolutions of $B$ and $BC$ commute with the evolution(s) from the previously decomposed time slice(s). We then commute them through $O_X$ again and remove them from the construction of $\tilde{U}$ in (e). Repeatedly applying the unitary decomposition for the other time slices, we obtain the unitary $\tilde{U}$ in (f), which is supported on a smaller region than the original unitary $U_T$. With a proper choice of the size $\ell$ of $B$, we can make sure that $Y$ lies outside this region, and, therefore, $\tilde{U}$ commutes with $O_Y$.

Figure 3

A construction of the unitary $\tilde{U}$ which results in an improved Lieb-Robinson bound for long-range interactions in Theorem 1. The horizontal axes list the sites in each subset. Here ${\mathcal{B}}_r$ denotes a $D$ ball of radius $r$ centered on $X$, and ${\mathcal{S}}_r={\mathcal{B}}_{r+\ell }\backslash {\mathcal{B}}_r$ a $D$-dimensional shell of inner radius $r$ and outer radius $r+\ell$, for some parameter $\ell$ to be chosen later. (See Fig. 7 in Appendix pp3 for an illustration of the sets.) The evolution unitaries are represented by boxes with the same color convention as in Fig. 1. We first divide the interval $[0,T]$ into $M=5$ equal time slices (upper panel). Note that because we consider $O_X(T)$ in the Heisenberg picture, the vertical axis is therefore backward in time so that the bottom time slice will correspond to the first unitary applied on $O_X$. The evolution during each time slice is approximated by three evolutions of subsystems using Lemma 1 (lower panel). The bottom two unitaries have their supports outside $X$ and therefore commute with $O_X$. They cancel with their Hermitian conjugates from ${\tilde{U}}^{†}$ in ${\tilde{U}}^{†}{O}_X\tilde{U}$. Repeating the argument for higher time slices, we can eliminate some unitaries (hatched boxes) from the construction of $\tilde{U}$. Finally, we are left with $\tilde{U}$ consisting only of unitaries (white boxes) that are supported entirely on the $D$ ball ${\mathcal{B}}_{r_0+5\ell }$ of radius $r_0+5\ell$. Therefore, $\tilde{U}$ commutes with $O_Y$, whose support lies in the complement ${\mathcal{B}}_{r_0+5\ell }^c$ of ${\mathcal{B}}_{r_0+5\ell }$.

Figure 4

A demonstration of the HHKL decomposition [27] of the evolution of a fixed time interval for a system with $m=10$ blocks, each consisting of $\ell$ sites. As before, each box represents a unitary (white) or its Hermitian conjugate (orange) supported on the covered sites. Using Lemma 1, the HHKL decomposition approximates the evolution of the whole system (a) by three unitaries supported on subsystems (b). By applying Lemma 1 repeatedly [(c),(d)], the evolution of the whole system is decomposed into a series of evolutions of subsystems, each of size at most $2\ell$.

Figure 5

The gate count for simulating the dynamics of a one-dimensional Heisenberg chain [Eq. (25)] of length $n$, with $\alpha =4$, $T=n$, and $ϵ={10}^{-3}$. We compare the gate count of the HHKL algorithm (orange square) to the QSP algorithm (blue circle). Note that the HHKL algorithm based on Lieb-Robinson bounds also uses the QSP algorithm as a subroutine. We obtain the scatter points using the approach described in Appendix E and fit them to a power-law model (solid lines). The asymptotic scalings of the gate count obtained from the power-law fits ($n^{3.29}$ for HHKL, $n^{4.00}$ for QSP) agree well with our theoretical predictions (see Table 1).

Figure 6

An illustration of $h_{a{b}^{\prime }}$ and $h_{bc}$ in a one-dimensional lattice. For short-range interactions, the sets $\{a,b^{\prime }\}$ and $\{b,c\}$ are separated by a distance of the same order as the size of $B$ (upper panel). The contributions from these terms to ${\delta }_{\text{overlap}}$ are bounded using a Lieb-Robinson bound. However, for long-range interactions, $\{a,b^{\prime }\}$ and $\{b,c\}$ can be geometrically close to each other (lower panel). In such cases, the norms of $h_{a{b}^{\prime }}$ and $h_{bc}$ decay as ${|b^{\prime }-a|}^{-\alpha }$ and ${|c-b|}^{-\alpha }$ and, therefore, their contributions to ${\delta }_{\text{overlap}}$ are small.

Figure 7

An example of the subset $X={\mathcal{B}}_{r_0}$ and five shells ${\mathcal{S}}_r$ for $r=r_0,r_0+\ell ,\dots ,r_0+4\ell$. The operator $O_Y$ is supported on $Y$, which lies on ${\mathcal{B}}_{r_0+5\ell }^c$, the complement of the ball ${\mathcal{B}}_{r_0+5\ell }$.

Figure 8

The empirical error of the unitary decomposition in Lemma 1, computed for the single-excitation one-dimensional Heisenberg chain ($\alpha =4$) in Eq. (25) at different values of $\ell$. The system size is fixed at $n=300$ and the evolution time at $t=0.01$. We fit the data (blue square) to the theoretical model $b/{\ell }^{\alpha -2}$ and obtain $b=1.62\times {10}^{-3}$.

Figure 9

The empirical gate count of PF4 (purple dots) from $n=4$ to $n=12$, extrapolated to larger system sizes (solid, purple), for simulating the dynamics of the Hamiltonian in Eq. (25) for time $T=n$ at a fixed error tolerance. The error bars are smaller than the size of the markers and hence not visible in the plot. Also shown in dashed lines are the slopes of the gate counts of several advanced algorithms for comparison. These slopes represent the scaling of the gate counts as functions of $n$. Their $y$-intercepts, which represent a constant multiplicative factor, should be ignored.

Figure 10

The nearest-point projection $p_A$ of two points $x$ and $y$ onto a compact set $A$ (oval). Also depicted are the line segment connecting the two image points $p_A(x)$ and $p_A(y)$, as well as the two hyperplanes orthogonal to it.