
2
t < t∗, t∗
Lt=O(1) t=O(polylog(n)) t=O(poly(n))
⟨A(t)⟩P P ?BQP-complete [18]
log⟨e−iH t ⟩P#P-hard [19, 20] #P-hard #P-hard
⟨e−iHt ⟩P? ? BQP-complete [21]
TABLE I. The computational complexity of computing the quantities in the leftmost column with additive error ε= 1/poly(n),
where nis the system size, for different times. All expectation values are with respect to product initial states. The constants
t∗and t∗
Lare independent of the system size but depend on the details of the problem. Entries highlighted in blue are results
from this work. Question marks denote regimes where the computational complexity is unknown.
The scaling with the time tis rather unfavorable, but
the computational cost is independent of system size.
Moreover, for any constant value of t, the run time has
a polynomial dependence on 1/ε, which is an improve-
ment over all previously known algorithms, such as those
based on Lieb–Robinson bounds. The cluster expansion
can thus be seen as an alternative approach to analyzing
the effective locality and light-cone structure of many-
body dynamics.
Our second result characterizes the complexity of com-
puting the Loschmidt echo, tr(e−itH ρ).
Result 2. (Informal version of Theorem 12) Given a lo-
cal Hamiltonian H, a product state ρ, and |t|< t∗
L, there
exists an algorithm that approximates log tr(e−iHtρ)up
to additive error εwith run time of at most
n×poly "n
1− |t|/t∗
L
1
ε1/log(t∗
L/|t|)#,(2)
where t∗
Lis a positive constant.
A key insight of this work is that when ρis a prod-
uct state, the objects analyzed in Results 1 and 2 fit the
framework of cluster expansions that are commonly ap-
plied to the partition function tr(e−βH ) [11, 17, 22]. We
give a novel proof of the convergence of these expansions
based on the counting of trees.
In both algorithms, the cluster expansion enables an
efficient grouping of the terms of a Taylor series by clus-
ters of subsystems. Crucially, we show that only con-
nected clusters contribute. Because the number of con-
nected clusters grows at most exponentially with the size
of the cluster, we can establish the convergence of the
cluster expansion at short times by bounding the magni-
tude of the individual terms. The computational cost of
the approximation algorithms follows by estimating the
cost of computing a truncated cluster expansion while
controlling the truncation error. For local observables,
we are able to extend the algorithm beyond the radius of
convergence of the cluster expansion using analytic con-
tinuation. The doubly exponential dependence on the
evolution time tin Result 1 is a direct consequence of
the analytic continuation scheme.
The above results have several important physics im-
plications. Result 2 implies that dynamical phase tran-
sitions [23] cannot occur at times t≤t∗
Lfor local Hamil-
tonians and product initial states. In addition, it es-
tablishes a novel quantum speed limit [24] that is in-
dependent of system size, in stark contrast to previous
results for general initial states [25, 26]. A generaliza-
tion of Result 2 to the multi-Hamiltonian Loschmidt echo
tr(ρQle−itH(l)), with H(l)local Hamiltonians, allows us
to prove Gaussian concentration bounds of local observ-
ables on states evolved for a short time, a case not cov-
ered by previous results [27–29]. More precisely, we show
that the probability of measuring H(2) in the evolved
product state ρ(t) = e−itH(1) ρeitH(1) away from the mean
tr(ρ(t)H(2)) by δis suppressed by eO(−δ2/n).
B. Complexity of dynamics
Our main results have nontrivial consequences for the
computational complexity of short-time quantum dy-
namics, which are summarized in Table I. For observ-
ables, it is known that approximating ⟨A(t)⟩with ad-
ditive error ε= 1/poly(n) up to times t= poly(n) is
BQP-complete. This follows from the fact that determin-
ing the state of a single qubit at the output of a circuit
with poly(n) gates is BQP-complete, combined with the
existence of local Hamiltonians that simulate arbitrary
quantum computations [18]. At the same time, Theo-
rem 6 shows that we can compute ⟨A(t)⟩classically with
a similar error with computational cost poly(n) as long
as t=O(1). This indicates a transition in the complex-
ity of simulating local observables as the system evolves.
The exact nature of this transition and the computational
complexity of the intermediate regime t∼polylog(n),
where the cluster expansion fails to be efficient, remains
an open problem.
For the Loschmidt echo, there are two meaningful no-
tions of approximation. The first one is with a small mul-
tiplicative error, which is equivalent to a small additive
error in the logarithm. For this, Theorem 12 shows that
there is an efficient approximation algorithm for times
|t|< t∗
Lwith polynomial cost in both nand 1/ε. Un-
like in Theorem 6, it is not possible to extend this result
to arbitrary times. If we take ρ∝I,L(t) becomes an
imaginary-time partition function. Approximating this
for |t|=O(1) even with an O(1) multiplicative error
has been shown to be #P-hard for 2-local, classical Ising
models [20]. Hence, there is only a constant gap between
the times accessible with our algorithm and the #P-hard
regime, where an efficient algorithm is unlikely to exist.