# Locally accurate MPS approximations for ground states of one-dimensional
gapped local Hamiltonians

Alexander M. Dalzell  Institute for Quantum Information and Matter, California
Institute of Technology, Pasadena, CA 91125, USA  Fernando G.S.L. Brandão
Institute for Quantum Information and Matter, California Institute of
Technology, Pasadena, CA 91125, USA  Google LLC, Venice, CA 90291, USA

###### Abstract

A key feature of ground states of gapped local 1D Hamiltonians is their
relatively low entanglement — they are well approximated by matrix product
states (MPS) with bond dimension scaling polynomially in the length $N$ of the
chain, while general states require a bond dimension scaling exponentially. We
show that the bond dimension of these MPS approximations can be improved to a
constant, independent of the chain length, if we relax our notion of
approximation to be more local: for all length-$k$ segments of the chain, the
reduced density matrices of our approximations are $\epsilon$-close to those
of the exact state. If the state is a ground state of a gapped local
Hamiltonian, the bond dimension of the approximation scales like
$(k/\epsilon)^{1+o(1)}$, and at the expense of worse but still
$\text{poly}(k,1/\epsilon)$ scaling of the bond dimension, we give an
alternate construction with the additional features that it can be generated
by a constant-depth quantum circuit with nearest-neighbor gates, and that it
applies generally for any state with exponentially decaying correlations. For
a completely general state, we give an approximation with bond dimension
$\exp(O(k/\epsilon))$, which is exponentially worse, but still independent of
$N$. Then, we consider the prospect of designing an algorithm to find a local
approximation for ground states of gapped local 1D Hamiltonians. When the
Hamiltonian is translationally invariant, we show that the ability to find
$O(1)$-accurate local approximations to the ground state in $T(N)$ time
implies the ability to estimate the ground state energy to $O(1)$ precision in
$O(T(N)\log(N))$ time.

##  1 Introduction

In nature, interactions between particles act locally, motivating the study of
many-body Hamiltonians consisting only of terms involving particles spatially
near each other. An important method that has emerged from this course of
study is the Density Matrix Renormalization Group (DMRG) algorithm [36, 37],
which aims to find a description of the ground state of local Hamiltonians on
a one-dimensional chain of sites. DMRG has been an indispensable tool for
research in many-body physics, but the rationale for its empirical success did
not become fully apparent until long after it was being widely used. Its
eventual justification required two ingredients: first, that the method can be
recast [20, 35] as a variational algorithm that minimizes the energy over the
set of matrix product states (MPS), a tensor network ansatz for 1D systems;
and second, that the MPS ansatz set actually contains a good approximation to
the ground state, at least whenever the Hamiltonian has a nonzero spectral
gap. More specifically, Hastings [14] showed that ground states of gapped
local Hamiltonians on chains with $N$ sites can be approximated to within
trace distance $\epsilon$ by an MPS with bond dimension (a measure of the
complexity of the MPS) only $\text{poly}(N,1/\epsilon)$, exponentially smaller
than what is needed to describe an arbitrary state on the chain. Even taking
into account these observations, DMRG is a heuristic algorithm and is not
guaranteed to converge to the global energy minimum as opposed to a local
minimum; however, a recently developed alternative algorithm [21, 2, 26],
sometimes referred to as the “Rigorous RG” (RRG) algorithm, avoids this issue
and provides a way one can guarantee finding an $\epsilon$-approximation to
the ground state in $\text{poly}(N,1/\epsilon)$ time.

These are extremely powerful results, but their value breaks down when the
chain becomes very long. The bond dimension required to describe the ground
state grows relatively slowly, but it still diverges with $N$. Meanwhile, if
we run the RRG algorithm on longer and longer chains, we will eventually
encounter an $N$ too large to handle given finite computational resources.
Indeed, often we wish to learn something about the ground state in the
thermodynamic limit ($N\rightarrow\infty$) but in this case these results no
longer apply. Analogues of DMRG for the thermodynamic limit [22, 34, 11, 38,
24, 31] — methods that, for example, optimize over the set of constant bond
dimension “uniform MPS” consisting of the same tensor repeated across the
entire infinite chain — have been implemented with successful results, but
these methods lack the second ingredient that justified DMRG: it is not clear
how large we must make the bond dimension to guarantee that the set over which
we are optimizing contains a good approximation to the ground state.

Progress toward this ingredient can be found work by Huang [17] (and later by
Schuch and Verstraete [27]), who showed that the ground state of a gapped
local 1D Hamiltonian can be approximated locally by a matrix product operator
(MPO) — a 1D tensor network object that corresponds to a (possibly mixed)
density operator as opposed to a quantum state vector — with bond dimension
independent of $N$ and polynomial in the inverse local approximation error.
Here their approximation sacrifices global fidelity with the ground state,
which decays exponentially with the chain length, in exchange for constant
bond dimension, while retaining high fidelity with the ground state reduced
density matrices on all segments of the chain with constant length. In other
words, the statistics for measurements of local operators are faithfully
captured by the MPO approximation, a notion of approximation that is often
sufficient in practice since many relevant observables, such as the individual
terms in the Hamiltonian, are local.

However, the result does not provide the necessary ingredient to justify
infinite analogues of DMRG because MPO do not make a good ansatz class for
variational optimization algorithms. One can specify the matrix elements for
an MPO, but the resulting operator will only correspond to a valid quantum
state if it is positive semi-definite, and verifying that this is the case is
difficult: it is $\mathsf{NP}$-hard for finite chains, and in the limit
$N\rightarrow\infty$ it becomes undecidable [19]. Thus, if we attempt to
perform variational optimization over the set of constant bond dimension MPO,
we can be certain that our search space contains a good local approximation to
the ground state, but we have no way of restricting our search only to the set
of valid quantum states; ultimately the minimal energy MPO we find may not
correspond to any quantum state at all.

In this work, we fix this problem by showing an analogous result for MPS
instead of MPO. We show that for any gapped nearest-neighbor Hamiltonian on a
1D chain with $N$ sites, and for any parameters $k$ and $\epsilon$, there is
an MPS representation of a state $|\tilde{\psi}\rangle$ with bond dimension
$\text{poly}(k,1/\epsilon)$ such that the reduced density matrix of
$|\tilde{\psi}\rangle\langle\tilde{\psi}|$ on any contiguous region of length
$k$ is $\epsilon$-close in trace distance to that of the true ground state.
Importantly, the bond dimension is independent of $N$. For general states
(including ground states of non-gapped local Hamiltonians), we give a
construction with bond dimension that is also independent of $N$ but
exponential in $k/\epsilon$. This extends a previous result [8] that formally
implied the existence of a uniform MPS approximation of this type when the
state is translationally invariant and $N=\infty$, albeit without explicit
attention paid to the dependence of the bond dimension on the locality $k$ or
approximation error $\epsilon$, or to an improvement therein when the state is
the ground state of a gapped Hamiltonian. Thus, we provide the missing
ingredient for variational algorithms in the thermodynamic limit as we show
that a variational set over a MPS with bond dimension independent in $N$ and
polynomial in $1/\epsilon$ contains a state that simultaneously captures all
the local properties of the ground state.

We present two proofs of our claim about ground states of gapped Hamiltonians.
The first yields superior scaling of the bond dimension, which grows
asymptotically slower than $(k/\epsilon)^{1+\delta}$ for any $\delta>0$;
however, it constructs an MPS approximation $|\tilde{\psi}\rangle$ that is
long-range correlated and non-injective. In contrast, the second proof
constructs an approximation that is injective and can be generated by a
constant-depth quantum circuit with nearest-neighbor gates, while retaining
$\text{poly}(k,1/\epsilon)$ bond dimension. The latter construction also
follows merely from the assumption that the state has exponential decay of
correlations. The proof idea originates with a strategy first presented in
[32] and constructs $|\tilde{\psi}\rangle$ by beginning with the true ground
state $\left|\psi\right\rangle$ and applying three rounds of operations:
first, a set of unitaries that, intuitively speaking, removes the short-range
entanglement from the chain; second, a sequence of rank 1 projectors that
zeroes-out the long-range entanglement; and third, the set of inverse
unitaries from step 1 to add back the short-range entanglement. Intuitively,
the method works because ground states of gapped Hamiltonians have a small
amount of long-range entanglement. The non-trivial part is arguing that the
local properties are preserved even as the small errors induced in step 2
accumulate to bring the global fidelity with the ground state to zero. The
fact that $|\tilde{\psi}\rangle$ can be produced by a constant-depth quantum
circuit acting on an initial product state suggests the possibility of an
alternative variational optimization algorithm using the set of constant-depth
circuits (a strict subset of constant-bond-dimension MPS) as the variational
ansatz. Additionally, we note that the disentangle-project-reentangle process
that we utilize in our proof might be of independent interest as a method for
truncating the bond dimension of MPS. We can bound the truncation error of
this method when the state has exponentially decaying correlations.

We also consider the question of whether these locally approximate MPS
approximations can be rigorously found (à la RRG) more quickly than their
globally approximate counterparts (and if they can be found at all in the
thermodynamic limit). We prove a reduction for ground states of
translationally invariant Hamiltonians showing that finding approximations to
local properties to even a fixed $O(1)$ precision implies being able to find
an approximation to the ground state energy to $O(1)$ precision with only
$O(\log(N))$ overhead. Since strategies for estimating the ground state energy
typically involve constructing a globally accurate approximation to the ground
state, this observation gives us an intuition that it may not be possible to
find the local approximation much more quickly than the global approximation,
despite the fact that the bond dimensions required for the two approximations
are drastically different.

##  2 Background

###  2.1 One-dimensional local Hamiltonians

In this paper, we work exclusively with gapped nearest-neighbor 1D
Hamiltonians that have a unique ground state. Our physical system is a set of
$N$ sites, arranged in one dimension on a line with open boundary conditions
(OBC), each with its own Hilbert space $\mathcal{H}_{i}$ of dimension $d$. The
Hamiltonian $H$ consists of terms $H_{i,i+1}$ that act non-trivially only on
$\mathcal{H}_{i}$ and $\mathcal{H}_{i+1}$:

$H=\sum_{i=1}^{N-1}H_{i,i+1}.$ (1)

We will always require that $H_{i,i+1}$ be positive semi-definite and satisfy
$\lVert H_{i,i+1}\rVert\leq 1$ for all $i$, where $\lVert\cdot\rVert$ is the
operator norm. When this is not the case it is always possible to rescale $H$
so that it is. We call $H$ translationally invariant if $H_{i,i+1}$ is the
same for all $i$. We will also always assume that $H$ has a unique ground
state $\left|\psi\right\rangle$ with energy $E$ and an energy gap $\Delta>0$
to its first excited state. We let
$\rho=\left|\psi\right\rangle\left\langle\psi\right|$ refer to the (pure)
density matrix representation of the ground state. For any density matrix
$\sigma$ and subregion $X$ of the chain, we let $\sigma_{X}$ refer to
$\text{Tr}_{X^{c}}(\sigma)$, the reduced density matrix of $\sigma$ after
tracing out the complement $X^{c}$ of $X$.

Theorems 1 and 2 will make statements about efficiently approximating the
ground state of such Hamiltonians with matrix product states, and Theorem 3 is
a statement about algorithms that estimate the ground state energy $E$ or
approximate the expectation $\left\langle\psi\right|O\left|\psi\right\rangle$
of a local observable $O$ in the ground state.

###  2.2 Matrix product states and matrix product operators

It is often convenient to describe states with one-dimensional structure using
the language of matrix product states (MPS).

######  Definition 1 (Matrix product state).

A matrix product state (MPS) $\left|\eta\right\rangle$ on $N$ sites of local
dimension $d$ is specified by $Nd$ matrices $A_{j}^{(i)}$ with $i=1,\ldots,d$
and $j=1,\ldots,N$. The matrices $A_{1}^{(i)}$ are $1\times\chi$ matrices and
$A_{N}^{(i)}$ are $\chi\times 1$ matrices, with the rest being
$\chi\times\chi$. The state is defined as

$\left|\eta\right\rangle=\sum_{i_{1}=1}^{d}\ldots\sum_{i_{N}=1}^{d}A_{1}^{(i_{1})}\ldots
A_{N}^{(i_{N})}\left|i_{1}\ldots i_{N}\right\rangle.$ (2)

The parameter $\chi$ is called the bond dimension of the MPS.

The same physical state has many different MPS representations, although one
may impose a canonical form [25] to make the representation unique. The bond
dimension of the MPS is a measure of the maximum amount of entanglement across
any “cut” dividing the state into two contiguous parts. More precisely, if we
perform a Schmidt decomposition on a state $\left|\eta\right\rangle$ across
every possible cut, the maximum number of non-zero Schmidt coefficients (i.e.
Schmidt rank) across any of the cuts is equal to the minimum bond dimension we
would need to exactly represent $\left|\eta\right\rangle$ as an MPS [33]. Thus
to show a state has an MPS representation with a certain bond dimension, it
suffices to bound the Schdmidt rank across all the cuts. This line of
reasoning shows that a product state, which has no entanglement, can be
written as an MPS with bond dimension 1. Meanwhile, a general state with any
amount of entanglement can always be written as an MPS with bond dimension
$d^{N/2}$.

A cousin of matrix product states are matrix product operators (MPO).

######  Definition 2 (Matrix product operator).

A matrix product operator (MPO) $\sigma$ on $N$ sites of local dimension $d$
is specified by $Nd^{2}$ matrices $A_{j}^{(i)}$ with $i=1,\ldots,d^{2}$ and
$j=1,\ldots,N$. The matrices $A_{1}^{(i)}$ are $1\times\chi$ matrices and
$A_{N}^{(i)}$ are $\chi\times 1$ matrices, with the rest being
$\chi\times\chi$. The operator is defined as

$\sigma=\sum_{i_{1}=1}^{d^{2}}\ldots\sum_{i_{N}=1}^{d^{2}}A_{1}^{(i_{1})}\ldots
A_{N}^{(i_{N})}\sigma_{i_{1}}\otimes\ldots\otimes\sigma_{i_{N}},$ (3)

where $\\{\sigma_{i}\\}_{i=1}^{d^{2}}$ is a basis for operators on a single
site. The parameter $\chi$ is called the bond dimension of the MPO.

However, MPO representations have the issue that specifying a set of matrices
$A_{j}^{(i)}$ does not always lead to an operator $\sigma$ that is positive
semi-definite, which is a requirement for the MPO to correspond to a valid
quantum state. Checking positivity of an MPO in general is $\mathsf{NP}$-hard
for chains of length $N$ and undecidable for infinite chains [19].

###  2.3 Notions of approximation

We are interested in the existence of an MPS that approximates the ground
state $\left|\psi\right\rangle$. We will have both a global and a local notion
of approximation, which we define here. We will employ two different distance
measures at different points in our theorems and proofs, the purified distance
[10, 29] and the trace distance.

######  Definition 3 (Purified distance).

If $\sigma$ and $\sigma^{\prime}$ are two normalized states on the same
system, then

$D(\sigma,\sigma^{\prime})=\sqrt{1-\mathcal{F}(\sigma,\sigma^{\prime})^{2}}$
(4)

is the purified distance between $\sigma$ and $\sigma^{\prime}$, where
$\mathcal{F}(\sigma,\sigma^{\prime})=\text{Tr}(\sqrt{\sigma^{1/2}\sigma^{\prime}\sigma^{1/2}})$
denotes the fidelity between $\sigma$ and $\sigma^{\prime}$.

######  Definition 4 (Trace distance).

If $\sigma$ and $\sigma^{\prime}$ are two normalized states on the same
system, then

$D_{1}(\sigma,\sigma^{\prime})=\frac{1}{2}\lVert\sigma-\sigma^{\prime}\rVert_{1}=\frac{1}{2}\text{Tr}(\lvert\sigma-\sigma^{\prime}\rvert)$
(5)

is the trace distance between $\sigma$ and $\sigma^{\prime}$.

######  Lemma 1 ([29]).

$D_{1}(\sigma,\sigma^{\prime})\leq
D(\sigma,\sigma^{\prime})\leq\sqrt{2D_{1}(\sigma,\sigma^{\prime})}.$ (6)

We also note that $D_{1}(\sigma,\sigma^{\prime})=D(\sigma,\sigma^{\prime})$ if
$\sigma$ and $\sigma^{\prime}$ are both pure. If the trace distance between
$\rho$ and $\sigma$ is small then we would say $\sigma$ is a good global
approximation to $\rho$. We are also interested in a notion of distance that
is more local.

######  Definition 5 ($k$-local purified distance).

If $\sigma$ and $\sigma^{\prime}$ are two normalized states on the same
system, then the $k$-local purified distance between $\sigma$ and
$\sigma^{\prime}$ is

$D^{(k)}(\sigma,\sigma^{\prime})=\max_{X:\lvert
X\rvert=k}D(\sigma_{X},\sigma^{\prime}_{X}),$ (7)

where the max is taken over all contiguous regions $X$ consisting of $k$
sites.

######  Definition 6 ($k$-local trace distance).

If $\sigma$ and $\sigma^{\prime}$ are two normalized states on the same
system, then the $k$-local trace distance between $\sigma$ and
$\sigma^{\prime}$ is

$D_{1}^{(k)}(\sigma,\sigma^{\prime}):=\max_{X:\lvert
X\rvert=k}D_{1}(\sigma_{X},\sigma^{\prime}_{X}),$ (8)

where the max is taken over all contiguous regions $X$ consisting of $k$
sites.

Note that these quantities lack the property that
$0=D^{(k)}(\sigma,\sigma^{\prime})=D_{1}^{(k)}(\sigma,\sigma^{\prime})$
implies $\sigma=\sigma^{\prime}$,111To see this consider the simple
counterexample where $k=2$,
$\sigma=\left|\eta\right\rangle\left\langle\eta\right|$,
$\sigma^{\prime}=\left|\nu\right\rangle\left\langle\nu\right|$, with
$\left|\eta\right\rangle=(\left|000\right\rangle+\left|111\right\rangle)/\sqrt{2}$,
$\left|\nu\right\rangle=(\left|000\right\rangle-\left|111\right\rangle)/\sqrt{2}$.
In fact here $\left\langle\nu|\eta\right\rangle=0$. This counterexample can be
generalized to apply for any $k$. but they do satisfy the triangle inequality.
It is also clear that taking $k=N$ recovers our notion of global distance:
$D^{(N)}(\sigma,\sigma^{\prime})=D(\sigma,\sigma^{\prime})$ and
$D_{1}^{(N)}(\sigma,\sigma^{\prime})=D_{1}(\sigma,\sigma^{\prime})$.

######  Definition 7 (Local approximation).

We say a state $\sigma$ on a chain of $N$ sites is a $(k,\epsilon)$-local
approximation to another state $\sigma^{\prime}$ if
$D_{1}^{(k)}\left(\sigma,\sigma^{\prime}\right)\leq\epsilon$.

