# Circuit depth versus energy in topologically ordered systems

Arkin Tikku Centre for Engineered Quantum Systems, University of Sydney,
Sydney, New South Wales 2006, Australia<EMAIL_ADDRESS>Isaac H.
Kim Department of Computer Science, University of California, Davis, CA 95616,
USA.
<EMAIL_ADDRESS>
###### Abstract

We prove a nontrivial circuit-depth lower bound for preparing a low-energy
state of a locally interacting quantum many-body system in two dimensions,
assuming the circuit is geometrically local. For preparing any state which has
an energy density of at most $\epsilon$ with respect to Kitaev’s toric code
Hamiltonian on a two dimensional lattice $\Lambda$, we prove a lower bound of
$\Omega\left(\min\left(1/\epsilon^{\frac{1-\alpha}{2}},\sqrt{\absolutevalue{\Lambda}}\right)\right)$
for any $\alpha>0$. We discuss two implications. First, our bound implies that
the lowest energy density obtainable from a large class of existing
variational circuits (e.g., Hamiltonian variational ansatz) cannot, in
general, decay exponentially with the circuit depth. Second, if long-range
entanglement is present in the ground state, this can lead to a nontrivial
circuit-depth lower bound even at nonzero energy density. Unlike previous
approaches to prove circuit-depth lower bounds for preparing low energy
states, our proof technique does not rely on the ground state to be
degenerate.

##  1 Introduction

Understanding the properties of ground- and excited states of local
Hamiltonians and calculating their energies is pivotal to advancing condensed
matter physics and quantum chemistry [1]. Tackling these problems using
classical methods is in general challenging due to the exponential nature of
the state space. Even on a quantum computer, it is generally not possible to
efficiently estimate ground state energies of local Hamiltonians up to
polynomial precision, as established by the quantum Cook-Levin theorem [2].
Finding ways to solve this problem efficiently for restricted classes of
Hamiltonians is therefore an active area of research [3].

Recent experimental advances have moreover spurred the study of this problem
using small-scale, noisy quantum devices [4]. Given the limitations of current
hardware, such as short coherence times, very few qubits and limited
connectivity, it is therefore important to understand which lattice models of
interest allow for resource-efficient preparation in this constrained setting.
A reasonable metric for this assessment is circuit depth, since the most
common state preparation methods on near-term devices rely on preparing a
state using some variational ansatz quantum circuit [5].

The hope is then that there exist interesting models that require only modest
circuit depth, to give good approximations to some target state or energy. If,
for example, circuits of polynomial depth are required, one may worry that the
short coherence times of such devices would prohibit a good quality of
approximation.

In fact, for many commonly studied lattice models in 2D [6, 7], preparing
exact ground states is known to be a task that in fact does require circuits
of depth polynomial in the system size if the gates are nearest-neighbor only
[8, 9]. One may however hope that preparing _some_ low-energy state as opposed
to the exact ground state might be significantly easier.

In this work, we show that preparing such states still requires circuits of
depth polynomial in their inverse energy density. Our main technical
contribution is to give a rigorous proof technique for circuit lower bounds of
low-energy states of Kiteav’s toric code with no assumption on the dimension
of the ground space.

We do so by generalizing a formalism introduced in [9]. This formalism allows
to prove circuit depth lower bounds for states for which one can find non-
trivial pairs of operators that act trivially on sufficiently small
subsystems. Finding such operators for an arbitrary state is in general hard.

To prove our circuit depth lower bound for low-energy states, we extend this
formalism to allow for operators that slightly perturb the state on the
subsystem. We show that operators that act trivially on ground states satisfy
this criterion when acting on sufficiently small subsystems of low-energy
states and use this fact to arrive at our main result.

Interestingly, this proof technique does not rely on the dimension of the
ground space of the model. It can furthermore be applied to low-energy states
of other frustration-free, local commuting models in 2D such as the quantum
double or Levin-Wen models [6, 7].

Circuit depth lower bounds for low-energy states of local Hamiltonians have
meanwhile played an important role in the quest for a quantum analogue of the
PCP theorem [10, 11, 12]. These results established circuit lower bounds for
stabilizer Hamiltonians that are not geometrically local in any fixed spatial
dimension and considered their preparation assuming quantum circuits with all-
to-all connectivity. An additional key assumption of these works is that
dimension of the ground space grows with system size. Our work lifts this
assumption and gives a clean and rigorous way to prove lower bounds on the
depth of geometrically local circuits that prepare low-energy states of
frustration-free, local commuting models with arbitrary ground space
dimension. We believe it should be possible to generalize our techniques to
local Hamiltonians and circuits on arbitrary interaction graphs and leave this
for future work.

Our paper is structured as follows: in Section 2 we cover notation and some
basic definitions. In Section 3, we state our main result and discuss it in a
broader context. In Section 4 we introduce the notions of exact and
approximate local invisibility of operators, which will form the backbone of
our circuit lower bound technique. In Section 5 we will introduce a formal aid
that we call a local marginal projector. This type of projection will be key
to proving lemmas en route to our main result. In Section 6, we introduce the
twist product, which gives us a way to detect long-range entanglement in a
state when combined with locally invisible operators. In Section 7 we finally
discuss how to adapt our proof technique to low-energy states and prove the
main result. We conclude with some discussion on potential future applications
of our technique in Section 8.

##  2 Preliminaries and notation

Here we cover some basic definitions and notation about quantum spin systems
on lattices and distance measures used throughout the paper.

We consider a quantum spin system on a 2D lattice $\Lambda$ with arbitrary
boundary conditions. For any pair of sites $v,u\in\Lambda$, their distance
$d(v,u)$ is the minimal number of edges that connect $v$ and $u$. For
$A,B\subset\Lambda$, their distance is defined as

$d(A,B):=\min_{u\in A,v\in B}d(u,v).$ (1)

For any site $v\in\Lambda$, define a $r$-disk at $v$ as

$v(r):=\\{u:d(v,u)\leq r\\}.$ (2)

More generally, for any set of sites $A\subset\Lambda$, define

$A(r):=\bigcup_{v\in A}v(r)$ (3)

as a $r$-thickening of the region $A$. Given a disc $A$ we will sometimes
refer to $A(-D)$ as the $D$-interior of $A$, which defines all points inside
of $A$ that are a distance $D$ away from the boundary of $A$, i.e.
$A(-D):=\\{v\in A|d(v,x)>D,\forall x\in A^{c}\\}$. We will denote the radius
of a disc $A$ by $\text{rad}(A)$.

The global Hilbert space is assumed to have a tensor product structure:

$\mathcal{H}_{\Lambda}:=\bigotimes_{v\in\Lambda}\mathcal{H}_{v},$ (4)

where $\dim(\mathcal{H}_{v})<\infty$. While we will refer to lattice sites as
qubits throughout the text, we shall note that all of our results equally
apply to qudit systems. We shall define the Hilbert space associated with
subsystem $A\subset\Lambda$ as $\mathcal{H}_{A}:=\bigotimes_{v\in
A}\mathcal{H}_{v}$. The supports of the operators and density matrices shall
be denoted in their subscripts by capital roman letters, unless this is
obvious from the context. For instance, $O_{A}$ and $\rho_{A}$ is an operator
and a density matrix, respectively, acting on $\mathcal{H}_{A}$. Given a pure
state vector $\ket{\psi}_{\Lambda}$ we shall denote its associated density
matrix by $\rho_{\Lambda}$ and it’s reduced state (marginal) onto region
$A\subset\Lambda$ by $\rho_{A}$, i.e. $\rho_{A}=\Tr_{A^{c}}[\rho_{\Lambda}]$,
where $A^{c}:=\Lambda\backslash A$, i.e. it denotes the complement of $A$ in
$\Lambda$. Given an operator $O$, we shall denote its support as
$\text{supp}(O)$.

The fidelity between two quantum states
$\rho,\sigma\in\mathcal{D}(\mathcal{H})$ is denoted by
$F(\rho,\sigma)=\|\rho^{\frac{1}{2}}\sigma^{\frac{1}{2}}\|_{1}^{2}$, where
$\lVert.\rVert_{1}$ denotes the Schatten 1-norm. A particularly convenient
distance measure for our purposes will be the _purified distance_ [13],
defined as

$D_{p}(\rho,\sigma):=\sqrt{1-F(\rho,\sigma)}.$ (5)

From the Fuchs-van-de-Graaf inequality [14] it follows that the purified
distance upper bounds the trace distance, i.e.

$\displaystyle\frac{1}{2}\left\|{\rho-\sigma}\right\|_{1}\leq
D_{p}{(\rho,\sigma)}.$ (6)

For the special case of pure states, the purified distance equals the trace
distance, i.e. the above inequality is saturated. The purified distance
satisfies several desirable properties [13]. Let
$\Phi:\mathcal{B}(\mathcal{H})\to\mathcal{B}(\mathcal{H}^{\prime})$ be a
completely positive trace-preserving map and $U$ be a unitary. Then

$\displaystyle D_{p}(\rho,\tau)\leq D_{p}(\rho,\sigma)+D_{p}(\sigma,\tau),$
(Triangle inequality) (7) $\displaystyle D_{p}(\Phi(\rho),\Phi(\tau))\leq
D_{p}(\rho,\sigma),$ (Monotonicity) (8) $\displaystyle D_{p}(U\rho
U^{\dagger},U\sigma U^{\dagger})=D_{p}(\rho,\sigma)$ (Unitary invariance) (9)

We will consider geometrically local Hamiltonians $H_{\Lambda}$ on a regular
lattice that without loss of generality can be written in the form:

$H_{\Lambda}=\sum_{X\subset\Lambda}h_{X},$ (10)

where each $h_{X}$ is a hermitian operator supported on a set of sites
contained in a $2\times 2$ square. Let us remark that one can always coarse-
grain a locally interacting quantum many-body systems in two dimensions to
ensure such a form. We shall choose a normalization condition such that each
$h_{X}$ satisfies $\left\|{h_{X}}\right\|_{\infty}=1$, where
$\left\|{\cdot}\right\|_{\infty}$ is the operator norm. We shall also assume
that the ground state energy is chosen to be $0$; this can be always achieved
by shifting and reweighting the terms of the Hamiltonian. For our purposes, it
will suffice to restrict ourselves to Hamiltonians $H_{\Lambda}$ for which the
global ground state is also a ground state of all the local terms, i.e. if
$\Pi^{0}_{\Lambda}$ is the projection onto the ground space of $H_{\Lambda}$
and $\Pi^{0}_{X}$ is the projection onto the ground space of a local term
$h_{X}$, then $\Pi^{0}_{X}\Pi^{0}_{\Lambda}=0$. This property is known as
frustration-freeness.

Apart from ground states, we will also be interested in low-energy states
$\rho^{\epsilon}$ of a Hamiltonian $H$, where
$\Tr[H\rho^{\epsilon}]\leq\epsilon\left\|{H}\right\|_{\infty}$ for some small
$\epsilon\in[0,1]$, which we will refer to as the energy density. For lattice
Hamiltonians $H_{\Lambda}$ we will assume that
$\left\|{H_{\Lambda}}\right\|_{\infty}=\mathcal{O}(\absolutevalue{\Lambda})$.

$\bm{s^{X}_{i}}$$\bm{s^{Z}_{i}}$ Figure 1: A $L=6$ instance of the square
toric code lattice with qubits placed on vertices and periodic boundary
conditions. Black faces denote $Z$-type stabilizers and white faces denote
$X$-type stablizers.

While our results apply to more general classes of models such as Kitaev’s
quantum double [6] or the Levin-Wen model [7], we focus on Kitaev’s toric code
[6] for concreteness. We will sometimes refer to the ground spaces of these
models containing states with long-range entanglement or topological order, by
which we mean that they cannot be prepared using geometrically local circuits
of constant depth [9, 8, 15]. This notion can be made more mathematically
precise, as we will do in Section 6.

The toric code Hamiltonian on a lattice $\Lambda$ can be defined in terms of
the generators of the stabilizer group $S^{\text{TC}}_{\Lambda}$ of the toric
code (see [16, 17] for reviews on stabilizer codes and the toric code).
Specifically, one may write it as the sum of projections onto the
$(-1)$-eigenspaces of the generators, so that the toric code forms its ground
space i.e.

$\displaystyle
H_{\Lambda}=\sum_{i}\frac{\mathbbm{1}-s^{X}_{i}}{2}+\sum_{i}\frac{\mathbbm{1}-s^{Z}_{i}}{2},$
(11)

where $\\{s_{i}^{X}\\}$ and $\\{s_{i}^{Z}\\}$ denote the $X$-type and $Z$-type
generators respectively, which are geometrically local (see Figure 1).
Sometimes we will be interested in considering the restriction of the
Hamiltonian $H_{\Lambda}$ defined on the full lattice to a region
$R\subset\Lambda$. Whe shall denote this restricted Hamiltonian as $H_{R}$,
which can be obtained from $H_{\Lambda}$ by simply omitting all the terms in
Equation (11), whose support is not contained in $R$. Sometimes we will be
interested in the projection onto the ground space of $H_{R}$, which we shall
denote as $\Pi_{R}^{0}$,

$\Pi_{R}^{0}:=\prod_{i}\frac{\mathbbm{1}-s^{Z}_{i}}{2}\prod_{i}\frac{\mathbbm{1}-s^{X}_{i}}{2},$
(12)

where once again we only consider $X$-type and $Z$-type generators whose
support is contained in $R$.

##  3 Main Result

Our work considers the following question:

######  Problem.

