Classical simulation of short-time quantum dynamics Dominik S. Wild1and Alvaro M. Alhambra1 2 1Max-Planck-Institut f ur Quantenoptik Hans-Kopfermann-Straße 1 D-85748 Garching Germany

2025-04-29 0 0 779.65KB 23 页 10玖币
侵权投诉
Classical simulation of short-time quantum dynamics
Dominik S. Wild1, and ´
Alvaro M. Alhambra1, 2,
1Max-Planck-Institut f¨ur Quantenoptik, Hans-Kopfermann-Straße 1, D-85748 Garching, Germany
2Instituto de F´ısica Torica UAM/CSIC, C/ Nicol´as Cabrera 13-15, Cantoblanco, 28049 Madrid, Spain
(Dated: July 12, 2023)
Recent progress in the development of quantum technologies has enabled the direct investigation
of dynamics of increasingly complex quantum many-body systems. This motivates the study of the
complexity of classical algorithms for this problem in order to benchmark quantum simulators and to
delineate the regime of quantum advantage. Here we present classical algorithms for approximating
the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the
evolution is governed by a local Hamiltonian. For short times, their computational cost scales
polynomially with the system size and the inverse of the approximation error. In the case of
local observables, the proposed algorithm has a better dependence on the approximation error than
algorithms based on the Lieb–Robinson bound. Our results use cluster expansion techniques adapted
to the dynamical setting, for which we give a novel proof of their convergence. This has important
physical consequences besides our efficient algorithms. In particular, we establish a novel quantum
speed limit, a bound on dynamical phase transitions, and a concentration bound for product states
evolved for short times.
I. INTRODUCTION
The study ofthe dynamics of quantum many-body
models is a highly active area of research in quantum
information science, both from the perspective of physics
and of computation. Probing dynamics provides access
to a wealth of physical phenomena and can enable the
solution of hard computational problems. Existing quan-
tum simulators are already allowing us to explore quan-
tum dynamics of high complexity. To assess the poten-
tial for quantum speed-up, it is important to understand
the reach of classical methods for these tasks. Unless
all quantum computations can be classically simulated,
i.e. BPP =BQP, classical algorithms will be unable to
approximate quantum dynamics in an arbitrary setting.
Nevertheless, there exist restricted regimes in which ef-
ficient classical simulation is possible. An important
special case is evolution for short times, during which
the quantum information will not spread much. Tensor-
network methods illustrate this point, as they provide
provably efficient means of simulating unitary dynamics
in one spatial dimension for short times [1, 2].
In this work, we characterize the computational com-
plexity of short-time dynamics under a local Hamiltonian
more generally. Locality in this context means that the
Hamiltonian can be written as a sum of operators sup-
ported on small subsystems. We do not require geometric
locality and we do not restrict the Hamiltonian to a finite-
dimensional lattice. Instead, we only impose that every
term in the Hamiltonian overlaps with a constant num-
ber of other terms. These conditions are satisfied by a
wide class of physically relevant Hamiltonians, including
parent Hamiltonians of quantum LDPC error-correcting
codes [3]. Dynamics governed by Hamiltonians of this
dominik.wild@mpq.mpg.de
alvaro.alhambra@csic.es
type are amenable to cluster expansions, which have long
been used in both classical and quantum statistical me-
chanics of lattice models [4–8], leading to results such as
the uniqueness of Gibbs states [9, 10], efficient approxi-
mation schemes for partition functions [11, 12], the decay
of correlations [13–15], and concentration bounds [16, 17].
Despite their long history, cluster expansions have typ-
ically been applied to equilibrium properties, while dy-
namics have been rarely considered.
The paper is structured as follows. In the remainder
of the introduction, we summarize the main results and
give an overview of their implications for the complexity
of quantum dynamics. In Sec. II, we define the cluster no-
tation used throughout. Sec. III discusses the results and
algorithm for local observables. In Sec. IV, we describe
corresponding results for the Loschmidt echo. Physical
consequences of these results are discussed in Sec. V. We
conclude in Sec. VI with further remarks and open ques-
tions. The main text provides an overview of all the proof
techniques, while technical details that are less crucial to
the understanding are placed in appendices.
A. Summary of results
Our first main result concerns the dynamics of a few-
body observable Aunder a local Hamiltonian H.
Result 1. (Informal version of Theorem 6) Given a lo-
cal Hamiltonian H, a few-body operator A, and a prod-
uct state ρ, there exists an algorithm that approximates
tr(eiHtAeiHtρ)up to additive error εwith run time of
at most
poly "1
εeπ|t|/texp(π|t|/t)#,(1)
where tis a positive constant.
arXiv:2210.11490v2 [quant-ph] 11 Jul 2023
2
t < t, t
Lt=O(1) t=O(polylog(n)) t=O(poly(n))
A(t)P P ?BQP-complete [18]
logeiH t P#P-hard [19, 20] #P-hard #P-hard
eiHt 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
tand 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(eitH ρ).
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(eiHtρ)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 tt
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(ρQleitH(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) = eitH(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 tpolylog(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.
3
The complexity of the analogous problem for real par-
tition functions and the thermodynamic free energy has
been recently considered in Ref. [30].
We may also consider the weaker additive approxima-
tion to the Loschmidt echo. Since |L(t)| ≤ 1, Theorem
12 also implies that we can efficiently approximate the
Loschmidt echo to an ε-additive error for |t|< t
L. Calcu-
lating the Loschmidt echo for circuits of polynomial size
with additive error ε= 1/poly(n) is BQP-complete [21].
To the best of our knowledge, the intermediate regime
has not been explored.
II. SETUP
A. Hamiltonian
We consider a set of nspins, V. Each spin vVis as-
sociated with a local Hilbert space Hvwith dim Hv=d.
The total Hilbert space is formed by the tensor product
space H=NvVHv. We call a subset of spins XV
a subsystem. For any linear operator Aon H, we de-
note its support by X= supp(A), i.e., Xis the smallest
subsystem in Von which Aacts nontrivially.
Next, we formally define the notion of local Hamiltoni-
ans. Given a set of subsystems S, we write a Hamiltonian
Has
H=X
XS
λXhX,(3)
where each λXis a real coefficient and hXis a Her-
mitian operator acting on the subsystem Xsuch that
supp(hX) = X. The coefficients satisfy |λX| ≤ 1 and are
chosen such that hX= 1, where ∥ · ∥ is the operator
norm. A Hamiltonian is called k-local if it is a sum of
terms that act on at most ksites or, equivalently, |X| k
for all XS.
To characterize the connectivity of the Hamiltonian,
we define the associated interaction graph G[22]. Given
a set of subsystems S, the interaction graph Gis a simple
graph with vertex set S. There is an edge between two
vertices Xand Yif the respective subsystems overlap.
We denote the maximum degree of the interaction graph
by d. Throughout this work, we only consider k-local
Hamiltonians for which, in addition, dis independent of
the system size n. Each local term in the Hamiltonian
therefore only overlaps with a constant number of other
terms, which includes many physically relevant cases such
as Hamiltonians with finite-range interactions. We point
out that the number of terms |S|in these Hamiltonians
increases at most linearly with the number of spins n.
B. Clusters
We define a cluster as a nonempty multiset of subsys-
tems from S. Here, multiset refers to a set with possibly
(a) (b)
(c) (d)
FIG. 1. A cluster of three subsystems W={W1, W2, W3}
that is (a) connected, (b) disconnected, (c) completely con-
nected to A, and (d) not completely connected to A. The
black dots indicate individual spins and crosses highlight spins
that form the support of A.
repeated elements but without ordering. We use bold-
font letters V,W, . . . to denote clusters. We call the
number of times a subsystem Xappears in a cluster W
the multiplicity µW(X). If Xis not contained in W, then
µW(X) = 0. The size |W|=PXSµW(X) of a cluster
is the number of subsystems that it contains, including
their multiplicity. The set of all clusters of size mis de-
noted by Cmand the set of all clusters by C=Sm1Cm.
We associate with every cluster Wa simple graph GW,
the so-called cluster graph. The vertices of GWcorre-
spond to the subsystems in W, with repeated subsys-
tems also appearing as repeated vertices. Two distinct
vertices Xand Yare connected by an edge if and only if
the respective subsystems overlap, i.e., XY̸=. We
say that a cluster Wis connected if and only if GWis
connected. We use the notation Gmfor the set of con-
nected clusters of size m, and G=Sm1Gmfor the set
of all connected clusters. The following statement con-
cerning the number of connected clusters is an essential
ingredient of our algorithms.
Lemma 1 (Proposition 3.6 of Haah et al. [22]).Given a
subsystem XS, the number of clusters in Gmthat con-
tain Xis bounded from above by (ed)m. Moreover, there
exists a deterministic classical algorithm with run time
exp(O(mlog d)) that outputs a list of all such clusters.
The classical algorithm is given as Algorithm 1 in Section
3.4 of Haah et al. [22].
The union W=V1V2of two clusters V1and V2is
defined as the union of the multisets, adding all multiplic-
4
ities such that µW(X) = µV1(X)+µV2(X) for all XS.
Another set of clusters of special interest is formed by the
clusters connected to the support of a few-body opera-
tor A. We say that a cluster Wis completely connected
to Aif and only if the cluster graph GW∪{supp(A)}is
connected, where we assume for simplicity that Aacts
on a subsystem contained in the Hamiltonian such that
supp(A)S. We denote the set of such clusters of size
mby GA
m, and GA=Sm1GA
m. The different sets of
clusters are illustrated in Fig. 1.
Before proceeding, we introduce further notation re-
lated to clusters. It is sometimes convenient to assign
a (nonunique) ordering to the subsystems in a cluster.
For W∈ Cm, we then write W={W1, W2, . . . , Wm}.
We make frequent use of the shorthands λW=
QXSλµW(X)
Xand W! = QXSµW(X)!. We often
take derivatives with respect to the parameters of the
Hamiltonian for all subsystems contained in a cluster
W. To this end, we define the cluster derivative DW,
which acts on any function of the Hamiltonian parame-
ters λ={λX:XS}as
DWf(λ) = "Y
XS
λXµW(X)#f(λ)λ=0
.(4)
Here, the subscript λ= 0 means to set λX= 0 for all
XSafter taking the derivatives. Hence, the cluster
derivative isolates the contribution from the monomial
λW.
For any function f(λ), we define its cluster expansion
as the multivariate Taylor-series expansion in λ. With
the above notation, the cluster expansion can be con-
cisely written as
f(0) + X
W∈C
λW
W!DWf(λ).(5)
Our goal is to establish conditions under which the clus-
ter expansion converges to f(λ) for different functions of
interest.
We illustrate the above concepts by an example in Ap-
pendix B 1.
C. Cluster partitions
A partition Pof a cluster Wis a multiset of clusters
{V1,V2,...,V|P|}such that W=V1V2···V|P|.
We are particularly interested in partitions where every
element is a connected cluster. We refer to these as par-
titions of Winto connected subclusters. The set of all
such partitions is denoted by Pc(W).
We introduce several quantities characterizing cluster
partitions. We use tildes to distinguish these from similar
quantities describing clusters. The multiplicity ˜µP(V) is
defined as the number of times the cluster Vappears
in the partition P. The size |P|=PV∈G ˜µP(V) is the
(a)
(c)
(b)
FIG. 2. Illustration of cluster and partition graphs. (a) A
connected cluster W={W1, W2, W3, W4}composed of four
subsystems. The dots indicate individual spins. (b) The cor-
responding cluster graph GW. The dashed outlines show the
partition P={{W1},{W2, W3},{W4}} of Winto connected
subclusters. (c) The partition graph ˜
GPassociated with P.
number of clusters in P, including their multiplicities.
We also use the shorthand
P! = Y
V∈G
˜µP(V)! (6)
For every partition P∈ Pc(W), we define a simple
graph ˜
GP, called the partition graph of P. The vertices
of ˜
GPare the clusters in P. Two clusters V,VPare
connected by an edge if and only if they overlap, that
is, there exist subsystems XVand YVsuch that
XY̸=. Alternatively, we may obtain ˜
GPfrom GW
as follows. For every VP, we merge the correspond-
ing vertices in GWinto a single vertex and remove all
loops. If any of the remaining edges are repeated, they
are reduced to a single edge. Figure 2 shows an example
of a partition graph and illustrates its connection to the
cluster graph.
III. LOCAL OBSERVABLES
A. Cluster expansion
We consider the expectation value of an observable
Afor an initial product state ρevolving under a local
Hamiltonian H. After time t, we have
A(t)= tr eiHtAeiHtρ.(7)
Due to the dependence of Hon the parameter set λ, we
may think of A(t)as a function of λ. The corresponding
cluster expansion is given by
fA(t) = A(0)+
X
m=1 X
W∈Cm
λW
W!DWA(t).(8)
5
For W∈ Cm, the cluster derivative can be explicitly
evaluated as
DWA(t)=(it)m
m!(9)
×X
σSm
tr hWσ(1) ,hWσ(2) ,···hWσ(m), Aρ,
where the sum runs over all permutations of the indices
{1,2, . . . , m}.
For simplicity, we assume that the support of Ais con-
tained in the set of subsystems Sof the local supports of
the Hamiltonian, although this constraint can be read-
ily relaxed. We establish the convergence of the cluster
expansion for short times in two steps. First, we show
that only clusters that are completely connected to A
contribute to the sum.
Lemma 2. For any cluster W/∈ GA,
DWA(t)= 0.(10)
Proof. Consider W/∈ GA
mfor any integer m > 0. For
every σSm, there exists a positive integer km
such that the intersection of Wσ(k)with Wσ(k+1)
Wσ(k+2) ∪ ··· ∪ Wσ(m)supp(A) is empty. Then,
hWσ(k),hWσ(k+1) ,···hWσ(m), A = 0, and the com-
mutator in Eq. (9) vanishes.
Second, we need to bound the magnitude of the clus-
ter derivative when it does not vanish. Note that
there are at most 2min the nested commutators of
Eq. (9). Repeated application of the triangle inequality
then yields tr hWσ(1) ,hWσ(2) ,···hWσ(m), Aρ
2mA. Hence, we find that for any W∈ GA
m,
|DWA(t)⟩| ≤ (2|t|)mA.(11)
By combining these observations, we are able to prove
convergence of the cluster expansion for short times:
Proposition 3. Consider an operator Afor which
supp(A)Sand let |t|< t= 1/(2ed). Then,
A(t)⟩−⟨A(0)⟩ −
M
X
m=1 X
W∈GA
m
λW
W!DWA(t)
edA(|t|/t)M+1
1− |t|/t.(12)
Proof. Consider the error of neglecting all clusters of size
m>M from the cluster expansion. Since |λX| ≤ 1 for
all XS, we can bound this error by
X
m=M+1 X
W∈GA
m
λW
W!DWA(t)
X
m=M+1
(2|t|)m|GA
m|∥A.
(13)
By assumption, supp(A)S, which allows us to obtain
every cluster in GA
mby starting from a cluster W∈ Gm+1
that contains X= supp(A) and reducing the multi-
plicity µW(X) by 1. It follows from Lemma 1 that
GA
m(ed)m+1. Substituting this bound into Eq. (13)
yields a geometric series, which converges when |t|< t.
Convergence of this series implies the convergence of the
cluster expansion such that fA(t) = A(t)and leads to
the error bound in the lemma.
We highlight that Proposition 3 holds for any quantum
state ρ. The restriction to product states only becomes
relevant when bounding the computational cost. In ad-
dition, the proposition is valid for complex values of t.
B. Computation for short times
We now discuss the computational cost of estimating
A(t)for a time |t|< tup to additive error εA. For
simplicity, we only give the asymptotic scaling of the al-
gorithm with εand |t|/tand suppress the dependence on
constant parameters such as the locality kor the connec-
tivity dof the Hamiltonian. Moreover, we exclude issues
of finite numerical precision, which have been addressed
rigorously by Haah et al. [22], from our considerations.
Our approximation algorithm computes the cluster ex-
pansion for all clusters up to size M, whose value is de-
termined by εand |t|/t. For all mM, we proceed in
two steps:
(i) Enumerate all the connected clusters in GA
m.
(ii) Compute and add the contributions of every clus-
ter.
Step (i) can be carried out by using the algorithm in
Lemma 1 to first compute clusters of size m+ 1 contain-
ing X= supp(A) and by subsequently reducing the mul-
tiplicity of Xby one. The run time is exp(O(m)). The
computational effort of step (ii) is dominated by the eval-
uation of the sum over nested commutators in Eq. (9).
We show in Appendix A that this can be done for a prod-
uct state in time exp(O(m)) by suitably grouping the m!
terms of the sum.
Together, the two steps lead to the following run time
of the approximation algorithm.
Proposition 4. Let ρbe a product state and |t|< t=
1/(2ed). There exists an algorithm that outputs an esti-
mate ˆ
fA(t)with run time
poly "1
1− |t|/t
1
ε1/log(t/|t|)#(14)
such that A(t)⟩ − ˆ
fA(t)εA.
Proof. According to Proposition 3, truncating the clus-
ter expansion at order M > log ed
(1−|t|/t)ε/log t
|t|leads
to an error that is bounded from above by εA. Fol-
lowing the above discussion of enumerating the clusters
摘要:

Classicalsimulationofshort-timequantumdynamicsDominikS.Wild1,∗and´AlvaroM.Alhambra1,2,†1Max-Planck-Institutf¨urQuantenoptik,Hans-Kopfermann-Straße1,D-85748Garching,Germany2InstitutodeF´ısicaTe´oricaUAM/CSIC,C/Nicol´asCabrera13-15,Cantoblanco,28049Madrid,Spain(Dated:July12,2023)Recentprogressinthedev...

展开>> 收起<<
Classical simulation of short-time quantum dynamics Dominik S. Wild1and Alvaro M. Alhambra1 2 1Max-Planck-Institut f ur Quantenoptik Hans-Kopfermann-Straße 1 D-85748 Garching Germany.pdf

共23页,预览5页

还剩页未读, 继续阅读

声明:本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知玖贝云文库,我们立即给予删除!
分类:图书资源 价格:10玖币 属性:23 页 大小:779.65KB 格式:PDF 时间:2025-04-29

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务
/ 23
客服
关注