As we discuss in the next subsection, previous results show that
$\left|\psi\right\rangle$ has a good global approximation
$|\tilde{\psi}\rangle$ that is an MPS with bond dimension that scales like a
polynomial in $N$. We will be interested in the question of what bond
dimension is required when what we seek is merely a good local approximation.

###  2.4 Previous results

####  2.4.1 Exponential decay of correlations and area laws

A key fact shown by Hastings [12] (see also [15, 13, 23] for improvements and
extensions) about nearest-neighbor 1D Hamiltonians with a non-zero energy gap
is that the ground state $\left|\psi\right\rangle$ has exponential decay of
correlations.

######  Definition 8 (Exponential decay of correlations).

A pure state $\sigma=\left|\eta\right\rangle\left\langle\eta\right|$ on a
chain of sites is said to have $(t_{0},\xi)$-exponential decay of correlations
if for every $t\geq t_{0}$ and every pair of regions $A$ and $C$ separated by
at least $t$ sites

$\displaystyle\text{Cor}(A:C)_{\left|\eta\right\rangle}$
$\displaystyle:=\max_{\lVert M\rVert,\lVert N\rVert\leq
1}\text{Tr}\left((M\otimes N)(\sigma_{AC}-\sigma_{A}\otimes\sigma_{C})\right)$
$\displaystyle\leq\exp(-t/\xi).$ (9)

The smallest $\xi$ for which $\sigma$ has $(t_{0},\xi)$-exponential decay of
correlations for some $t_{0}$ is called the correlation length of $\sigma$.

######  Lemma 2.

If $\left|\psi\right\rangle$ is the unique ground state of a Hamiltonian
$H=\sum_{i}H_{i,i+1}$ with spectral gap $\Delta$, then
$\left|\psi\right\rangle$ has $(t_{0},\xi)$-exponential decay of correlations
for some $t_{0}=O(1)$ and $\xi=O(1/\Delta)$.

###### Proof.

This statement is implied by Theorem 4.1 of [23]. ∎

While the exponential decay of correlations holds for lattice models in any
spatial dimension, the other results we discuss are only known to hold in one
dimension.

For example, in one dimension it has been shown that ground states of gapped
Hamiltonians obey an area law, that is, the entanglement entropy of any
contiguous region is bounded by a constant times the length of the boundary of
that region, which in one dimension is just a constant. This statement was
also first proven by Hastings in [14] where it was shown that for any
contiguous region $X$

$S(\rho_{X})\leq\exp(O(\log(d)/\Delta)),$ (10)

which is independent of the number of sites in $X$, where $S$ denotes the von
Neumann entropy $S(\sigma)=-\text{Tr}(\sigma\log\sigma)$. The area law has
since been improved [1, 2] to

$S(\rho_{X})\leq\tilde{O}(\log^{3}(d)/\Delta),$ (11)

where the $\tilde{O}$ signifies a suppression of factors that scale
logarithmically with the quantity stated.

It was also discovered that an area law follows merely from the assumption of
exponential decay of correlations in one dimension: if a pure state $\rho$ has
$(t_{0},\xi)$-exponential decay of correlations, then it satisfies [5]

$S(\rho_{X})\leq t_{0}\exp(\tilde{O}(\xi\log(d))).$ (12)

####  2.4.2 Efficient global MPS approximations

The area law is closely related to the existence of an efficient MPS
approximation to the ground state. To make this implication concrete, one
needs an area law using the $\alpha$-Renyi entropy for some value of $\alpha$
with $0<\alpha<1$ [32], where the Renyi entropy is given by
$S_{\alpha}(\rho_{X})=-\text{Tr}(\log(\rho_{X}^{\alpha}))/(1-\alpha)$. An area
law for the von Neumann entropy (corresponding to $\alpha=1$) is not alone
sufficient [28]. However, for all of the area laws mentioned above, the
techniques used are strong enough to also imply the existence of efficient MPS
approximations, and, moreover, area laws have indeed been shown for the
$\alpha$-Renyi entropy [16] with $0<\alpha<1$.

Hastings’ [14] original area law implied the existence of a global
$\epsilon$-approximation $|\tilde{\psi}\rangle$ for $\left|\psi\right\rangle$
with bond dimension

$\chi=e^{\tilde{O}\left(\frac{\log(d)}{\Delta}\right)}\left(\frac{N}{\epsilon}\right)^{O\left(\frac{\log(d)}{\Delta}\right)}.$
(13)

The improved area law in [1, 2] yields a better scaling for $\chi$ which is
asymptotically sublinear in $N$:

$\chi=e^{\tilde{O}\left(\frac{\log^{3}(d)}{\Delta}\right)}\left(\frac{N}{\epsilon}\right)^{\tilde{O}\left(\frac{\log(d)}{(\Delta\log(N/\epsilon))^{1/4}}\right)}.$
(14)

Finally, the result implied only from exponential decay of correlations [5] is

$\chi=e^{t_{0}e^{\tilde{O}\left(\xi\log(d)\right)}}\left(\frac{N}{\epsilon}\right)^{\tilde{O}\left(\xi\log(d)\right)}.$
(15)

Crucially, if the local Hilbert space dimension $d$ and the gap $\Delta$ (or
alternatively, the correlation length $\xi$) are taken to be constant, then
all three results read $\chi=\text{poly}(N,1/\epsilon)$.

####  2.4.3 Existence of MPS approximations in the thermodynamic limit

The aforementioned results, which describe explicit bounds on the bond
dimension needed for good MPS approximations, improved upon important prior
work that characterized which states can be approximated by MPS in the first
place. Of course, any state on a finite chain can be exactly described by an
MPS, but the question of states living on the infinite chain is more subtle.
In [9], the proper mathematical framework was developed to study MPS, which
they call finitely correlated states, in the limit of infinite system size,
and in [8] it was shown that any translationally invariant state on the
infinite chain can be approximated arbitrarily well by a uniform
(translationally invariant) MPS in the following sense: for any
translationally invariant pure state $\rho$ there exists a net — a
generalization of a sequence — of translationally invariant MPS
$\rho_{\alpha}$ for which the expectation value $\text{Tr}(\rho_{\alpha}A)$ of
any finitely supported observable $A$ converges to $\text{Tr}(\rho A)$. An
implication of this is that if we restrict to observables $A$ with support on
only $k$ contiguous sites, there exists a translationally invariant MPS that
approximates the expectation value of all $A$ to arbitrarily small error
$\epsilon$. Thus, they established that local approximations for
translationally invariant states exist within the set of translationally
invariant MPS, but provided no discussion of the bond dimension required for
such an approximation, and did not explicitly consider the case where the
state is the ground state of a gapped, local Hamiltonian.

Our Theorem 1, which is stated in the following section, may be viewed as a
generalization and improvement on this work in several senses. Most
importantly, we present a construction for which a bound on the bond dimension
can be explicitly obtained. This bound scales like $\text{poly}(k,1/\epsilon)$
when the state is a ground state of a gapped nearest-neighbor Hamiltonian, and
exponentially in $k/\epsilon$ when it is a general state. Furthermore, our
method works for states on the finite chain that are not translationally
invariant, where it becomes unclear how the methods of this previous work
would generalize.

####  2.4.4 Constant-bond-dimension MPO local approximations

The problem of finding matrix product operator representations that capture
all the local properties of a state has been studied before. Huang [17] showed
the existence of a positive semi-definite MPO $\rho^{\chi}$ with bond
dimension

$\chi=e^{\tilde{O}\left(\frac{\log^{3}(d)}{\Delta}+\frac{\log(d)\log^{3/4}(1/\epsilon)}{\Delta^{1/4}}\right)}=(1/\epsilon)^{o(1)}$
(16)

that is a $(2,\epsilon)$-local approximation to the true ground state $\rho$,
where $o(1)$ indicates the quantity approaches 0 as
$1/\epsilon\rightarrow\infty$. Crucially, this is independent of the length of
the chain $N$. Additionally, because the Hamiltonian is nearest-neighbor, we
have $\text{Tr}(H\rho^{\chi})-\text{Tr}(H\rho)\leq(N-1)\epsilon$, i.e., the
energy per site (energy density) of the state $\rho^{\chi}$ is within
$\epsilon$ of the ground state energy density. Huang constructs this MPO
explicitly and notes it is a convex combination over pure states which
themselves are MPS with bond dimension independent of $N$. Thus, one of these
MPS must have energy density within $\epsilon$ of the ground state energy
density. However, it is not guaranteed (nor is it likely) that one of these
constant-bond-dimension MPS is also a good local approximation to the ground
state; thus our result may be viewed as an improvement on this front as we
show the existence not only of a low-energy-density constant-bond-dimension
MPS, but also one that is a good local approximation to the ground state.

An alternative MPO construction achieving the same task was later given in
[27]. In this case, the MPO is a $(k,\epsilon)$-local approximation to the
ground state and has bond dimension

$\chi=(k/\epsilon)e^{\tilde{O}\left(\frac{\log^{3}(d)}{\Delta}+\frac{\log(d)\log^{3/4}(k/\epsilon^{3})}{\Delta^{1/4}}\right)}=(k/\epsilon)^{1+o(1)}.$
(17)

The idea they use is simple. They break the chain into blocks of size $l$,
which is much larger than $k$. On each block they construct a constant bond
dimension MPO that closely approximates the reduced density matrix of the
ground state on that block, which is easy since each block has constant length
and they must make only a constant number of bond truncations to the exact
state. The tensor product of these MPO will be an MPO on the whole chain that
is a good approximation on any length-$k$ region that falls within one of the
larger length $l$ blocks, but not on a region that crosses the boundary
between blocks. To remedy this, they take the mixture of MPO formed by
considering all $l$ translations of the boundaries between the blocks. Now as
long as $l$ is much larger than $k$, any region of length $k$ will only span
the boundary between blocks for a small fraction of the MPO that make up this
mixture, and the MPO will be a good local approximation.

This same idea underlies our proof of Theorem 1, with the complication that we
seek a pure state approximation and cannot take a mixture of several MPS.
Instead, we combine the translated MPS in superposition, which brings new but
manageable challenges.

##  3 Statement of results

###  3.1 Existence of local approximation

######  Theorem 1.

Let $\left|\psi\right\rangle$ be a state on a chain of $N$ sites of local
dimension $d$. For any $k$ and $\epsilon$ there exists an MPS
$|\tilde{\psi}\rangle$ with bond dimension at most $\chi$ such that

  1. (1)

$|\tilde{\psi}\rangle$ is a $(k,\epsilon)$-local approximation to
$\left|\psi\right\rangle$

  2. (2)

$\chi=e^{O(k\log(d)/\epsilon)}$

provided that $N$ is larger than some constant $N_{0}=O(k^{3}/\epsilon^{3})$
that is independent of $\left|\psi\right\rangle$.

If $\left|\psi\right\rangle$ has $(t_{0},\xi)$-exponential decay of
correlations, then the bound on the bond dimension can be improved to

  1. (2’)

$\chi=e^{t_{0}e^{\tilde{O}\left(\xi\log(d)\right)}}(k/\epsilon^{3})^{O\left(\xi\log(d)\right)}$