(Low-energy state preparation) Let $\Lambda$ be a $2D$ lattice and let
$H_{\Lambda}$ be a frustration-free, commuting Hamiltonian whose ground space
is topologically ordered (this notion will be made mathematically precise
later in Section 6). Let $\rho^{\epsilon}_{\Lambda}$ be a state of global
energy density at most $\epsilon$, i.e.
$\Tr[H_{\Lambda}\rho^{\epsilon}_{\Lambda}]\leq|\Lambda|\epsilon$ and let
$\ket{\psi^{\epsilon}}_{\Lambda^{\prime}}=U\ket{0}^{\otimes\absolutevalue{\Lambda^{\prime}}}$
denote its purification on an extended lattice $\Lambda^{\prime}=\Lambda\cup
E$, where $E$ denotes a register of purifying ancillas. What is the smallest
depth of any quantum circuit implementing $U$ only using geometrically local
gates in 2D ?

Our main result gives an answer to this question for the case in which the
Hamiltonian is given by the toric code Hamiltonian with arbitrary ground space
degeneracy and arbitrary boundary conditions:

######  Theorem 1.

Let $\rho^{\epsilon}_{\Lambda}$ be a state with energy density at most
$\epsilon$ with respect to the toric code Hamiltonian $H_{\Lambda}$ on a 2D
lattice $\Lambda$ with arbitrary boundary conditions. Then any local quantum
circuit that prepares $\rho^{\epsilon}_{\Lambda}$ from a product state must be
of depth
$D=\Omega\left(\min\left(1/\epsilon^{\frac{1-\alpha}{2}},\sqrt{\absolutevalue{\Lambda}}\right)\right)$
for any $\alpha>0$.

This is an unexpected result, for the reasons discussed below. It is well-
known that the toric code Hamiltonian at finite temperature has no topological
order, as does a topologically trivial Hamiltonian. More precisely, such
states can be created by applying a finite number of layers of local quantum
channels [18]. Therefore, when it comes down to the properties of these
systems at finite energy density, it is natural to expect those states to have
similar properties. In particular, it would be natural to conjecture that the
complexity of preparing a state with energy density $\epsilon$ is, up to a
polylogarithmic factor, independent of whether the underlying Hamiltonian is
topologically ordered or not at zero temperature.

If one were to accept such a conjecture, one would be inclined to conclude
that the circuit depth for preparing the low-energy states of a topologically
trivial Hamiltonian would be also polynomial in $1/\epsilon$. However, this
seems unlikely to be true. For instance, we can consider the trivial
Hamiltonian $H=\sum_{i}Z_{i}$, for which even the exact ground state can be
prepared in $O(1)$ depth. Even if a small perturbation is added to such a
Hamiltonian, the new ground state can be mapped to the trivial state by a
locality-preserving unitary known as quasi-adiabatic continuation [19]. Since
there is an approach to simulate locally interacting time-dependent
Hamiltonian that can approximate local properties up to an error $\delta$,
with a circuit depth that scales polylogarithmically with $1/\delta$ [20, 21],
it is natural to expect that the quasi-adiabatic continuation can be also
simulated with a similar complexity. Thus, our result suggests that, despite
being both “trivial,” there is a subtle sense in which the finite-temperature
state of the toric code Hamiltonian and the trivial Hamiltonian are different.

On the conceptual side, our primary contribution lies in pointing out this
subtle difference by proving a new circuit depth lower bound. While the
purported polylogarithmic circuit-depth upper bound for general topologically
trivial Hamiltonian has not been proven rigorously yet, we believe this is a
reasonable conjecture in light of our plausibility argument above.

Our second conceptual contribution can be viewed as establishing a fundamental
limitation in approximating local properties of ground states using
geometrically local circuits. If such a circuit prepares a state that can
approximate local expectation values of the ground state up to an error
$\epsilon$, then this circuit by definition prepares a state with energy
density $O(\epsilon)$. Our lower bound shows that, in the worst case, the
circuit depth required to achieve such an error must thus grow polynomially
with $1/\epsilon$.

We note that this limitation is not just of theoretical interest. There is a
vast literature of numerical studies of the variational quantum eigensolver
(VQE) [5], and many focus on how the error with respect to the ground state
energy _per site_ decays with the circuit depth. In particular, we note that
there are results in the literature which report a decay the of the energy
that is exponential in the circuit depth of the variational ansatz [22, 23].
Our result shows rigorously that such a scaling can not be achieved in
general, if the ground space of the cost Hamiltonian is topologically ordered.
Understanding the performance of VQE is in general a difficult task, and our
work provides one approach to elucidate its limitations.

On the technical front, our main contribution lies in a novel proof technique
for proving robust circuit depth lower bound. Most notably, our lower bound
does not rely on the ground state degeneracy and therefore removes one of the
key assumptions in recent works on circuit lower bounds for low-energy states
of constant-rate stabilizer codes [11, 12]. Moreover, our proof technique
relies only on the existence of certain unitary “loop operators” of constant
depth that stabilize the ground space. As such, the technique is applicable to
a wider class of models such as Kitaev’s quantum double [6] and Levin-Wen
string-net models [7].

We note that our proof strategy is inspired by the work of Haah [9], which
gave a rigorous circuit-depth lower bound for the ground state of the toric
code on a sphere, which has a unique ground state. We provide a more robust
version of this technique, which is applicable to general mixed states, not
just pure states or ground states.

###  3.1 Relation to prior work

Our work is related to Ref. [11], which proves a $\Omega(\log(1/\epsilon))$
circuit depth lower bound for the preparation of low-energy states of high-
rate stabilizer Hamiltonians with $O(1)$-local but geometrically non-local
circuits. However, to the best of our knowledge, it is unclear how to prove
our main result using their approach. Therefore, we view our work to be
complementary to Ref. [11]; we make a stronger assumption on the form of the
circuit and derive a stronger lower bound.

##  4 Exact and approximate local invisibility

In this Section, we introduce the concept of _approximately locally invisible
operators_ , which will play a crucial role in the proof of our main result.
Local invisibility is a notion first introduced by Haah [9]. To give some
intuition for the concept of approximate local invisibility, we first restate
Haah’s original definition of exact local invisibility.

######  Definition 1.

(Local invisibility) Let $A\subset{\Lambda}$ be a disc of radius at most $r$
and let $B:=A(t^{\prime})\subset{\Lambda}$ for some $t^{\prime}\geq t\geq 0$.
An operator $P\in\mathcal{B}(\mathcal{H}_{\Lambda})$ is $(A,B)$-locally
invisible with respect to a state $\rho_{\Lambda}$ if for a disc $A\subset
B\subset\Lambda$ and any state $\rho_{\Lambda}^{\prime}$ such that
$\rho_{B}^{\prime}=\rho_{B}$, we have

$\rho_{A}=\frac{\text{Tr}_{A^{c}}\left[P\rho_{\Lambda}^{\prime}P^{\dagger}\right]}{\text{Tr}\left[P\rho_{\Lambda}^{\prime}P^{\dagger}\right]}.$
(13)

An operator is then $(r,t)$-locally invisible with respect to a state
$\rho_{\Lambda}$ if it is $(A,B)$-locally invisible with respect to $\Lambda$
with $A$ and $B$ specified as above.

One class of operators that satisfy this condition for a state
$\rho_{\Lambda}$ is any operator $P$ that stabilizes a state $\rho_{\Lambda}$,
i.e. $P\rho_{\Lambda}P^{\dagger}=\rho_{\Lambda}$. If this operator is a
unitary of depth $T$, then we may even fully characterize its parameters.

######  Fact 1.

Let $\rho_{\Lambda}\in\mathcal{D}(\mathcal{H}_{\Lambda})$ and let
$P\in\mathcal{B}(\mathcal{H}_{\Lambda})$ be a unitary operator such that
$P\rho_{\Lambda}P^{\dagger}=\rho_{\Lambda}$. Suppose that $P$ is of circuit
depth at most $T$ with respect to nearest-neighbor gates. Then $P$ is
$(r,t)$-locally invisible with respect to $\rho_{\Lambda}$ for
$r=\mathcal{O}\left(\sqrt{\Lambda}\right)$ and $t=\Omega\left(T\right)$.

###### Proof.

The proof follows immediately from the assumption that $P$ stabilizes
$\rho_{\Lambda}$ and requires one to choose $t\geq T$ in order for the
definition to hold. ∎

Let us give a concrete example of such an operator. Define
$\rho_{\Lambda}^{0}=\frac{\Pi_{R}^{0}{\rho_{\Lambda}}\Pi_{R}^{0}}{\text{Tr}\left[\Pi_{R}^{0}{\rho_{\Lambda}}\Pi_{R}^{0}\right]}$,
for some $\rho_{\Lambda}$, where $\Pi_{R}^{0}$ is the projection onto the
local toric code ground space as defined in Eq. (12) and assume that
$\text{Tr}[\Pi_{R}^{0}\rho_{\Lambda}\Pi_{R}^{0}]>0$. Consider a toric code
stabilizer $s^{Z}\in S_{R}^{\text{TC}}$ which is a tensor product of $Z$ that
forms a “loop” inside $R$; see Fig. 2. One can show that this loop is
$(A,A(2))$-locally invisible with respect to $\rho^{0}_{\Lambda}$ for any disc
$A\subset\Lambda$, because all the toric code stabilizers supported strictly
on $R$ stabilize $\rho^{0}_{\Lambda}$. Note how the support of $s^{Z}_{R}$ is
crucial, i.e. any $Z$-type loop operator with support overlapping with
$R^{c}$, is in general not locally invisible with respect to
$\rho^{0}_{\Lambda}$.

$\Lambda$$R$$A^{\prime}$$B^{\prime}$$A$$B$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}s^{Z}}$
Figure 2: A $Z$-type loop operator $s^{Z}\in\mathcal{S}_{R}^{\text{TC}}$ that
stabilizes the ground space of $H_{R}$. Its annular support is contained in
$R\subset\Lambda$ and it is locally invisible with respect to any state in the
ground space of $H_{R}$. Locally invisible regions $A$ and $A^{\prime}$ are
shown with $B=A(t)$ for some $t=\mathcal{O}(1)$ and likewise for $B^{\prime}$.

For the state $\rho_{\Lambda}$ prior to the projection, it is generally not
clear how to find a nontrivial operator which is locally invisible. However in
some cases, as we will see later, one may be able to find an operator that
approximately satisfies local invisibility.

######  Definition 2.

(Approximate local invisibility) Let $\delta\in[0,1]$ and let $A\subset
B\subset\Lambda$ be as given in Definition 1 . An operator
$P\in\mathcal{B}(\mathcal{H}_{\Lambda})$ is $(\delta,r,t)$-locally invisible
with respect to a state $\rho_{\Lambda}$ if for any state
$\rho_{\Lambda}^{\prime}$ such that $\rho_{B}=\rho_{B}^{\prime}$, we have

$D_{p}\left(\rho_{A},\frac{\text{Tr}_{A^{c}}\left[P\rho_{\Lambda}^{\prime}P^{\dagger}\right]}{\text{Tr}\left[P\rho_{\Lambda}^{\prime}P^{\dagger}\right]}\right)\leq\delta.$
(14)

In Definition 2, we used the purified distance as our distance measure of
choice; see Section 2 for details. This is solely for convenience and can
directly be translated into a statement using the trace distance via Eq. (6).

The relationship between exact and approximate local invisibility becomes
interesting when considering unitary operators and states that are
sufficiently close to each other in purified distance. Namely, if a unitary
operator is exactly locally invisible with respect to some state, then it is
approximately locally invisible with respect to any sufficiently small
perturbation of the state.

######  Lemma 1.

Let $\rho_{\Lambda}$ and $\sigma_{\Lambda}$ be two quantum states such that
$D_{p}{\left(\rho_{\Lambda},\sigma_{\Lambda}\right)}\leq\epsilon$. Then if $P$
is a $(r,t)$-locally invisible unitary with respect to $\rho_{\Lambda}$ for
any disc $A$ of radius at most $r$ and any disc $B:=A(t)$ for
$t\geq\text{depth}(P)$, then $P$ is $(2\epsilon,r,t)$-approximately locally
invisible with respect to $\sigma_{\Lambda}$.

###### Proof.

Our goal here is to show that for any state $\sigma^{\prime}_{\Lambda}$ s.t.
$\sigma^{\prime}_{B}=\sigma_{B}$, we have that

$\displaystyle
D_{p}{\left(\sigma_{A},\Tr_{A^{c}}\left[P\sigma^{\prime}_{\Lambda}P^{\dagger}\right]\right)}\leq
2\epsilon.$ (15)

This immediately follows from triangle inequality and our assumptions. We have

$\displaystyle
D_{p}{\left(\sigma_{A},\Tr_{A^{c}}\left[P\sigma^{\prime}_{\Lambda}P^{\dagger}\right]\right)}$
$\displaystyle\leq
D_{p}{\left(\sigma_{A},\rho_{A}\right)}+D_{p}{\left(\rho_{A},\Tr_{A^{c}}\left[P\rho^{\prime}_{\Lambda}P^{\dagger}\right]\right)}$
$\displaystyle+D_{p}{\left(\Tr_{A^{c}}\left[P\rho^{\prime}_{\Lambda}P^{\dagger}\right],\Tr_{A^{c}}\left[P\sigma^{\prime}_{\Lambda}P^{\dagger}\right]\right)}$
(16) $\displaystyle\leq\epsilon+0+\epsilon=2\epsilon,$ (17)

where the bound on the first term follows from our closeness assumption and
monotonicity of the purified distance and the second term is equal to zero
since $P$ is exactly locally invisible with respect to $\rho_{\Lambda}$.

We bound the third term on the RHS of line 16 as follows: Suppose
$T:=\text{depth}(P)$. Then since $\sigma^{\prime}_{B}=\sigma_{B}$, the
lightcone of the depth $T$ unitary $P$ implies that
$\Tr_{B(-T)^{c}}\left[P\sigma^{\prime}_{\Lambda}P^{\dagger}\right]=\Tr_{B(-T)^{c}}\left[P\sigma_{\Lambda}P^{\dagger}\right]$,
where $B(-T)$ is the $T$-interior of $B$ as defined in 2. Since $t\geq T$ we
have $A\subseteq B(-T)$ from which it follows that
$\Tr_{A^{c}}\left[P\sigma^{\prime}_{\Lambda}P^{\dagger}\right]=\Tr_{A^{c}}\left[P\sigma_{\Lambda}P^{\dagger}\right]$.
As $P$ is defined to be exactly locally invisible, i.e.
$\Tr_{A^{c}}\left[P\rho^{\prime}_{\Lambda}P^{\dagger}\right]=\Tr_{A^{c}}\left[P\rho_{\Lambda}P^{\dagger}\right]$
we therefore have that

$\displaystyle
D_{p}{\left(\Tr_{A^{c}}\left[P\rho^{\prime}_{\Lambda}P^{\dagger}\right],\Tr_{A^{c}}\left[P\sigma^{\prime}_{\Lambda}P^{\dagger}\right]\right)}=D_{p}{\left(\Tr_{A^{c}}\left[P\rho_{\Lambda}P^{\dagger}\right],\Tr_{A^{c}}\left[P\sigma_{\Lambda}P^{\dagger}\right]\right)}\leq\epsilon,$
(18)

where the inequality from unitary invariance and monotonicity of the purified
distance and our assumption that
$D_{p}{(\rho_{\Lambda},\sigma_{\Lambda})}\leq\epsilon$. ∎

Our lemma shows that, assuming that $P$ is a unitary, the notion of local
invisibility with respect to a state is in a sense ’robust’ to perturbations
to the state.

It is interesting to note that for stabilizer Hamiltonians, the stabilizers
themselves yield constant-depth unitaries that are exactly locally invisible
with respect to their ground states. Also for more general local commuting
projector models, such as the quantum double or string-net models [6, 7] there
exist loop operators that act trivally on any state in the ground space. These
are sometimes referred to as Wilson loop operators [24]. We will use this fact
later to find approximately locally invisible operators for our low-energy
states.

##  5 Local marginal projectors

A particularly useful notion to define in order to prove our main result is
the concept of a _local marginal projector_ (LMP for short). A LMP can be used
to fix the marginal of a state $\sigma_{\Lambda}$ on some region $S$ to a
desired marginal $\rho_{S}$. The main purpose of this section is to prove
properties of local marginal projectors, since they play an important role en
route to our main theorem.

Let us first define local marginal projectors and then explain the key result
of this section at a high level.

######  Definition 3.

(Local marginal projector) Let $\outerproduct{0^{n}}{0^{n}}_{S}$ be the
projection onto the all-zero state supported on a region
$S\subset\Lambda^{\prime}$ and let $U$ be a local quantum circuit of depth-$D$
that prepares a state $\ket{\psi}_{\Lambda^{\prime}}$, i.e.
$\ket{\psi}_{\Lambda^{\prime}}=U\ket{0^{n}}_{\Lambda^{\prime}}$. Then we say
that

$\displaystyle\Pi_{S(D)}:=U\left(\outerproduct{0^{n}}{0^{n}}_{S}\otimes\mathbbm{1}_{S^{c}}\right)U^{\dagger}$
(19)

is a local marginal projector (LMP) on $S(D)$ with respect to the state
$\ket{\psi}_{\Lambda^{\prime}}$.

Throughout the following sections, we will routinely consider an operator $P$
that is $(\delta,r,t)$-locally invisible with respect to a state
$\rho_{\Lambda}\in\mathcal{D}(\mathcal{H}_{\Lambda})$ and its purification
$\ket{\psi}_{\Lambda^{\prime}}\in\mathcal{H}_{\Lambda^{\prime}}$, and LMPs
$\Pi_{S(D)}$ with respect to this purification. To signify this relationship
between a state $\rho_{\Lambda}$, associated LMPs $\Pi_{S(D)}$ and an operator
$P$ succinctly, we will introduce the following definition.

######  Definition 4.

Let $\rho_{\Lambda}\in\mathcal{D}(\mathcal{H}_{\Lambda})$ be a state with
purification $\ket{\psi}_{\Lambda^{\prime}}$ on an extended lattice
$\Lambda^{\prime}=\Lambda\cup E$, where $E$ is a register of purifying
ancillas. Let $P\in\mathcal{B}(\mathcal{H}_{\Lambda})$ be a unitary operator
of depth at most $t$ that is $(\delta,r,t)$-approximately locally invisible
with respect to $\rho_{\Lambda}$ and let $\Pi:=\left\\{\Pi_{S(D)}\right\\}$ be
the set of LMPs $\Pi_{S(D)}$ with respect to $\ket{\psi}_{\Lambda^{\prime}}$
where $S(D)\subset{\Lambda}$. Then we call $(P,\,\,\Pi,\,\rho_{\Lambda})$ a
$(\delta,r,t)$-triple.

With slight abuse of notation, we will sometimes refer to an LMP whose support
can remain unspecified with $\Pi$, since this will be clear from context. We
will later also consider states $\rho_{\Lambda}$ for which we can find pairs
$P$ and $Q$ of $(\delta,r,t)$-locally invisible operators. We will then denote
the associated $(\delta,r,t)$-triple by
$\left(\\{P,Q\\},\,\,\Pi,\,\rho_{\Lambda}\right)$.

Having introduced these two key concepts, let us now explain the main
technical statement that we intend to prove in this section. Roughly speaking,
we intend to show that for any $(\delta,r,t)$-triple
$(P,\,\,\Pi,\,\rho_{\Lambda})$, we have that

$P\Pi_{\mathcal{P}^{\prime}}\approx\expectationvalue{P}{\psi}\Pi_{\mathcal{P}^{\prime}},$
(20)

where $\mathcal{P}^{\prime}$ is some sufficiently large thickening of
$p:=\text{supp}(P)$. This will prove to be a useful fact to property of
$(\delta,r,t)$-triple in order to prove our main theorem. We will make this
statement more precise in Proposition 2.

###  5.1 Properties of LMPs

We will now state some basic facts about LMPs. Note that all the LMPs
appearing below will be defined with respect to the same state
$\ket{\psi}_{\Lambda}$. For this section we will only consider a lattice
$\Lambda$ and no extension $\Lambda^{\prime}$.

######  Fact 2.

(Stabilization property) $\ket{\psi}_{\Lambda}=\Pi_{S(D)}\ket{\psi}_{\Lambda}$
for any $S(D)\subset\Lambda$.

######  Fact 3.

(Union property) Let $S_{1},S_{2}\subset\Lambda$. Then
$\Pi_{S_{1}(D)}\Pi_{S_{2}(D)}=\Pi_{(S_{1}\cup S_{2})(D)}$

######  Fact 4.

Let $\Lambda=\bigcup_{i}S_{i}$ and let $\Pi_{S_{i}(D)}$ the LMP on $S_{i}(D)$
with respect to the state $\ket{\psi}_{\Lambda}$. Then

$\displaystyle\outerproduct{\psi}{\psi}_{\Lambda}=\prod_{i}\Pi_{S_{i}(D)}.$
(21)

######  Fact 5.

For any $S,S^{\prime}\subset\Lambda$ we have that
$\left[\Pi_{S(D)},\Pi_{S^{\prime}(D)}\right]=0$.

A local marginal projector $\Pi_{S(D)}$ with respect to a state
$\ket{\psi}_{\Lambda}$ locally projects any state $\sigma_{\Lambda}$ onto
$\Tr_{S^{\prime c}}[\outerproduct{\psi}{\psi}_{\Lambda}]$ for a disc
$S^{\prime}\subset S$ s.t. $S^{\prime}(D)=S$. More formally, we have:

######  Lemma 2.

Let $S\subset\Lambda$ be a disk of radius $r>D$ and let $\Pi_{S(D)}$ be a LMP
with respect to a state $\ket{\psi}_{\Lambda}=U\ket{0^{n}}_{\Lambda}$. Let
$\sigma_{\Lambda}$ be an arbitrary state such that
$\Pi_{S(D)}\sigma_{\Lambda}\Pi_{S(D)}\neq 0$. Then for any concentric disk of
$S^{\prime}\subset S\subset\Lambda$ of radius $r-D$ or less,

$\Tr_{S^{\prime
c}}\left[\outerproduct{\psi}{\psi}_{\Lambda}\right]=\frac{\Tr_{S^{\prime
C}}\left[\Pi_{S(D)}\sigma_{\Lambda}\Pi_{S(D)}\right]}{\Tr[\Pi_{S(D)}\sigma_{\Lambda}]}.$
(22)

###### Proof.

We prove the claim by showing that the expectation value of any
$O_{S^{\prime}}\in\mathcal{B}(\mathcal{H}_{S^{\prime}})$ is identical for
$|\psi\rangle_{\Lambda}$ and any purification of
$\sigma_{\Lambda}^{\prime}=\frac{\Pi_{S(D)}\sigma_{\Lambda}\Pi_{S(D)}}{\Tr[\Pi_{S(D)}\sigma_{\Lambda}]}$,
denoted as $|\phi\rangle_{\Lambda^{\prime}}$.111Here $\Lambda^{\prime}$ is the
purifying space. The equivalence of the two expectation values can be
established by showing that $U^{\dagger}|\psi\rangle_{\Lambda}$ and
$U^{\dagger}\Pi_{S(D)}|\phi\rangle_{\Lambda^{\prime}}$, upon normalizing the
states, have identical marginals over $S$. Note that the support of $U$ and
$\Pi_{S(D)}$ is still confined to $\Lambda$. Keeping this in mind, note that

$\displaystyle U^{\dagger}|\psi\rangle_{\Lambda}$
$\displaystyle=|0^{n}\rangle_{S}\otimes|0^{n}\rangle_{\Lambda\setminus S},$
(23) $\displaystyle U^{\dagger}\Pi_{S(D)}|\phi\rangle_{\Lambda^{\prime}}$
$\displaystyle=|0^{n}\rangle_{S}\otimes|\phi^{\prime}\rangle_{\Lambda^{\prime}\setminus
S},$

where $|\phi^{\prime}\rangle$ is some (possibly unnormalized) state with a
positive norm. Since $U$ is a depth-$D$ quantum circuit and
$\ket{\phi}_{\Lambda^{\prime}}$ is a purification of
$\sigma^{\prime}_{\Lambda}$, our claim follows from the standard “lightcone”
arguments.

For the interested readers, we explain the details below. Note that

$U^{\dagger}\Pi_{S(D)}\ket{\phi}_{\Lambda^{\prime}}=\left(\outerproduct{0^{n}}{0^{n}}_{S}\otimes\mathbbm{1}_{S^{c}}\right)U^{\dagger}\ket{\phi}_{\Lambda^{\prime}}=\ket{0^{n}}_{S}\otimes|\phi^{\prime}\rangle_{\Lambda^{\prime}\setminus
S},$ (24)

where $\ket{\phi^{\prime}}$ is some nonzero vector. Also recall that
$U^{\dagger}\ket{\psi}_{\Lambda}=\ket{0^{n}}_{\Lambda}=\ket{0^{n}}_{S}\otimes\ket{0^{n}}_{S^{c}}$.

$\displaystyle\expectationvalue{O_{S^{\prime}}}{\psi}-\frac{\expectationvalue{\Pi_{S(D)}O_{S^{\prime}}\Pi_{S(D)}}{\phi}}{\expectationvalue{\Pi_{S(D)}}{\phi}}$
$\displaystyle=\expectationvalue{U^{\dagger}O_{S^{\prime}}U}{0^{n}}-\frac{\bra{\phi^{\prime}}_{\Lambda^{\prime}\setminus
S}\otimes\bra{0^{n}}_{S}U^{\dagger}O_{S^{\prime}}U\ket{\phi^{\prime}}_{\Lambda^{\prime}\setminus
S}\otimes\ket{0^{n}}_{S}}{\langle\phi^{\prime}|\phi^{\prime}\rangle}$ (25)
$\displaystyle=\Tr\left[U^{\dagger}O_{S^{\prime}}U\outerproduct{0^{n}}{0^{n}}_{S}\right]-\Tr\left[U^{\dagger}O_{S^{\prime}}U\outerproduct{0^{n}}{0^{n}}_{S}\right]$
(26) $\displaystyle=0.$ (27)

Here we used the fact that $U^{\dagger}O_{S^{\prime}}U$ is supported on $S$ to
arrive at the second line. ∎

######  Lemma 3.

Let $O\in\mathcal{B}(\mathcal{H}_{\Lambda})$ and let $\Pi_{S(D)}$ be a LMP
with respect to $\ket{\psi}_{\Lambda}=U\ket{0^{n}}_{\Lambda}$. Then for any
region $S^{\prime}$, s.t. $\text{supp}(O)\subset{S^{\prime}}$ and
$S=S^{\prime}(D)$ we have that:

$\displaystyle\Pi_{S(D)}O\Pi_{S(D)}=\expectationvalue{O}{\psi}\Pi_{S(D)}$ (28)

###### Proof.

The proof follows in analogy to equations (25-27), but by showing that

$\displaystyle\expectationvalue{O}{\psi}-\frac{\bra{\phi}\Pi_{S(D)}O\Pi_{S(D)}\ket{\phi^{\prime}}}{\bra{\phi}\Pi_{S(D)}\ket{\phi^{\prime}}}=0$
(29)

for any
$\ket{\phi}_{\Lambda},\ket{\phi^{\prime}}_{\Lambda}\in\mathcal{H}_{\Lambda}$

∎

###  5.2 LMPs and local invisibility

In this section, we will develop some technical lemmas on how LMPs can be used
to put bounds on the action of approximately locally invisible operators.

######  Lemma 4.

Let $(P,\,\,\Pi,\,\rho_{\Lambda})$ be a $(\delta,r,t)$-triple. Let $S$ be any
disc of radius at most $r-D$ and let $B:=S(t^{\prime})$ for $t^{\prime}\geq
t+D$ (see Figure 3). Then for any $\sigma_{\Lambda}$, such that
$\sigma_{B}=\rho_{B}$, we have

$\displaystyle\left\|{\Pi_{S(D)}P\sigma_{\Lambda}P^{\dagger}\Pi_{S(D)}-P\sigma_{\Lambda}P^{\dagger}}\right\|_{1}\leq
2\delta.$ (30)

###### Proof.

This claim follows directly from the approximate local invisibility of $P$ and
the fact that LMPs with respect to some state $\ket{\psi}_{\Lambda^{\prime}}$
supported on some region $S$ stabilize any state that looks like the marginal
of $\ket{\psi}_{\Lambda^{\prime}}$ on $S$. By our local invisibility
assumption we have that

$\displaystyle
D_{p}\left(\rho_{A},\Tr_{A^{c}}\left[P\sigma_{\Lambda}P^{\dagger}\right]\right)\leq\delta$
(31)

for any disk $A$ of radius $r$ or less, which is concentric with region $B$.
It is immediate that

$\displaystyle
F\left(\rho_{A},\Tr_{A^{c}}\left[P\sigma_{\Lambda}P^{\dagger}\right]\right)\geq
1-\delta^{2}.$ (32)

Let $\Lambda^{\prime}$ be our extended lattice on which we define purifcations
$\ket{\psi}_{\Lambda^{\prime}}$ and $P\ket{\phi}_{\Lambda^{\prime}}$ of
$\rho_{A}$ and $\Tr_{A^{c}}\left[P\sigma_{\Lambda}P^{\dagger}\right]$
respectively. By Uhlmann’s theorem there exists a unitary $U_{A^{c}}$ acting
on the purifiying space $A^{c}$, such that
$\left|{}_{\Lambda^{\prime}}\bra{\psi}U_{A^{c}}P\ket{\phi}_{\Lambda^{\prime}}\right|^{2}=F\left(\rho_{A},\Tr_{A^{c}}\left[P\sigma_{\Lambda}P^{\dagger}\right]\right)$
implying that

$\displaystyle
D_{p}\left(U_{A^{c}}\outerproduct{\psi}{\psi}_{\Lambda^{\prime}}U_{A^{c}}^{\dagger},P\outerproduct{\phi}{\phi}_{\Lambda^{\prime}}P^{\dagger}\right)\leq\delta$
(33)

Now let $A=S(D)$, where $\text{rad}(S)\leq r-D$. Then we have that

$\displaystyle\left\|{U_{S(D)^{c}}\outerproduct{\psi}{\psi}_{\Lambda^{\prime}}U_{S(D)^{c}}^{\dagger}-P\outerproduct{\phi}{\phi}_{\Lambda^{\prime}}P^{\dagger}}\right\|_{1}\leq
D_{p}\left(U_{S(D)^{c}}\outerproduct{\psi}{\psi}_{\Lambda^{\prime}}U_{S(D)^{c}}^{\dagger},P\outerproduct{\phi}{\phi}_{\Lambda^{\prime}}P^{\dagger}\right)\leq\delta$
(34)

Since
$\left\|{XYZ}\right\|_{1}\leq\left\|X\right\|_{\infty}\left\|{Y}\right\|_{1}\left\|Z\right\|_{\infty}$
for any $X,Y,Z\in\mathcal{B}(\mathcal{H})$, and since
$\left\|\Pi_{S(D)}\right\|_{\infty}=1$, we get

$\displaystyle\left\|{\Pi_{S(D)}U_{S(D)^{c}}\outerproduct{\psi}{\psi}_{\Lambda^{\prime}}U_{S(D)^{c}}^{\dagger}\Pi_{S(D)}-\Pi_{S(D)}P\outerproduct{\phi}{\phi}_{\Lambda^{\prime}}P^{\dagger}\Pi_{S(D)}}\right\|_{1}\leq\delta.$
(35)

Moreover, since $\left[\Pi_{S(D)},U_{S(D)^{c}}\right]=0$ and
$\Pi_{S(D)}\ket{\psi}_{\Lambda^{\prime}}=\ket{\psi}_{\Lambda^{\prime}}$, it
follows that

$\displaystyle\left\|{U_{S(D)^{c}}\outerproduct{\psi}{\psi}_{\Lambda^{\prime}}U_{S(D)^{c}}^{\dagger}-\Pi_{S(D)}P\outerproduct{\phi}{\phi}_{\Lambda^{\prime}}P^{\dagger}\Pi_{S(D)}}\right\|_{1}\leq\delta$
(36)

Via triangle inequality it then follows

$\displaystyle\left\|{\Pi_{S(D)}P\outerproduct{\phi}{\phi}_{\Lambda^{\prime}}P^{\dagger}\Pi_{S(D)}-P\outerproduct{\phi}{\phi}_{\Lambda^{\prime}}P^{\dagger}}\right\|_{1}\leq
2\delta.$ (37)

Noting that and $\text{supp}(P)\subset\Lambda$ and $S(D)\subset\Lambda$ and
using monotonicity of trace distance under partial trace, we thus conclude
that
$\left\|{\Pi_{S(D)}P\sigma_{\Lambda}P^{\dagger}\Pi_{S(D)}-P\sigma_{\Lambda}P^{\dagger}}\right\|_{1}\leq
2\delta$. ∎

Lemma 4 can then be lifted to a statement in the operator norm about LMPs and
approximately locally invisible operators .

$r-D$$D$$t$$D$$S$$S(D)$$B$$S^{\prime}$ Figure 3: Arrangements of discs
$S,S(D),B$ and $S^{\prime}$ as described in Proposition 1.

######  Proposition 1.

Let $(P,\,\,\Pi,\,\rho_{\Lambda})$ be a $(\delta,r,t)$-triple. Let $S$ be any
disc of radius at most $r-D$ and let $S^{\prime}:=S(t^{\prime})$ for
$t^{\prime}\geq t+2D$ (see Fig. 3). Then

$\displaystyle\left\|{\Pi_{S(D)}P\Pi_{S^{\prime}(D)}-P\Pi_{S^{\prime}(D)}}\right\|_{\infty}\leq
2\delta$ (38)

###### Proof.

The proof is a simple consequence of combining Lemmas 2 and 4 and changing to
the operator norm. Using Lemma 2, we have that for any disc $B$ of radius at
least $\text{rad}(S)+D+t$, such that $B(D)=S^{\prime}$:

$\displaystyle\rho_{B}=\frac{\Tr_{B^{c}}\left[\Pi_{S^{\prime}(D)}\sigma_{\Lambda}\Pi_{S^{\prime}(D)}\right]}{\Tr[\Pi_{S^{\prime}(D)}\sigma_{\Lambda}\Pi_{S^{\prime}(D)}]},$
(39)

where $\rho_{B}=\Tr_{B^{c}}[\rho_{\Lambda}]$. Invoking Eq. (37), which may be
understood as a ’purified version’ of Lemma 4, we then have that

$\displaystyle\left\|{\Pi_{S(D)}P\Pi_{S^{\prime}(D)}\outerproduct{\phi}{\phi}_{\Lambda^{\prime}}\Pi_{S^{\prime}(D)}P^{\dagger}\Pi_{S(D)}-P\Pi_{S^{\prime}(D)}\outerproduct{\phi}{\phi}_{\Lambda^{\prime}}\Pi_{S^{\prime}(D)}P^{\dagger}}\right\|_{1}\leq
2\delta,$ (40)

where $\outerproduct{\phi}{\phi}_{\Lambda^{\prime}}$is a purification of
$\sigma_{\Lambda}$. To bound the complex Euclidean norm between these two
states by their trace distance, we shall use the following fact:

######  Fact 6.

Let $\Pi\in\mathcal{B}(\mathcal{H})$ be a projector. If
$\left\|{\outerproduct{\psi}{\psi}-\Pi\outerproduct{\psi}{\psi}\Pi}\right\|_{1}\leq\epsilon$,
then $\left\|\ket{\psi}-\Pi\ket{\psi}\right\|\leq\epsilon$.

This can be seen as follows. Since $0\leq\expectationvalue{\Pi}{\psi}\leq 1$,
we have that

$\displaystyle\norm{\ket{\psi}-\Pi\ket{\psi}}=\sqrt{1-\expectationvalue{\Pi}{\psi}}\leq\sqrt{1-\left(\expectationvalue{\Pi}{\psi}\right)^{2}}=\norm{\outerproduct{\psi}{\psi}-\Pi\outerproduct{\psi}{\psi}\Pi}_{2}$
(41)

As $\norm{A}_{2}\leq\norm{A}_{1}$, we arrive at Fact 6 .

This implies that for any state $\ket{\phi}_{\Lambda^{\prime}}$

$\displaystyle\left\|\Pi_{S(D)}P\Pi_{S^{\prime}(D)}\ket{\phi}_{\Lambda^{\prime}}-P\Pi_{S^{\prime}(D)}\ket{\phi}_{\Lambda^{\prime}}\right\|\leq
2\delta,$ (42)

from which it follows that
$\left\|{\Pi_{S(D)}P\Pi_{S^{\prime}(D)}-P\Pi_{S^{\prime}(D)}}\right\|_{\infty}\leq
2\delta$ . ∎

This statement straightforwardly generalizes to an arbitrary number of discs
$S_{i}$ that satisfy the conditions in Proposition 1.

######  Corollary 1.

Let $(P,\,\,\Pi,\,\rho_{\Lambda})$ be a $(\delta,r,t)$-triple. Let
$\\{S_{i}\\}$ be any set of $k$ discs of radius at most $r-D$ and let
$\\{S^{\prime}_{i}\\}$ be any set of corresponding $k$ discs where
$S^{\prime}_{i}:=S_{i}(t+2D)$. Then

$\displaystyle\left\|{\prod_{i\in[k]}\Pi_{S_{i}(D)}P\prod_{i\in[k]}\Pi_{S_{i}^{\prime}(D)}-P\prod_{i\in[k]}\Pi_{S_{i}^{\prime}(D)}}\right\|_{\infty}\leq
2k\delta.$ (43)

###### Proof.

The proof follows from Proposition 1 and repeated application of triangle
inequality and Hoelder’s inequality. ∎

Corollary 1 implies that a version of Proposition 1 still holds when $\Pi$ is
an LMP with support larger than any disc of radius at most $r-D$, since one
can divide the support of $\Pi$ into smaller regions of radius at most $r-D$
and then apply Corollary 1.

We will now use this technique in order to prove the main proposition of this
section. Suppose $(P,\,\,\Pi,\,\rho_{\Lambda})$ is a $(\delta,r,t)$\- triple.
Roughly speaking, if the support of $\Pi$ fully covers some sufficiently large
thickening $\mathcal{P}^{\prime}$ of the support of the $(\delta,r,t)$-locally
invisible operator $P$ (see Figure 4(a)), then the action of $P$ on the LMP is
approximately proportional to the expectation value of $P$ with respect to
$\ket{\psi}_{\Lambda^{\prime}}$.

######  Proposition 2.

Let $(P,\,\,\Pi,\,\rho_{\Lambda})$ be a $(\delta,r,t)$-triple and let
$p:=\text{supp}(P)$. Let $\\{S_{i}\\}$ be any set of $k_{P}$ discs of radius
$D<\text{rad}(S_{i})\leq r-D$, such that $p(D)\subseteq\bigcup S_{i}$. For
every disc $S_{i}$, let $S^{\prime}_{i}:=S_{i}(t+2D)$ be a disc concentric to
$S_{i}$. Suppose
$\Pi_{\mathcal{P}^{\prime}}=\prod_{i}\Pi_{S^{\prime}_{i}(D)}$, where
$\mathcal{P}^{\prime}=\mathcal{P}(t+2D)$. Then

$\displaystyle\left\|P\Pi_{\mathcal{P}^{\prime}}-\expectationvalue{P}{\psi}\Pi_{\mathcal{P}^{\prime}}\right\|_{\infty}\leq
2\delta\,k_{P}$ (44)

###### Proof.

The proof follows from breaking up the support of the LMP covering the support
of $P$ into $k_{P}$ locally invisible regions, such that we can apply
Corollary 1 and then leverage Lemma 3 to prove our proposition. Let
$\Pi_{\mathcal{P}}:=\prod_{i}\Pi_{S_{i}(D)}$. Then