with $N_{0}=O(k^{2}/\epsilon^{2})+t_{0}\exp(\tilde{O}(\xi\log(d))$ and if,
additionally, $\left|\psi\right\rangle$ is the unique ground state of a
nearest-neighbor 1D Hamiltonian $H$ with spectral gap $\Delta$, it can be
further improved to

  1. (2”)

$\chi=(k/\epsilon)e^{\tilde{O}\left(\frac{\log^{3}(d)}{\Delta}+\frac{\log(d)}{\Delta^{1/4}}\log^{3/4}(k/\epsilon^{3})\right)}$

with $N_{0}=O(k^{2}/\epsilon^{2})+\tilde{O}(\log(d)/\Delta^{3/4})$. Here
$\chi$ is asymptotically equivalent to $(k/\epsilon)^{1+o(1)}$ where $o(1)$
indicates that the quantity approaches 0 as $(k/\epsilon)\rightarrow\infty$.

However, the state $|\tilde{\psi}\rangle$ that we construct in the proof of
Theorem 1 is long-range correlated and cannot be generated from a constant-
depth quantum circuit. Thus, while $|\tilde{\psi}\rangle$ is a good local
approximation to the ground state $\left|\psi\right\rangle$ of $H$, it is not
the exact ground state of any gapped local 1D Hamiltonian.

Next, we show that it remains possible to approximate the state even when we
require the approximation to be produced by a constant-depth quantum circuit;
the scaling of the bond dimension is faster in $k$ and $1/\epsilon$, but it is
still polynomial.

######  Theorem 2.

Let $\left|\psi\right\rangle$ be a state on a chain of $N$ sites of local
dimension $d$. If $\left|\psi\right\rangle$ has $(t_{0},\xi)$-exponential
decay of correlations, then, for any $k$ and $\epsilon$, there is an MPS
$|\tilde{\psi}\rangle$ with bond dimension at most $\chi$ such that

  1. (1)

$|\tilde{\psi}\rangle$ is a $(k,\epsilon)$-local approximation to
$\left|\psi\right\rangle$

  2. (2)

$\chi=e^{t_{0}e^{\tilde{O}\left(\xi\log(d)\right)}}\left(k/\epsilon^{2}\right)^{O\left(\xi^{2}\log^{2}(d)\right)}$

  3. (3)

$|\tilde{\psi}\rangle$ can be prepared from the state
$\left|0\right\rangle^{\otimes N}$ by a quantum circuit that has depth
$\tilde{O}(\chi^{2})$ and consists only of unitary gates acting on neighboring
pairs of qubits

If, additionally, $\left|\psi\right\rangle$ is the unique ground state of a
nearest-neighbor 1D Hamiltonian with spectral gap $\Delta$, then the bound on
the bond dimension can be improved to

  1. (2’)

$\chi=e^{\tilde{O}\left(\frac{\log^{4}(d)}{\Delta^{2}}\right)}\left(k/\epsilon^{2}\right)^{O\left(\frac{\log(d)}{\Delta}\right)}$

The sort of constant-depth quantum circuit that can generate the state
$|\tilde{\psi}\rangle$ in Theorem 2 is shown in Figure 1. Proof summaries as
well as full proofs of Theorems 1 and 2 appear in Section 4.

We also note that, unlike Theorem 1, Theorem 2 does not require that the chain
be longer than some threshold $N_{0}$; the statement holds regardless of the
chain length, although this should be considered a technical detail and not an
essential aspect of the constructions.

Figure 1:  Constant-depth quantum circuit that constructs the
$(k,\epsilon)$-local approximation $|\tilde{\psi}\rangle$ in Theorem 2
starting from the initial state $\left|0\right\rangle^{\otimes N}$. It is
drawn here as a depth-2 circuit where unitaries $U_{j}$ act on segments
consisting of $O(\xi^{2}\log(d)\log(k/{\epsilon^{2}}))$ contiguous sites. Each
of these unitaries could themselves be decomposed into a sequence of nearest-
neighbor gates with depth $\text{poly}(k,1/\epsilon)$.

###  3.2 Reduction from estimating energy density to finding local properties

The previously stated results show that there exists a state that is both a
$(k,\epsilon)$-local approximation and an MPS with bond dimension
$\text{poly}(k,1/\epsilon)$. They say nothing of the algorithmic complexity
required to find a $(k,\epsilon)$-local approximation. The proofs describe how
to construct the local approximation from a description of the exact ground
state, but following this strategy would require first finding a description
of the exact ground state (or perhaps a global approximation to it). One might
hope that a different strategy would allow the local approximation to be found
much more quickly than the global approximation, since the bond dimension
needed to represent the approximation is much smaller. However, the following
result challenges the validity of this intuition, at least in the case that
the Hamiltonian is translationally invariant, by showing a relationship
between the problem of finding a local approximation and the problem of
estimating the energy density.

######  Problem 1 (Estimating energy density).

Given a nearest-neighbor translationally invariant 1D Hamiltonian $H$ on
$N\geq 2$ sites and error parameter $\epsilon$, produce an estimate
$\tilde{u}$ such that $\lvert u-\tilde{u}\rvert\leq\epsilon$ where $u=E/(N-1)$
is the ground state energy density.

######  Problem 2 (Approximating local properties).

Given a nearest-neighbor translationally invariant Hamiltonian $H$, an error
parameter $\delta$, and an operator $O$ whose support is contained within a
contiguous region of length $k$, produce an estimate $\tilde{v}$ such that
$\lvert v-\tilde{v}\rvert\leq\delta$, where
$v=\left\langle\psi\right|O\left|\psi\right\rangle/\lVert O\rVert$ is the
expectation value of the operator $O/\lVert O\rVert$ in the ground state
$\left|\psi\right\rangle$ of $H$.

Problem 1 is the restriction of Problem 2 to the case where $k=2$ and the
operator $O$ is the energy interaction term. Thus, there is a trivial
reduction from Problem 1 to Problem 2 with $\delta=\epsilon$. However, the
next theorem, whose proof is presented in Section 4, states a much more
powerful reduction.

######  Theorem 3.

Suppose one has an algorithm that solves Problem 2 for any single-site ($k=1$)
operator $O$ and $\delta=0.9$ in $f(\Delta,d,N)$ time, under the promise that
the Hamiltonian $H$ has spectral gap at least $\Delta$. Here $d$ denotes the
local dimension of $H$ and $N$ the length of the chain. Then there is an
algorithm for Problem 1 under the same promise that runs in time

$f\left(\frac{\min(2\Delta,(N-1)\epsilon,2)}{12},2d,N\right)O(\log(1/\epsilon)).$
(18)

Estimating the energy density to precision $\epsilon$ is equivalent to
measuring the total energy to precision $\epsilon(N-1)$, so the quantity
$\min(2\Delta,(N-1)\epsilon,2)$ is equivalent to the global energy resolution,
twice the gap, or two, whichever is smallest. Thus, one may take
$\epsilon=O(1/N)$ and understand the theorem as stating that finding local
properties to within $O(1)$ precision can be done at most $O(\log(N))$ faster
than finding an estimate to the total ground state energy to $O(1)$ precision.
If local properties can be found in time independent of $N$ (i.e. there is an
$N$-independent upper bound to $f$), then the ground state energy can be
estimated to $O(1)$ precision in time $O(\log(N))$, which would be optimal
since the ground state energy scales extensively with $N$, and
$\Omega(\log(N))$ time would be needed simply to write down the output.

Another way of understanding the significance of the theorem is in the
thermodynamic limit. Here it states that if one could estimate expectation
values of local observables in the thermodynamic limit to $O(1)$ precision in
some finite amount of time (for constant $\Delta$ and $d$), then one could
compute the ground state energy density of such Hamiltonians to precision
$\epsilon$ in $O(\log(1/\epsilon))$ time. This would be an exponential speedup
over the best-known algorithm for computing the energy density given in [17],
which has runtime $\text{poly}(1/\epsilon)$. Taking the contrapositive, if one
could show that $\text{poly}(1/\epsilon)$ time is necessary for computing the
energy density, this would imply that Problem 2 with $\delta=O(1)$ is in
general uncomputable in the thermodynamic limit, even given the promise that
the input Hamiltonian is gapped. It is already known that Problem 2 is
uncomputable when there is no such promise [3].

It is not clear whether a $O(\log(1/\epsilon))$ time algorithm for computing
the energy density is possible. The $\text{poly}(1/\epsilon)$ algorithm in
[17] works even when the Hamiltonian is not translationally invariant, but it
is not immediately apparent to us how one might exploit translational
invariance to yield an exponential speedup.

##  4 Proofs

###  4.1 Important lemmas for Theorems 1 and 2

The pair of lemmas stated here are utilized in both Theorem 1 and Theorem 2.
The first lemma captures the essence of the area laws stated previously, and
will be essential when we want to bound the error incurred by truncating a
state along a certain cut.

######  Lemma 3 (Area laws [5], [1]).

If $\sigma=\left|\psi\right\rangle\left\langle\psi\right|$ has
$(t_{0},\xi)$-exponential decay of correlations then for any $\chi$ and any
region of the chain $A$, there is a state $\tilde{\sigma}_{A}$ with rank at
most $\chi$ such that

$D(\sigma_{A},\tilde{\sigma}_{A})\leq
C_{1}\exp\left(-\frac{\log(\chi)}{8\xi\log(d)}\right),$ (19)

where $C_{1}=\exp(t_{0}\exp(\tilde{O}(\xi\log(d))))$ is a constant independent
of $N$.

If $\sigma$ is the unique ground state of a nearest-neighbor Hamiltonian with
spectral gap $\Delta$, then this can be improved to

$D(\sigma_{A},\tilde{\sigma}_{A})\leq
C_{2}\exp\left(-\tilde{O}\left(\frac{\Delta^{1/3}\log^{4/3}(\chi)}{\log^{4/3}(d)}\right)\right),$
(20)

where $C_{2}=\exp(\tilde{O}(\log^{8/3}(d)/\Delta))$.

###### Proof.

The first part follows from the main theorem of [5]. The second follows from
the 1D area law presented in [1], and $\log(d)$ dependence explicitly stated
in [2]. ∎

In both proofs we will also utilize the well-known fact that Schmidt ranks
cannot differ by more than a factor of $d$ between any two neighboring cuts on
the chain.

######  Lemma 4.

Any state $\sigma_{AB}$ on a bipartite system $AB$ satisfies the following
relations.

$\displaystyle\text{rank}(\sigma_{AB})\text{rank}(\sigma_{B})$
$\displaystyle\geq\text{rank}(\sigma_{A})$ (21)
$\displaystyle\text{rank}(\sigma_{AB})\text{rank}(\sigma_{A})$
$\displaystyle\geq\text{rank}(\sigma_{B})$ (22)
$\displaystyle\text{rank}(\sigma_{A})\text{rank}(\sigma_{B})$
$\displaystyle\geq\text{rank}(\sigma_{AB})$ (23)

###### Proof.

We can purify $\sigma_{AB}$ with an auxiliary system $C$ into the state
$\left|\eta\right\rangle$. We can let
$\sigma=\left|\eta\right\rangle\left\langle\eta\right|$ and note that
$\text{rank}(\sigma_{AB})=\text{rank}(\sigma_{C})$. Thus each of these three
equations say the same thing with permutations of $A$, $B$, and $C$. We will
show the first equation. Write Schmidt decomposition

$\left|\eta\right\rangle=\sum_{j=1}^{\text{rank}(\sigma_{AB})}\lambda_{j}\left|\nu_{j}\right\rangle_{AB}\otimes\left|\omega_{j}\right\rangle_{C}$
(24)

and then decompose $\left|\nu_{j}\right\rangle$ to find

$\left|\eta\right\rangle=\sum_{j=1}^{\text{rank}(\sigma_{AB})}\sum_{k=1}^{\text{rank}(\sigma_{B})}\lambda_{j}\gamma_{jk}\left|\tau_{jk}\right\rangle_{A}\otimes\left|\mu_{k}\right\rangle_{B}\otimes\left|\omega_{j}\right\rangle_{C},$
(25)

where $\\{\left|\mu_{k}\right\rangle\\}_{k=1}^{\text{rank}(\sigma_{B})}$ are
the eigenvectors of $\sigma_{B}$. This shows that the support of $\sigma_{A}$
is spanned by the set of $\left|\tau_{jk}\right\rangle$ and thus its rank can
be at most $\text{rank}(\sigma_{AB})\text{rank}(\sigma_{B})$. ∎

######  Corollary 1.

If $\left|\eta\right\rangle$ is a state on a chain of $N$ sites with local
dimension $d$, and the Schmidt rank of $\left|\eta\right\rangle$ across the
cut between sites $m$ and $m+1$ is $\chi$, then the Schmidt rank of
$\left|\eta\right\rangle$ across the cut between sites $m^{\prime}$ and
$m^{\prime}+1$ is at most $\chi d^{\lvert m-m^{\prime}\rvert}$.

###### Proof.

Without loss of generality, assume $m\leq m^{\prime}$. The reduced density
matrix of $\left|\eta\right\rangle\left\langle\eta\right|$ on sites
$[m+1,m^{\prime}]$ has rank at most $d^{\lvert m^{\prime}-m\rvert}$ since this
is the dimension of the entire Hilbert space on that subsystem. Meanwhile the
rank of the reduced density matrix on sites $[1,m]$ is $\chi$. So by the
previous lemma, the rank over sites $[1,m^{\prime}]$ is at most $\chi
d^{\lvert m^{\prime}-m\rvert}$. ∎

###  4.2 Proof of Theorem 1

First we state and prove a lemma that will be essential for showing the first
part of Theorem 1. Then we provide a proof summary of Theorem 1, followed by
its full proof.

######  Lemma 5.

Given two quantum systems $A$ and $B$ and states $\tau_{A}$ on $A$ and
$\tau_{B}$ on $B$, there exists a state $\sigma_{AB}$ on the joint system $AB$
such that $\sigma_{A}=\tau_{A}$, $\sigma_{B}=\tau_{B}$, and
$\text{rank}(\sigma_{AB})\leq\max(\text{rank}(\tau_{A}),\text{rank}(\tau_{B}))$.

###### Proof.

We’ll apply an iterative procedure. For round 1 let $\alpha_{1}=\tau_{A}$ and
$\beta_{1}=\tau_{B}$. In round $j$ write spectral decomposition

$\displaystyle\alpha_{j}$
$\displaystyle=\sum_{i=1}^{a_{j}}\lambda_{j,i}\left|s_{j,i}\right\rangle\left\langle
s_{j,i}\right|_{A}$ (26) $\displaystyle\beta_{j}$
$\displaystyle=\sum_{i=1}^{b_{j}}\mu_{j,i}\left|r_{j,i}\right\rangle\left\langle
r_{j,i}\right|_{B},$ (27)

where $a_{j}$ and $b_{j}$ are the ranks of states $\alpha_{j}$ and
$\beta_{j}$, eigenvectors $\\{s_{j,i}\\}_{i=1}^{a_{j}}$ and
$\\{r_{j,i}\\}_{i=1}^{b_{j}}$ form orthonormal bases of the Hilbert spaces of
systems $A$ and $B$, respectively, and eigenvalues
$\\{\lambda_{j,i}\\}_{i=1}^{a_{j}}$ and $\\{\mu_{j,i}\\}_{i=1}^{b_{j}}$ are
non-decreasing with increasing index $i$ (i.e. smallest eigenvalues first).
Then define

$\left|u_{j}\right\rangle=\sum_{i=1}^{\min(a_{j},b_{j})}\sqrt{\min(\lambda_{j,i},\mu_{j,i})}\left|s_{j,i}\right\rangle_{A}\otimes\left|r_{j,i}\right\rangle_{B},$
(28)

which may not be a normalized state. Define recursion relation

$\displaystyle\alpha_{j+1}$
$\displaystyle=\alpha_{j}-\text{Tr}_{B}(\left|u_{j}\right\rangle\left\langle
u_{j}\right|)$ $\displaystyle\beta_{j+1}$
$\displaystyle=\beta_{j}-\text{Tr}_{A}(\left|u_{j}\right\rangle\left\langle
u_{j}\right|)$ (29)

and repeat until round $m$ when $\alpha_{m+1}=\beta_{m+1}=0$. Let

$\sigma_{AB}=\sum_{j=1}^{m}\left|u_{j}\right\rangle\left\langle u_{j}\right|.$
(30)

Clearly $\text{rank}(\sigma_{AB})\leq m$. We claim that
$m\leq\max(\text{rank}(\tau_{A}),\text{rank}(\tau_{B}))$. To show this we note
that

$a_{j+1}+b_{j+1}\leq\max(a_{j},b_{j}).$ (31)

We can see this is true by inspecting the $i$th term in the Schmidt
decomposition of $\left|u_{j}\right\rangle$ in Eq. (28), and noting that
either its reduced density matrix on system $A$ is
$\lambda_{j,i}\left|s_{j,i}\right\rangle\left\langle s_{j,i}\right|$ or its
reduced density matrix on system $B$ is
$\mu_{j,i}\left|r_{j,i}\right\rangle\left\langle r_{j,i}\right|$ (or both). So
when the reduced density matrices of $\left|u_{j}\right\rangle\left\langle
u_{j}\right|$ are subtracted from $\alpha_{j}$ and $\beta_{j}$ to form
$\alpha_{j+1}$ and $\beta_{j+1}$ in Eqs. (29), each of the $\min(a_{j},b_{j})$
terms causes the combined rank $a_{j+1}+b_{j+1}$ to decrease by at least one
in comparison to $a_{j}+b_{j}$.

This alone implies that $m\leq\max(a_{1},b_{1})+1$, since by Eq. (31), the
sequence $\\{a_{j}+b_{j}\\}_{j}$ must decrease by at least $\min(a_{1},b_{1})$
after the first round, and then by at least $1$ in every other round, reaching
0 when $j=\max(a_{1},b_{1})+1$. However, we can also see that the last round
must see a decrease by at least 2, because it is impossible for $a_{m}=0$ and
$b_{m}=1$ or vice versa (since $\text{Tr}(\alpha_{j})$ must equal
$\text{Tr}(\beta_{j})$ for all $j$). Thus $m\leq\max(a_{1},b_{1})$.

Moreover, Eqs. (29) and (30) imply that $\sigma_{A}=\alpha_{1}=\tau_{A}$ and
$\sigma_{B}=\beta_{1}=\tau_{B}$. ∎

Figure 2: Schematic overview of the proof of Theorem 1. Many states
$\left|\phi_{j}\right\rangle$ are constructed with staggered divisions between
regions $M_{j,i}$ of length $l$, then the $\left|\phi_{j}\right\rangle$ are
summed in superposition. Properties supported within a length-$k$ region $X$
are faithfully captured by $\left|\phi_{j}\right\rangle$ for values of $j$
such that $X$ does not overlap the boundaries between regions $M_{j,i}$. Most
values of $j$ qualify under this criteria as long as $l$ is much larger than
$k$. Additional structure is defined (the regions $B_{j,j^{\prime}}$ in Part
1, and $B_{j,i}$ in Part 2) in order to force
$\left\langle\phi_{j}|\phi_{j^{\prime}}\right\rangle=\delta_{jj^{\prime}}$,
but this structure is not reflected on the schematic.

###### Proof summary of Theorem 1.

In Ref. [27], an MPO that is a $(k,\epsilon)$-local approximation to a given
state $\left|\psi\right\rangle$ was formed by dividing the chain into many
length-$l$ segments, tensoring together a low-bond-dimension approximation of
the exact state reduced to each segment, and then summing over (as a mixture)
translations of locations for the divisions between the segments. We follow
the same idea but for pure states: for each integer $j=0,\ldots,l-1$, we
divide the state into many length-$l$ segments and create a pure state
approximation $\left|\phi_{j}\right\rangle$ that captures any local properties
that are supported entirely within one of the segments. Then to form
$|\tilde{\psi}\rangle$, we sum in superposition over all the
$\left|\phi_{j}\right\rangle$, where each $\left|\phi_{j}\right\rangle$ has
boundaries between segments occurring in different places (see Figure 2).
Thus, for any length-$k$ region $X$, a large fraction of the terms
$\left|\phi_{j}\right\rangle$ in the superposition are individually good
approximations on region $X$. The fact that a small fraction of the terms are
not necessarily a good approximation creates additional, but small, error in
the local approximation.

In order to avoid interaction between different terms in the superposition, we
add additional structure to make the $\left|\phi_{j}\right\rangle$ in the
superposition exactly orthogonal to one another. In our construction for
general states, this additional structure consists of a set of disjoint,
sparsely distributed, single-site regions $B_{j,j^{\prime}}$, one for each
pair of integers $j\neq j^{\prime}$ with $0\leq j,j^{\prime}<l$. We force
$\left|\phi_{j}\right\rangle$ to be the pure state $\left|0\right\rangle$ and
$\left|\phi_{j^{\prime}}\right\rangle$ to be $\left|1\right\rangle$ when
reduced to $B_{j,j^{\prime}}$ to guarantee that
$\left\langle\phi_{j}|\phi_{j^{\prime}}\right\rangle=0$. Our construction for
states that have exponential decay of correlations is similar: we define a
series of regions $B_{j,i}$ and for each pair $(j,j^{\prime})$ force
$\left|\phi_{j}\right\rangle$ and $\left|\phi_{j^{\prime}}\right\rangle$ to
have orthogonal supports when reduced to one of these regions.

Our approach for constructing $\left|\phi_{j}\right\rangle$ differs if
$\left|\psi\right\rangle$ is a general state (Part 1), or if it is a state
that either has exponentially decaying correlations or (additionally) is the
ground state of a nearest-neighbor Hamiltonian (Part 2). In the latter case,
we examine each length-$l$ segment individually and truncate the bonds of the
exact state on all but a few of the rightmost sites within that segment. The
area law implies these truncations have minimal effect. We use those few
rightmost sites to purify the mixed state on the rest of the segment. Then
$\left|\phi_{j}\right\rangle$ is a tensor product over pure states on each of
the segments. The bond dimension can be bounded within each segment of
$\left|\phi_{j}\right\rangle$ which is sufficient to bound the bond dimension
of $|\tilde{\psi}\rangle$.

This does not work for general states because without an area law, bond
truncations result in too much error, and without the truncations we do not
have enough room to purify the state. For a general state, there is simply too
much entropy in the length-$l$ segment to fully absorb with only a few sites
at the edge of the segment. Instead, we have the various segments absorb each
other’s entropy by developing a procedure to engineer entanglement between
different length-$l$ segments that exactly preserves the reduced density
matrix on each segment and keeps the Schmidt rank constant (albeit exponential
in $k/\epsilon$) across any cut. The crux of this procedure is captured in
Lemma 5. ∎

###### Proof of Theorem 1.

Part 1: Items (1) and (2)
First we consider the case of a general state $\left|\psi\right\rangle$ and
construct an approximation $|\tilde{\psi}\rangle$ satisfying items (1) and
(2). A different construction is given in Part 2 to show items (2’) and (2”),
but it is similar in approach. Throughout this proof, we use a convention
where sites are numbered $0$ to $N-1$, which differs from the rest of the
paper.

We choose integer $l$ to be specified later. We require $l>k$. To construct
$|\tilde{\psi}\rangle$, we will first construct states
$\left|\phi_{j}\right\rangle$ for $j=0,\ldots,l-1$ and then sum these states
in superposition. Any reference to the index $j$ will be taken mod $l$.
Consider a fixed value of $j$. To construct $\left|\phi_{j}\right\rangle$ we
break the chain into $n=\lfloor N/l\rfloor$ blocks where $n-1$ blocks
$\\{M_{j,i}\\}_{i=1}^{n-1}$ have length exactly $l$ and the final block
$M_{j,0}$ has length at least $l$ and less than $2l$. We arrange the blocks so
that the leftmost site of block $M_{j,1}$ is site $j$; thus block $M_{j,i}$
contains the sites $[j+l(i-1),j+li-1]$ for $i=1,\ldots,n-1$, and the last
block $M_{j,0}$ “rolls over” to include sites at both ends of the chain: sites
$[j+l(n-1),N-1]$ and $[0,j-1]$. A schematic of the arrangement is shown in
Figure 2. Any reference to the index $i$ will be taken mod $n$.

We also define $l^{2}-l$ single-site blocks on the chain which we label
$B_{j,j^{\prime}}$ for all pairs $j\neq j^{\prime}$. $B_{j,j^{\prime}}$
consists of the site with index $3l^{2}(j+j^{\prime})+l(j-j^{\prime})+2l^{2}$.
This definition is possible as long as their are sufficiently many sites:
$N\geq N_{0}=O(l^{3})$. It can be verified that since $0\leq j,j^{\prime}\leq
l-1$, the distance between any $B_{j,j^{\prime}}$ and
$B_{j^{\prime\prime},j^{\prime\prime\prime}}$ for any distinct pairs
$(j,j^{\prime})$ and $(j^{\prime\prime},j^{\prime\prime\prime})$ is at least
$l$. For each $j$, let $B_{j}=\cup_{j^{\prime}\neq j}B_{j,j^{\prime}}\cup
B_{j^{\prime},j}$. For each $j,i$, let $A_{j,i}=M_{j,i}\setminus M_{j,i}\cap
B_{j}$. Thus, in most cases $A_{j,i}=M_{j,i}$ since $B_{j}$ is a relatively
small set of sites. Let $A_{j}=\cup_{i=0}^{n-1}A_{j,i}$ = $B_{j}^{c}$, the
complement of $B_{j}$.

The state $\left|\phi_{j}\right\rangle$ will have the form

$\left|\phi_{j}\right\rangle=\left|Q_{j}\right\rangle_{A_{j}}\otimes\bigotimes_{j^{\prime}\neq
j}\left(\left|0\right\rangle_{B_{j,j^{\prime}}}\otimes\left|1\right\rangle_{B_{j^{\prime},j}}\right),$
(32)

where $\left|0\right\rangle$ and $\left|1\right\rangle$ are two of the $d$
computational basis states located on a single site. In other words
$\left|\phi_{j}\right\rangle$ is a product state over all single site regions
$B_{j,j^{\prime}}$ with some other (yet to be specified) state
$\left|Q_{j}\right\rangle$ on the remainder of the chain $A_{j}$.

To construct $\left|Q_{j}\right\rangle$, we apply Lemma 5 iteratively as
follows. We let $\sigma_{1}=\rho_{A_{j,j+2}}$ (the reduced matrix of the exact
state $\rho$ on region $A_{j,j+2}$). We combine $\sigma_{1}$ with
$\rho_{A_{j,j+3}}$ using Lemma 5 to form a state $\sigma_{2}$ on region
$A_{j,j+2}A_{j,j+3}$ such that
$\text{rank}(\sigma_{2})\leq\max(\text{rank}(\sigma_{1}),\text{rank}(\rho_{A_{j,j+3}}))$.
For any $j,i$, the rank of the state on any region $A_{j,i}$ is less than
$d^{2l}$ since any region contains at most $2l$ sites. So if we apply this
process iteratively, forming $\sigma_{p+1}$ by combining $\sigma_{p}$ and the
state on region $A_{j,j+p+2}$ ($j+p+2$ is taken mod $n$), then we end up with
a state $\sigma_{n-2}$ with rank at most $d^{2l}$ defined over all of $A_{j}$
except $A_{j,j}$ and $A_{j,j+1}$. Since by construction $B_{j}$ contains no
sites with index smaller than $2l^{2}$ and $A_{j,j}$ and $A_{j,j+1}$ are
contained within the first $2l^{2}$ sites, we have $A_{j,j}=M_{j,j}$ and
$A_{j,j+1}=M_{j,j+1}$ meaning each of these two regions each contain $l$ sites
and the total dimension of the Hilbert space over $A_{j,j}A_{j,j+1}$ is at
least $d^{2l}$. Thus we may use regions $A_{j,j}$ and $A_{j,j+1}$ to purify
the state $\sigma_{n-2}$. We let $\left|Q_{j}\right\rangle$ be any such
purification.

The key observation is that the state $\left|\phi_{j}\right\rangle$, as
defined by Eq. (32), will get any local properties exactly correct as long as
they are supported entirely within a segment $A_{j,i}$ for some $i\neq j,j+1$.
As long as $l$ is large, this will be the case for most length-$k$ regions,
but it will not be the case for some regions that cross the boundaries between
regions $A_{j,i}$ or for regions that contain one of the single site regions
$B_{j,j^{\prime}}$ or $B_{j^{\prime},j}$.

To fix this we sum in superposition over the states
$\left|\phi_{j}\right\rangle$ for each value of $j$. The motivation to do this
is so that every length-$k$ region will be contained within $A_{j,i}$ for some
value of $i$ in most, but not all, of the terms in the superposition. We will
show that most is good enough. We let

$|\tilde{\psi}\rangle=\frac{1}{\sqrt{l}}\sum_{j=0}^{l-1}\left|\phi_{j}\right\rangle.$
(33)

We note that
$\left\langle\phi_{j}|\phi_{j^{\prime}}\right\rangle=\delta_{jj^{\prime}}$
since $\left|\phi_{j}\right\rangle$ is simply $\left|0\right\rangle$ when
reduced to region $B_{j,j^{\prime}}$ and $\left|1\right\rangle$ when reduced
to region $B_{j^{\prime},j}$, while $\left|\phi_{j^{\prime}}\right\rangle$ is
$\left|1\right\rangle$ when reduced to region $B_{j,j^{\prime}}$ and
$\left|0\right\rangle$ when reduced to $B_{j^{\prime},j}$. Thus
$|\tilde{\psi}\rangle$ is normalized:

$\langle\tilde{\psi}|\tilde{\psi}\rangle=\frac{1}{l}\sum_{j,j^{\prime}}\left\langle\phi_{j}|\phi_{j^{\prime}}\right\rangle=1.$
(34)

This completes the construction of the approximation. We now wish to show it
has the desired properties. To show item (1), we compute the (local) distance
from $\left|\psi\right\rangle$ to $|\tilde{\psi}\rangle$. Let
$\tilde{\rho}=|\tilde{\psi}\rangle\langle\tilde{\psi}|$ and consider an
arbitrary length-$k$ region $X$. We may write

$\displaystyle D_{1}(\rho_{X},\tilde{\rho}_{X})$ $\displaystyle={}$
$\displaystyle\frac{1}{2}\left\lVert\left(\frac{1}{l}\sum_{j=0}^{l-1}\sum_{j^{\prime}=0}^{l-1}\text{Tr}_{X^{c}}(\left|\phi_{j}\right\rangle\left\langle\phi_{j^{\prime}}\right|)\right)-\text{Tr}_{X^{c}}(\left|\psi\right\rangle\left\langle\psi\right|)\right\rVert_{1}.$
(35)

First we examine terms in the sum for which $j\neq j^{\prime}$. Since
$B_{j,j^{\prime}}$ and $B_{j^{\prime},j}$ are separated by at least $l$ sites
and $l>k$, $X^{c}$ must include either $B_{j,j^{\prime}}$ or
$B_{j^{\prime},j}$ (or both). Since $\left|\phi_{j}\right\rangle$ and
$\left|\phi_{j^{\prime}}\right\rangle$ have orthogonal support on both those
regions, and at least one of them is traced out, the term vanishes.

Thus we have

$\displaystyle D_{1}(\rho_{X},\tilde{\rho}_{X})$
$\displaystyle=\frac{1}{2}\left\lVert\frac{1}{l}\sum_{j=0}^{l-1}\text{Tr}_{X^{c}}(\left|\phi_{j}\right\rangle\left\langle\phi_{j}\right|-\left|\psi\right\rangle\left\langle\psi\right|)\right\rVert_{1}$
$\displaystyle\leq\frac{1}{l}\sum_{j=0}^{l-1}D_{1}\left(\rho_{X},\text{Tr}_{X^{c}}(\left|\phi_{j}\right\rangle\left\langle\phi_{j}\right|)\right).$
(36)

For a particular $j$, there are two cases. Case 1 includes values of $j$ for
which $X$ falls completely within the $A_{j,i}$ for some $i$ with $i\neq
j,j+1$. For these values of $j$ the term vanishes because the reduced density
matrix of $\left|\phi_{j}\right\rangle\left\langle\phi_{j}\right|$ on $X$ is
exactly $\rho_{X}$. Case 2 includes all other values of $j$. For this to be
the case, either $X$ spans the boundary between two regions $M_{j,i}$ and
$M_{j,i+1}$ (at most $k-1$ different values of $j$), $X$ contains a site
$B_{j,j^{\prime}}$ or $B_{j^{\prime},j}$ for some $j^{\prime}$ (at most 2
values of $j$, since the separation between sites $B_{j,j^{\prime}}$ implies
only one may lie within $X$), or $X$ is contained within $A_{j,j}$ or
$A_{j,j+1}$ (at most 2 values of $j$). In this case, the term will not
necessarily be close to zero, but we can always upper bound the trace distance
by 1. The number of terms in the sum that qualify as Case 2 is therefore at
most $k+3$, and the total error can be bounded:

$D_{1}(\rho_{X},\tilde{\rho}_{X})\leq\frac{k+3}{l}.$ (37)

Choosing $l=(k+3)/\epsilon$ shows item (1), that $|\tilde{\psi}\rangle$ is a
$(k,\epsilon)$-local approximation to $\left|\psi\right\rangle$.

To show item (2), we bound the Schmidt rank of the state
$|\tilde{\psi}\rangle$ across every cut that bipartitions the chain into two
contiguous regions. Since $|\tilde{\psi}\rangle$ is a superposition over $l$
terms $\left|\phi_{j}\right\rangle$, the Schmidt rank can be at most $l$ times
greater than that of an individual $\left|\phi_{j}\right\rangle$. Fix some
value of $j$ and some cut of the chain at site $s$. Since
$\left|\phi_{j}\right\rangle$ is a product state between regions $A_{j}$ and
$B_{j}$, and moreover it is a product state on each individual site in
$B_{j}$, we may ignore $B_{j}$ when calculating the Schmidt rank (it has no
entanglement), and focus merely on $\left|Q_{j}\right\rangle_{A_{j}}$. We
constructed the state $\left|Q_{j}\right\rangle$ by building up mixed states
$\sigma_{p}$ on region $A_{j,j+2}\ldots A_{j,j+p+1}$ until $p=n-2$, then
purified with the remaining two regions. Each $\sigma_{p}$ has
$\text{rank}(\sigma_{p})\leq d^{2l}$. Now consider an integer $b$ with $1\leq
b\leq n-1$ and $b\neq j,j+1$. Denote $\sigma=\sigma_{n-2}$ and note that

$\displaystyle\text{rank}(\sigma_{A_{j,1}\ldots A_{j,b}})$
$\displaystyle\leq{}$ $\displaystyle\text{rank}(\sigma_{A_{j,j+2}\ldots
A_{j,b}})\text{rank}(\sigma_{A_{j,j+2}\ldots A_{j,0}})$ $\displaystyle={}$
$\displaystyle\text{rank}(\sigma_{b-j-1})\text{rank}(\sigma_{n-j-1})\leq
d^{4l},$ (38)

where the first inequality follows from Lemma 4.

Moreover, we may choose $b$ such that the cut between $A_{j,b}$ and
$A_{j,b+1}$ falls within $l$ sites of site $s$. We find that the region
$A_{j,1}\ldots A_{j,b}$ differs from the region containing sites $[0,s]$ by at
most $l$ sites at each edge. Thus the Schmidt rank on the region left of the
cut can be at most $d^{2l}$ larger than that of $A_{j,1}\ldots A_{j,b}$
(Corollary 1), giving a bound of $d^{6l}$ for the the Schmidt rank of
$\left|\phi_{j}\right\rangle$. This implies the Schmidt rank of
$|\tilde{\psi}\rangle$ is at most $ld^{6l}$, which proves item (2). This
applies whenever $N\geq N_{0}=O(l^{3})=O(k^{3}/\epsilon^{3})$, a bound which
must be satisfied in order for the chain to be long enough to fit all the
regions $B_{j,j^{\prime}}$ as defined above. This completes Part 1.

Part 2: Items (2’) and (2”)

This construction is mostly similar to the previous one with a few key
differences. We choose integers $l$, $t$, and $\chi^{\prime}$ to be specified
later. We require $t$ be even and $l\geq 2k$, $l\geq 2t$. We assume $N\geq
N_{0}=2l^{2}$. We also require that $d\geq 4$. If this is not the case, we
coarse-grain the system by combining neighboring sites, and henceforth we
assume $d\geq 4$.

As in Part 1, to construct $|\tilde{\psi}\rangle$, we will first construct
states $\left|\phi_{j}\right\rangle$ for $j=0,\ldots,l-1$ and then sum these
states in superposition. Consider a fixed value of $j$. To construct
$\left|\phi_{j}\right\rangle$ we break the chain into $n=\lfloor N/l\rfloor$
blocks and we arrange them exactly as in Part 1.

Now the construction diverges from Part 1: the state
$\left|\phi_{j}\right\rangle$ will be a product state over each of these
blocks

$\left|\phi_{j}\right\rangle=\left|\phi_{j,0}\right\rangle_{M_{j,0}}\otimes\ldots\otimes\left|\phi_{j,n-1}\right\rangle_{M_{j,n-1}}$
(39)

with states $\left|\phi_{j,i}\right\rangle$ for $i=0,\ldots,n-1$ that we now
specify.

The idea is to create a state $\left|\phi_{j,i}\right\rangle$ that has nearly
the same reduced density matrix as $\left|\psi\right\rangle$ on the leftmost
$l-t$ sites of region $M_{j,i}$. It uses the rightmost $t$ sites to purify the
reduced density matrix on the leftmost $l-t$ sites. First we denote the
leftmost $l-t$ sites of block $M_{j,i}$ by $A_{j,i}=[j+l(i-1),j+li-t-1]$ and
the rightmost $t$ sites by $B_{j,i}=[j+li-t,j+li-1]$ (or appropriate “roll
over” definitions when $i=0$). We write $\left|\psi\right\rangle$ as an exact
MPS with exponential bond dimension and form $\left|\psi_{j,i}\right\rangle$
by truncating to bond dimension $\chi^{\prime}$ (i.e. projecting onto the span
of the right Schmidt vectors associated with the largest $\chi^{\prime}$
Schmidt coefficients, then normalizing the state) at the cut to the left of
region $A_{j,i}$, every cut within $A_{j,i}$, and at the cut to the right of
$A_{j,i}$, for a total of at most $2l-t$ truncations (recall the final region
$M_{j,0}$ may have as many as $2l-1$ sites). We denote the pure density matrix
of this state by
$\rho^{(j,i)}=\left|\psi_{j,i}\right\rangle\left\langle\psi_{j,i}\right|$. We
can bound the effect of these truncations using the area law given by Lemma 3:

$D(\rho^{(j,i)},\rho)\leq\sqrt{2l-t}\epsilon^{\chi^{\prime}},$ (40)

where $\epsilon^{\chi^{\prime}}$ is the cost (in purified distance) of a
single truncation, given by the right hand side of Eq. (19), or by Eq. (20) in
the case $\left|\psi\right\rangle$ is the ground state of a gapped nearest-
neighbor 1D Hamiltonian. These truncations were not possible in Part 1 because
we could not invoke the area law for general states.

Because of the truncations, we can express the reduced density matrix
$\rho_{A_{j,i}}^{(j,i)}$ as a mixture of $\chi^{\prime 2}$ pure states
$\\{\left|\phi_{j,i,z}\right\rangle\\}_{z=0}^{\chi^{\prime 2}-1}$ each of
which can be written as an MPS with bond dimension $\chi^{\prime}$:

$\rho_{A_{j,i}}^{(j,i)}=\sum_{z=0}^{\chi^{\prime
2}-1}p_{j,i,z}\left|\phi_{j,i,z}\right\rangle\left\langle\phi_{j,i,z}\right|,$
(41)

for some probability distribution $\\{p_{j,i,z}\\}_{z=0}^{\chi^{\prime 2}-1}$.
We now form $\left|\phi_{j,i}\right\rangle$ by purifying
$\rho_{A_{j,i}}^{(j,i)}$ onto the region $M_{j,i}$ using the space $B_{j,i}$,
which contains $t$ sites, as the purifying subspace:

$\left|\phi_{j,i}\right\rangle_{M_{j,i}}=\sum_{z=0}^{\chi^{\prime
2}-1}\sqrt{p_{j,i,z}}\left|\phi_{j,i,z}\right\rangle_{A_{j,i}}\otimes\left|r_{j,i,z}\right\rangle_{B_{j,i}},$
(42)

where the set of states
$\\{\left|r_{j,i,z}\right\rangle\\}_{z=0}^{\chi^{\prime 2}-1}$ is an
orthonormal set defined on region $B_{j,i}$. This purification will only be
possible if the dimension of $B_{j,i}$ is sufficiently large, and we comment
later on this fact, as well as how exactly to choose the set
$\\{\left|r_{j,i,z}\right\rangle\\}_{z=0}^{\chi^{\prime 2}-1}$.

The key observation is that state $\left|\phi_{j}\right\rangle$ will get any
local properties approximately correct as long as they are supported entirely
within a segment $A_{j,i}$ for some $i$, and as long as $\chi^{\prime}$ is
large enough that the $2l-t$ truncations do not have much effect on the
reduced density matrix there. Thus we will choose our parameters so that
$\chi^{\prime}$ is large (but independent of $N$), such that $l$ is much
larger than $t$ and $k$ (so that most regions fall within a region $A_{j,i}$),
and such that $t$ is large enough that it is possible to purify states on
$A_{j,i}$ onto $M_{j,i}$. But, as in Part 1, we have the issue that some
regions will not be contained entirely within region $A_{j,i}$ for some $i$.

We again deal with this issue by summing in superposition:

$|\tilde{\psi}\rangle=\frac{1}{\sqrt{l}}\sum_{j=0}^{l-1}\left|\phi_{j}\right\rangle.$
(43)

To complete the construction we also must specify the orthonormal states
$\\{\left|r_{j,i,z}\right\rangle\\}_{z=0}^{\chi^{\prime 2}-1}$ defined on the
$t$ sites in region $B_{j,i}$. We choose a set that satisfies the following
requirements.

  1. (1)

The reduced density matrix of $\left|r_{j,i,z}\right\rangle$ on any single
site among the leftmost $t/2$ sites of $B_{j,i}$ (recall we have assumed $t$
is even) is entirely supported on basis states $1,\ldots,\lfloor d/2\rfloor$.

  2. (2)

The reduced density matrix on any single site among the rightmost t/2 sites is
entirely supported on basis states $\lfloor d/2\rfloor+1,\ldots,d$.

  3. (3)

Let $j^{\prime}=j+i\mod l$, and let $i_{0}=i\mod l$. If $t\leq i_{0}\leq l-t$
then for all $z$, $\left|r_{j,i,z}\right\rangle$ is orthogonal to the support
of the reduced density matrix of $\left|\phi_{j^{\prime}}\right\rangle$ on
region $B_{j,i}$.

We assess how large $t$ must be for it to be possible to satisfy these three
conditions. The third item specifically applies only for values of $i$ that
lead to values of $j^{\prime}$ that are at least $t$ away from $j$ (modulo
$l$) so that the purifying system $B_{j,i}$ does not overlap with
$B_{j^{\prime},i^{\prime}}$ for any $i^{\prime}$. The support of the reduced
density matrix of any $\left|\phi_{j^{\prime}}\right\rangle$ on region
$B_{j,i}$ has dimension at most $\chi^{\prime 2}$. Thus, if the dimension of
$B_{j,i}$ is more than $2\chi^{\prime 2}$ it will always be possible to choose
an orthonormal set $\\{\left|r_{j,i,z}\right\rangle\\}_{z=0}^{\chi^{\prime
2}-1}$ satisfying the third condition. The first and second conditions cut the
accessible part of the local dimension of the purifying system in half, so a
purification that satisfies all three conditions will be possible if $\lfloor
d/2\rfloor^{t}\geq 2\chi^{\prime 2}$. Any choice of set that meets all three
conditions is equally good for our purposes.

We now demonstrate that the three conditions imply that for any pair
$(j,j^{\prime})$ there are regions of the chain on which the supports of the
reduced density matrices of states $\left|\phi_{j}\right\rangle$ and
$\left|\phi_{j^{\prime}}\right\rangle$ are orthogonal. If it is the case that
$j-j^{\prime}\mod l<t$ or $j^{\prime}-j\mod l<t$, then for every $i$ the
region $B_{j,i}$ overlaps with $B_{j^{\prime},i^{\prime}}$ for some
$i^{\prime}$. Because $B_{j,i}\neq B_{j^{\prime},i^{\prime}}$, there will be
some site that is in the right half of one of the two regions, but in the left
half of the other, and items 1 and 2 imply that the two states will be
orthogonal when reduced to this site. If this is not the case, then as long as
there is some $i$ for which $j^{\prime}=j+i\mod l$, then item 3 implies the
orthogonality of the supports of $\left|\phi_{j}\right\rangle$ and
$\left|\phi_{j^{\prime}}\right\rangle$. In fact because $n\geq 2l$, there will
be at least 2 such values of $i$. We conclude that
$\left\langle\phi_{j}|\phi_{j^{\prime}}\right\rangle=\delta_{jj^{\prime}}$,
which implies that $|\tilde{\psi}\rangle$ is normalized as shown by the
computation

$\langle\tilde{\psi}|\tilde{\psi}\rangle=\frac{1}{l}\sum_{j,j^{\prime}}\left\langle\phi_{j}|\phi_{j^{\prime}}\right\rangle=1.$
(44)

We have now shown how to define the approximation $|\tilde{\psi}\rangle$ and
discussed the conditions for the parameters $t$, $\chi^{\prime}$, and $d$ that
make the construction possible. Now we assess the error in the approximation
(locally). Let $\tilde{\rho}=|\tilde{\psi}\rangle\langle\tilde{\psi}|$ and
consider an arbitrary length-$k$ region $X$. We may write

$\displaystyle D_{1}(\rho_{X},\tilde{\rho}_{X})$ $\displaystyle={}$
$\displaystyle\frac{1}{2}\left\lVert\left(\frac{1}{l}\sum_{j=0}^{l-1}\sum_{j^{\prime}=0}^{l-1}\text{Tr}_{X^{c}}(\left|\phi_{j}\right\rangle\left\langle\phi_{j^{\prime}}\right|)\right)-\text{Tr}_{X^{c}}(\left|\psi\right\rangle\left\langle\psi\right|)\right\rVert_{1}.$
(45)

For the same reason that led to the conclusion
$\left\langle\phi_{j}|\phi_{j^{\prime}}\right\rangle=\delta_{jj^{\prime}}$, we
can conclude that
$\text{Tr}_{X^{c}}(\left|\phi_{j}\right\rangle\left\langle\phi_{j^{\prime}}\right|)=\delta_{jj^{\prime}}$,
so long as $k$ is smaller than $l/2$. To see that this holds, it is sufficient
to show that there is a region lying completely outside of $X$ with the
property that $\left|\phi_{j}\right\rangle$ and
$\left|\phi_{j}^{\prime}\right\rangle$ share no support on the region. Since
$k=\lvert X\rvert\leq l/2$ and $\lvert B_{j,i}\rvert=t\leq l/2$, for any $j$,
$X$ can overlap the region $B_{j,i}$ for at most one value of $i$. We showed
before that for any $j$ there would be at least two values of $i$ for which a
subregion of $B_{j,i}$ has this property, implying one of them must lie
outside $X$.

Thus we have

$\displaystyle D_{1}(\rho_{X},\tilde{\rho}_{X})$
$\displaystyle=\frac{1}{2}\left\lVert\frac{1}{l}\sum_{j=0}^{l-1}\text{Tr}_{X^{c}}(\left|\phi_{j}\right\rangle\left\langle\phi_{j}\right|-\left|\psi\right\rangle\left\langle\psi\right|)\right\rVert_{1}$
$\displaystyle\leq\frac{1}{l}\sum_{j=0}^{l-1}D_{1}\left(\rho_{X},\text{Tr}_{X^{c}}(\left|\phi_{j}\right\rangle\left\langle\phi_{j}\right|)\right).$
(46)

For a particular $j$, there are two cases. Case 1 occurs if $X$ falls
completely within the $A_{j,i}$ for some $i$, in which case the only error is
due to the $2l-t$ truncations to bond dimension $\chi^{\prime}$. Since the
trace norm $D_{1}$ is smaller than the purified distance $D$ (Lemma 1), the
contribution for these values of $j$ is at most
$\sqrt{2l-t}\epsilon^{\chi^{\prime}}$. Case 2 includes values of $j$ for which
$X$ does not fall completely within a region $A_{j,i}$ for any $i$. In this
case, the term will not necessarily be close to zero, but we can always upper
bound the trace distance by 1. The number of terms in the sum that qualify as
Case 1 is of course bounded by $l$ (there are only $l$ terms) and the number
of Case 2 terms is at most $t+k-1$. Thus the total error can be bounded:

$\displaystyle D_{1}(\rho_{X},\tilde{\rho}_{X})$ $\displaystyle\leq{}$
$\displaystyle\frac{1}{l}(l\sqrt{2l-t}\epsilon^{\chi^{\prime}}+(t+k-1))$
$\displaystyle\leq{}$
$\displaystyle\sqrt{2l}\epsilon^{\chi^{\prime}}+(k+t)/l.$ (47)

We will choose parameters so this quantity is less than $\epsilon$. Parameters
$l$ and $t$ will be related to $\chi^{\prime}$ as follows.

$\displaystyle t$ $\displaystyle=\log(2\chi^{\prime 2})/\log(\lfloor
d/2\rfloor)$ (48) $\displaystyle l$ $\displaystyle=2(k+t)/\epsilon$ (49)

If $\left|\psi\right\rangle$ is known only to have exponentially decaying
correlations, then we choose

$\log(\chi^{\prime})=16\xi\log(d)\log(16C_{1}\sqrt{\xi\log(d)(k+3)}/\epsilon^{3/2}),$
(50)

where $C_{1}=\exp(t_{0}\exp(\tilde{O}(\xi\log(d))))$ is the constant from Eq.
(19). We note that $t\leq 3\log(\chi^{\prime})$, so we can bound

$\displaystyle D_{1}(\rho_{X},\tilde{\rho}_{X})$
$\displaystyle\leq\frac{\sqrt{4(k+t)}C_{1}}{\sqrt{\epsilon}}e^{-\frac{\log(\chi^{\prime})}{8\xi\log(d)}}+\frac{\epsilon}{2}$
$\displaystyle\leq\frac{\sqrt{4(k+3)\log(\chi^{\prime})}C_{1}}{\sqrt{\epsilon}}e^{-\frac{\log(\chi^{\prime})}{8\xi\log(d)}}+\frac{\epsilon}{2}$
$\displaystyle\leq\frac{\sqrt{64\xi\log(d)(k+3)}C_{1}}{\sqrt{\epsilon}}e^{-\frac{\log(\chi^{\prime})}{16\xi\log(d)}}+\frac{\epsilon}{2}$
$\displaystyle\leq\frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon,$ (51)

where in the third line we have used the (crude) bound $\sqrt{u}\leq e^{u}$
with $u=\log(\chi^{\prime})/(16\xi\log(d))$.

In the case that $\left|\psi\right\rangle$ is known to be the ground state of
a gapped local Hamiltonian, we may choose

$\log(\chi^{\prime})=\tilde{O}(\Delta^{-1/4}\log(d)\log^{3/4}(C_{2}\sqrt{k+3}/\epsilon^{3/2})),$
(52)

where $C_{2}=\exp(\tilde{O}(\log^{8/3}(d)/\Delta)$ is the constant in Eq. (20)
and the same analysis will follow. This proves item (1) of the theorem for the
construction in Part 2.

Items (2’) and (2”) assert that $|\tilde{\psi}\rangle$ can be written as an
MPS with constant bond dimension, which we now show. Each state
$\left|\phi_{j}\right\rangle$ is a product state with pure state
$\left|\phi_{j,i}\right\rangle$ on each each block $M_{j,i}$, and
$\left|\phi_{j,i}\right\rangle$ has bond dimension at most $2\chi^{\prime 2}$.
Thus, if we cut the state $\left|\phi_{j}\right\rangle$ at a certain site, the
bond dimension will be at most $4\chi^{\prime 2}$ (recall that block $M_{j,0}$
may have sites at both ends of the chain and can contribute to the bond
dimension). Since $|\tilde{\psi}\rangle$ is a sum over
$\left|\phi_{j}\right\rangle$ for $l$ values of $j$, the bond dimension $\chi$
of $|\tilde{\psi}\rangle$ is at most $4l\chi^{\prime 2}$. For the case of
exponentially decaying correlations, this evaluates to

$\displaystyle\chi$
$\displaystyle=4l(256C_{1}^{2}\xi\log(d)(k+3)/\epsilon^{3})^{16\xi\log(d)}$
$\displaystyle\leq
e^{t_{0}e^{\tilde{O}(\xi\log(d))}}(k/\epsilon^{3})^{O(\xi\log(d))},$ (53)

proving item (2’), and for the case of ground state of gapped Hamiltonian, we
find

$\displaystyle\chi$
$\displaystyle=4l\exp(\tilde{O}(\Delta^{-1/4}\log(d)\log^{3/4}(C_{2}\sqrt{k+3}/\epsilon^{3/2})))$
$\displaystyle\leq(k/\epsilon)e^{\tilde{O}\left(\frac{\log^{3}(d)}{\Delta}+\frac{\log(d)}{\Delta^{1/4}}\log^{3/4}(k/\epsilon^{3})\right)},$
(54)

proving item (2”), where the second factor is asymptotically
$(k/\epsilon)^{o(1)}$. For completeness, we note that if we combined
neighboring sites because $d<4$, we can now uncombine them possibly incurring
a factor of 2 or 3 increase in the bond dimension, which has no effect on the
stated asymptotic forms for $\chi$.

These results hold as long as $N\geq 2l^{2}$, which translates to $N\geq
O(k^{2}/\epsilon^{2})+t_{0}\exp(\tilde{O}(\xi\log(d)))$ in the case of
exponentially decaying correlations, and $N\geq
O(k^{2}/\epsilon^{2})+\tilde{O}(\log(d)/\Delta^{3/4})$ in the case that
$\left|\psi\right\rangle$ is a ground state of a local Hamiltonian. This
completes the proof. ∎

Now we demonstrate that the state $|\tilde{\psi}\rangle$ constructed in the
proof of Theorem 1, Part 2, is long-range correlated. Given an integer $m$,
consider the pair of regions $A=[0,l(l-1)-1]$ and $C=[l(l-1+m),N-1]$, which
are separated by $ml$ sites. Assume $n\geq 2l+m$, so that $A$ and $C$ both
contain at least $l^{2}$ sites. Define the following operators.

$\displaystyle Q_{1}=$
$\displaystyle\left|\phi_{0,1}\right\rangle\left\langle\phi_{0,1}\right|\otimes\ldots\otimes\left|\phi_{0,l}\right\rangle\left\langle\phi_{0,l}\right|$
$\displaystyle Q_{2}=$
$\displaystyle\left|\phi_{0,l+m}\right\rangle\left\langle\phi_{0,l+m}\right|\otimes\ldots$
$\displaystyle\ldots\otimes\left|\phi_{0,n-1}\right\rangle\left\langle\phi_{0,n-1}\right|\otimes\left|\phi_{0,0}\right\rangle\left\langle\phi_{0,0}\right|$
(55)

The operator $Q_{1}$ is supported on $A$ and $Q_{2}$ is supported on $C$.
Since $A$ and $C$ each contain blocks $M_{i}$ for at least $l$ values of $i$,
conditions (1), (2), and (3) above imply that
$Q_{1}|\tilde{\psi}\rangle=Q_{2}|\tilde{\psi}\rangle=\left|\phi_{0}\right\rangle/\sqrt{l}$.
Thus

$\displaystyle\text{Cor}(A:C)_{|\tilde{\psi}\rangle}\geq$
$\displaystyle\text{Tr}((Q_{1}\otimes
Q_{2})(\tilde{\rho}_{AC}-\tilde{\rho}_{A}\otimes\tilde{\rho}_{C}))$
$\displaystyle=$ $\displaystyle\text{Tr}(Q_{1}\otimes
Q_{2}|\tilde{\psi}\rangle\langle\tilde{\psi}|)$
$\displaystyle-\text{Tr}(Q_{1}|\tilde{\psi}\rangle\langle\tilde{\psi}|)\text{Tr}(Q_{2}|\tilde{\psi}\rangle\langle\tilde{\psi}|)$
$\displaystyle=$ $\displaystyle 1/l-1/l^{2}.$ (56)

The choice of $l$ is independent of the chain length $N$, so the above
quantity is independent of $N$ and independent of the parameter $m$ measuring
the distance between $A$ and $C$. Thus, the correlation certainly does not
decay exponentially in the separation between the regions.

###  4.3 Proof of Theorem 2

In this section, we first state a pair of lemmas that will be essential for
the proof of Theorem 2, then we give a proof summary of Theorem 2, and finally
we provide the full proof of Theorem 2.

First, an important and well-known tool we use is Uhlmann’s theorem [30],
which expresses the fact that if two states are close, their purifications
will be equally close up to a unitary acting on the purifying auxiliary space.

######  Lemma 6 (Uhlmann’s theorem [30]).

Suppose $\tau_{A}$ and $\sigma_{A}$ are states on system $A$. Suppose $B$ is
an auxiliary system and $\left|T\right\rangle_{AB}$ and
$\left|S\right\rangle_{AB}$ are purifications of $\tau_{A}$ and $\sigma_{A}$,
respectively. Then

$D(\tau_{A},\sigma_{A})=\min_{U}\sqrt{1-\lvert\left\langle
S\right|_{AB}(I_{A}\otimes U)\left|T\right\rangle_{AB}\rvert^{2}},$ (57)

where the min is taken over unitaries on system $B$.

Second, we prove the following essential statement about states with
exponential decay of correlations.

######  Lemma 7.

If $L$ and $R$ are disjoint regions of a 1D lattice of $N$ sites and the state
$\tau=\left|\eta\right\rangle\left\langle\eta\right|$ has
$(t_{0},\xi)$-exponential decay of correlations, then

$D(\tau_{LR},\tau_{L}\otimes\tau_{R})\leq
C_{3}\exp(-\text{dist}(L,R)/\xi^{\prime})$ (58)

whenever $\text{dist}(L,R)\geq t_{0}$, where $\xi^{\prime}=16\xi^{2}\log(d)$
and $C_{3}=\exp(t_{0}\exp(\tilde{O}(\xi\log(d))))$.

If $\tau$ is the unique ground state of a gapped nearest-neighbor 1D
Hamiltonian with spectral gap $\Delta$, then this can be improved to

$D(\tau_{LR},\tau_{L}\otimes\tau_{R})\leq
C_{4}\exp(-\text{dist}(L,R)/\xi^{\prime})$ (59)

whenever $\text{dist}(L,R)\geq\Omega(\log^{4}(d)/\Delta^{2})$, where
$\xi^{\prime}=O(1/\Delta)$ and $C_{4}=\exp(\tilde{O}(\log^{3}(d)/\Delta))$.

For pure states $\sigma$, we call $\sigma$ a Markov chain for the tripartition
$L/M/R$ if $\sigma_{LR}=\sigma_{L}\otimes\sigma_{R}$. Thus Lemma 7 states that
exponential decay of correlations implies that the violation of the Markov
condition, as measured by the purified distance (or alternatively, trace
distance) decays exponentially with the size of $M$.

###### Proof of Lemma 7.

The goal is to show that an exponential decay of correlations in
$\tau=\left|\eta\right\rangle\left\langle\eta\right|$ implies that $\tau_{LR}$
is close to $\tau_{L}\otimes\tau_{R}$. We will do this by truncating the rank
of $\tau$ on the region $L$ to form $\sigma$, arguing that $\sigma_{LR}$ is
close to $\sigma_{L}\otimes\sigma_{R}$, and finally using the triangle
inequality to show the same holds for $\tau$.

Lemma 3 says that there is a state $\sigma_{L}$ with rank $\chi$ defined on
region $L$ such that

$D(\tau_{L},\sigma_{L})\leq C_{1}e^{-\frac{\log(\chi)}{8\xi\log(d)}}.$ (60)

In fact, the choice of $\sigma_{L}$ of rank $\chi$ that minimizes the distance
to $\tau_{L}$ is the state $P_{L}\tau_{L}/\text{Tr}(P_{L}\tau_{L})$ where
$P_{L}$ is the projector onto the eigenvectors of $\tau_{L}$ associated with
the largest $\chi$ eigenvalues. Accordingly, we define a normalization
constant $q=1/\text{Tr}(P_{L}\tau_{L})$ and let
$\left|\nu\right\rangle=\sqrt{q}P_{L}\left|\eta\right\rangle$ and
$\sigma=\left|\nu\right\rangle\left\langle\nu\right|=qP_{L}\tau P_{L}$ be
normalized states.

We first need to show that

$\text{Cor}(L:R)_{\left|\nu\right\rangle}:=\max_{\lVert A\rVert,\lVert
B\rVert\leq 1}\text{Tr}((A\otimes
B)(\sigma_{LR}-\sigma_{L}\otimes\sigma_{R}))$ (61)

is small, given only that $\text{Cor}(L:R)_{\left|\eta\right\rangle}$ is
small. Suppressing tensor product symbols, we can write

$\displaystyle{}\text{Tr}((AB)(\sigma_{LR}-\sigma_{L}\sigma_{R}))$
$\displaystyle=\left\langle\nu\right|AB\left|\nu\right\rangle-\left\langle\nu\right|A\left|\nu\right\rangle\left\langle\nu\right|B\left|\nu\right\rangle$
$\displaystyle=q\left\langle\eta\right|P_{L}ABP_{L}\left|\eta\right\rangle-q^{2}\left\langle\eta\right|P_{L}AP_{L}\left|\eta\right\rangle\left\langle\eta\right|P_{L}BP_{L}\left|\eta\right\rangle$
$\displaystyle=q\left\langle\eta\right|(P_{L}AP_{L})B\left|\eta\right\rangle-q^{2}\left\langle\eta\right|P_{L}AP_{L}\left|\eta\right\rangle\left\langle\eta\right|P_{L}B\left|\eta\right\rangle$
$\displaystyle=q\left\langle\eta\right|(P_{L}AP_{L})B\left|\eta\right\rangle$
$\displaystyle\hskip
6.0pt-q^{2}\left\langle\eta\right|P_{L}AP_{L}\left|\eta\right\rangle\left(\left\langle\eta\right|P_{L}B\left|\eta\right\rangle-\left\langle\eta\right|P_{L}\left|\eta\right\rangle\left\langle\eta\right|B\left|\eta\right\rangle\right)$
$\displaystyle\hskip
6.0pt-q^{2}\left\langle\eta\right|P_{L}AP_{L}\left|\eta\right\rangle\
\left\langle\eta\right|P_{L}\left|\eta\right\rangle\left\langle\eta\right|B\left|\eta\right\rangle$
$\displaystyle=q\left(\left\langle\eta\right|(P_{L}AP_{L})B\left|\eta\right\rangle-\left\langle\eta\right|P_{L}AP_{L}\left|\eta\right\rangle\left\langle\eta\right|B\left|\eta\right\rangle\right)$
$\displaystyle\hskip
6.0pt-q^{2}\left\langle\eta\right|P_{L}AP_{L}\left|\eta\right\rangle\left(\left\langle\eta\right|P_{L}B\left|\eta\right\rangle-\left\langle\eta\right|P_{L}\left|\eta\right\rangle\left\langle\eta\right|B\left|\eta\right\rangle\right),$
(62)

from which we can conclude

$\text{Cor}(L:R)_{\left|\nu\right\rangle}\leq(q+q^{2})\text{Cor}(L:R)_{\left|\eta\right\rangle}.$
(63)

The normalization constant $q$ is $1/(1-D(\tau_{L},\sigma_{L})^{2})$ which
will be close to 1 as long as $\chi$ is sufficiently large. If we choose
$\log(\chi)=8\xi\log(d)(1+\log(C_{1}))$ or larger, then $q$ will certainly be
smaller than 2 and $q+q^{2}\leq 6$.

The combination of the fact that $\sigma_{L}$ has small rank and that $\sigma$
has small correlations between $L$ and $R$ will allow us to show that
$\sigma_{LR}$ is close to $\sigma_{L}\otimes\sigma_{R}$. We do this by
invoking Lemma 20 of [5], although we reproduce the argument below. We can
express the trace norm as

$\displaystyle\lVert\sigma_{LR}-\sigma_{L}\otimes\sigma_{R}\rVert_{1}$
$\displaystyle={}$ $\displaystyle\max_{\lVert T\rVert\leq
1}\text{Tr}(T(\sigma_{LR}-\sigma_{L}\otimes\sigma_{R}))$ $\displaystyle={}$
$\displaystyle\max_{\lVert T\rVert\leq
1}\text{Tr}(P_{L}TP_{L}(\sigma_{LR}-\sigma_{L}\otimes\sigma_{R})),$ (64)

where the second equality follows from the fact that $P_{L}$ fixes the state
$\sigma$. We can perform a Schmidt decomposition of the operator $P_{L}TP_{L}$
into a sum of at most $\chi^{2}$ terms which are each a product operator
across the $L/R$ partition

$P_{L}TP_{L}=\sum_{j=1}^{\chi^{2}}T_{L,j}\otimes T_{R,j}$ (65)

and also such that $\lVert T_{L,j}\rVert,\lVert T_{R,j}\rVert\leq 1$ (see
Lemma 20 of [5] for full justification of this). Then we may write

$\displaystyle\lVert\sigma_{LR}-\sigma_{L}\otimes\sigma_{R}\rVert_{1}$
$\displaystyle\leq{}$ $\displaystyle\max_{\lVert T\rVert\leq
1}\text{Tr}\left(\left(\sum_{j=1}^{\chi^{2}}T_{L,j}\otimes
T_{R,j}\right)(\sigma_{LR}-\sigma_{L}\otimes\sigma_{R})\right)$
$\displaystyle\leq{}$ $\displaystyle\sum_{j=1}^{\chi^{2}}\max_{\lVert
T_{L,j}\rVert,\lVert T_{R,j}\rVert\leq 1}\text{Tr}\left(\left(T_{L,j}\otimes
T_{R,j}\right)(\sigma_{LR}-\sigma_{L}\otimes\sigma_{R})\right)$
$\displaystyle\leq{}$
$\displaystyle\chi^{2}\text{Cor}(L:R)_{\left|\nu\right\rangle}$
$\displaystyle\leq{}$ $\displaystyle
6\chi^{2}\text{Cor}(L:R)_{\left|\eta\right\rangle}\leq
6\chi^{2}\exp(-\text{dist}(L,R)/\xi)$ (66)

as long as $\chi\geq 8\xi\log(d)(1+\log(C))$ and $\text{dist}(L,R)\geq t_{0}$.

Moreover the purified distance is bounded by the square root of the trace norm
of the difference (Lemma 1), allowing us to say

$D(\sigma_{LR},\sigma_{L}\otimes\sigma_{R})\leq\sqrt{6}\chi\exp(-\text{dist}(L,R)/(2\xi)).$
(67)

Then, by the triangle inequality, we can bound

$\displaystyle D(\tau_{LR},\tau_{L}\otimes\tau_{R})$ $\displaystyle\leq{}$
$\displaystyle
D(\tau_{LR},\sigma_{LR})+D(\sigma_{LR},\sigma_{L}\otimes\sigma_{R})$
$\displaystyle+D(\sigma_{L}\otimes\sigma_{R},\tau_{L}\otimes\tau_{R})$
$\displaystyle\leq{}$ $\displaystyle
D(\tau_{LR},\sigma_{LR})+D(\sigma_{LR},\sigma_{L}\otimes\sigma_{R})$
$\displaystyle+D(\sigma_{L},\tau_{L})+D(\sigma_{R},\tau_{R})$
$\displaystyle\leq{}$ $\displaystyle
3C_{1}\exp\left(-\frac{\log(\chi)}{8\xi\log(d)}\right)+\sqrt{6}\chi\exp\left(-\frac{\text{dist}(L,R)}{2\xi}\right).$
(68)

We can choose

$\log(\chi)=8\xi\log(d)(1+\log(3C_{1}))+\text{dist}(L,R)/(4\xi).$ (69)

Then each term can be bounded so that

$D(\tau_{LR},\tau_{L}\otimes\tau_{R})\leq
2\sqrt{6}(3eC_{1})^{8\xi\log(d)}e^{-\frac{\text{dist}(L,R)}{32\xi^{2}\log(d)}},$
(70)

which proves the first part of the Lemma.

If $\tau$ is the unique ground state of a gapped Hamiltonian, then we may use
the second part of Lemma 3, and bound

$\displaystyle D(\tau_{LR},\tau_{L}\otimes\tau_{R})$ $\displaystyle\leq{}$
$\displaystyle
3C_{2}e^{-\tilde{O}\left(\frac{\Delta^{1/3}\log^{4/3}(\chi)}{\log^{4/3}(d)}\right)}+\sqrt{6}\chi
e^{-O\left(\Delta\text{dist}(L,R)\right)}.$ (71)

Here we can choose

$\log(\chi)=O\left(\frac{\log(d)(1+\log(3C_{2}))^{\frac{3}{4}}}{\Delta^{1/4}}+\Delta\text{dist}(L,R)\right),$
(72)

and then each term is small enough to make the bound

$\displaystyle D(\tau_{LR},\tau_{L}\otimes\tau_{R})$ $\displaystyle\leq{}$
$\displaystyle
e^{\tilde{O}\left(\frac{\Delta^{5/3}\text{dist}(L,R)^{4/3}}{\log^{4/3}(d)}\right)}$
$\displaystyle+\sqrt{6}e^{O\left(\frac{\log(d)\log^{3/4}(3eC_{2})}{\Delta^{1/4}}\right)}e^{-O\left(\Delta\text{dist}(L,R)\right)}$
$\displaystyle\leq{}$ $\displaystyle
e^{\tilde{O}\left(\frac{\log^{3}(d)}{\Delta}\right)}e^{-O\left(\Delta\text{dist}(L,R)\right)}$
(73)

as long as $\text{dist}(L,R)\geq\Omega(\log^{4}(d)/\Delta^{2})$, so that the
first term in the second line is dominated by the second term. Also note we
have used $\log(C_{2})=\tilde{O}(\log^{8/3}(d)/\Delta)$ in the last line. This
proves the second part of the lemma. ∎

Figure 3: Schematic for the proof of Theorem 2. The chain is divided into
regions $M_{i}$ of length $l$, which are themselves divided into left and
right halves $M_{i}^{L}$ and $M_{i}^{R}$. The state $|\tilde{\psi}\rangle$ is
constructed by starting with $\left|\psi\right\rangle$, applying unitaries
that act only on $M_{i}$ for each $i$ to disentangle the state across the
$M_{i}^{L}/M_{i}^{R}$ cut, projecting onto a product state across those cuts,
and finally applying the inverse unitaries on regions $M_{i}$.

###### Proof summary for Theorem 2.

First, we make the following observation about tripartitions of the chain into
contiguous regions $L$, $M$, and $R$: since $\left|\psi\right\rangle$ has
exponential decay of correlations, the quantity
$D(\rho_{LR},\rho_{L}\otimes\rho_{R})$ is exponentially small in $\lvert
M\rvert/\xi^{\prime}$, where $\xi^{\prime}=O(\xi^{2}\log(d))$. This is
captured in Lemma 7 and requires the area law result from [5]. One can
truncate $\rho_{L}$ and $\rho_{R}$ to bond dimension $d^{\lvert M\rvert/2}$,
incurring small error, then purify $\rho_{L}$ into $\left|\alpha\right\rangle$
using the left half of region $M$ as the purifying auxiliary space and
$\rho_{R}$ into $\left|\beta\right\rangle$ using the right half. Since
$\left|\alpha\right\rangle\otimes\left|\beta\right\rangle$ and
$\left|\psi\right\rangle$ are nearly the same state after tracing out $M$,
there is a unitary $U$ acting only on $M$ that nearly disentangles
$\left|\psi\right\rangle$ across the central cut of $M$, with
$U\left|\psi\right\rangle\approx\left|\alpha\right\rangle\otimes\left|\beta\right\rangle$
(Uhlmann’s theorem, Lemma 6).

The proof constructs the approximation $|\tilde{\psi}\rangle$ by applying
three steps of operations on the exact state $\left|\psi\right\rangle$. First,
the chain is broken up into many regions $\\{M_{i}\\}_{i=0}^{n+1}$ of length
$l$, and disentangling unitaries $U_{i}$ as described above are applied to
each region $M_{i}$ in parallel. The state is close to, but not exactly, a
product state across the center cut of each region $M_{i}$. To make it an
exact product state, the second step is to apply rank-1 projectors $\Pi_{i}$
onto the right half of the state across each of these cuts, starting with the
leftmost cut and working our way down the chain. Then, the third step is to
apply the reverse unitaries $U_{i}^{\dagger}$ that we applied in step 1.

The projection step is the cause of the error between
$\left|\psi\right\rangle$ and $|\tilde{\psi}\rangle$. The number of
projections is $O(N)$, but the error accrued locally is only constant. This
follows from the fact that the projectors are rank 1, so once we apply
projector $\Pi_{i}$, region $M_{j}$ is completely decoupled from
$M_{j^{\prime}}$ when $j<i$ and $j^{\prime}>i$. Thus any additional
projections, which act only on the regions to the right of $M_{i}$, have no
effect on the reduced density matrix on $M_{j}$ (except to reduce its norm).
Using this logic, we show that the number of errors that actually affect the
state locally on a region $X$ is proportional to the number of sites in $X$,
and not the number of sites in the whole chain. To make this error less than
$\epsilon$ for any region of at most $k$ sites, we can choose
$l=O(\xi^{\prime}\log(k/\epsilon))$.

After step 2, the state is a product state on blocks of $l$ sites each, and in
step 3, unitaries are applied that couple neighboring blocks, so the maximum
Schmidt rank across any cut cannot exceed $d^{l}$. This yields the scaling for
$\chi$.

The result is improved when $\left|\psi\right\rangle$ is the ground state of a
gapped local Hamiltonian by using the improved area law [1, 2] in the proof of
Lemma 7 and in the truncation of the states $\rho_{L}$ and $\rho_{R}$ before
purifying into $\left|\alpha\right\rangle$ and $\left|\beta\right\rangle$.

Finally, it can be seen that $|\tilde{\psi}\rangle$ is formed by a constant-
depth quantum circuit with two layers of unitaries, where each unitary acts on
$l$ qubits. The first layer prepares the product state over blocks of length
$l$ that is attained after applying projections in step 2, and the second
layer applies the inverse unitaries from step 3. Each unitary in this circuit
can be decomposed into a sequence of nearest-neighbor gates with depth
$\tilde{O}(d^{2l})$. ∎

###### Proof of Theorem 2.

We fix an even integer $l$, which we will specify later, and divide the $N$
sites of the chain into $n+2$ segments of length $l$, which we label, from
left to right: $M_{0},M_{1},\ldots,M_{n+1}$. If $N$ does not divide $l$
evenly, then we allow segment $M_{n+1}$ to have fewer than $l$ sites. For
$i\in[1,n]$ let $L_{i}$ be the sites to the left of region $M_{i}$ and let
$R_{i}$ be the sites to the right of region $M_{i}$.

Lemma 7 tells us that, since $\left|\psi\right\rangle$ has
$(t_{0},\xi)$-exponential decay of correlations, for any $i\in[1,n]$,
$\rho_{L_{i}R_{i}}$ is close to $\rho_{L_{i}}\otimes\rho_{R_{i}}$ when $l$ is
much larger than $\xi^{\prime}$; that is,

$D(\rho_{L_{i}R_{i}},\rho_{L_{i}}\otimes\rho_{R_{i}})\leq
C_{3}\exp(-l/\xi^{\prime})$ (74)

whenever $l\geq t_{0}$. We also choose $\chi=d^{l}$ and for each $i$ define
$\rho^{\prime}_{L_{i}}$ and $\rho^{\prime}_{R_{i}}$, each with rank at most
$\sqrt{\chi}$ by taking $A=L_{i}$ and $A=R_{i}$ in Lemma 3. Thus we have

$\displaystyle D(\rho_{L_{i}},\rho^{\prime}_{L_{i}})$ $\displaystyle\leq
C_{1}\exp(-l/(16\xi)),$ (75) $\displaystyle
D(\rho_{R_{i}},\rho^{\prime}_{R_{i}})$ $\displaystyle\leq
C_{1}\exp(-l/(16\xi)).$ (76)

Then by the triangle inequality we have

$\displaystyle
D(\rho_{L_{i}R_{i}},\rho^{\prime}_{L_{i}}\otimes\rho^{\prime}_{R_{i}})$
$\displaystyle\leq{}$ $\displaystyle
D(\rho_{L_{i}R_{i}},\rho_{L_{i}}\otimes\rho_{R_{i}})+D(\rho_{L_{i}}\otimes\rho_{R_{i}},\rho^{\prime}_{L_{i}}\otimes\rho_{R_{i}})$
$\displaystyle+D(\rho^{\prime}_{L_{i}}\otimes\rho_{R_{i}},\rho^{\prime}_{L_{i}}\otimes\rho^{\prime}_{R_{i}})$
$\displaystyle={}$ $\displaystyle
D(\rho_{L_{i}R_{i}},\rho_{L_{i}}\otimes\rho_{R_{i}})+D(\rho_{L_{i}},\rho^{\prime}_{L_{i}})+D(\rho_{R_{i}},\rho^{\prime}_{R_{i}})$
$\displaystyle\leq{}$ $\displaystyle C\exp(-l/\xi^{\prime\prime}),$ (77)

where $C\leq 2C_{1}+C_{3}$, $\xi^{\prime\prime}=\max(\xi^{\prime},16\xi)$,
whenever $l\geq t_{0}$.

Note that $\left|\psi\right\rangle_{L_{i}M_{i}R_{i}}$ can be viewed as a
purification of $\rho_{L_{i}R_{i}}$ with $M_{i}$ the purifying auxiliary
system. Divide region $M_{i}$ in half, forming $M_{i}^{L}$ (left half) and
$M_{i}^{R}$ (right half). See Figure 3 for a schematic. Each of these
subsystems has total dimension $d^{l/2}$ and thus can act as the purifying
auxiliary system for $\rho^{\prime}_{L_{i}}$ or $\rho^{\prime}_{R_{i}}$. Let
$\left|\alpha_{i}\right\rangle_{L_{i}M_{i}^{L}}$ be a purification of
$\rho^{\prime}_{L_{i}}$ and $\left|\beta_{i}\right\rangle_{M_{i}^{R}R_{i}}$ be
a purification of $\rho^{\prime}_{R_{i}}$. Thus,
$\left|\alpha_{i}\right\rangle\otimes\left|\beta_{i}\right\rangle$, which is
defined over the entire original chain, is a purification of
$\rho^{\prime}_{L_{i}}\otimes\rho^{\prime}_{R_{i}}$.

Uhlmann’s theorem (Lemma 6) shows how these purifications are related by a
unitary on the purifying auxiliary system: for each $M_{i}$ with $i\in[1,n]$,
there is a unitary $U_{i}$ acting non-trivially on region $M_{i}$ and as the
identity on the rest of the chain such that $U_{i}\left|\psi\right\rangle$ is
very close to
$\left|\alpha_{i}\right\rangle\otimes\left|\beta_{i}\right\rangle$, a product
state across the cut between $M_{i}^{L}$ and $M_{i}^{R}$. In other words,
$U_{i}$ disentangles $L_{i}$ from $R_{i}$, up to some small error, by acting
only on $M_{i}$. Formally we say that

$\left\lvert\left\langle\alpha_{i}\right|_{L_{i}M_{i}^{L}}\otimes\left\langle\beta_{i}\right|_{M_{i}^{R}R_{i}}U_{i}\left|\psi\right\rangle_{L_{i}M_{i}R_{i}}\right\rvert=\sqrt{1-\delta_{i}^{2}},$
(78)

where $\delta_{i}\leq C\exp(-l/\xi^{\prime\prime})$ for all $i$.

An equivalent way to write this fact is

$\displaystyle U_{i}\left|\psi\right\rangle_{L_{i}M_{i}R_{i}}={}$
$\displaystyle\sqrt{1-\delta_{i}^{2}}\left|\alpha_{i}\right\rangle_{L_{i}M_{i}^{L}}\otimes\left|\beta_{i}\right\rangle_{M_{i}^{R}R_{i}}$
$\displaystyle+\delta_{i}\left|\phi_{i}^{\prime}\right\rangle_{L_{i}M_{i}^{L}M_{i}^{R}R_{i}}$
(79)

where $\left|\phi_{i}^{\prime}\right\rangle$ is a normalized state orthogonal
to $\left|\alpha_{i}\right\rangle\otimes\left|\beta_{i}\right\rangle$.

We can define the projector

$\Pi_{i}=I_{L_{i}M_{i}^{L}}\otimes\left|\beta_{i}\right\rangle\left\langle\beta_{i}\right|_{M_{i}^{R}R_{i}},$
(80)

whose rank is 1 when considered as an operator acting only on
$M_{i}^{R}R_{i}$.

We notice that $\Pi_{i}U_{i}\left|\psi\right\rangle_{L_{i}M_{i}R_{i}}$ is a
product state across the $M_{i}^{L}/M_{i}^{R}$ cut and has a norm close to 1.
Suppose we alternate between applying disentangling operations $U_{i}$ and
projections $\Pi_{i}$ onto a product state as we move down the chain. Each
$\Pi_{i}$ will reduce the norm of the state, but we claim the norm will never
vanish completely (and delay the proof for later for clarity of argument).

######  Claim 1.

If $l\geq\xi^{\prime\prime}\log(3C)$, then

$\lVert\Pi_{n}U_{n}\ldots\Pi_{1}U_{1}\left|\psi\right\rangle\rVert\neq 0.$
(81)

This allows us to define

$|\tilde{\phi}\rangle=\frac{\Pi_{n}U_{n}\ldots\Pi_{1}U_{1}\left|\psi\right\rangle}{\lVert\Pi_{n}U_{n}\ldots\Pi_{1}U_{1}\left|\psi\right\rangle\rVert}.$
(82)

Note that, to put our proof in line with what is described in the introduction
and proof summary earlier, we may act with all the unitaries prior to the
projectors if we conjugate the projectors

$|\tilde{\phi}\rangle\propto\Pi^{\prime}_{n}\ldots\Pi^{\prime}_{1}U_{n}\ldots
U_{1}\left|\psi\right\rangle,$ (83)

where $\Pi^{\prime}_{i}=U_{n}\ldots U_{i+1}\Pi_{i}U_{i+1}^{\dagger}\ldots
U_{n}^{\dagger}$, which still only acts on the region $R_{i}$.

This can be compared with the state $\left|\phi\right\rangle$ defined by
applying the disentangling operations without projecting:

$\left|\phi\right\rangle=U_{n}\ldots U_{1}\left|\psi\right\rangle.$ (84)

We claim that $|\tilde{\phi}\rangle$ is a good local approximation for
$\left|\phi\right\rangle$ (and delay the proof for clarity of argument).

######  Claim 2.

For any integer $k^{\prime}$, $|\tilde{\phi}\rangle$ is a
$(k^{\prime},\epsilon^{\prime})$-local approximation to
$\left|\phi\right\rangle$ with
$\epsilon^{\prime}=C\sqrt{k^{\prime}/l+3}\exp(-l/\xi^{\prime\prime})$.

Next we can define

$|\tilde{\psi}\rangle=U_{n}^{\dagger}\ldots
U_{1}^{\dagger}|\tilde{\phi}\rangle,$ (85)

which parallels the relationship

$\left|\psi\right\rangle=U_{n}^{\dagger}\ldots
U_{1}^{\dagger}\left|\phi\right\rangle.$ (86)

Now suppose $X$ is a contiguous region of the chain of length $k$. Then there
is a region $X^{\prime}$ of the chain of length at most $k^{\prime}=k+2l$ that
contains $X$ and is made up of regions $M_{j}$ where
$j\in[a^{\prime},b^{\prime}]$. Then

$\displaystyle\lVert\text{Tr}_{X^{c}}(|\tilde{\psi}\rangle\langle\tilde{\psi}|-\left|\psi\right\rangle\left\langle\psi\right|)\rVert_{1}$
$\displaystyle\leq{}$ $\displaystyle\lVert\text{Tr}_{X^{\prime
c}}(|\tilde{\psi}\rangle\langle\tilde{\psi}|-\left|\psi\right\rangle\left\langle\psi\right|)\rVert_{1}$
$\displaystyle={}$ $\displaystyle\lVert\text{Tr}_{X^{\prime
c}}(|\tilde{\phi}\rangle\langle\tilde{\phi}|-\left|\phi\right\rangle\left\langle\phi\right|)\rVert_{1}$
$\displaystyle\leq{}$ $\displaystyle C\sqrt{k/l+5}\exp(-l/\xi^{\prime\prime})$
$\displaystyle\leq{}$ $\displaystyle C\sqrt{6k}\exp(-l/\xi^{\prime\prime}),$
(87)

where the third line follows from the fact that $\left|\phi\right\rangle$ and
$\left|\psi\right\rangle$ are related by a unitary that does not couple region
$X^{\prime}$ and region $X^{\prime c}$, and the fourth line follows from Claim
2.

If we choose $l=\max(t_{0},\xi^{\prime\prime}\log(3C\sqrt{k}/\epsilon))$, then
the requirements of Claim 1 are satisfied, and we can see from Eq. (4.3) that
$|\tilde{\psi}\rangle$ is a $(k,\epsilon)$-local approximation to
$\left|\psi\right\rangle$, item (1) of the theorem.

Item (2) states that $|\tilde{\psi}\rangle$ can be written as an MPS with
constant bond dimension. This can be seen by the following logic. The Schmidt
rank of $|\tilde{\phi}\rangle$ across any cut $M_{i}^{L}/M_{i}^{R}$ is 1, as
discussed in the proof of Claim 2 (see Eq. (4.3)), since the projector
$\Pi_{i}$ projects onto a product state across that cut and unitaries $U_{j}$
with $j>i$ act trivially across the cut. By Corollary 1, this implies that the
Schmidt rank across any cut $M_{i}^{R}/M_{i+1}^{L}$ can be at most $d^{l/2}$.
Acting with the inverse unitaries $U_{j}^{\dagger}$ on $|\tilde{\phi}\rangle$
to form $|\tilde{\psi}\rangle$ preserves the Schmidt rank across the cut
$M_{i}^{R}/M_{i+1}^{L}$, since none couple both sides of the cut. Because any
cut is at most distance $l/2$ from some $M_{i}^{R}/M_{i+1}^{L}$ cut, the
Schmidt rank across an arbitrary cut can be at most a factor of $d^{l/2}$
greater, again by Corollary 1, meaning the maximum Schmidt rank across any cut
of $\left|\psi\right\rangle$ is $\chi=d^{l}$.

Given our choice of $l=\xi^{\prime\prime}\log(C\sqrt{6k}/\epsilon)$, we find
that the state can be represented by an MPS with bond dimension

$\displaystyle\chi$
$\displaystyle=(\sqrt{6}C)^{\xi^{\prime\prime}\log(d)}(k/\epsilon^{2})^{\xi^{\prime\prime}\log(d)/2}$
$\displaystyle=e^{e^{\tilde{O}(\xi\log(d))}}(k/\epsilon^{2})^{O(\xi^{2}\log^{2}(d))}.$
(88)

This proves item (2). Note that, in the case that our choice of $l$ exceeds
$N$, it is not possible to form the construction we have described. However,
in this case $d^{l}$ will exceed $d^{N}$ and we may take
$|\tilde{\psi}\rangle=\left|\psi\right\rangle$, which is a local approximation
for any $k$ and $\epsilon$ and has bond dimension in line with item (2) or
(2’).

Item (2’) follows by using the same equations with
$C=2C_{2}+C_{4}=\exp(\tilde{O}(\log^{3}(d)/\Delta))$ and
$\xi^{\prime\prime}=O(1/\Delta)$. For Lemma 7 to apply, we must have
$l\geq\Omega(\log^{4}(d)/\Delta^{2})$, but this will be satisfied for
sufficiently large choices of $k/\epsilon^{2}$. Thus the final analysis yields

$\chi=e^{\tilde{O}(\log^{4}(d)/\Delta^{2})}(k/\epsilon^{2})^{O\left(\log(d)/\Delta\right)}.$
(89)

Item (3) states that $|\tilde{\psi}\rangle$ can be formed from a low-depth
quantum circuit. In the proof of Claim 2, we show how the state
$|\tilde{\phi}\rangle$ is a product state across divisions
$M_{i}^{L}/M_{i}^{R}$, as in Eq. (4.3). Thus the state $|\tilde{\phi}\rangle$
can be created from $\left|0\right\rangle^{\otimes N}$ by acting with non-
overlapping unitaries on regions $M_{i}^{R}M_{i+1}^{L}$ in parallel. Each of
these unitaries is supported on $l$ sites. Then, $|\tilde{\psi}\rangle$ is
related to $|\tilde{\phi}\rangle$ by another set of non-overlapping unitaries
supported on $l$ sites, as shown in Eq. (85). We conclude that
$|\tilde{\psi}\rangle$ can be created from the trivial state by two layers of
parallel unitary operations where each unitary is supported on $l$ sites, as
illustrated in Figure 1. In [6], it is shown how any $l$-qudit unitary can be
decomposed into $O(d^{2l})=O(\chi^{2})$ two-qudit gates, with no need for
ancillas. We can guarantee that these gates are all spatially local by
spending at most depth $O(l)$ performing swap operations to move any two sites
next to each other, a factor only logarithmic in the total depth. This proves
the theorem. ∎

###### Proof of Claim 1.

We prove by induction. Let
$|\tilde{\phi}_{j}\rangle=\Pi_{j}U_{j}\ldots\Pi_{1}U_{1}\left|\psi\right\rangle$.
Note that $\Pi_{i}U_{i}\left|\psi\right\rangle$ is non-zero for all $i$, so in
particular $|\tilde{\phi}_{1}\rangle$ is non-zero. Furthermore we note that,
if it is non-zero, $|\tilde{\phi}_{j}\rangle$ can be written as a product
state
$\left|\alpha^{\prime}_{j}\right\rangle_{L_{j}M_{j}^{L}}\otimes\left|\beta_{j}\right\rangle_{M_{j}^{R}R_{j}}$
for some unnormalized but non-zero state
$\left|\alpha^{\prime}_{j}\right\rangle$, and the reduced density matrix of
$|\tilde{\phi}_{j}\rangle$ on $R_{j}$ is $\rho^{\prime}_{R_{j}}$. If we assume
$|\tilde{\phi}_{j}\rangle$ is non-zero then we can write

$\displaystyle|\tilde{\phi}_{j+1}\rangle$
$\displaystyle=\Pi_{j+1}U_{j+1}|\tilde{\phi}_{j}\rangle$
$\displaystyle=\left|\alpha_{j}^{\prime}\right\rangle\otimes\Pi_{j+1}U_{j+1}\left|\beta_{j}\right\rangle$
(90)

and

$\displaystyle\lVert|\tilde{\phi}_{j+1}\rangle\rVert^{2}$
$\displaystyle=\lVert\left|\alpha_{j}^{\prime}\right\rangle\otimes\Pi_{j+1}U_{j+1}\left|\beta_{j}\right\rangle\rVert^{2}$
$\displaystyle=\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}\lVert\Pi_{j+1}U_{j+1}\left|\beta_{j}\right\rangle\rVert^{2}$
$\displaystyle=\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}\text{Tr}(\Pi_{j+1}U_{j+1}\left|\beta_{j}\right\rangle\left\langle\beta_{j}\right|U_{j+1}^{\dagger}\Pi_{j+1})$
$\displaystyle=\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}\text{Tr}(\Pi_{j+1}U_{j+1}\rho^{\prime}_{R_{j}}U_{j+1}^{\dagger}\Pi_{j+1})$
$\displaystyle\geq\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}\text{Tr}(\Pi_{j+1}U_{j+1}\rho_{R_{j}}U_{j+1}^{\dagger}\Pi_{j+1})$
$\displaystyle-\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}\lVert\rho_{R_{j}}-\rho^{\prime}_{R_{j}}\rVert_{1}$
$\displaystyle\geq\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}\text{Tr}(\Pi_{j+1}U_{j+1}\rho
U_{j+1}^{\dagger}\Pi_{j+1})$
$\displaystyle-\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}\lVert\rho_{R_{j}}-\rho^{\prime}_{R_{j}}\rVert_{1}$
$\displaystyle\geq\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}\lVert\Pi_{j+1}U_{j+1}\left|\psi\right\rangle\rVert^{2}$
$\displaystyle-\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}\lVert\rho_{R_{j}}-\rho^{\prime}_{R_{j}}\rVert_{1}$
$\displaystyle\geq\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}(1-C\exp(-l/\xi^{\prime\prime}))^{2}$
$\displaystyle-\lVert\left|\alpha^{\prime}_{j}\right\rangle\rVert^{2}C\exp(-l/\xi^{\prime\prime})$
$\displaystyle>0$