$\displaystyle\left\|{\Pi_{\mathcal{P}}P\Pi_{\mathcal{P}^{\prime}}-P\Pi_{\mathcal{P}^{\prime}}}\right\|_{\infty}=\left\|{\prod_{i=1}^{k_{P}}\Pi_{S_{i}(D)}P\prod_{i=1}^{k_{P}}\Pi_{S^{\prime}_{i}(D)}-P\prod_{i=1}^{k_{P}}\Pi_{S^{\prime}_{i}(D)}}\right\|_{\infty}\leq
2\delta k_{P},$ (45)

where we have made use of Corollary 1 in the last step. Using Facts 2 and 3
respectively it follows that
$\Pi_{\mathcal{P}}P\Pi_{\mathcal{P}^{\prime}}=\Pi_{\mathcal{P}}P\Pi_{\mathcal{P}}\Pi_{\mathcal{P}^{\prime}}=\expectationvalue{P}{\psi}\Pi_{\mathcal{P}}\Pi_{\mathcal{P}^{\prime}}=\expectationvalue{P}{\psi}\Pi_{\mathcal{P}^{\prime}}$
and therefore

$\displaystyle\left\|{\Pi_{\mathcal{P}}P\Pi_{\mathcal{P}^{\prime}}-P\Pi_{\mathcal{P}^{\prime}}}\right\|_{\infty}=\left\|{\expectationvalue{P}{\psi}\Pi_{\mathcal{P}^{\prime}}-P\Pi_{\mathcal{P}^{\prime}}}\right\|_{\infty},$
(46)

from which follows our claim. ∎

$\Lambda$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}P}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Pi_{\mathcal{P}^{\prime}}}$
(a)

$d_{\text{sep}}$$M^{c}$$M$$\Lambda$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}P}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Q}$
(b)

Figure 4:  (a) An example of a LMP $\Pi_{\mathcal{P}^{\prime}}$ (cyan)
covering the support of an approximately locally invisible loop operator $P$
(red). (b) A pair of intersecting $(\delta,A,B)$-locally invisible loop
operators $P$ and $Q$ supported on the lattice $\Lambda$ partitioned into two
regions $M$ and $M^{c}$, such that at most one region of intersection of the
loop operators is contained in either half. Note that the partition may be
chosen arbitrarily as long as it satisfies this criterion. Let
$\mathcal{P}^{\prime}$ be a thickening of $\text{supp}(P)$ as shown in Figure
4(a) and defined in Proposition 3. We may write $\mathcal{P}^{\prime}$ as the
union of the three sets
$V_{1}:=\\{S_{i}(D)\subset\mathcal{P}^{\prime}:S_{i}(D)\subset M\\}$ (cyan
shade) and
$V_{2}:=\\{S_{i}(D)\subset\mathcal{P}^{\prime}:S_{i}(D)\cap\text{supp}(Q)=\emptyset\\}$
(green shade) and
$V_{3}=\\{S_{i}(D)\subset\mathcal{P}^{\prime}:(S_{i}(D)\subset
M^{c})\cap(S_{i}(D)\cap\text{supp}(Q)\neq\emptyset)\\}$ (violet shade).

##  6 The twist product

We will now introduce a key concept behind our circuit lower bound proof
technique. This is the notion of the twist product.

######  Definition 5.

(Twist product) Let $P$ and $Q$ be two bipartite operators that w.l.o.g admit
decompositions $P=\sum_{j}P_{M}^{j}\otimes P_{M^{c}}^{j}$ and
$Q=\sum_{k}Q_{M}^{k}\otimes Q_{M^{c}}^{k}$. Then we define their twist product
as

$\displaystyle P\infty Q:=\sum_{j,k}P_{M^{c}}^{j}Q_{M^{c}}^{k}\otimes
Q_{M}^{k}P_{M}^{j}$ (47)

By summing over either of the two indices one may also conveniently write this
as:

$\displaystyle P\infty
Q=\sum_{j}P_{M^{c}}^{j}QP_{M}^{j}=\sum_{k}Q_{M}^{k}PQ_{M^{c}}^{k}$ (48)

This product was first introduced in [9] and can be used to construct a
witness function for the presence of long-range entanglement in a state
$\ket{\psi}$. Haah shows how one can do so by finding two non-trivial exactly
locally invisible operators $P$ and $Q$ with respect to $\ket{\psi}$ that
intersect at two points. He proves that if $\expectationvalue{P\infty
Q}{\psi}\neq\expectationvalue{P}{\psi}\expectationvalue{Q}{\psi}$, then the
state $\ket{\psi}$ is not connected to a product state via a geometrically
local circuit of constant depth and therefore must exhibit long-range
entanglement.

As a concrete example, Haah considers the toric code Hamiltonian defined on a
sphere. For this, he identifies $P$ and $Q$ with an $X$ and $Z$ type
stabilizer of the toric code respectively. Both are exactly locally invisible
by definition and form closed loops that can be put on the lattice such that
they intersect at two points (see Figure 4(b)). Their so-called ’twist paring’
$\expectationvalue{P\infty Q}{\psi}$ evaluates to (-1) and may be understood
as the phase acquired by the wavefunction when braiding an $e$ and an $m$
excitation in the toric code around each other. Therefore
$\expectationvalue{P\infty
Q}{\psi}\neq\expectationvalue{P}{\psi}\expectationvalue{Q}{\psi}$, which
implies that the ground state of the toric code on a sphere cannot be prepared
with a constant depth circuit. Such states are sometimes referred to as being
topologically ordered.

Developing this line of argument further then allows for a rigorous proof of a
circuit lower bound when the ground state is unique. This setting poses an
obstacle to previously established techniques for circuit depth lower bounds
[8, 15], which only deal with the case where the ground space is degenerate.

In this section, we will extend this framework and show that it may still be
used when $P$ and $Q$ are only $(\delta,r,t)$-approximately locally invisible
with respect to $\ket{\psi}$. One may therefore say that the witness function
is robust to perturbations to $\ket{\psi}$ in purified distance.

The main purpose of this section is to prove an upper bound on this robust
witness function

$\displaystyle C(P,Q)_{\ket{\psi}}:=\left|\expectationvalue{P\infty
Q}{\psi}-\expectationvalue{P}{\psi}\expectationvalue{Q}{\psi}\right|$ (49)

in terms of the circuit depth $D$ required to prepare $\ket{\psi}$ (see
Theorem 2). Later, we will combine this with a lower bound on this function in
terms of the local invisibility parameter $\delta$ in order to give a circuit
lower bound for low-energy states.

To prove Theorem 2, we first have to establish some properties of the twist
product and how it can be combined with LMPs for our purposes. A key property
of the twist product is the following:

######  Lemma 5.

Consider a bipartite lattice $\Lambda=M\cup M^{c}$ and let
$P,Q,O\in\mathcal{B}(\mathcal{H}_{\Lambda})$. If $\text{supp}(O)\subset M$ or
$\text{supp}(O)\cap\text{supp}(Q)=\emptyset$, then $(PO)\infty Q=(P\infty
Q)O$.

###### Proof.

This is immediate from rewriting the twist product as in Eq. (48). If
$\text{supp}(O)\cap\text{supp}(Q)=\emptyset$ then we have $(PO)\infty
Q=\sum_{j}Q_{M}POQ_{M^{c}}=\sum_{j}Q_{M}PQ_{M^{c}}O=(P\infty Q)O$. If
$\text{supp}(O)\subset M$, we have $(PO)\infty
Q=\sum_{j}P_{M^{c}}^{j}QP_{M}^{j}O=(P\infty Q)O$ ∎

From here onwards, we will specifically consider the twist product of two
operators $P,Q\in\mathcal{B}(\mathcal{H}_{\Lambda})$ supported on two
intersecting annuli (see Fig. 4(b)) and our choice of bipartition
$\Lambda=M\cup M^{c}$ will separate the two points at which the annuli
intersect. Note however that our proof techniques could straightforwardly be
generalized to settings where both $P$ and $Q$ do not have annular support.
The only requirement is for these operators is to intersect at two points that
are sufficiently far apart from each other.

The following proposition will be instrumental in proving Theorem 2:

######  Proposition 3.

Let $\left(\\{P,Q\\},\,\,\rho_{\Lambda},\,\Pi\right)$ be a
$(\delta,r,t)$-triple, where $P$ and $Q$ are constant-depth unitaries that are
supported on intersecting annuli (see Fig. 4(b)) of equal diameter $d_{P}$.
Let $p:=\text{supp}(P)$ denote the annular support and assume that it has a
thickness of $\tau_{p}=\mathcal{O}(1)$.

Let $\\{S_{i}\\}$ be a set of discs such that $\bigcup_{i}S_{i}\supseteq
p(t+3D)$, where $3D+t+\tau_{p}\leq\text{rad}(S_{i})\leq r-D$. For every disc
$S_{i}$, let $S^{\prime}_{i}:=S_{i}(t+2D)$ be a disc concentric to $S_{i}$
such that $\bigcup_{i}S^{\prime}_{i}\supseteq p\left(2t+5D\right)$. Suppose
that $\Pi_{\mathcal{P}^{\prime}}:=\prod_{i}\Pi_{S_{i}(D)}$ and
$\Pi_{\mathcal{P}^{\prime\prime}}=\prod_{i}\Pi_{S^{\prime}_{i}(D)}$, where
$\mathcal{P}^{\prime}=\mathcal{P}(t+2D)$ and let $k_{Q}$ be an upper bound on
the number of discs $S_{i}(D)$ that touch one of the intersections of $P$ with
$Q$. Further assume that the intersections of both annuli are apart by a
distance $d_{\text{sep}}>2\,\text{rad}\left(S^{\prime}_{i}(D)\right)$. Then

$\displaystyle\left\|{P\infty
Q\ket{\psi}_{\Lambda^{\prime}}-P\Pi_{\mathcal{P}^{\prime}}\infty
Q\ket{\psi}_{\Lambda^{\prime}}}\right\|_{\infty}\leq
2\delta\,k_{Q}\,\alpha_{P}$ (50)

where
$\alpha_{P}:=\sum_{j}\left\|P_{M}^{j}\right\|_{\infty}\left\|P_{M^{c}}^{j}\right\|_{\infty}$
for $P=\sum_{j}P_{M}^{j}\otimes P_{M^{c}}^{j}$.

###### Proof.

We will prove this proposition via Lemma 5, Proposition 2 and Corollary 1. We
shall consider decomposing $\mathcal{P}^{\prime}=V_{1}\cup V_{2}\cup V_{3}$
into three sets, that each correspond to the three distinct cases illustrated
in Figure 4(b). Accordingly, we will consider the projection
$\Pi_{\mathcal{P}^{\prime}}$, and decompose it with respect to this
partitioning. We then write

$\displaystyle\Pi_{\mathcal{P}^{\prime}}=\prod_{S_{i}\in
V_{3}}\Pi_{S_{i}(D)}\prod_{S_{i}\in V_{1}\cup V_{2}}\Pi_{S_{i}(D)}$ (51)

where, with slight abuse of notation, $S_{i}\in V_{m}$ and later
$S^{\prime}_{i}\in V_{m}$ for $m\in\\{1,2,3\\}$, if $S_{i}(D)\in V_{m}$. Using
Lemma 5 and Fact 2 we then have

$\displaystyle P\Pi_{\mathcal{P}^{\prime}}\infty
Q\ket{\psi}_{\Lambda^{\prime}}=\left(P\prod_{S_{i}\in
V_{3}}\Pi_{S_{i}(D)}\infty Q\right)\prod_{S_{i}\in V_{1}\cup
V_{2}}\Pi_{S_{i}(D)}\ket{\psi}_{\Lambda^{\prime}}=\left(P\prod_{S_{i}\in
V_{3}}\Pi_{S_{i}(D)}\infty Q\right)\ket{\psi}_{\Lambda^{\prime}}$ (52)
$\displaystyle=\left(P\prod_{S_{i}\in V_{3}}\Pi_{S_{i}(D)}\infty
Q\right)\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}\ket{\psi}_{\Lambda}.$ (53) Therefore
$\displaystyle\left\|\left(P\Pi_{\mathcal{P}^{\prime}}\infty
Q\right)\ket{\psi}_{\Lambda^{\prime}}-P\infty
Q\ket{\psi}_{\Lambda^{\prime}}\right\|=\left\|\left(P\prod_{S_{i}\in
V_{3}}\Pi_{S_{i}(D)}\infty Q\right)\ket{\psi}_{\Lambda^{\prime}}-P\infty
Q\ket{\psi}_{\Lambda^{\prime}}\right\|$ (54) and using Fact 2 once again, we
have $\displaystyle=\left\|\left(P\prod_{S_{i}\in V_{3}}\Pi_{S_{i}(D)}\infty
Q\right)\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}\ket{\psi}_{\Lambda^{\prime}}-(P\infty
Q)\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}\ket{\psi}_{\Lambda^{\prime}}\right\|.$ (55) We
will now choose a partitioning $\Lambda=M\cup M^{c}$ such that the cut is
chosen to be as far away from $\text{supp}(P)\cap\text{supp}(Q)\cap M^{c}$ as
possible, but still separates it from $\text{supp}(P)\cap\text{supp}(Q)\cap
M$. From Eq.(48) we get
$\displaystyle=\left\|\sum_{j}P_{M^{c}}^{j}\prod_{S_{i}\in
V_{3}}\Pi_{S_{i}(D)}QP_{M}^{j}\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}\ket{\psi}_{\Lambda^{\prime}}-\left(\sum_{j}P_{M^{c}}^{j}QP_{M}^{j}\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}\right)\ket{\psi}_{\Lambda^{\prime}}\right\|$
(56) $\displaystyle\leq\sum_{j}\left\|{P_{M^{c}}^{j}\prod_{S_{i}\in
V_{3}}\Pi_{S_{i}(D)}QP_{M}^{j}\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}-P_{M^{c}}^{j}QP_{M}^{j}\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}}\right\|_{\infty},$ (57) where the upper bound
follows from definition of the operator norm and triangle inequality. Since
$d_{\text{sep}}>2\,\text{rad}\left(S^{\prime}_{i}(D)\right)$, our choice of
partitioning implies that $S^{\prime}_{i}(D)\subset M^{c}$ if
$S^{\prime}_{i}\in V_{3}$. Therefore $\left[\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)},\,P_{M}^{j}\right]=0$ for all $j$, such that:
$\displaystyle=\sum_{j}\left\|{P_{M^{c}}^{j}\prod_{S_{i}\in
V_{3}}\Pi_{S_{i}(D)}Q\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}P_{M}^{j}-P_{M^{c}}^{j}Q\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}P_{M}^{j}}\right\|_{\infty}$ (58)
$\displaystyle\leq\left(\sum_{j}\left\|{P_{M^{c}}^{j}}\right\|_{\infty}\left\|{P_{M}^{j}}\right\|_{\infty}\right)\left\|{\prod_{S_{i}\in
V_{3}}\Pi_{S_{i}(D)}Q\prod_{S_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}-Q\prod_{S^{\prime}_{i}\in
V_{3}}\Pi_{S^{\prime}_{i}(D)}}\right\|_{\infty}\leq
2\delta\,k_{Q}\,\alpha_{P},$ (59)

where the last step follows from applying Corollary 1 and assuming that at
most $k_{Q}$ discs from the set $\\{S_{i}\\}$ overlap with with
$\text{supp}(Q)\cup M$. ∎

Next we prove an upper bound on our witness function

$\displaystyle C(P,Q)_{\ket{\psi}}:=\left|\expectationvalue{P\infty
Q}{\psi}-\expectationvalue{P}{\psi}\expectationvalue{Q}{\psi}\right|,$ (60)

which can be understood as a “robust” version of Haah’s witness function [9].

Upper bounding this approximate witness function will be instrumental in
proving our circuit-depth lower bound. This will follow with the help of
Proposition 2 and 3. Our setup will be the same as in Figure 4(b).

######  Theorem 2.

Let $\left(\\{P,Q\\},\Pi,\rho_{\Lambda}\right)$ be a $(\delta,r,t)$-triple,
where $P$ and $Q$ are as defined in Proposition 3. Then for $k_{P}$ as defined
in Proposition 2 and $k_{Q}$ as defined in Proposition 3, we have that

$\displaystyle\left|\expectationvalue{P\infty
Q}{\psi}-\expectationvalue{P}{\psi}\expectationvalue{Q}{\psi}\right|\leq
2\delta\left(\alpha_{P}k_{Q}+\alpha_{Q}k_{P}\right),$ (61)

with $\alpha_{P}$ and $\alpha_{Q}$ being defined as in Proposition 3.

###### Proof.

The proof follows via triangle inequality, as well as using Eq. (48) and our
bounds proved in Propositions 2 and 3 respectively.
Let $\mathcal{P}^{\prime}\supset p(D)$ be as defined in Proposition 3. Adding
and substracting the two terms
$\expectationvalue{P\Pi_{\mathcal{P}^{\prime}}\infty Q}{\psi}$ and
$\expectationvalue{\Pi_{\mathcal{P}^{\prime}}\infty
Q}{\psi}\expectationvalue{P}{\psi}$ to the LHS of Eq. (61) and applying
triangle inequality, we get:

$\displaystyle\left|\expectationvalue{P\infty
Q}{\psi}-\expectationvalue{P}{\psi}\expectationvalue{Q}{\psi}\right|$
$\displaystyle\leq\left|\expectationvalue{P\infty
Q}{\psi}-\expectationvalue{P\Pi_{\mathcal{P}^{\prime}}\infty Q}{\psi}\right|$
$\displaystyle+\left|\expectationvalue{P\Pi_{\mathcal{P}^{\prime}}\infty
Q}{\psi}-\expectationvalue{\Pi_{\mathcal{P}^{\prime}}\infty
Q}{\psi}\expectationvalue{P}{\psi}\right|$
$\displaystyle+\left|\expectationvalue{\Pi_{\mathcal{P}^{\prime}}\infty
Q}{\psi}\expectationvalue{P}{\psi}-\expectationvalue{Q}{\psi}\expectationvalue{P}{\psi}\right|,$
(62) $\displaystyle\leq
2\delta\,k_{Q}\alpha_{P}+\left|\expectationvalue{\left(P\Pi_{\mathcal{P}^{\prime}}-\Pi_{\mathcal{P}^{\prime}}\expectationvalue{P}{\psi}\right)\infty
Q}{\psi}\right|,$ (63)

where the third term vanishes since
$\expectationvalue{\Pi_{\mathcal{P}^{\prime}}\infty
Q}{\psi}=\expectationvalue{Q}{\psi}$ and where the first term can be upper
bounded using Proposition 3. Using Cauchy-Schwarz on the second term and
switching to operator norm it follows that

$\displaystyle\left|\expectationvalue{P\infty
Q}{\psi}-\expectationvalue{P}{\psi}\expectationvalue{Q}{\psi}\right|$
$\displaystyle\leq
2\delta\,k_{Q}\alpha_{P}+\left\|{P\Pi_{\mathcal{P}^{\prime}}-\Pi_{\mathcal{P}^{\prime}}\expectationvalue{P}{\psi}}\right\|_{\infty}\sum_{j}\left\|{Q_{M^{c}}^{j}}\right\|_{\infty}\left\|{Q_{M}^{j}}\right\|_{\infty}$
(64) where we have used that $\left\|{P\infty
Q}\right\|_{\infty}=\left\|{\sum_{j}Q_{M}^{j}PQ_{M^{c}}^{j}}\right\|_{\infty}\leq\left\|{P}\right\|_{\infty}\sum_{j}\left\|{Q_{M}^{j}}\right\|_{\infty}\left\|{Q_{M^{c}}^{j}}\right\|_{\infty}$.
Bounding the second term using Proposition 2, we obtain $\displaystyle\leq
2\delta k_{Q}\alpha_{P}+2\delta
k_{P}\alpha_{Q}=2\delta\left(\alpha_{P}k_{Q}+\alpha_{Q}k_{P}\right)$ (65)

∎

##  7 Circuit depth lower bound for low-energy states

We will now apply the tools we have developed in the previous sections in
order to prove a circuit depth lower bound for low-energy states
$\rho^{\epsilon}_{\Lambda}$ of of the toric code Hamiltonian in 2D with no
assumptions on the ground space degeneracy.

We will prove our result by showing that the stabilizers of toric code yield
approximately locally invisible operators for low-energy states. Our starting
point will be to show that for any such state $\rho^{\epsilon}_{\Lambda}$, one
can find a region $R\subset\Lambda$ on which the state has high overlap with
its projection onto the ground space of $H_{R}$, i.e. the restriction of
$H_{\Lambda}$ to region $R$. This implies that any toric code stabilizer
$s_{R}$ supported on region $R$ that is exactly locally invisible with respect
to any of the states in the ground space of $H_{R}$, is approximately locally
invisible with respect to low-energy states $\rho^{\epsilon}_{\Lambda}$ of
$H_{\Lambda}$.

While we consider the toric code for concreteness, our bound applies to all
commuting projector models in 2D for which there exist local operators that
stabilize any ground state and that are constant depth unitaries.

###  7.1 Approximately locally invisible operators for low-energy states

We now introduce the notion of _good subsystem_ and show how it can be used to
find approximately locally invisible operators for low-energy states of
certain classes of Hamiltonians. Intuitively, a “good” subsystem is a
subsystem whose energy density within that subsystem is “sufficiently low.”
This Section contains two elementary but useful facts. The first fact is that,
if a global state has an energy density of $\epsilon$, for any $\ell\leq L$,
there is a subsystem of size $\ell\times\ell$ with local energy density at
most $\epsilon$. We shall refer to such a subsystem as a $\epsilon$-good
subsystem. The second fact is that an $\epsilon$-good subsystem has
$\Omega(1)$ overlap with some state in the ground space of the subsystem,
provided that $\epsilon$ is smaller than the inverse of the subsystem size.

Let us state the formal definition below.

######  Definition 6.

A subsystem $R\subset\Lambda$ is $\epsilon$-good with respect to
$\rho_{\Lambda}$ and a Hamiltonian $H_{\Lambda}$ if $\rho_{\Lambda}$ has an
energy density of at most $\epsilon$ over $R$.

######  Lemma 6.

Let $\rho_{\Lambda}^{\epsilon}$ be a state with energy density $\epsilon$,
i.e. $\Tr[H_{\Lambda}\rho^{\epsilon}]=\epsilon\absolutevalue{\Lambda}$. For
any $\ell$ such that $2\leq\ell\leq L$, there is a subsystem $R$ of size
$\ell\times\ell$ such that $R$ is $\epsilon$-good.

###### Proof.

Let $v_{\ell}$ be a $\ell\times\ell$ subsystem such that its bottom left
corner is $v\in\Lambda$. We may write our Hamiltonian as:

$H_{\Lambda}=\sum_{v\in\Lambda}\frac{H_{v_{\ell}}}{\ell^{2}}.$ (66)

Thus, we can conclude that

$\text{Tr}\left[\rho_{\Lambda}^{\epsilon}\frac{H_{\Lambda}}{L^{2}}\right]=\mathbb{E}_{v\sim\Lambda}\left[\text{Tr}\left[\rho_{\Lambda}^{\epsilon}\frac{H_{v_{\ell}}}{\ell^{2}}\right]\right],$
(67)

where $\mathbb{E}_{v\sim\Lambda}[\cdot]$ is the average over $v$ chosen
uniformly randomly over $\Lambda$. Since the left hand side of Eq. (67) is
$\epsilon$, we conclude that the mean of
$\text{Tr}\left[\rho_{\Lambda}\frac{H_{v_{\ell}}}{\ell^{2}}\right]$ ought to
be $\epsilon$. If this quantity is strictly larger than $\epsilon$, we arrive
at a contradiction. Therefore, there exists a $v\in\Lambda$ such that
$\text{Tr}\left[\rho_{\Lambda}^{\epsilon}\frac{H_{v_{\ell}}}{\ell^{2}}\right]\leq\epsilon.$

$\text{Tr}\left[\rho_{\Lambda}^{\epsilon}\frac{H_{v_{\ell}}}{\ell^{2}}\right]\leq\epsilon.$
(68)

∎

Having shown that for any low-energy state $\rho^{\epsilon}$ there exists a
local patch $R$ with energy density at most $\epsilon$, we are now in position
to show that any low-energy state is close to its projection onto the ground
space of $H_{R}$ provided certain conditions on $H_{\Lambda}$ hold. While we
can prove such a statement for general frustration-free Hamiltonians with a
local gap (see Appendix A), we will only consider frustration-free, commuting
Hamiltonians for now.

We show how these conditions imply that the projection onto the ground space
of $H_{R}$ approximately stabilizes the low-energy state, i.e.,
$\rho_{\Lambda}^{\epsilon}\approx\Pi_{R}^{\text{0}}\rho_{\Lambda}^{\epsilon}\Pi_{R}^{\text{0}}$.

######  Proposition 4.

Suppose $R$ is $\epsilon$-good with respect to $\rho_{\Lambda}^{\epsilon}$.
Then

$D_{p}\left(\rho_{\Lambda}^{\epsilon},\frac{\Pi_{R}^{0}\rho_{\Lambda}^{\epsilon}\Pi_{R}^{0}}{\text{Tr}\left[\Pi_{R}^{0}\rho_{\Lambda}^{\epsilon}\Pi_{R}^{0}\right]}\right)\leq\sqrt{|R|\epsilon}$
(69)

The proof of Proposition 4 is based on two well-known facts: the quantum union
bound [25] and the gentle measurement lemma [26]. We state these facts below
for the readers’ convenience.

######  Fact 7 (Commutative union bound[25]).

Let $\rho\in\mathcal{D}(\mathcal{H})$ and $\\{\Pi_{i}\\}$ be a set of
commuting projectors. Then we have

$1-\Tr[\left(\prod_{i}\Pi_{i}\right)\rho]\leq\sum_{i}\Tr[(\mathbbm{1}-\Pi_{i})\rho].$
(70)

######  Fact 8 (Gentle measurement lemma [26]).

Let $\Pi$ be a projection and $\rho\in\mathcal{D}(\mathcal{H})$, such that
$\Tr[\Pi\rho]\geq 1-\epsilon$. For
$\rho^{\prime}=\frac{\Pi\rho\Pi}{\Tr[\Pi\rho\Pi]}$, the following bound holds:

$D_{p}(\rho,\rho^{\prime})\leq\sqrt{\epsilon}.$ (71)

The gentle measurement lemma is usually stated in terms of the trace distance.
Here we use a version that is more suitable for our purpose and is also
tighter by a constant factor. This version of the lemma follows from
Eq.(9.202) in Ref. [26].

Now we are in a position to prove Proposition 4.

_Proof of Proposition 4._ Using the union bound (Fact 7) to lower bound the
energy of $\rho_{\Lambda}^{\epsilon}$ over the patch $R$, we have