as long as $l\geq\xi^{\prime\prime}\log(3C)$. ∎

###### Proof of Claim 2.

First, consider the cut $M_{i}^{L}/M_{i}^{R}$ during the formation of the
state $|\tilde{\phi}\rangle$. When the projector $\Pi_{i}$ is applied, the
state becomes a product state across this cut. The remaining operators are
$U_{j}$ and $\Pi_{j}$ with $j>i$, and thus they have no effect on the Schmidt
rank across the $M_{i}^{L}/M_{i}^{R}$ cut, meaning $|\tilde{\phi}\rangle$ is a
product state across each of these cuts, or in other words

$\displaystyle|\tilde{\phi}\rangle={}$
$\displaystyle\left|\phi_{1}\right\rangle_{M_{0}M_{1}^{L}}\otimes\left|\phi_{2}\right\rangle_{M_{1}^{R}M_{2}^{L}}\otimes\ldots$
$\displaystyle\ldots\otimes\left|\phi_{n}\right\rangle_{M_{n-1}^{R}M_{n}^{L}}\otimes\left|\phi_{n+1}\right\rangle_{M_{n}^{R}M_{n+1}}.$
(91)

Given an integer $k$ and a contiguous region $X$ of length $k$, we can find
integers $a$ and $b$ such that $Y=M_{a}^{R}M_{a+1}\ldots M_{b-1}M_{b}^{L}$
contains $X$ and $\lvert b-a\rvert\leq k/l+2$. Then