$\displaystyle\text{Tr}\left[\rho^{\epsilon}_{\Lambda}H_{R}\right]\geq
1-\Tr[\left(\prod_{s\in
S_{R}}\frac{\mathbbm{1}+s}{2}\right)\rho^{\epsilon}_{\Lambda}].$ (72)

As $R$ is $\epsilon$-good it follows that

$|R|\epsilon\geq 1-\Tr[\left(\prod_{s\in
S_{R}}\frac{\mathbbm{1}+s}{2}\right)\rho^{\epsilon}_{\Lambda}].$ (73)

Since $\prod_{s\in S_{R}}\frac{I+s}{2}=\Pi_{R}^{0}$, we conclude

$\Tr[\Pi_{R}^{0}\rho^{\epsilon}_{\Lambda}]\geq 1-|R|\epsilon.$ (74)

From Fact 8, the claim follows.

∎

This bound tells us that distance of $\rho^{\epsilon}_{R}$ to the local ground
state
$\rho^{0}_{R}:=\frac{\Pi_{R}^{0}\rho_{R}^{\epsilon}\Pi_{R}^{0}}{\text{Tr}\left[\Pi_{R}^{0}\rho_{R}^{\epsilon}\Pi_{R}^{0}\right]}$
is constant, if the energy of $\rho_{R}^{\epsilon}$ is a constant. Therefore,
a low-energy state $\rho^{\epsilon}_{\Lambda}$ actually provides a good
approximation to a local ground state on any region $R$ with a constant energy
$\absolutevalue{R}\epsilon<1$.

The bound given in Proposition 4 is key in allowing us to find approximately
locally invisible operators for low-energy states $\rho^{\epsilon}_{\Lambda}$
of the toric code Hamiltonian.

######  Corollary 2.

Let $\rho^{\epsilon}_{\Lambda}$ be a state of energy density at most
$\epsilon$ with respect to the toric code Hamiltonian $H_{\Lambda}$. Suppose
$R$ is an $\epsilon$-good subsystem. Then any any
$s\in\mathcal{S}^{\text{TC}}_{R}$ is $(\delta,r,t)$-approximately locally
invisible with respect to $\rho^{\epsilon}_{\Lambda}$ for
$\delta=2\sqrt{|R|\epsilon}\,\,$ and
$r=\mathcal{O}\left(\sqrt{\Lambda}\right)$ and $t=2$.

###### Proof.

Let
$\rho^{0}_{\Lambda}:=\frac{\Pi_{R}^{0}\rho_{\Lambda}^{\epsilon}\Pi_{R}^{0}}{\text{Tr}\left[\Pi_{R}^{0}\rho_{R}^{\epsilon}\Pi_{R}^{0}\right]}$.
As the support of $s$ is contained in $R$ it follows from Fact 1 that any $s$
is $(r,t)$-locally invisible with respect to $\rho^{0}_{\Lambda}$ for
$r=\mathcal{O}\left(\sqrt{\Lambda}\right)$ and $t=\Omega(1)$. Since $s$ is a
depth-1 unitary, one may choose $t=2$. From Proposition 4 and Lemma 1 our
claim then follows. ∎

This is precisely what we need in order to apply our formalism developed in
Sections 4-6 to low-energy states. This is the content of our main theorem.

###  7.2 Main theorem

Having found non-trivial $(\delta,r,t)$-approximately locally invisible
operators for low-energy states $\rho^{\epsilon}_{\Lambda}$ of the toric code
Hamiltonian, we are now in a position to prove a circuit-depth lower bound for
these states. See 1

###### Proof.

Our proof follows from giving upper and lower bounds on $C(P,Q)_{\ket{\psi}}$
for $P$ and $Q$ chosen to be toric code stabilizers supported on the
$\epsilon$-good subsystem $R$ of $\rho^{\epsilon}_{\Lambda}$. We will prove an
upper bound in terms of the circuit depth $D$ required to prepare any low-
energy state $\rho^{\epsilon}_{\Lambda}$ and a lower bound in terms of the
energy of $\rho^{\epsilon}_{\Lambda}$ over the patch $R$.

Let $\ket{\psi^{\epsilon}}_{\Lambda^{\prime}}$ be the purification of
$\rho^{\epsilon}_{\Lambda}$. Let $R\subset\Lambda\subset\Lambda^{\prime}$ be
an $\epsilon$-good patch and let $s_{R}^{X},s_{R}^{Z}\in S^{\text{TC}}_{R}$,
where the superscript denotes whether it is an $X$-type or $Z$-type
stabilizer, which are $(\delta,r,t)$-approximately invisible with respect to
$\rho_{\Lambda}^{\epsilon}$ as shown in Corollary 2. Then

$\displaystyle
C\left(s_{R}^{X},s_{R}^{Z}\right)_{\ket{\psi^{\epsilon}}}=\absolutevalue{\expectationvalue{s_{R}^{X}\infty
s_{R}^{Z}}{\psi^{\epsilon}}-\expectationvalue{s_{R}^{X}}{\psi^{\epsilon}}\expectationvalue{s_{R}^{Z}}{\psi^{\epsilon}}}\geq
2-3\sqrt{|R|\epsilon}+|R|\epsilon,$ (75)

where $C\left(s_{R}^{X},s_{R}^{Z}\right)_{\ket{\psi^{0}}}=2$. This bound
immediately follows from the fact that

$\displaystyle\left|\expectationvalue{O_{R}}{\psi^{\epsilon}}-\expectationvalue{O_{R}}{\psi^{0}}\right|\leq\left\|O_{R}\right\|_{\infty}\left\|\rho^{\epsilon}_{R}-\rho^{0}_{R}\right\|_{1},$
(76)

for any $O_{R}\in\mathcal{B}(\mathcal{H}_{R})$, where
$\ket{\psi^{0}}_{\Lambda^{\prime}}$ is a purification of
$\rho^{0}_{\Lambda^{\prime}}$ as defined in the proof of Corollary 2. Since
$\left\|s^{X}_{R}\infty
s^{Z}_{R}\right\|_{\infty}=\left\|s^{X}_{R}\right\|_{\infty}=\left\|s^{Z}_{R}\right\|_{\infty}=1$
and
$\expectationvalue{s^{X}_{R}}{\psi^{\epsilon}}=\expectationvalue{s^{Z}_{R}}{\psi^{\epsilon}}=1$
and $\expectationvalue{s^{X}_{R}\infty s^{X}_{R}}{\psi^{\epsilon}}=-1$ our
lower bound in Eq. (75). From Proposition 4 we have that
$\left\|\rho^{\epsilon}_{R}-\rho^{0}_{R}\right\|_{1}\leq\sqrt{|R|\epsilon}$.

Next, we prove an upper bound on
$C\left(s_{R}^{X},s_{R}^{Z}\right)_{\ket{\psi^{\epsilon}}}$ via Theorem 2. For
our choices of $P=s^{X}_{R}$ and $Q=s^{Z}_{R}$, we have that
$\delta=2\sqrt{\absolutevalue{R}\epsilon}$ and $\alpha_{P}=\alpha_{Q}=1$ and
therefore

$\displaystyle C\left(s_{R}^{X},s_{R}^{Z}\right)_{\ket{\psi^{\epsilon}}}\leq
2\sqrt{\absolutevalue{R}\epsilon}(k_{P}+k_{Q})$ (77)

To determine $k_{Q}$, we can choose the radius of the disc-shaped supports
$S_{i}(D)$ of the LMPs in Proposition 3 to be
$\text{rad}(S_{i}(D))=4D+t+\tau_{p}$, where $\tau_{p}$ denotes equals the
thickness of the annular support of $s^{x}_{R}$ and $t$ denotes the local
invisibility parameter. Thus, $k_{Q}=4\,\left(4D+t+\tau_{p}\right)$, since at
most $4\,\,\text{rad}\left(S_{i}(D)\right)$ discs will overlap with one of the
intersections of the two annuli formed by $s^{X}_{R}$ and $s^{Z}_{R}$.

For $k_{P}$ we can independently choose
$\text{rad}\left(S_{i}(D)\right)=\mathcal{O}(\sqrt{R})$, such that $k_{P}=1$.
This can be done, since $k_{P}$ and $k_{Q}$ bound independent terms in Eq.
(62). Given these choices of $k_{P}$ and $k_{Q}$, we have

$\displaystyle C\left(s_{R}^{X},s_{R}^{Z}\right)_{\ket{\psi^{\epsilon}}}\leq
2\sqrt{\absolutevalue{R}\epsilon}\left(9+16\,D\,\right),$ (78)

as $t=2$ and $\tau_{p}=1$ for the stabilizer $s^{x}_{R}$. Putting both upper
and lower bounds together, we then have

$\displaystyle 2-3\sqrt{|R|\epsilon}+|R|\epsilon\leq
C\left(s_{R}^{X},s_{R}^{Z}\right)_{\ket{\psi^{\epsilon}}}$ $\displaystyle\leq
2\sqrt{\absolutevalue{R}\epsilon}\left(9+16\,D\,\right),$ (79)
$\displaystyle\frac{1}{16\sqrt{\absolutevalue{R}\epsilon}}-\frac{21}{32}+\frac{1}{32}\sqrt{\absolutevalue{R}\epsilon}$
$\displaystyle\leq D,$ (80)

implying that $D=\Omega\left(1/\sqrt{\absolutevalue{R}\epsilon}\right)$. To
ensure a non-trivial value for the local invisibility parameter we require
$\sqrt{\absolutevalue{R}\epsilon}<1/2$ where $\epsilon\in[0,1)$ since we need
that $\absolutevalue{R}>1$. This condition is satisfied for
$R=\mathcal{O}(1/\epsilon^{\alpha})$ for $\alpha\in(0,1)$. We thus have

$\displaystyle
D=\Omega\left(1/\epsilon^{\frac{1-\alpha}{2}}\right)\,\,\,\,\,\,\,\,\text{for}\,\,\,\alpha\in(0,1)$
(81)

Our result then follows by taking the minimum between the bound in Eq.
(7.2)and a circuit lower bound for preparing the exact ground state. We can
obtain a lower bound for the exact ground state by invoking Corollary III.5 of
Haah’s work [9] and using the stabilizers as exactly locally invisible
operators for the ground state. The lower bound for preparing the ground state
then becomes $D=\Omega\left(d_{\text{sep}}\right)$, where $d_{\text{sep}}$ is
the distance between the two points of intersection of the annuli (see Figure
4(b)), which are now allowed to be supported on the whole lattice $\Lambda$.
Since our lattice is 2D, we have that
$d_{\text{sep}}=\mathcal{O}\left(\sqrt{\absolutevalue{\Lambda}}\right)$, such
that $D=\Omega\left(\sqrt{\absolutevalue{\Lambda}}\right)$. ∎

Some comments are in order. While we have stated our main theorem in terms of
the toric code with arbitrary ground space dimension, our lower bound holds
for any CSS stabilizer code with stabilizers that can be contained in an
$\epsilon$-good subsystem $R$ and which intersect at only two points. A
natural choice for this are codes with deformable and contractable loop-like
stabilizers that can be made to fit onto any patch $R$, as can be found in the
2D surface or color codes [27]. For such codes, one can always find depth-1
unitaries that can be supported on some local patch $R$ and made to intersect
at two distant points.

Note that our lower bound does not depend on the explcit value of the twist
pairing $\expectationvalue{s^{X}\infty s^{Z}}{\psi}$ and therefore applies to
any model with constant-depth unitaries that leave any ground state invariant
. Examples for this are the quantum double models defined for abelian groups
and string-net models [6, 7] and therefore also include Hamiltonians beyond
the stabilizer formalism.

It is important to note that our bounds implicitly depend on the circuit depth
of the approximately locally invisible unitaries $P$ and $Q$. In particular,
$\alpha_{P}=\mathcal{O}\left(\exp(\text{depth}(P))\right)$ for a general
unitary and likewise for $\alpha_{Q}$. Our circuit depth lower bound technique
is therefore suitable for models for which one can find operators $P$ and $Q$
of constant depth.

##  8 Outlook

To summarize, we prove a rigorous circuit-depth lower bound for preparing low-
energy states of a two-dimensional topologically ordered system. The main
surprise is that the complexity, quantified in terms of the depth of the
circuit, is lower bounded as a polynomial in $1/\epsilon$. This suggests a
subtle difference between topologically ordered Hamiltonians and trivial
Hamiltonians at finite temperature, and also shows a fundamental difficulty in
approximating local quantities of these systems at low energy using low-depth
circuits.

Going further, we believe that our techniques can be generalized to the
setting where our local Hamiltonian is defined on an arbitrary graph and the
circuits that prepare its ground states or low-energy states admit all-to-all
connectivity. We hope that this might pave the way to finding Hamiltonians
that satisfy the NLTS theorem with no requirement on the degeneracy of the
ground space.

Note: During the completion of this work, we became aware of independent work
by Cong et al. [28], which also derives a circuit depth lower bound for the
toric code. Our results agree where they overlap.

## Acknowledgements

AT would like to thank Dom Williamson for helpful comments. IK thanks Robert
Koenig for a helpful discussion. This research was supported in part by the
National Science Foundation under Grant No. NSF PHY-1748958. We thank the
Kavli Institute for Theoretical Physics for hospitality while part of this
work was completed. AT was supported by the Sydney Quantum Academy, Sydney,
NSW, Australia.