$\displaystyle\text{Tr}_{Y^{c}}(|\tilde{\phi}\rangle\langle\tilde{\phi}|)$
$\displaystyle={}$
$\displaystyle\left|\phi_{a+1}\right\rangle\left\langle\phi_{a+1}\right|\otimes\ldots\otimes\left|\phi_{b}\right\rangle\left\langle\phi_{b}\right|$
$\displaystyle\propto{}$
$\displaystyle\text{Tr}_{L_{a}M_{a}^{L}M_{b}^{R}R_{b}}\left(\Pi_{b}U_{b}\ldots\Pi_{a}U_{a}\left|\psi\right\rangle\left\langle\psi\right|U_{a}^{\dagger}\Pi_{a}\ldots
U_{b}^{\dagger}\Pi_{b}\right).$ (92)

The advantage here is that all of the $U_{i}$ and $\Pi_{i}$ for which
$i\not\in[a,b]$ have disappeared. On the other hand, we have

$\displaystyle\text{Tr}_{Y^{c}}(\left|\phi\right\rangle\left\langle\phi\right|)$
$\displaystyle={}$ $\displaystyle\text{Tr}_{Y^{c}}(U_{n}\ldots
U_{1}\left|\psi\right\rangle\left\langle\psi\right|U_{1}^{\dagger}\ldots
U_{n}^{\dagger})$ $\displaystyle={}$
$\displaystyle\text{Tr}_{L_{a}M_{a}^{L}M_{b}^{R}R_{b}}\left(U_{b}\ldots
U_{a}\left|\psi\right\rangle\left\langle\psi\right|U_{a}^{\dagger}\ldots
U_{b}^{\dagger}\right).$ (93)

Note that, since

$U_{i}\left|\psi\right\rangle=\sqrt{1-\delta_{i}^{2}}\left|\alpha_{i}\right\rangle\otimes\left|\beta_{i}\right\rangle+\delta_{i}\left|\phi_{i}^{\prime}\right\rangle,$
(94)

we can say that

$\Pi_{i}U_{i}\left|\psi\right\rangle=U_{i}\left|\psi\right\rangle-\delta_{i}(I-\Pi_{i})\left|\phi_{i}^{\prime}\right\rangle,$
(95)

and thus

$\displaystyle\Pi_{b}U_{b}\ldots\Pi_{a}U_{a}\left|\psi\right\rangle$
$\displaystyle={}$ $\displaystyle U_{b}\ldots U_{a}\left|\psi\right\rangle-$
$\displaystyle\sum_{j=a}^{b}\delta_{j}(\Pi_{b}U_{b}\ldots\Pi_{j+1}U_{j+1})(I-\Pi_{j})\left|\phi_{j}^{\prime}\right\rangle$
$\displaystyle\equiv{}$ $\displaystyle U_{b}\ldots
U_{a}\left|\psi\right\rangle-\delta\left|\phi^{\prime}\right\rangle,$ (96)

where $\delta\leq\sqrt{\sum_{j=a}^{b}\delta_{j}^{2}}$ and normalized
$\left|\phi^{\prime}\right\rangle$ is normalized. This implies