## References

  * [1] Sam McArdle et al.  “Quantum computational chemistry”  In _Rev. Mod. Phys._ 92 American Physical Society, 2020, pp. 015003  DOI: 10.1103/RevModPhys.92.015003
  * [2] Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi and Mikhail N Vyalyi  “Classical and quantum computation”  American Mathematical Soc., 2002
  * [3] Lin Lin and Yu Tong  “Near-optimal ground state preparation”  In _Quantum_ 4 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2020, pp. 372  DOI: 10.22331/q-2020-12-14-372
  * [4] John Preskill  “Quantum Computing in the NISQ era and beyond”  In _Quantum_ 2 Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften, 2018, pp. 79  DOI: 10.22331/q-2018-08-06-79
  * [5] Alberto Peruzzo et al.  “A variational eigenvalue solver on a photonic quantum processor”  In _Nature Communications_ 5.1 Springer ScienceBusiness Media LLC, 2014  DOI: 10.1038/ncomms5213
  * [6] A.Yu. Kitaev  “Fault-tolerant quantum computation by anyons”  In _Annals of Physics_ 303.1, 2003, pp. 2–30  DOI: https://doi.org/10.1016/S0003-4916(02)00018-0
  * [7] Michael A. Levin and Xiao-Gang Wen  “String-net condensation: A physical mechanism for topological phases”  In _Physical Review B_ 71.4 American Physical Society (APS), 2005  DOI: 10.1103/physrevb.71.045110
  * [8] S. Bravyi, M.. Hastings and F. Verstraete  “Lieb-Robinson Bounds and the Generation of Correlations and Topological Quantum Order”  In _Physical Review Letters_ 97.5 American Physical Society (APS), 2006  DOI: 10.1103/physrevlett.97.050401
  * [9] Jeongwan Haah  “An Invariant of Topologically Ordered States Under Local Unitary Transformations”  In _Communications in Mathematical Physics_ 342.3 Springer ScienceBusiness Media LLC, 2016, pp. 771–801  DOI: 10.1007/s00220-016-2594-y
  * [10] Dorit Aharonov, Itai Arad and Thomas Vidick  “The Quantum PCP Conjecture”  arXiv, 2013  DOI: 10.48550/ARXIV.1309.7495
  * [11] Anurag Anshu and Chinmay Nirkhe  “Circuit lower bounds for low-energy states of quantum code Hamiltonians”, 2021  arXiv:2011.02044 [quant-ph]
  * [12] Anurag Anshu, Nikolas P. Breuckmann and Chinmay Nirkhe  “NLTS Hamiltonians from good quantum codes”  arXiv, 2022  DOI: 10.48550/ARXIV.2206.13228
  * [13] Marco Tomamichel  “A Framework for Non-Asymptotic Quantum Information Theory”  arXiv, 2012  DOI: 10.48550/ARXIV.1203.2142
  * [14] Christopher A. Fuchs and Jeroen Graaf  “Cryptographic Distinguishability Measures for Quantum Mechanical States”, 1998  arXiv:quant-ph/9712042 [quant-ph]
  * [15] Robert König and Fernando Pastawski  “Generating topological order: No speedup by dissipation”  In _Physical Review B_ 90.4 American Physical Society (APS), 2014  DOI: 10.1103/physrevb.90.045101
  * [16] Daniel Gottesman  “Stabilizer Codes and Quantum Error Correction”  arXiv, 1997  DOI: 10.48550/ARXIV.QUANT-PH/9705052
  * [17] Barbara M. Terhal  “Quantum error correction for quantum memories”  In _Reviews of Modern Physics_ 87.2 American Physical Society (APS), 2015, pp. 307–346  DOI: 10.1103/revmodphys.87.307
  * [18] Matthew B. Hastings  “Topological Order at Nonzero Temperature”  In _Phys. Rev. Lett._ 107 American Physical Society, 2011, pp. 210501  DOI: 10.1103/PhysRevLett.107.210501
  * [19] M.. Hastings and Xiao-Gang Wen  “Quasiadiabatic continuation of quantum states: The stability of topological ground-state degeneracy and emergent gauge invariance”  In _Physical Review B_ 72.4 American Physical Society (APS), 2005  DOI: 10.1103/physrevb.72.045141
  * [20] Jeongwan Haah, Matthew B. Hastings, Robin Kothari and Guang Hao Low  “Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians”  In _SIAM Journal on Computing_ Society for Industrial & Applied Mathematics (SIAM), 2021, pp. FOCS18–250–FOCS18–284  DOI: 10.1137/18m1231511
  * [21] Álvaro M. Alhambra and J. Cirac  “Locally Accurate Tensor Networks for Thermal States and Time Evolution”  In _PRX Quantum_ 2 American Physical Society, 2021, pp. 040331  DOI: 10.1103/PRXQuantum.2.040331
  * [22] Jan Lukas Bosse and Ashley Montanaro  “Probing ground state properties of the kagome antiferromagnetic Heisenberg model using the Variational Quantum Eigensolver”  arXiv, 2021  DOI: 10.48550/ARXIV.2108.08086
  * [23] Chris Cade, Lana Mineh, Ashley Montanaro and Stasja Stanisic  “Strategies for solving the Fermi-Hubbard model on near-term quantum computers”  In _Physical Review B_ 102.23 American Physical Society (APS), 2020  DOI: 10.1103/physrevb.102.235122
  * [24] Ze-Pei Cian, Mohammad Hafezi and Maissam Barkeshli  “Extracting Wilson loop operators and fractional statistics from a single bulk ground state”  arXiv, 2022  DOI: 10.48550/ARXIV.2209.14302
  * [25] Samad Khabbazi Oskouei, Stefano Mancini and Mark M. Wilde  “Union bound for quantum information processing”  In _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ 475.2221 The Royal Society, 2019, pp. 20180612  DOI: 10.1098/rspa.2018.0612
  * [26] Mark M. Wilde  “Preface to the Second Edition”  In _Quantum Information Theory_ Cambridge University Press, pp. xi–xii  DOI: 10.1017/9781316809976.001
  * [27] H. Bombin  “An Introduction to Topological Quantum Codes”  arXiv, 2013  DOI: 10.48550/ARXIV.1311.0277
  * [28] Iris Cong et al.  “Enhancing Detection of Topological Order by Local Error Correction”  arXiv, 2022  DOI: 10.48550/ARXIV.2209.12428
  * [29] Jingliang Gao  “Quantum union bounds for sequential projective measurements”  In _Physical Review A_ 92.5 American Physical Society (APS), 2015  DOI: 10.1103/physreva.92.052331
  * [30] Anurag Anshu, Itai Arad and Thomas Vidick  “Simple proof of the detectability lemma and spectral gap amplification”  In _Physical Review B_ 93.20 American Physical Society (APS), 2016  DOI: 10.1103/physrevb.93.205142
  * [31] Dorit Aharonov, Itai Arad, Zeph Landau and Umesh Vazirani  “Quantum Hamiltonian complexity and the detectability lemma”  arXiv, 2010  DOI: 10.48550/ARXIV.1011.3445

##  Appendix A Leakage bound for locally gapped frustration-free Hamiltonians

Here we prove a generalization of our leakage bound from Section 7.1 to non-
commuting but frustration-free systems that are locally gapped. While we do
not use this result for our main result we include it here since it may be of
independent interest. Our proof will follow analagously, but we will make a
slight modification by using Gao’s union bound [29] for non-commutative
projections and apply it to the so-called detectability lemma operator [30],
instead of the ground space projector itself.

We will now briefly state a version of the detectability lemma and its
converse which cater to our needs and whose proofs can be found in [30]. The
detectability lemma defines an approximate ground space projector (AGSP) for
any gapped frustration-free Hamiltonian in terms of a product of the local
Hamiltonian terms in a particular staggered ordering (see [31] for more
details) . We will use the detectability lemma and its converse together with
the gentle measurement lemma to bound the distance of our low-energy state to
the local ground space. We will now briefly state these lemmas without going
into much detail and we will defer the proofs to their respective references.

######  Fact 9.

(Detectability lemma) Let $H=\sum_{i}\mathbbm{1}-\Pi_{i}$ be a frustration-
free local Hamiltonian with gap $\gamma$, for a set of projections
$\\{\Pi_{i}\\}$ and let $\Pi^{0}$ denote the projection onto the ground space
of $H$. Then there exists an ordered product $\text{DL}(H):=\prod_{i}\Pi_{i}$
, s.t. for any $\ket{\psi}$ we have that

$\displaystyle\norm{\text{DL}(H)(\mathbbm{1}-\Pi^{0})\ket{\psi}}^{2}\leq\left(\frac{\gamma}{g^{2}}+1\right)^{-1}$
(82)

where $g\in\mathbbm{N}^{+}$ is a constant for any geometrically local
Hamiltonians in any dimension and $q\in\mathbbm{N}^{+}$.

Since $H$ is frustration-free, $\text{DL}(H)$ exactly stabilizes the ground
space, i.e. $\text{DL}(H)\Pi^{0}=\Pi^{0}$ and we may therefore equivalently
write Equation 82 as
$\left\|{\Pi^{0}-\text{DL}(H)}\right\|_{\infty}\leq\left(\frac{\gamma}{g^{2}}+1\right)^{-\frac{1}{2}}$.
Moreover, one may apply Gao’s union bound [29] to $\text{DL}(H)$ to in order
prove a converse to the detectability lemma.

######  Fact 10.

(Converse of the detectability lemma) Let $\rho\in\mathcal{H}$ be an arbitrary
state and let $\text{DL}(H)$ be the detectability lemma operator for a local
Hamiltonian $H=\sum_{i}\mathbbm{1}-\Pi_{i}$ as defined in Fact 9.

$\displaystyle\Tr[\text{DL}^{\dagger}(H)\text{DL}(H)\rho]\geq 1-4\Tr[H\rho]$
(83)

The converse will be useful to us as it will allow us to make a statement
about the actual distance of $\rho^{\epsilon}_{R}$ to the ground space of
$H_{R}$ only in terms of $\Tr[H_{R}\rho^{\epsilon}_{R}]$ and the local gap
$\gamma_{R}$.

######  Proposition 5.

Let $H_{\Lambda}=\sum_{X\subset\Lambda}\mathbbm{1}-\Pi_{X}$ be a frustration-
free, non-commuting local Hamiltonian and suppose $R\subset\Lambda$ is
$\epsilon$-good for a low-energy state $\rho_{\Lambda}^{\epsilon}$. Suppose
$\Pi^{0}_{R}$ is the projection onto the ground space of $H_{R}$. Then

$\displaystyle
D_{p}\left(\rho_{\Lambda}^{\epsilon},\frac{\Pi_{R}^{0}\rho_{\Lambda}^{\epsilon}\Pi_{R}^{0}}{\text{Tr}\left[\Pi_{R}^{0}\rho_{\Lambda}^{\epsilon}\Pi_{R}^{0}\right]}\right)$
$\displaystyle\leq\sqrt{4\absolutevalue{R}\epsilon+\left(\frac{\gamma_{R}}{g^{2}}+1\right)^{-1}},$
(84)

where $\gamma_{R}$ denotes the local gap of $H_{\Lambda}$, which we assume to
be a constant.

###### Proof.

Our proof strategy is to give a lower bound to
$\Tr[\Pi^{0}_{R}\rho_{R}^{\epsilon}]$ by using the fact that we may use the
converse of the detectability lemma and our low-energy assumption to give a
lower bound to
$\Tr[\text{DL}^{\dagger}(H_{R})\text{DL}(H_{R})\rho_{R}^{\epsilon}]$ and the
fact that $\text{DL}(H_{R})$ is an approximation to $\Pi^{0}_{R}$. Our
estimate for $\Tr[\Pi^{0}_{R}\rho_{R}^{\epsilon}]$ then allows to invoke the
gentle measurement lemma. We thus have

$\displaystyle\left\|{\text{DL}^{\dagger}(H_{R})\text{DL}(H_{R})-\Pi^{0}_{R}}\right\|_{\infty}$
$\displaystyle=\sup_{\norm{\ket{\psi}}=1}\norm{\text{DL}^{\dagger}(H_{R})\text{DL}(H_{R})(\mathbbm{1}-\Pi_{R}^{0})\ket{\psi}}$
(85)
$\displaystyle\leq\sup_{\norm{\ket{\psi}}=1}\left\|{\text{DL}^{\dagger}(H_{R})}\right\|_{\infty}\norm{(\text{DL}(H_{R})(\mathbbm{1}-\Pi_{R}^{0})\ket{\psi}}\leq\left(\frac{\gamma_{R}}{g^{2}}+1\right)^{-1},$
(86)

where the last line follows from the definition of the operator norm, the fact
that $\left\|{\text{DL}^{\dagger}(H_{R})}\right\|_{\infty}\leq 1$ since it is
a product of projections and the use of the detectability lemma. With regards
to an estimate of $\Tr[\Pi^{0}_{R}\rho^{\epsilon}_{\Lambda}]$, we therefore
have

$\displaystyle\left|\Tr[\Pi^{0}_{R}\rho^{\epsilon}_{\Lambda}]-\Tr[\text{DL}^{\dagger}(H_{R})\text{DL}(H_{R})\rho^{\epsilon}_{\Lambda}]\right|\leq\left(\frac{\gamma_{R}}{g^{2}}+1\right)^{-1}.$
(87)

Using our low-energy assumption and the converse of the detectability lemma
gives

$\displaystyle\Tr[\Pi^{0}_{R}\rho^{\epsilon}_{\Lambda}]\geq
1-\left(4\absolutevalue{R}\epsilon+\left(\frac{\gamma_{R}}{g^{2}}+1\right)^{-1}\right).$
(88)

From the gentle measurement lemma, our proposition then follows.

∎