$\frac{\lvert\left\langle\psi\right|U_{a}^{\dagger}\ldots
U_{b}^{\dagger}\Pi_{b}U_{b}\ldots\Pi_{a}U_{a}\left|\psi\right\rangle\rvert}{\lVert\Pi_{a}\ldots
U_{b}^{\dagger}\Pi_{b}U_{b}\ldots\Pi_{a}U_{a}\left|\psi\right\rangle\rVert}\geq\sqrt{1-\delta^{2}},$
(97)

which shows that $D_{1}(\tau,\tau^{\prime})\leq\delta$, where

$\displaystyle\tau=U_{b}\ldots
U_{a}\left|\psi\right\rangle\left\langle\psi\right|U_{a}^{\dagger}\ldots
U_{b}^{\dagger}$
$\displaystyle\tau^{\prime}=\frac{\Pi_{b}U_{b}\ldots\Pi_{a}U_{a}\left|\psi\right\rangle\left\langle\psi\right|U_{a}^{\dagger}\Pi_{a}\ldots
U_{b}^{\dagger}\Pi_{b}}{\lVert\Pi_{a}\ldots
U_{b}^{\dagger}\Pi_{b}U_{b}\ldots\Pi_{a}U_{a}\left|\psi\right\rangle\rVert^{2}}$
(98)

and hence

$\displaystyle
D_{1}(\text{Tr}_{X^{c}}(\left|\phi\right\rangle\left\langle\phi\right|),\text{Tr}_{X^{c}}(|\tilde{\phi}\rangle\langle\tilde{\phi}|))$
$\displaystyle\leq
D_{1}(\text{Tr}_{Y^{c}}(\left|\phi\right\rangle\left\langle\phi\right|),\text{Tr}_{Y^{c}}(|\tilde{\phi}\rangle\langle\tilde{\phi}|))$
$\displaystyle\leq D_{1}(\tau_{Y},\tau^{\prime}_{Y})\leq
D_{1}(\tau,\tau^{\prime})\leq\delta$ $\displaystyle\leq
C\sqrt{k/l+3}\exp(-l/\xi^{\prime\prime}).$ (99)

This holds for any region $X$ of length $k$, so this proves the claim. ∎

###  4.4 Proof of Theorem 3

First we state a lemma that will do most of the legwork needed for Theorem 3.
Then we prove Theorem 3.

######  Lemma 8.

Suppose, for $j=0,1$, $H^{(j)}$ is a translationally invariant Hamiltonian
defined on a chain of length $N$ and local dimension $d$. Further suppose that
$|\psi^{(j)}\rangle$ is the unique ground state of $H^{(j)}$ with energy
$E_{0}^{(j)}$, and let $\Delta^{(j)}$ be the spectral gap of $H^{(j)}$. We may
form a new chain with local dimension $2d$ by adding an ancilla qubit to each
site of the chain. Then there is a Hamiltonian $K$ defined on this chain such
that

  1. (1)

The ground state energy of $K$ is

$E_{0}^{K}=\frac{1}{3}\min_{j}E_{0}^{(j)}.$ (100)

  2. (2)

If $E_{0}^{(0)}<E_{0}^{(1)}$, then the ground state of $K$ is
$\left|0^{N}\right\rangle_{A}\otimes|\psi^{(0)}\rangle$ and if
$E_{0}^{(1)}<E_{0}^{(0)}$, then the ground state is
$\left|1^{N}\right\rangle_{A}\otimes|\psi^{(1)}\rangle$, where $A$ refers to
the $N$ ancilla registers collectively.

  3. (3)

If $E_{0}^{(0)}<E_{0}^{(1)}$, then the spectral gap of $K$ is at least
$\min(\Delta^{(0)},E_{0}^{(1)}-E_{0}^{(0)},1)/3$ and if
$E_{0}^{(1)}<E_{0}^{(0)}$, then the spectral gap of $K$ is at least
$\min(\Delta^{(1)},E_{0}^{(0)}-E_{0}^{(1)},1)/3$.

###### Proof of Lemma 8.

Note that a variant of this lemma is employed in [3, 7, 4] to show the
undecidability of certain properties of translationally invariant
Hamiltonians.

Since $H^{(j)}$ is translationally invariant, it is specified by its single
interaction term $H^{(j)}_{i,i+1}$:

$H^{(j)}=\sum_{i=1}^{N-1}H^{(j)}_{i,i+1}.$ (101)

The Hamiltonian $K$ will be defined over a new chain where we attach to each
site an ancilla qubit, increasing the local Hilbert space dimension by a
factor of 2. We refer to the ancilla associated with site $i$ by the subscript
$A_{i}$, and we refer to the collection of ancillas together with the
subscript $A$. Operators or states without a subscript are assumed to act on
the original $d$-dimensional part of the local Hilbert spaces. Let

$K=\sum_{i=1}^{N-1}K_{i,i+1},$ (102)

where

$\displaystyle K_{i,i+1}={}$
$\displaystyle\;\;\;\frac{1}{3}H^{(0)}_{i,i+1}\otimes\left|00\right\rangle\left\langle
00\right|_{A_{i}A_{i+1}}$ (103)
$\displaystyle+\frac{1}{3}H^{(1)}_{i,i+1}\otimes\left|11\right\rangle\left\langle
11\right|_{A_{i}A_{i+1}}$ (104)
$\displaystyle+I_{i,i+1}\otimes\left(\left|01\right\rangle\left\langle
01\right|+\left|10\right\rangle\left\langle 10\right|\right)_{A_{i}A_{i+1}}$
(105)

with $I_{i,i+1}$ denoting the identity operation on sites $i$ and $i+1$. In
this form it is clear that $K$ is a nearest-neighbor translationally invariant
Hamiltonian and that each interaction term has operator norm 1 (a requirement
under our treatment of 1D Hamiltonians). The picture we get is that if two
neighboring ancillas are both $\left|0\right\rangle$, then $H^{(0)}_{i,i+1}/3$
is applied, if both are $\left|1\right\rangle$ then $H^{(1)}_{i,i+1}/3$ is
applied, and if the ancillas are different, then $I_{i,i+1}$ is applied.
Following this intuition, we can rewrite $K$ as follows.

$K=\sum_{x=0}^{2^{N}-1}\left(\left|x\right\rangle\left\langle
x\right|_{A}\otimes\sum_{i=1}^{N-1}K_{x,i}\right),$ (106)

where the first sum is over all settings of the ancillas and the operator
$K_{x,i}$ acts on the non-ancilla portion of sites $i$ and $i+1$, with

$K_{x,i}=\begin{cases}H^{(0)}_{i,i+1}/3&\text{ if }x_{i}=x_{i+1}=0\\\
H^{(1)}_{i,i+1}/3&\text{ if }x_{i}=x_{i+1}=1\\\ I_{i,i+1}&\text{ if }x_{i}\neq
x_{i+1}\end{cases}$ (107)

We analyze the spectrum of $K$. If $H^{(j)}$ has eigenvalues $E^{(j)}_{n}$
with corresponding eigenvectors $|\phi^{(j)}_{n}\rangle$ (where $E^{(j)}_{n}$
is non-decreasing with increasing integers $n$), then the states
$\left|0^{N}\right\rangle_{A}\otimes|\phi^{(0)}_{n}\rangle$ and
$\left|1^{N}\right\rangle_{A}\otimes|\phi^{(1)}_{n}\rangle$ are eigenstates of
$K$ with eigenvalues $E^{(0)}_{n}/3$ and $E^{(1)}_{n}/3$, respectively.

Recall that eigenvectors of a Hamiltonian span the whole Hilbert space over
which the Hamiltonian is defined. Therefore, the eigenvectors of $K$ listed
above span the entire sectors of the Hilbert space associated with the
ancillas set to $\left|0^{N}\right\rangle_{A}$ or
$\left|1^{N}\right\rangle_{A}$. Suppose $\left|\phi\right\rangle$ is another
eigenvector of $K$. Since it is orthogonal to all of the previously listed
eigenvectors, $\left|\phi\right\rangle$ can be written

$\left|\phi\right\rangle=\sum_{x=1}^{2^{N}-2}\alpha_{x}\left|x\right\rangle_{A}\otimes\left|\eta_{x}\right\rangle$
(108)

for some set of complex coefficients $\alpha_{x}$ with
$\sum_{x}\lvert\alpha_{x}\rvert^{2}=1$ and some set of normalized states
$\left|\eta_{x}\right\rangle$. The sum explicitly leaves out the $x=0=0^{N}$
and $x=2^{N}-1=1^{N}$ binary strings because these states lie in the subspace
spanned by eigenstates already listed. We wish to lower bound the energy of
the state $\left|\phi\right\rangle$, i.e., the quantity

$\displaystyle\left\langle\phi\right|K\left|\phi\right\rangle$
$\displaystyle=\sum_{x=1}^{2^{N}-2}\sum_{y=1}^{2^{N}-2}\alpha^{*}_{x}\alpha_{y}\left\langle
x\right|_{A}\left\langle\eta_{x}\right|K\left|y\right\rangle_{A}\left|\eta_{y}\right\rangle$
$\displaystyle=\sum_{x=1}^{2^{N}-2}\sum_{y=1}^{2^{N}-2}\sum_{z=0}^{2^{N}-1}\alpha^{*}_{x}\alpha_{y}\left\langle
x|z\right\rangle\left\langle
z|y\right\rangle_{A}\left\langle\eta_{x}\right|\sum_{i=1}^{N-1}K_{z,i}\left|\eta_{y}\right\rangle$
$\displaystyle=\sum_{x=1}^{2^{N}-2}\lvert\alpha_{x}\rvert^{2}\left\langle\eta_{x}\right|\sum_{i=1}^{N-1}K_{x,i}\left|\eta_{x}\right\rangle.$
(109)

We make the following claim:

######  Claim 3.

For any state $\left|\eta\right\rangle$, and any $1\leq a<b\leq N$

$\left\langle\eta\right|\sum_{i=a}^{b-2}H^{(j)}_{i,i+1}\left|\eta\right\rangle\geq\frac{b-a}{N-1}E_{0}^{(j)}-1.$
(110)

###### Proof of Claim 3.

First we prove it in the case that $M:=b-a$ divides $N$. Let region $Y$ refer
to sites $[a,b-1]$, let
$\rho=\text{Tr}_{Y^{c}}(\left|\eta\right\rangle\left\langle\eta\right|)$, and
let $\sigma=\rho\otimes\ldots\otimes\rho$ be $N/M$ copies of $\rho$ which
covers all $N$ sites. Then

$\displaystyle\text{Tr}(H^{(j)}\sigma)=$
$\displaystyle\frac{N}{M}\left\langle\eta\right|\sum_{i=a}^{b-2}H^{(j)}_{i,i+1}\left|\eta\right\rangle$
$\displaystyle+\sum_{k=1}^{N/M-1}\left\langle\eta\right|H^{(j)}_{kM,kM+1}\left|\eta\right\rangle$
$\displaystyle\leq$
$\displaystyle\frac{N}{M}\left\langle\eta\right|\sum_{i=a}^{b-2}H^{(j)}_{i,i+1}\left|\eta\right\rangle+\left(\frac{N}{M}-1\right),$
(111)

where the last line follows from the fact that the interaction strength
$\lVert H^{(j)}_{i,i+1}\rVert\leq 1$. Moreover, by the variational principle,
$\text{Tr}(H^{(j)}\sigma)\geq E_{0}^{(j)}$. These observations together yield

$\left\langle\eta\right|\sum_{i=a}^{b-2}H^{(j)}_{i,i+1}\left|\eta\right\rangle\geq(M/N)(E_{0}^{(j)}+1)-1,$
(112)

which implies the statement of the claim.

Now suppose $M$ does not divide $N$. We decompose $N=sM+r$ for non-negative
integers $s$ and $r<M$. Let
$\sigma=\rho\otimes\ldots\otimes\rho\otimes\left|\nu\right\rangle\left\langle\nu\right|$
where there are $s$ copies of $\rho$ and $\left|\nu\right\rangle$ is the exact
ground state of $\sum_{i=N-r+1}^{N-1}H^{(j)}_{i,i+1}$, which has energy
$E_{r}$. Then

$\text{Tr}(H^{(j)}\sigma)\leq
s\left\langle\eta\right|\sum_{i=a}^{i_{0}+M_{0}-2}H^{(j)}_{i,i+1}\left|\eta\right\rangle+E_{r}+s.$
(113)

Here we invoke the variational principle twice. First, note that the
expectation value of $\sum_{i=N-r+1}^{N-1}H^{(j)}_{i,i+1}$ in the state
$|\phi_{0}^{(j)}\rangle$ (the exact ground state of the whole chain) is
exactly $(r-1)E_{0}^{(j)}/(N-1)$. Since $\left|\nu\right\rangle$ is the exact
ground state of that Hamiltonian, $E_{r}$ must be smaller than this quantity.
Second, as before, $\text{Tr}(H^{(j)}\sigma)\geq E^{(j)}_{0}$. Combining these
observations yields

$\displaystyle\left\langle\eta\right|\sum_{i=i_{0}}^{i_{0}+M-1}H^{(j)}_{i,i+1}\left|\eta\right\rangle$
$\displaystyle\geq\frac{1}{s}E_{0}^{(j)}\left(1-\frac{r-1}{N-1}\right)-1$
$\displaystyle=\frac{M}{N-1}E_{0}^{(j)}-1.$ (114)

∎

Now we use this claim to complete the proof of Lemma 8. For any binary string
$x$ we can associate a sequence of indices
$1=i_{0}<i_{1}<\ldots<i_{m}<i_{m+1}=N+1$ such that $x_{i}=x_{i_{k}}$ for all
$k=1,\ldots,m$ and all $i$ in the interval $[i_{k},i_{k+1}-1]$. Moreover we
require $x_{i_{k-1}}\neq x_{i_{k}}$. In other words, $x$ can be decomposed
into substrings of consecutive 0s and consecutive 1s, with $i_{j}$
representing the index of the “domain wall” that separates a substring of 0s
from a substring of 1s. The parameter $m$ is the number of domain walls. Using
this notation, and letting $E_{0}^{K}=\min_{j}E_{0}^{(j)}/3$ we can rewrite

$\displaystyle\left\langle\eta_{x}\right|\sum_{i=1}^{N-1}K_{x,i}\left|\eta_{x}\right\rangle={}$
$\displaystyle\sum_{k=0}^{m}\left\langle\eta_{x}\right|\sum_{i=i_{k}}^{i_{k+1}-2}\frac{1}{3}H_{i,i+1}^{(x_{i_{k}})}\left|\eta_{x}\right\rangle$
$\displaystyle+\sum_{k=1}^{m}\left\langle\eta_{x}\right|I_{i_{k}-1,i_{k}}\left|\eta_{x}\right\rangle$
$\displaystyle\geq{}$
$\displaystyle\sum_{k=0}^{m}\left(\frac{i_{k+1}-i_{k}}{3(N-1)}E_{0}^{(x_{i_{j}})}-\frac{1}{3}\right)+m$
$\displaystyle\geq{}$ $\displaystyle E_{0}^{K}+\frac{2m-1}{3}.$ (115)

For any $x$ other than $0^{N}$ and $1^{N}$, there is at least one domain wall
and $m\geq 1$. Thus we can say

$\left\langle\phi\right|K\left|\phi\right\rangle\geq E_{0}^{K}+1/3.$ (116)

We have shown that any state orthogonal to the states
$\left|0^{N}\right\rangle_{A}\otimes|\phi^{(0)}_{n}\rangle$ and
$\left|1^{N}\right\rangle_{A}\otimes|\phi^{(1)}_{n}\rangle$ will have energy
at least 1/3 larger than the lowest energy state of the system. Without loss
of generality, suppose $E_{0}^{(0)}\leq E_{0}^{(1)}$. Then, the ground state
energy is $E_{0}^{K}=E_{0}^{(0)}/3$ and the ground state is
$\left|0^{N}\right\rangle_{A}\otimes|\phi^{(0)}_{0}\rangle$ (note that in the
statement of the Lemma we have
$\left|\psi^{(0)}\right\rangle=\left|\phi_{0}^{(0)}\right\rangle$). The first
excited state is either
$\left|0^{N}\right\rangle_{A}\otimes|\phi^{(0)}_{1}\rangle$,
$\left|1^{N}\right\rangle_{A}\otimes|\phi^{(1)}_{0}\rangle$, or lies outside
the sector associated with ancillas $\left|0^{N}\right\rangle$ and
$\left|1^{N}\right\rangle$, whichever has lowest energy. The three cases lead
to spectral gaps of $\Delta^{(0)}/3$, $(E_{0}^{(1)}-E_{0}^{(0)})/3$, and
something larger than 1/3 (due to Eq. (116)), respectively. This proves all
three items of the Lemma. ∎

###### Proof of Theorem 3.

We begin by specifying a family of Hamiltonians, parameterized by
$t\in[0,1/2]$ and defined over a chain of length $N$ with local dimension $d$.

$H^{Z}(t)=\sum_{i=1}^{N-1}I_{i}\otimes
I_{i+1}-(1-t)\left|0\right\rangle\left\langle
0\right|_{i}\otimes\left|0\right\rangle\left\langle 0\right|_{i+1}$ (117)

The ground state of $H^{Z}(t)$ is the trivial product state
${\left|0\right\rangle}^{\otimes N}$ with ground state energy $t(N-1)$, and
thus energy density $t$. The interaction strength is bounded by $1$ and the
spectral gap is $1-t\geq 1/2$.

Now we construct an algorithm for Problem 1. We are given $H$ as input, with
associated parameters $N$ and $d$, and a lower bound $\Delta$ on the spectral
gap. Let the true ground state energy for $H$ be $E$ and let $u=E/(N-1)$. We
choose a value of $s$ between 0 and $1$, and we apply Lemma 8 to construct a
Hamiltonian $K$ combining Hamiltonians $H/2$ and $H^{Z}(s/2)$. $K$ acts on $N$
sites, has local dimension $2d$, and has spectral gap at least
$\min(\Delta,\lvert s-u\rvert(N-1),1)/6$. We are given a procedure to solve
Problem 2 with $\delta=0.9$ for a single site, i.e. we can estimate the
expectation value of any single site observable in the ground state of $K$. If
$s<u$, the true reduced density matrix of $K$ will have its ancilla bits all
set to 1. If $s>u$ the reduced density matrix corresponds to the reduced
density matrix of $H$ with all its ancilla bits set to 0. Thus we can choose
our single site operator to be the $Z_{A}$ operator that has eigenvalue $1$
for states whose ancilla bit is $\left|0\right\rangle$ and eigenvalue $-1$ for
states whose ancilla bit is $\left|1\right\rangle$. If we have a procedure to
determine $\left\langle\psi\right|Z_{A}\left|\psi\right\rangle$ to precision
0.9 then we can determine the setting of one of the ancilla bits in the ground
state and thus determine whether $u$ is larger or smaller than $s$. The time
required to make this determination is $f(\min(\Delta,(N-1)\lvert
s-u\rvert,1)/6,2d,N)$. Because we have control over $s$, we can use this
procedure to binary search for the value of $u$. We assume we are given a
lower bound on $\Delta$ but since we do not know $u$ a priori, we have no
lower bound on $\lvert s-u\rvert$, so we may not know how long to run the
algorithm for Problem 2 in each step of the binary search. If our desired
precision is $\epsilon$, we will impose a maximum runtime of
$f(\min(\Delta,(N-1)\epsilon/2,1)/6,2d,N)$ for each step. Thus, if we choose a
value of $s$ for which $\lvert s-u\rvert<\epsilon/2$, the output of this step
of the binary search may be incorrect. After such a step, our search window
will be cut in half and the correct value of $u$ will no longer be within the
window. However, $u$ will still lie within $\epsilon/2$ of one edge of the
window. Throughout the binary search, some element of the search window will
always lie within $\epsilon/2$ of $u$, so if we run the search until the
window has width $\epsilon$ and output the value $\tilde{u}$ in the center of
the search window, we are guaranteed that $\lvert
u-\tilde{u}\rvert\leq\epsilon$. The number of steps required is
$O(\log(1/\epsilon))$ and the time for each step is
$f(\min(2\Delta,(N-1)\epsilon,2)/12,2d,N)$, yielding the statement of the
theorem. ∎

##  5 Discussion

Our results paint an interesting landscape of the complexity of approximating
ground states of gapped nearest-neighbor 1D Hamiltonians locally. On the one
hand, we show all $k$-local properties of the ground state can be captured by
an MPS with only constant bond dimension, an improvement over the
$\text{poly}(N)$ bond dimension required to represent the global
approximation. This constant scales like a polynomial in $k$ and $1/\epsilon$,
when parameters like $\Delta$, $\xi$, and $d$ are taken as constants. On the
other hand, we give evidence that, at least for the case where the Hamiltonian
is translationally invariant, finding the local approximation may not offer a
significant speedup over finding the global approximation: we have shown that
the ability to find even a constant-precision estimate of local properties
would allow one to learn a constant-precision estimate of the ground state
energy with only $O(\log(N))$ overhead. This reduction does not allow one to
learn any global information about the state besides the ground state energy,
so it falls short of giving a concrete relationship between the complexity of
the global and local approximations. Nonetheless, the reduction has concrete
consequences. In particular, at least one of the following must be true about
translationally invariant gapped Hamiltonians on chains of length $N$:

  1. (1)

The ground state energy can be estimated to $O(1)$ precision in $O(\log(N))$
time.

  2. (2)

Local properties of the ground state cannot be estimated to $O(1)$ precision
in time independent of $N$.

In particular, the second item, if true, would seem to imply that, in the
translationally invariant case when $N\rightarrow\infty$, local properties
cannot be estimated at all.

Indeed, it is when the chain is very long, or when we are considering the
thermodynamic limit directly that our results are most relevant. In the
translationally invariant case as $N\rightarrow\infty$, our first proof method
(Theorem 1) yields a local approximation that is a translationally invariant
MPS. However, the MPS is non-injective and the state is a macroscopic
superposition on the infinite chain. Thus the bulk tensors alone do not
uniquely define the state and specification of a boundary tensor at infinity
is also required [31, 38]. Our second proof method (Theorem 2), on the other
hand, yields a periodic MPS (with period $O(\log(k/\epsilon^{2}))$) that is
injective and can be constructed by a constant-depth quantum circuit made from
spatially local gates. If we allow the locality of the gates to be
$O(\log(k/\epsilon^{2}))$, then the circuit can have depth 2, as in Figure 1.
If we require the locality of the gates be only a constant, say 2, then the
circuit can have depth $\text{poly}(k,1/\epsilon)$.

The fact that the approximation is injective perhaps makes the latter method
more powerful. Injective MPS are the exact ground states of some local gapped
Hamiltonian [9, 25]. Additionally, non-injective MPS form a set of measure
zero among the entire MPS manifold, so variational algorithms that explore the
whole manifold are most compatible with an injective approximation. In fact,
since the approximation can be generated from a constant-depth circuit, the
result justifies a more restricted variational ansatz using states of that
form. This ansatz could provide several advantages over MPS in terms of number
of parameters needed and ability to quickly calculate local observables, like
the energy density. However, algorithms that perform variational optimization
of the energy density generally suffer from two issues, regardless of the