# Efficient Quantum Algorithm for Filtering Product States

Reinis Irmejs<EMAIL_ADDRESS>Max-Planck-Institut für Quantenoptik,
Hans-Kopfermann-Straße 1, D-85748 Garching, Germany  Munich Center for Quantum
Science and Technology (MCQST), Schellingstraße 4, D-80799 Munich, Germany
Mari Carmen Bañuls  Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-
Straße 1, D-85748 Garching, Germany  Munich Center for Quantum Science and
Technology (MCQST), Schellingstraße 4, D-80799 Munich, Germany  J. Ignacio
Cirac  Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße 1, D-85748
Garching, Germany  Munich Center for Quantum Science and Technology (MCQST),
Schellingstraße 4, D-80799 Munich, Germany

###### Abstract

We introduce a quantum algorithm to efficiently prepare states with an
arbitrarily small energy variance at the target energy. We achieve it by
filtering a product state at the given energy with a Lorentzian filter of
width $\delta$. Given a local Hamiltonian on $N$ qubits, we construct a parent
Hamiltonian whose ground state corresponds to the filtered product state with
variable energy variance proportional to $\delta\sqrt{N}$. We prove that the
parent Hamiltonian is gapped and its ground state can be efficiently
implemented in $\text{poly}(N,1/\delta)$ time via adiabatic evolution. We
numerically benchmark the algorithm for a particular non-integrable model and
find that the adiabatic evolution time to prepare the filtered state with a
width $\delta$ is independent of the system size $N$. Furthermore, the
adiabatic evolution can be implemented with circuit depth
$\mathcal{O}(N^{2}\delta^{-4})$. Our algorithm provides a way to study the
finite energy regime of many body systems in quantum simulators by directly
preparing a finite energy state, providing access to an approximation of the
microcanonical properties at an arbitrary energy.

##  I Introduction

Quantum computing introduces a novel approach to computational tasks, with one
of the main advantages being the efficient simulation of physical quantum
systems. The advantage lies in the potential for exponential enhancement in
spatial resources by encoding the system’s degrees of freedom into qubits,
enabling direct operations and calculations on them [1, 2, 3, 4].

A particularly compelling application pertains to determining the ground state
properties of systems – a realm of zero-temperature behavior. While, in
general, identifying the ground state of a local Hamiltonian stands as a QMA-
hard problem [5, 6], for typical physically relevant systems solutions are
attainable. Quantum adiabatic evolution offers a method for preparing the
ground state of a specified Hamiltonian. This process commences from a readily
preparable ground state of the Hamiltonian $H_{0}$ and involves time-evolving
the system to a target Hamiltonian $H_{1}$. This strategy’s success relies on
an energy gap that scales favorably with system size [7].

Nonetheless, studying excited states is equally important, particularly to
understand systems in thermal equilibrium. In practice, addressing a
particular eigenstate of the system is extremely difficult. However, analyzing
states of a small energy variance around the target energy is equally
interesting. Having access to finite energy states of a small energy variance
could be useful for studying physics in many fields. In the field of many-body
physics, one can calculate the expectation values for observables, perform
time dynamics simulations, and calculate entanglement properties of the state,
i.e., Renyi entropies [8, 9]. Furthermore, given access to two states at
different energies, it becomes possible to verify the predictions of the
eigenstate thermalization hypothesis [10]. In chemistry, the excited states
can be used to simulate molecular dynamics [11]. The preparation of such
states has been well studied using tensor networks [12, 13, 14]. In [13], a
relationship between the energy variance and the associated entanglement
entropy of the state was established, showing the need for a large bond
dimension to approximate the states with small energy variance.

The difficulty of analyzing the excited states classically has sparked an
interest in developing quantum algorithms for this purpose. The first quantum
algorithm to prepare excited states with reduced variance was quantum phase
estimation (QPE) [15, 16]; however, this approach is very costly. An
alternative is to use time series [17, 18, 19, 20, 21], which does not require
preparation of the state to extract its properties; nevertheless, it uses
costly controlled evolution operations. In [22], observables at a given energy
were calculated without direct state preparation but through energy filtering
with a cosine filter, deconstructing it into a sum of Loschmidt echoes coupled
with subsequent classical post-processing.

In this work, we propose a very different way of directly preparing a state of
small energy variance. For a given Hamiltonian $H$, we find a product state
$\ket{\Psi}$ at the target energy and filter it to an arbitrarily small
variance. This is achieved by defining a parent Hamiltonian $\mathcal{H}$ that
depends on $H$, $\ket{\Psi}$, and on a filter width parameter $\delta$ that is
proportional to the desired energy variance. By construction, the unique
ground state $\ket{\Phi}$ of the parent Hamiltonian $\mathcal{H}$ corresponds
to the filtered product state. Furthermore, we define a gapped adiabatic path
that connects the initial product state $\ket{\Psi}$ with the filtered state
$\ket{\Phi}$. Thus, performing adiabatic evolution along this path allows one
to efficiently prepare a finite variance approximation of the excited
eigenstate at a given energy. We notice that in [23], a similar parent
Hamiltonian construction was used to prepare a Gibbs state of a Hamiltonian
with commuting terms.

In Section II, we formally introduce the algorithm, in Section III, we perform
a numerical investigation to establish tighter bounds to the algorithmic
runtime, followed by a summary of our results in Section IV and our
conclusions and outlook in Section V.

##  II Method

###  II.1 Outline

In this work, we set out to perform the following task. We start with a local
Hamiltonian $H$ of interest and a product state $\ket{\Psi}$ that has energy
$E_{0}$ and variance $\sigma^{2}_{0}$ with respect to $H$. We want to create a
new state $\ket{\Phi}$ that has the same (or close) energy $E_{0}$ but a
substantially reduced variance $\sigma^{2}_{\mathcal{L}}$. This is similar to
preparing a microcanonical superposition at energy $E_{0}$, just with a finite
width. We develop an algorithm that allows us to arbitrarily reduce the
variance $\sigma^{2}_{\mathcal{L}}$ in $\text{poly}(N,\delta^{-1})$ time. We
achieve this by applying a Lorentzian filter of width $\delta$ on top of the
product state $\ket{\Psi}$ (FIG. 1) and suppressing the components of
eigenstates with energy far away from $E_{0}$. In the rest of the section, we
formally show how this task can be done in a polynomial time, with respect to
the system size $N$ and the desired energy variance
$\sigma^{2}_{\mathcal{L}}$.

Figure 1: Illustration of the filtering. The figure shows the density of
states (DOS) for the Hamiltonian $H$ and the product state $\ket{\Psi}$. The
red line shows the process of applying the Lorentzian filter
$\mathcal{F}^{-1}_{\mathcal{L}}$ onto the product state $\ket{\Psi}$, which
leads to a state of reduced energy variance.

The algorithm informally proceeds as follows:

  1. 1.

Start with a product state $\ket{\Psi}$, at the desired energy $E_{0}$. Define
projectors $P_{i}$ on each site $i$ that annihilate the state $\ket{\Psi}$.
The sum of these projectors $P=\sum_{i}P_{i}$ defines a Hamiltonian whose
ground state is the product state (see Lemma II.1).

  2. 2.

Pick the width $\delta$ of the Lorentzian filter to be applied to
$\ket{\Psi}$.

  3. 3.

Construct the parent Hamiltonian:

$\displaystyle\mathcal{H}(E_{0},\delta)=\sum_{i}\mathcal{F}_{\mathcal{L}}^{\dagger}P_{i}\mathcal{F}_{\mathcal{L}},$
$\displaystyle\text{where}\quad\mathcal{F}_{\mathcal{L}}=(1+i\delta^{-1}(H-E_{0})).$

The parent Hamiltonian $\mathcal{H}$ has a unique ground state that
corresponds to the filtered state (Lemma II.1), and it remains gapped (Lemma
II.2).

  4. 4.

Prepare the filtered state $\ket{\Phi}$ by adiabatically evolving the product
state $\ket{\Psi}$ with $\mathcal{H}(\delta)$ by slowly increasing
$\delta^{-1}(s)=s\delta^{-1}$ from $s=0$ to $1$. In Lemma II.3, we show that
the adiabatic evolution time is $T=\text{poly}(N,\delta^{-1})$. Note that
$\mathcal{H}(s=0)=P$. In Lemma B, we address the circuit depth required for
Trotterized time evolution.

  5. 5.

By choosing a suitable $\delta$, we can thus prepare a filtered product state
of arbitrary energy variance. In Lemma II.4, we discuss how the variance of
the filtered state decreases with $\delta$ in the thermodynamic limit.

###  II.2 The algorithm

Let $H$ be a local Hamiltonian of interest with eigenbasis
$H\ket{e_{n}}=e_{n}\ket{e_{n}}$ and $\ket{\Psi}$ be a product state for which
we can define local projectors $P_{i}$ that annihilate it. Let the energy of
the product state be $E_{0}$. We set out to prepare the filtered state
$\ket{\Phi}$, corresponding to filter $\mathcal{F}_{\mathcal{L}}$. This state
is given by $\ket{\Phi}\propto\mathcal{F}^{-1}_{\mathcal{L}}\ket{\Psi}$. In
this paper, we will use the Lorentzian filter $\mathcal{F}_{\mathcal{L}}$;
however, the strategy works for any filter that is polynomial in $H$. The
Lorentzian filter is given by

$\mathcal{F}_{\mathcal{L}}(E,\delta)=(1+i\delta^{-1}(H-E)),$ (1)

with the corresponding filtered state :

$\displaystyle\ket{\Phi}\propto\mathcal{F}^{-1}_{\mathcal{L}}\ket{\Psi}=\sum_{n}\frac{c_{n}}{1+i\delta^{-1}(e_{n}-E)}\ket{e_{n}},$
(2)
$\displaystyle\absolutevalue{\bra{e_{n}}\ket{\Phi}}^{2}\propto\frac{\absolutevalue{c_{n}}^{2}}{1+\delta^{-2}(e_{n}-E)^{2}}.$
(3)

Note that the probability amplitude of $\ket{e_{n}}$ has been suppressed here
by a Lorentzian factor
$\frac{\absolutevalue{c_{n}}^{2}}{1+\delta^{-2}(e_{n}-E)^{2}}$.

For a filter $\mathcal{F}_{\mathcal{L}}$ and initial state $\ket{\Psi}$ we can
define the parent Hamiltonian $\mathcal{H}$:

$\mathcal{H}=\sum_{i}\mathcal{F}^{\dagger}_{\mathcal{L}}P_{i}\mathcal{F}_{\mathcal{L}}.$
(4)

Note that for a local Hamiltonian $H$, the operator norm of the parent
Hamiltonian scales as $\norm{\mathcal{H}}=\mathcal{O}(N^{3}\delta^{-2})$. We
take this scaling into account when establishing the bounds for the runtime
and circuit depth. In the rest of the section, we formally show that by
finding the ground state of $\mathcal{H}$, we obtain the filtered state
$\ket{\Phi}$ and that one can achieve this task in a polynomial time on a
quantum computer.

######  Lemma II.1.

Let $H$ be an arbitrary, k-local many body Hamiltonian, $\ket{\Psi}$ the
initial product state and $\sum_{i=1}^{N}P_{i}$ a sum of local, commuting
projectors satisfying $P_{i}$,
$\commutator{P_{i}}{P_{j}}=0,P_{i}\ket{\Psi}=0\quad\forall i,j$. Let $E$ and
$\delta$ be the center and width of the filter $\mathcal{F}^{-1}(E,\delta)$,
respectively. Then
$\mathcal{H}=\mathcal{F}^{\dagger}\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}$
is a parent Hamiltonian whose unique ground state is the filtered state
$\ket{\mathrm{GS}}_{\mathcal{H}}=\frac{1}{\mathcal{N}}\mathcal{F}^{-1}(E,\delta)\ket{\Psi}$,
where $\mathcal{N}$ is a normalization constant

###### Proof.

The unique ground state of $\sum_{i=1}^{N}P_{i}$ is the initial state
$\ket{\Psi}$ with a ground state energy 0, by construction. Note that
$\mathcal{H}$ is a sum of positive semi-definite terms since:

$\mathcal{F}^{\dagger}P_{i}\mathcal{F}=\mathcal{F}^{\dagger}P_{i}P_{i}\mathcal{F}=r_{i}^{\dagger}r_{i}\quad\text{where}\quad
r_{i}\equiv P_{i}\mathcal{F},$ (5)

thus the ground state of the parent Hamiltonian $\mathcal{H}$ has energy
$E\geq 0$. Furthermore, note that, by construction,

$P_{i}\ket{\Psi}=P_{i}\mathcal{F}\mathcal{F}^{-1}\ket{\Psi}=\mathcal{F}^{\dagger}P_{i}\mathcal{F}\mathcal{F}^{-1}\ket{\Psi}=0.$
(6)

Hence the parent Hamiltonian $\mathcal{H}$ has ground state:

$\ket{\mathrm{GS}}_{\mathcal{H}}=\frac{1}{\mathcal{N}}\mathcal{F}^{-1}\ket{\Psi}=\ket{\Phi},$
(7)

with ground state energy 0. Therefore,

$\displaystyle 0$
$\displaystyle=\left(\sum_{i=1}^{N}P_{i}\right)\ket{\Psi}=\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}\mathcal{F}^{-1}\ket{\Psi},$

and thus,

$\mathcal{H}\mathcal{F}^{-1}(E,\delta)\ket{\Psi}=\mathcal{F}^{\dagger}\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}\mathcal{F}^{-1}\ket{\Psi}=0,$
(8)

where the normalized ground state is given by:
$\ket{\mathrm{GS}}_{\mathcal{H}}=\frac{1}{\mathcal{N}}\mathcal{F}^{-1}(E,\delta)\ket{\Psi}$,
which corresponds to the filtered state $\ket{\Phi}$. ∎

Next, we prove that the parent Hamiltonian $\mathcal{H}$ is gapped.

######  Lemma II.2.

The parent Hamiltonian $\mathcal{H}$ is gapped with a gap $\Delta\geq 1$ for a
filter satisfying $\mathcal{F}^{\dagger}\mathcal{F}\succeq 1$.

###### Proof.

We use the martingale method [24] to prove that $\mathcal{H}$ is gapped; in
particular, we show that $\mathcal{H}^{2}-\Delta\mathcal{H}\succeq 0$ for a
gap of $\Delta=1$.

$\displaystyle\mathcal{H}^{2}-\mathcal{H}=$
$\displaystyle=\mathcal{F}^{\dagger}\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}^{\dagger}\mathcal{F}\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}-\mathcal{F}^{\dagger}\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}$
$\displaystyle=\mathcal{F}^{\dagger}\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}^{\dagger}\mathcal{F}\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}-\mathcal{F}^{\dagger}\left(\sum_{i=1}^{N}P^{2}_{i}\right)\mathcal{F}$
$\displaystyle\succeq\mathcal{F}^{\dagger}\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}^{\dagger}\mathcal{F}\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}-\mathcal{F}^{\dagger}\left(\sum_{i=1}^{N}P_{i}\right)^{2}\mathcal{F}$
$\displaystyle=\mathcal{F}^{\dagger}\left(\sum_{i=1}^{N}P_{i}\right)(\mathcal{F}^{\dagger}\mathcal{F}-1)\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}$
$\displaystyle=V^{\dagger}(\mathcal{F}^{\dagger}\mathcal{F}-1)V$
$\displaystyle\succeq 0,$

since $(\mathcal{F}^{\dagger}\mathcal{F}-1)\succeq 0$, where
$V=\left(\sum_{i=1}^{N}P_{i}\right)\mathcal{F}$. ∎

In the following Lemma II.3, we combine the results to show that the algorithm
has a polynomial run time.

######  Lemma II.3.

Provided that the parent Hamiltonian $\mathcal{H}$ is k-local, we can prepare
the ground state
$\ket{\Phi}=\frac{1}{\mathcal{N}}\mathcal{F}^{-1}(E,\delta)\ket{\Psi}$, hence
perform the filtering, in time $T=\text{poly}(N,\delta^{-1})$ and consequently
with circuit depth $D=\text{poly}(N,\delta^{-1})$.

The proof is given in the Appendix A.

In Lemma II.4, we establish the relationship of the obtained energy variance
$\sigma^{2}_{\mathcal{L}}$ and the Lorentzian filter width $\delta$.

######  Lemma II.4.

Let $H$ be a local Hamiltonian on $N$ qubits, $\ket{\Psi}$ the initial product
state, and $\mathcal{F}_{\mathcal{L}}$ the Lorentzian filter with parameters
$E$, $\delta$. If the filter energy is $E=\bra{\Psi}H\ket{\Psi}$, then the
variance of the filtered state is
$\sigma^{2}_{\mathcal{L}}\approx\delta\sqrt{2\sigma^{2}_{0}/\pi}$, in the
limit where $\delta/\sqrt{\sigma^{2}_{0}}<<1$.

See Appendix C for the proof and the exact variance dependence.

The above results prove that the filtering of a product state with a
Lorentzian filter can be achieved in $\text{poly}(N,\delta^{-1})$ time.

###  II.3 Product State remarks

For a product state $\ket{\Psi}$ with regards to the energy eigenbasis of a
local Hamiltonian $H=\sum_{j}h_{j}$, the variance scales as:

$\displaystyle\sigma^{2}_{0}=\bra{\Psi}H^{2}\ket{\Psi}-\bra{\Psi}H\ket{\Psi}^{2}=\mathcal{O}(N),$
(9)

where $E_{0}=\bra{\Psi}H\ket{\Psi}$. Furthermore, $E_{0}$ and the initial
variance $\sigma^{2}_{0}$ can be easily computed classically. If the filter
energy $E$ is chosen to be the product state energy
$E_{0}=\bra{\Psi}H\ket{\Psi}$, provably successful energy filtering of the
product state $\ket{\Psi}$ can be achieved.

For any product state $\ket{\Psi}=\otimes_{i}\ket{\phi_{i}}$ we can always
create the projectors $P_{i}$ acting on a single qubit by
$P_{i}=\mathbb{I}-\ket{\phi_{i}}\bra{\phi_{i}}$. For a local $H$, product
states span an extensive energy range [25]. For a target energy within that
range, it is then possible to prepare a state with a small energy variance on
a quantum computer. Note that our runtime guarantees are provable only when we
filter around the product state energy $E_{0}$. This arises from the fact that
the Lorentzian and Gaussian functions decay at different speeds. Thus, if we
pick $E\neq E_{0}$, the final energy $\bra{\Phi}H\ket{\Phi}$ can differ from
the filter energy $E$.

##  III Results

In the previous sections, we have shown that the Lorentzian filtering can be
done in a polynomial time by adiabatic evolution since the gap of the parent
Hamiltonian $\mathcal{H}$ does not close throughout the evolution. However,
the bounds on the adiabatic runtime are often loose, and in practice, one
requires a much shorter runtime. We numerically benchmark the algorithm to
show that we already observe a good agreement with theory for moderate system
sizes $N$ and show that the algorithm requires a significantly shorter
adiabatic evolution time. For the numerical results, we use the Transverse
Field Ising (TFI) Hamiltonian $H$

$H=J\left(\sum_{i=1}^{N-1}Z_{i}Z_{i+1}+\sum_{i=1}^{N}gX_{i}+hZ_{i}\right),$
(10)

with coefficients $(J,g,h)=(1,-1.05,0.5)$, far away from integrability. The
$(X_{i},Z_{i})$ denotes the respective Pauli matrix on site $i$. We consider
two types of initial product states $\ket{\Psi}$. Firstly, the
antiferromagnetic (AFM) state $\ket{\text{AFM}}=\ket{101\dots}$. Secondly, we
look at a family of translationally invariant product states of the form
$\ket{p(\theta)}=(\cos(\theta)\ket{0}+\sin(\theta)\ket{1})^{\otimes N}$. In
principle, varying $\theta$ allows us to cover an extensive range of energies
(see Appendix D). While in the thermodynamic limit, the product states have a
Gaussian eigenstate distribution, for small systems, the distribution can
differ. We investigate the case for $\theta=\pi/6$ as the state lies closer to
the center of the spectrum, where the density of states is larger, and has an
eigenstate distribution closer to the Gaussian one. We expect this to give a
better agreement with the theory for small systems.

For a given product state $\ket{\Psi}$, we create the projectors $P_{i}$ on
each site that annihilate it. We proceed to investigate the parent
Hamiltonian:

$\mathcal{H}=(1-\frac{i}{\delta}(H-E_{F}))\left(\sum_{i=1}^{N}P_{i}\right)(1+\frac{i}{\delta}(H-E_{F})).$
(11)

In this section, we show numerical results obtained with exact diagonalization
for system sizes up to $N=18$ sites. Reaching larger system sizes with a
classical simulation proves to be a computationally prohibitive task. In
particular, since we are targeting states in the middle of the spectrum, the
entanglement entropy is expected to scale as a volume law, preventing a
systematic exploration with matrix product state methods [26], as we discuss
more in detail in Appendix E.

###  III.1 Expected decrease of the energy variance

Here, we numerically investigate the ground state of $\mathcal{H}$
corresponding to the filtered product state. In particular, we investigate how
the variance $\sigma^{2}_{\mathcal{L}}$ of the Lorentzian-filtered state
depends on the parameter $\delta$ for various system sizes $N$. In Lemma II.4,
we derive the relationship between variance and $\delta$. For low $\delta$
values, this relationship reduces to:

$\sigma^{2}_{\mathcal{L}}/\sqrt{\sigma^{2}_{0}}=\delta\sqrt{2/\pi}.$ (12)

In Fig. 2, we consider the decay of the variance for the AFM initial state,
which lies at the edge of the spectrum of the Hamiltonian $H$. Fig. 3
correspondingly shows the results for the initial state
$\ket{p(\theta=\pi/6)}$, which lies more toward the center of the spectrum. We
observe a good agreement with theory in both cases, with a better agreement
for the small system sizes in the case of $\ket{p(\theta=\pi/6)}$ initial
state.

Figure 2:  The figure shows, for various system sizes $N$, the performance of
the filter applied on the AFM product state at the mean energy which, in the
thermodynamic limit, corresponds to energy density $E_{0}/JN=1$. The black
line shows the expected variance decay (Eq. 12). Figure 3:  The figure shows,
for various system sizes $N$, the performance of the filter applied on the
$\ket{p(\theta=\pi/6)}$ product state at the mean energy which, in the
thermodynamic limit, corresponds to energy density $E_{0}/JN=-0.409$. The
black line shows the expected variance decay (Eq. 12).

###  III.2 Adiabatic Evolution

To better understand the actual adiabatic runtime $T$ required, we numerically
investigate the performance of the adiabatic evolution in practice. On a
quantum device, one could prepare the filtered state by time evolving the
product state with $\mathcal{H}(\delta)$ while smoothly increasing
$\delta^{-1}$ from 0 to the desired value. In particular, for this study, we
choose the adiabatic scheduling
$\delta^{-1}(s)=\sin(\pi/2\sin(s\pi/2)^{2})^{2}\delta^{-1}_{\max}$ which
ensures a slower change of the parameter at the beginning and end of the
evolution. This scheduling of the adiabatic evolution is essential for an
optimal runtime [27].

To investigate the accuracy of the adiabatic evolution for various system
sizes, we study the fidelity of the adiabatic state $\mathcal{F}$ with respect
to the exact filtered state and monitor the ground state energy of the parent
Hamiltonian $\mathcal{H}$ since, for perfectly adiabatic evolution, it should
remain zero throughout. Note that the parent Hamiltonian $\mathcal{H}$ (Eq.
11) has a norm that increases with $\delta^{-1}$. To keep it normalized
throughout adiabatic evolution, we rescale it to
$\tilde{\mathcal{H}}(\delta)=\mathcal{H}(\delta)/(1+\delta^{-2})$. Note that
the rescaling affects the gap, which we take into account when establishing
the runtime. We apply the adiabatic evolution in the following way:

$\ket{\Phi}_{\mathrm{adi}}=\prod_{l=1}^{T/\tau}\exp(-i\tau\tilde{\mathcal{H}}\\{\delta(l\frac{\tau}{T})\\})\ket{\Psi},$
(13)

where $\tau$ is the discrete adiabatic time step, and $T$ is the total
adiabatic evolution time. To benchmark the adiabatic evolution, we fix the
desired filter width to be $\delta=0.1$ and perform the evolution for several
system sizes $N$ and runtimes $T$. In Fig. 4 and Fig. 5, we show the
dependence of the fidelity $\mathcal{F}$ and the parent Hamiltonian
$\mathcal{H}$ energy with respect to the adiabatic evolution time $T$. In both
cases, the parent Hamiltonian $\mathcal{H}$ energy appears independent of the
system size, while the fidelity shows a favorable behavior towards larger $N$.
These results provide a more favorable scaling for the adiabatic runtime $T$
compared to the adiabatic theorem, which suggests that $T=\mathcal{O}(N^{3})$.
The results suggest that the adiabatic evolution runtime could be taken
independently of the system size to prepare the state with a given fidelity
$\mathcal{F}$. However, in Appendix B, we show that the circuit depth required
to implement this evolution via the first-order Trotterization scales as
$\mathcal{O}(N^{2})$ since $\norm{\mathcal{H}}=\mathcal{O}(N^{3})$.

Figure 4:  The figure shows results for adiabatic evolution of the $\ket{AFM}$
initial product state for final filter width $\delta=0.1$ and several system
sizes $N$. We use $\tau=0.1$. The upper plot shows one minus the fidelity
between the evolved state and the exact filtered one as a function of the
number of timesteps $T/\tau$. The lower plot shows the parent Hamiltonian
$\mathcal{H}$ energy at the end of the adiabatic evolution. Figure 5:  The
figure shows results for adiabatic evolution of $\ket{p(\theta=\pi/6)}$
initial product state for final filter width $\delta=0.1$ and various system
sizes $N$. We use $\tau=0.1$. The upper plot shows one minus the fidelity
between the evolved state and the exact filtered one as a function of the
number of timesteps $T/\tau$. The lower plot shows the parent Hamiltonian
$\mathcal{H}$ energy at the end of the adiabatic evolution.

##  IV Discussion

In this section, we review the results from Section III and discuss the
behavior and drawbacks of the Lorentzian filtering for finite system sizes.

Firstly, Fig. 2 and Fig. 3 show that, even for small system sizes $N$, the
variance of the filtered state follows the decreasing behavior expected in the
thermodynamic limit (Eq. 12). In the numerics, we observe that the smaller
systems start to deviate from this behavior first. The first reason for this
behavior is that the eigenstate distribution of the product state is not
Gaussian for small systems. The second reason is the discreteness of the
spectrum. In Eq. (3), we establish that the suppression due to Lorentzian
filtering is given by
$\frac{\absolutevalue{c_{n}}^{2}}{1+\delta^{-2}(e_{n}-E)^{2}}$. Suppose that
the closest eigenstate is $\eta=\min_{n}{\absolutevalue{e_{n}-E}}$ away from
the center of the filter. It is clear that further lowering $\delta$ leads to
no further filtering when $\delta^{-1}\eta\gtrsim 1$. However, for larger
systems, the discreteness of the spectrum should not pose any problems. Note
that for a Hamiltonian $H$ on $N$ sites, the energy extent is $O(N)$, while
there are $2^{N}$ eigenstates. This means that the density of states, along
with the number of states supported by the product state, increases
exponentially with $N$, and thus $\eta$ becomes exponentially small in $N$.
The exponential density of states allows for successful filtering to be
performed up to exponentially small $\delta$ values.

Secondly, in Fig. 4 and Fig. 5, we observe that the adiabatic runtime required
to reach a certain precision is essentially independent of the system size
$N$. Even though the fidelity is only accessible in exact calculations,
measuring the energy of the parent Hamiltonian $\mathcal{H}$ at the end of the
evolution, as seen in the figures, provides a reliable indication that the
adiabatic evolution has indeed prepared the required state. The numerics
indicate that the runtime of the algorithm is much faster than expected, and
one can prepare a state of given $\delta$ with a fixed number of Trotter steps
that are independent of $N$.

Thirdly, perhaps the biggest drawback of the proposed algorithm is the fact
that it requires evolving the system under a geometrically non-local
Hamiltonian. Whereas this would, in principle, be possible on some platforms,
like trapped ions [28], on other quantum computer implementations with only
local gates available, it would require $\mathcal{O}(N)$ additional swap
operations, which will increase the cost of the algorithm and, potentially,
render it unsuitable for NISQ devices. This is, however, not surprising when
considering that the states we are trying to filter are excited eigenstates of
the Hamiltonian, which usually exhibit an entanglement volume law [29, 30,
31], and thus cannot be encoded, in general, in the ground state of a
geometrically local Hamiltonian (which would only accommodate area law
entanglement).

##  V Conclusion

We have developed a novel algorithm for preparing states with an arbitrarily
small energy variance at a target energy on a quantum computer. The algorithm
effectively prepares a state that would result from applying a Lorentzian
filter of width $\delta$ to an initial product state. The filtered state is,
in fact, adiabatically prepared as the ground state of a parent Hamiltonian.
Furthermore, we prove that the algorithm is efficient since the parent
Hamiltonian remains gapped with a gap independent of system size; thus, it can
be efficiently prepared with adiabatic evolution. Indeed, the running time of
the algorithm is polynomial both in the system size and the inverse width.

We show that when preparing the finite energy state, its variance decreases
with the parameter $\delta$ that defines the Lorentzian filter, and already
for moderate system sizes, we observe good agreement with the asymptotic
predictions for large sizes. While according to the theoretical bounds, the
adiabatic runtime scales as $O(N^{3}\delta^{-4})$, our numerics suggest that
in practice, the required time is much more favorable due to the looseness of
the theoretical bound from the adiabatic theorem. In practice, we estimate
that the adiabatic runtime scales as $O(\delta^{-4})$, thus allowing us to
perform adiabatic evolution and prepare the finite energy state with circuit
depth $O(N^{2}\delta^{-4})$ (see Appendix B).

Our approach provides a new way of probing finite energy physics on quantum
devices by directly giving access to small energy variance states. Having
access to the state itself provides novel ways to probe finite energy regimes
of isolated quantum systems and allows this algorithm to serve as a subroutine
in more complicated analysis on quantum devices. Future work should focus on
developing new algorithms that take advantage of the access to filtered
product states.

###### Acknowledgements.

We thank Georgios Styliaris for helpful discussions. We acknowledge the
support from the German Federal Ministry of Education and Research (BMBF)
through FermiQP (Grant No. 13N15890) and EQUAHUMO (Grant No. 13N16066) within
the funding program quantum technologies—from basic research to market. This
research is part of the Munich Quantum Valley (MQV), which is supported by the
Bavarian state government with funds from the Hightech Agenda Bayern Plus.
This work was partially supported by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) under Germany’s Excellence Strategy – EXC-2111 –
390814868; and by the EU-QUANTERA project TNiSQ (BA 6059/1-1).

## References

  * Deutsch [1985] D. Deutsch, Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400, 97 (1985).
  * Lloyd [1996] S. Lloyd, Science 273, 1073 (1996).
  * Cirac and Zoller [2004] J. I. Cirac and P. Zoller, Physics Today 57, 38 (2004).
  * Georgescu  _et al._ [2014] I. M. Georgescu, S. Ashhab, and F. Nori, Rev. Mod. Phys. 86, 153 (2014).
  * Kempe  _et al._ [2006] J. Kempe, A. Kitaev, and O. Regev, SIAM Journal on Computing 35, 1070 (2006).
  * Cubitt and Montanaro [2016] T. Cubitt and A. Montanaro, SIAM Journal on Computing 45, 268 (2016).
  * Farhi  _et al._ [2000] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser,  (2000), arXiv:0001106 [quant-ph] .
  * Johri  _et al._ [2017] S. Johri, D. S. Steiger, and M. Troyer, Physical Review B 96, 195136 (2017).
  * Wang  _et al._ [2023] Y. Wang, B. Zhao, and X. Wang, Physical Review Applied 19, 044041 (2023).
  * Deutsch [2018] J. M. Deutsch, Reports on Progress in Physics 81, 082001 (2018).
  * Sokolov  _et al._ [2021] I. O. Sokolov, P. K. Barkoutsos, L. Moeller, P. Suchsland, G. Mazzola, and I. Tavernelli, Phys. Rev. Res. 3, 013125 (2021).
  * Yu  _et al._ [2017] X. Yu, D. Pekker, and B. K. Clark, Phys. Rev. Lett. 118, 017201 (2017).
  * Bañuls  _et al._ [2020] M. C. Bañuls, D. A. Huse, and J. I. Cirac, Phys. Rev. B 101, 144305 (2020).
  * Yang  _et al._ [2022] Y. Yang, J. I. Cirac, and M. C. Bañuls, Phys. Rev. B 106, 024307 (2022).
  * Kitaev [1997] A. Y. Kitaev, Russian Mathematical Surveys 52, 1191 (1997).
  * Abrams and Lloyd [1999] D. S. Abrams and S. Lloyd, Phys. Rev. Lett. 83, 5162 (1999).
  * O’Brien  _et al._ [2019] T. E. O’Brien, B. Tarasinski, and B. M. Terhal, New Journal of Physics 21, 023022 (2019).
  * Cruz  _et al._ [2020] P. M. Q. Cruz, G. Catarina, R. Gautier, and J. Ferná ndez-Rossier, Quantum Science and Technology 5, 044005 (2020).
  * Jensen  _et al._ [2020] P. W. K. Jensen, L. B. Kristensen, J. S. Kottmann, and A. Aspuru-Guzik, Quantum Science and Technology 6, 015004 (2020).
  * Seki and Yunoki [2022] K. Seki and S. Yunoki, Phys. Rev. B 106, 155111 (2022).
  * Ding and Lin [2023] Z. Ding and L. Lin, PRX Quantum 4, 020331 (2023).
  * Lu  _et al._ [2021] S. Lu, M. C. Bañuls, and J. I. Cirac, PRX Quantum 2, 020321 (2021).
  * Ge  _et al._ [2016] Y. Ge, A. Molnár, and J. I. Cirac, Phys. Rev. Lett. 116, 080503 (2016).
  * Koma and Nachtergaele [1995] T. Koma and B. Nachtergaele, “The spectral gap of the ferromagnetic xxz chain,” (1995), arXiv:cond-mat/9512120 [cond-mat] .
  * Lieb [1973] E. H. Lieb, Communications in Mathematical Physics 31, 327 (1973).
  * Schollwöck [2011] U. Schollwöck, Annals of Physics 326, 96–192 (2011).
  * Reichardt [2004] B. W. Reichardt, in  _Proceedings of the thirty-sixth annual ACM symposium on Theory of computing_ (2004) pp. 502–510.
  * Grzesiak  _et al._ [2020] N. Grzesiak, R. Blümel, K. Wright, K. M. Beck, N. C. Pisenti, M. Li, V. Chaplin, J. M. Amini, S. Debnath, J.-S. Chen, and Y. Nam, Nature Communications 11 (2020), 10.1038/s41467-020-16790-9.
  * Bianchi  _et al._ [2022] E. Bianchi, L. Hackl, M. Kieburg, M. Rigol, and L. Vidmar, PRX Quantum 3, 030201 (2022).
  * Huang [2021] Y. Huang, Nuclear Physics B 966, 115373 (2021).
  * Anshu  _et al._ [2022] A. Anshu, A. W. Harrow, and M. Soleimanifar, Nature Physics 18, 1362–1366 (2022).
  * Kato [1950] T. Kato, Journal of the Physical Society of Japan 5, 435 (1950).
  * Amin [2009] M. H. S. Amin, Physical Review Letters 102 (2009), 10.1103/physrevlett.102.220401.
  * Low and Chuang [2017] G. H. Low and I. L. Chuang, Physical Review Letters 118, 010501 (2017), 1606.02685 .
  * Low and Chuang [2019] G. H. Low and I. L. Chuang, Quantum 3, 163 (2019).
  * Childs  _et al._ [2021] A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, Physical Review X 11 (2021), 10.1103/PhysRevX.11.011020.
  * Hartmann  _et al._ [2005] M. Hartmann, G. Mahler, and O. Hess, Journal of Statistical Physics 119, 1139 (2005), arXiv:cond-mat/0406100 [cond-mat.stat-mech] .
  * Keating  _et al._ [2015] J. P. Keating, N. Linden, and H. J. Wells, Communications in Mathematical Physics 338, 81 (2015), arXiv:1403.1121 [math-ph] .

##  Appendix A Adiabatic runtime

In this appendix we discuss the adiabatic runtime and prove Lemma II.3.

###### Proof.

The adiabatic theorem states that if the adiabatic evolution is slow enough
and the state is gapped then the system will remain in the instantaneous
ground state of the Hamiltonian $H(s)$. The result from [32, 27, 33] states
that the required runtime for the adiabatic evolution is:

$T\geq\max_{s}(\norm{\dot{H}(s)}/\Delta(s)^{2}),$ (14)

where we smoothly vary the parameter $s$ from $0$ to $1$. To keep the norm of
the parent Hamiltonian independent of $\delta^{-1}$ throughout the adiabatic
evolution, we rescale it as follows:

$\displaystyle\tilde{\mathcal{H}}(s)$
$\displaystyle=\frac{1}{1+s^{2}\delta^{-2}}V\left(\sum_{i=1}^{N}P_{i}\right)V^{{\dagger}},\quad\text{where}$
$\displaystyle V$ $\displaystyle=\left(1+is\delta^{-1}(H-E)\right).$

When rescaled in this way from Lemma II.2 one can clearly see that the gap
$\Delta(s)\geq\frac{1}{1+s^{2}\delta^{-2}}$. Furthermore, by differentiating
$\tilde{\mathcal{H}}(s)$ with respect to $s$ we obtain that:

$\displaystyle\dot{\tilde{\mathcal{H}}}(s)$
$\displaystyle=\frac{-2s\delta^{-2}}{(1+s^{2}\delta^{-2})^{2}}V\left(\sum_{i=1}^{N}P_{i}\right)V^{{\dagger}}$
$\displaystyle+\frac{1}{1+s^{2}\delta^{-2}}(\dot{V}\left(\sum_{i=1}^{N}P_{i}\right)V^{\dagger}+V\left(\sum_{i=1}^{N}P_{i}\right)\dot{V}^{{\dagger}})$
$\displaystyle=\frac{1}{1+s^{2}\delta^{-2}}(-2s\delta^{-2}\mathcal{H}(s)$
$\displaystyle+\delta^{-1}(i(H-E)\left(\sum_{i=1}^{N}P_{i}\right)V^{\dagger}+h.c.)$
$\displaystyle=O(N^{3}),$

since $\norm{V}=\mathcal{O}(\delta^{-1}N)$ and $\norm{H}=\mathcal{O}(N)$
Combining the previous bound for $\norm{\dot{\tilde{\mathcal{H}}}(s)}$ and the
scaling of the gap $\Delta(s)$ we arrive at the adiabatic runtime:

$\displaystyle T$
$\displaystyle\geq\max_{s}(\norm{\dot{\tilde{\mathcal{H}}}(s)}/\Delta(s)^{2})$
$\displaystyle=O(N^{3}\delta^{-4}),$

which gives the $T=\text{poly}(N,\delta)$ adiabatic runtime.

Secondly, we use the fact that the time evolution on quantum computers can be
performed efficiently for a local Hamiltonian
$H=\sum_{\gamma=1}^{M}h_{\gamma}$ using any of the algorithms [34, 35, 36].
Thus, the evolution can be simulated with a $\text{poly}(N,\delta)$-depth
quantum circuit. In Appendix B, we explicitly show the depth required to
implement the first-order Trotter evolution. ∎

##  Appendix B Trotter Circuit depth for the adiabatic evolution

This appendix shows that the first-order Trotterized time evolution of
$\mathcal{H}$ can be implemented with depth $D=O(TN^{2})$.

######  Lemma B.1.

Suppose $\\{P_{i}\\}$ are a set of one-site projectors, and
$H=\sum_{\gamma}^{M}h_{\gamma}$ is a local Hamiltonian such the range of
interactions $\absolutevalue{\text{sup }{h_{\gamma}}}\leq w$ and that for any
site $i$ there are at most $v$ terms $h_{\gamma}$ acting on it. Then the
first-order Trotterized evolution of the parent Hamiltonian
$\mathcal{H}=(1-i\delta^{-1}(H-E_{0}))\left(\sum_{i=1}^{N}P_{i}\right)(1+i\delta^{-1}(H-E_{0}))$
for time $T$ with timestep $\tau$ can be implemented with circuit depth
$D=\mathcal{O}(TN^{2})$

###### Proof.

Let’s consider the circuit depth required to implement a single Trotter step
of the parent Hamiltonian $\mathcal{H}$ for a small $\tau$. The parent
Hamiltonian $\mathcal{H}$ can be split into parts:

$\displaystyle\mathcal{H}$ $\displaystyle=\left(\sum_{i=1}^{N}P_{i}\right)$
$\displaystyle-\frac{i}{\delta}\commutator{H}{\left(\sum_{i=1}^{N}P_{i}\right)}$
$\displaystyle+\frac{1}{\delta^{2}}(H-E_{F})\left(\sum_{i=1}^{N}P_{i}\right)(H-E_{F}).$

It’s clear that the terms in $\left(\sum_{i=1}^{N}P_{i}\right)$ are 1-local;
thus, their evolution can be implemented with a $D=O(1)$ circuit. Similarly,
for the second set of terms
$\commutator{H}{\left(\sum_{i=1}^{N}P_{i}\right)}$, it’s clear to see that it
is a sum of $\mathcal{O}(N)$ geometrically local terms of weight at most $w$;
thus can be implemented with a circuit of depth $O(1)$. The most complicated
terms arise from the third set of terms
$(H-E_{F})\left(\sum_{i=1}^{N}P_{i}\right)(H-E_{F})$. First, note that we can
implement any evolution of type $\exp(-i\tau h_{i}P_{j}h_{k})$ with a constant
circuit depth, assuming that the qubits have all-to-all connectivity. Suppose
we pick any three sites $i,j,k$. Then, the support of all the terms acting on
all 3 of these vertices can be described by:

$\displaystyle S_{ijk}$ $\displaystyle=\\{i-(w-1)\dots i+(w-1)$
$\displaystyle\cup j-(w-1)\dots j+(w-1)$ $\displaystyle\cup k-(w-1)\dots
k+(w-1)\\},$

and $\absolutevalue{S_{ijk}}\leq 3(2w-1)$. Since for any vertex $i$, there are
at most $v$ terms in $H$ and one term in $\left(\sum_{i=1}^{N}P_{i}\right)$
acting on it, the number of terms acting on all 3 of these vertices is at most
$(v+1)^{3}$, and they all have support within $S_{ijk}$, allowing them to be
implemented with circuit depth independent of $N$. There are $N^{3}$
combinations of vertices $i,j,k$, but each of these terms only have support on
sites within $S_{ijk}$; thus, we can implement the evolution of $N/(3(2w-1))$
combinations in parallel, leading to the necessary circuit depth being
$O(N^{2})$. Thus, the entire evolution of the parent Hamiltonian $\mathcal{H}$
can be implemented with circuit depth $D=O(T/\tau N^{2})=O(TN^{2})$, which
concludes the proof. ∎

##  Appendix C Theoretical Variance decay

In this appendix, we prove Lemma II.4.

###### Proof.

We investigate the theoretical variance decay provided by filtering the
product state $\ket{\Psi}$ by a Lorentzian filter
$\mathcal{L}(E_{F},\delta)\propto\frac{1}{(e-E_{F})^{2}+\delta^{2}}$, where
$e$ is the energy of eigenstate $\ket{e}$. For a local Hamiltonian $H$, at
large $N$ the local density of states (or energy distribution) of the product
state $g(E)$ can be approximated by a Gaussian [37, 38]
$\mathcal{G}(E_{0},\sigma^{2}_{0})$ centered at $E_{0}=\bra{\Psi}H\ket{\Psi}$
and with variance
$\sigma^{2}_{0}=\bra{\Psi}H^{2}\ket{\Psi}-\bra{\Psi}H\ket{\Psi}^{2}$. This
allows us to estimate the variance upon the application of the filter
$\mathcal{L}(E_{F},\delta)$ as follows:

$\displaystyle\sigma^{2}_{\mathcal{L}}$
$\displaystyle=\frac{\int_{-\infty}^{\infty}e^{2}\mathcal{G}(E_{0},\sigma^{2}_{0})\mathcal{L}(E_{F},\delta)de}{\int_{-\infty}^{\infty}\mathcal{G}(E_{0},\sigma^{2}_{0}))\mathcal{L}(E_{F},\delta)de}$
$\displaystyle-\left(\frac{\int_{-\infty}^{\infty}e\mathcal{G}(E_{0},\sigma^{2}_{0})\mathcal{L}(E_{F},\delta)de}{\int_{-\infty}^{\infty}\mathcal{G}(E_{0},\sigma^{2}_{0}))\mathcal{L}(E_{F},\delta)de}\right)^{2}$
$\displaystyle=\frac{\mathcal{I}_{2}}{\mathcal{I}_{0}}-\left(\frac{\mathcal{I}_{1}}{\mathcal{I}_{0}}\right)^{2}.$

We investigate the filtered energy variance when the Lorentzian filter is
applied at the center of the product state energy, thus $E_{F}=E_{0}$. In this
case, the above integrals can be evaluated to yield:

$\displaystyle\mathcal{I}_{0}$
$\displaystyle=\int_{-\infty}^{\infty}\frac{\exp(-(e-E_{0})^{2}/2\sigma^{2}_{0})}{(e-E_{0})^{2}+\delta^{2}}de$
$\displaystyle=\int_{-\infty}^{\infty}\frac{\exp(-e^{\prime
2}/2\sigma^{2}_{0})}{e^{\prime 2}+\delta^{2}}de^{\prime}$
$\displaystyle=\frac{\pi}{\delta}\exp(\frac{\delta^{2}}{2\sigma^{2}_{0}})\left[1-\erf\left(\delta/\sqrt{2\sigma^{2}_{0}}\right)\right],$
$\displaystyle\mathcal{I}_{1}$
$\displaystyle=\int_{-\infty}^{\infty}\frac{\exp(-(e-E_{0})^{2}/2\sigma^{2}_{0})}{(e-E_{0})^{2}+\delta^{2}}ede$
$\displaystyle=\int_{-\infty}^{\infty}\frac{\exp(-e^{\prime
2}/2\sigma^{2}_{0})}{e^{\prime 2}+\delta^{2}}(e^{\prime}+E_{0})de^{\prime}$
$\displaystyle=0+\int_{-\infty}^{\infty}\frac{\exp(-e^{\prime
2}/2\sigma^{2}_{0})}{e^{\prime 2}+\delta^{2}}E_{0}de^{\prime}$
$\displaystyle=\mathcal{I}_{0}E_{0},$ $\displaystyle\mathcal{I}_{2}$
$\displaystyle=\int_{-\infty}^{\infty}\frac{\exp(-(e-E_{0})^{2}/2\sigma^{2}_{0})}{(e-E_{0})^{2}+\delta^{2}}e^{2}de$
$\displaystyle=\int_{-\infty}^{\infty}\frac{\exp(-e^{\prime
2}/2\sigma^{2}_{0})}{e^{\prime
2}+\delta^{2}}(e^{\prime}+E_{0})^{2}de^{\prime}$
$\displaystyle=\int_{-\infty}^{\infty}\frac{\exp(-e^{\prime
2}/2\sigma^{2}_{0})}{e^{\prime 2}+\delta^{2}}e^{\prime
2}de^{\prime}+E^{2}_{0}$
$\displaystyle=-\pi\delta\exp(\frac{\delta^{2}}{2\sigma^{2}_{0}})\left(1-\erf(\delta/\sqrt{2\sigma^{2}_{0}})\right)$
$\displaystyle+\sqrt{2\pi\sigma^{2}_{0}}+E^{2}_{0}$
$\displaystyle=-\delta^{2}\mathcal{I}_{0}+\sqrt{2\pi\sigma^{2}_{0}}+E^{2}_{0}.$

Combining the above results in the following filtered variance:

$\displaystyle\sigma^{2}_{\mathcal{L}}$
$\displaystyle=-\delta^{2}+\frac{\delta\exp(-\frac{\delta^{2}}{2\sigma^{2}_{0}})\sqrt{2\sigma^{2}_{0}/\pi}}{\left(1-\erf(\delta/\sqrt{2\sigma^{2}_{0}})\right)}.$
(15)

Note that in the limit where:

$\lim_{\delta\to\infty}{\sigma^{2}_{\mathcal{L}}}=\sigma^{2}_{0}.$

However, we are interested in the limit for small $\delta$ values
$(\delta/\sqrt{2\sigma^{2}_{0}}<<1)$ for which we get the asymptotic behavior:

$\displaystyle\sigma^{2}_{\mathcal{L}}$
$\displaystyle\approx\delta\sqrt{2\sigma^{2}_{0}/\pi}=\mathcal{O}(\delta\sqrt{N}).$
(16)

This establishes the bound for the theoretical decay of the variance in the
thermodynamic limit. ∎

##  Appendix D Translationaly invariant product states

A family of states we consider in our investigation is translationally
invariant product states, defined by:

$\ket{p(\theta)}=(\cos(\theta)\ket{0}+\sin(\theta)\ket{1})^{\otimes N}.$ (17)

For the TFI Ising model Eq. 10, such product state parametrization covers a
range of energies, allowing us to investigate the performance of the filter
across the whole spectrum. In the thermodynamic limit, the energy of
$\ket{p(\theta)}$ is $E/JN=\cos^{2}(2\theta)+h\cos(2\theta)+g\sin(2\theta)$.
The dependence on the angle $\theta$ is depicted in Fig. 6.

Figure 6: $E/JN$ dependence on the parameter $\theta$. We have marked the
$\theta=\pi/6$ value used in the work. The AFM state has $E/JN=-1$ in the
thermodynamic limit.

##  Appendix E MPS investigation

We have limited the numerics in Section III to only exact calculations for
small systems. One could expect that matrix product state (MPS) methods [26]
would allow us to reach larger system sizes. However, this proves to be a very
challenging task. In this appendix, we provide details about the drawbacks of
such MPS calculations for this particular model and illustrate why it is hard
to go beyond the system sizes accessible with the exact methods.

Firstly, we investigate the ground state of $\mathcal{H}$ using DMRG. In Fig.
7, we show that we approach the ground state slowly in the number of sweeps.
As shown in the figure, which illustrates the ground state search
corresponding already for a small system size $N=16$ (which can be solved with
exact diagonalization), even after 1000 sweeps, the error in the energy is
considerably large (note that the exact value is zero).

Secondly, we look at the entanglement entropy of the filtered states and how
it depends on the system size $N$ and $\delta^{-1}$ to understand the
fundamental limitations in their approximability as MPS. Fig. 8 shows the
dependence of the entropy of half chain with $\delta^{-1}$ for various system
sizes, obtained from our exact calculations. The results indicate a tendency
to a linear increase with $N$ for sufficiently small $\delta$, consistent with
a volume law. We thus conclude that the MPS techniques will not be able to
efficiently capture the ground state, respectively, the adiabatic evolution of
the parent Hamiltonian $\mathcal{H}$. This behavior is expected since we are
trying to approximate an energy eigenstate at the center of the spectrum,
which follows the volume law of entanglement. The inability to express these
states as MPS further solidifies the need for a quantum algorithm that is
capable of preparing such states and investigating their properties.

Figure 7: The figure shows the decay of the parent Hamiltonian $\mathcal{H}$
energy with the number of DMRG sweeps. The convergence to the true value of
$\expectationvalue{\mathcal{H}}=0$ happens slowly. Figure 8: The figure shows
the dependence of the bipartite entanglement entropy with $\delta^{-1}$ and
for various system sizes $N$. We observe that for a given $\delta^{-1}$, the
entanglement grows linearly with $N$.


# ISNet: Integrate Image-Level and Semantic-Level Context
for Semantic Segmentation

Zhenchao Jin, Bin Liu, Qi Chu, Nenghai Yu
CAS Key Laboratory of Electromagnetic Space Information,
University of Science and Technology of China
<EMAIL_ADDRESS>flowice@, qchu<EMAIL_ADDRESS>Corresponding author.

###### Abstract

Co-occurrent visual pattern makes aggregating contextual information a common
paradigm to enhance the pixel representation for semantic image segmentation.
The existing approaches focus on modeling the context from the perspective of
the whole image, i.e., aggregating the image-level contextual information.
Despite impressive, these methods weaken the significance of the pixel
representations of the same category, i.e., the semantic-level contextual
information. To address this, this paper proposes to augment the pixel
representations by aggregating the image-level and semantic-level contextual
information, respectively. First, an image-level context module is designed to
capture the contextual information for each pixel in the whole image. Second,
we aggregate the representations of the same category for each pixel where the
category regions are learned under the supervision of the ground-truth
segmentation. Third, we compute the similarities between each pixel
representation and the image-level contextual information, the semantic-level
contextual information, respectively. At last, a pixel representation is
augmented by weighted aggregating both the image-level contextual information
and the semantic-level contextual information with the similarities as the
weights. Integrating the image-level and semantic-level context allows this
paper to report state-of-the-art accuracy on four benchmarks, i.e., ADE20K,
LIP, COCOStuff and Cityscapes 111Our code will be available at
https://github.com/SegmentationBLWX
/sssegmentation..

##  1 Introduction

Semantic image segmentation, which assigns per-pixel predictions of object
categories for the given image, is a fundamental problem in computer vision.
This task is exceptionally significant to tons of real-world applications,
_e.g._ , automatic driving and robot sensing. Recent developments of deep
neural networks [24, 16] encourage the emergence of a series of works [4, 5,
35, 7, 22, 30], where FCN is the cornerstone of these works. Its encoder-
decoder structure, which reduces the spatial dimension to extract features and
then leverages upsampling to recover spatial extent, shows numerous
improvements in semantic segmentation. Based on this, recent researches mainly
focus on two issues to further boost the segmentation performance. One is how
to improve the encoder structure so that the models can extract more robust
representation for each pixel [29, 25, 34]. The other is how to model the
context so that the network can enhance the representation capability of each
pixel by encoding the contextual information into the original feature
representations [11, 35, 4, 30, 14, 17], which is also the interest of this
paper.

Figure 1:  Main idea of integrating image-level and semantic-level context.
The blue region on the upper branch denotes for semantic-level context and the
purple area on the lower branch stands for image-level context.

Co-occurrent visual pattern inspires the emergence of a series of works about
modeling context. These approaches can be roughly divided into two types,
_i.e._ , multi-scale context modeling and relational context modeling. For
multi-scale context modeling, Deeplab [4] introduces the atrous spatial
pyramid pooling (ASPP) so that it can leverage various dilation convolutions
to capture the multi-scale contextual information. PSPNet [35] proposes to
utilize pyramid spatial pooling to aggregate the multi-scale contextual
information. For relational context modeling, Wang _et al._ [26] first revisit
the traditional local means [1], and then design a non-local block to weighted
aggregate the contextual information in the whole image. Zhu _et al._ propose
an asymmetric pyramid non-local block to decrease the compution and GPU memory
consumption of the standard non-local module. Apart from this, ACFNet [32] and
OCRNet [30] first group the pixels into a set of regions, and then augment the
pixel representations by weighted aggregating the region representations where
the weights are determined by the relations between the pixels and regions.
Though impressive, these solutions only focus on aggregating the contextual
information from the perspective of the whole image (_i.e._ , image-level
contextual information), while discard the significance of the pixel
representations of the same category. Accordingly, they all suffer from the
same issue that the contextual information of each pixel is unevenly captured
from the category region the pixel belongs to and the regions of other
categories. For instance, the pixels in the boundaries or the regions of
objects of small scales tend to capture much more contextual information from
the regions of other objects. Since the label of a pixel is the category of
the object that the pixel belongs to, too much contextual information from
other objects may cause the network to mislabel these pixels as other
categories.

To alleviate the problem above, this paper proposes to augment the pixel
representations by aggregating the image-level and semantic-level contextual
information, respectively. As illustrated in Figure 1, the image-level context
stands for all the pixels in the input image and the semantic-level context
denotes for the pixels in the same category region. Based on this definition,
an image-level context module (ILCM) is first designed to capture the
contextual information from the whole image and thereby, we can obtain the
image-level contextual information. Then, a novel semantic-level context
module (SLCM) is proposed to aggregate representations of the same category
for each pixel (_i.e._ , the semantic-level contextual information), where the
category regions are learned under the supervision of the ground-truth
segmentation. Next, the similarities between the pixel representation and the
image-level contextual information, the semantic-level contextual information
are calculated. At last, the pixel representations are augmented by weighted
aggregating the image-level contextual information and the semantic-level
contextual information, where the weights are determined by the calculated
similarities. On the whole, our major contributions are summarized as follows:

  * •

To the best of our knowledge, this paper first explores improving the pixel
representations by aggregating the image-level contextual information and
semantic-level contextual information, respectively.

  * •

This paper designs a simple yet effective image-level context module (ILCM)
and a novel semantic-level context module (SLCM) to capture the contextual
information from the perspective of the whole image and the category region,
respectively. Experimental results demonstrate the effectiveness of our
method.

  * •

A general architecture framework named ISNet is proposed in this paper, which
reveals how to leverage ILCM and SLCM to consistently boost the performance of
semantic image segmentation. The proposed framework allows this paper to
achieve state-of-the-art accuracy on four segmentation benchmarks, _i.e._ ,
ADE20K, LIP, COCOStuff and Cityscapes.

##  2 Related Work

Semantic Segmentation. To generate pixel-wise semantic predictions for a given
image, image classification networks [4, 24] are extended to yield semantic
segmentation masks. FCN [22] is the first work to apply fully convolution on
the whole image to produce labels of every pixel and many researchers have
made efforts based on FCN in the past few years. Specifically, these studies
can be roughly divided into two groups. One is to design a novel backbone
network [25, 29] to extract more robust feature representation for each pixel.
Considering high-resolution representations are essential for position-
sensitive vision problems, Wang _et al._ [25] propose a backbone network named
HRNet to maintain high-resolution representations through the whole process.
ResNeSt [34] presents a modularized architecture to capture cross-feature
interactions and learn diverse representations by utilizing the channel-wise
attention on different network branches. The other is to introduce richer
contextual information for each pixel [14, 23, 35, 4, 3, 11]. For instance,
adopting different sizes of convolutional/pooling kernels or dilation rates to
gather multi-scale visual cues [35, 4, 27], employing neural attention [6] to
directly exchange the contextual information between paired pixels [17, 3, 11,
28, 31] and building the image pyramids or feature pyramids [18, 21]. This
paper focuses on the latter one, _i.e._ , aggregating more meaningful
contextual information to augment the pixel representations.

Figure 2:  The overview of the proposed framework (ISNet). First, the
semantic-level context module (SLCM) and image-level context module (ILCM) are
utilized to extract the semantic-level contextual information
$\mathcal{R}_{sl}$ and the image-level contextual information
$\mathcal{R}_{il}$, respectively. Then, we calculate the similarities between
pixel representations $\mathcal{R}$ and $\mathcal{R}_{sl}$,
$\mathcal{R}_{il}$. At last, both contextual information are adopted to
augment the pixel representations according to the calculated similarities.

Context Aggregation. While FCN captures information from bottom-up, contextual
information with wide field-of-view is also critical for pixel labeling task
and is exploited by numerous studies. Deeplab [4, 5, 7] proposes atrous
convolution kernels to force the network to perceive larger area and obtain
the higher resolution output. Based on Deeplab, DenseASPP [27] densifies the
dilated rates to make the network conver larger scale ranges. PSPNet [35]
adopts spatial pooling to gain the feature maps of different receptive field
sizes so that the combined feature maps could aggregate multi-scale object
clues. DANet [11] and OCNet [31] first calculate the similarities between the
pixels as the weights, and then improve the pixel representations by weighted
aggregation of all the pixels in the input image. Apart from this, some works
[30, 32, 20] first group the pixels into a set of regions, and then the pixel
representations are augmented by weighted aggregating the region
representations where the weights are determined by their context relations.
Although our semantic-level context module sees similar to these methods, the
key difference is that we augment a pixel representation only by adopting the
region representation with the same category as the pixel representation
rather than all region representations.

##  3 Methodology

As demonstrated in Figure 2, our ISNet incorporates the image-level contextual
information and semantic-level contextual information for semantic image
segmentation. We first introduce the overall formulation of our framework in
Section 3.1. Then, the details of image-level context module (ILCM) and
semantic-level context module (SLCM) are described in Section 3.2 and Section
3.3, respectively. Finally, we show the multi-task loss function used for
training the proposed ISNet in Section 3.4.

###  3.1 Formulation

Given the input image $\mathcal{I}\in\mathbb{R}^{3\times H\times W}$, we first
use a backbone network $\mathscr{B}$ (_e.g._ , ResNet [16]) to project the
pixels in $\mathcal{I}$ into a non-linear embedding space so that we can
obtain the pixel representations $\mathcal{R}$:

$\mathcal{R}=\mathscr{B}(\mathcal{I}),$ (1)

where $\mathcal{R}$ is a matrix of size $C\times\frac{H}{8}\times\frac{W}{8}$
and the dimension of a pixel representation is $C$.

Then, the image-level context module $\mathscr{M}_{il}$ is utilized to
aggregate the contextual information from the whole image:

$\mathcal{R}_{il}=\mathscr{M}_{il}(\mathcal{R}),$ (2)

where $\mathcal{R}_{il}$ is a matrix of size
$C\times\frac{H}{8}\times\frac{W}{8}$ storing the image-level contextual
information for each pixel representation. Simultaneously, the semantic-level
context module $\mathscr{M}_{sl}$ is designed to capture the contextual
information within individual category regions:

$\mathcal{R}_{sl}=\mathscr{M}_{sl}(\mathcal{R}),$ (3)

where $\mathcal{R}_{sl}$ is a matrix of size
$C\times\frac{H}{8}\times\frac{W}{8}$ storing the semantic-level contextual
information for each pixel representation. After that, we calculate the
similarities between $\mathcal{R}$ and $\mathcal{R}_{il}$:

$\mathcal{S}_{il}=Softmax(\frac{\mathcal{R}^{\frac{HW}{64}\times
C}\otimes\mathcal{R}^{C\times\frac{HW}{64}}_{il}}{\sqrt{C}}),$ (4)

where $\mathcal{S}_{il}$ is a matrix of size
$\frac{HW}{64}\times\frac{HW}{64}$ and $\otimes$ stands for matrix
multiplication. The same for $\mathcal{R}$ and $\mathcal{R}_{sl}$:

$\mathcal{S}_{sl}=Softmax(\frac{\mathcal{R}^{\frac{HW}{64}\times
C}\otimes\mathcal{R}^{C\times\frac{HW}{64}}_{sl}}{\sqrt{C}}),$ (5)

where $\mathcal{S}_{sl}$ is a matrix of size
$\frac{HW}{64}\times\frac{HW}{64}$. This operation is inspired by the self-
attention mechanism [6]. Next, we leverage $\mathcal{R}_{il}$ and
$\mathcal{R}_{sl}$ to augment $\mathcal{R}$:

$\mathcal{R}_{aug}=\mathscr{A}(\mathcal{R}^{\prime}_{il}\oplus\mathcal{R}^{\prime}_{sl}\oplus\mathcal{R}),$
(6)

where $\oplus$ denotes for the concatenation operation and $\mathscr{A}$ is a
transform function used to reduce the channels of the input matrix tensors to
have size $C\times\frac{H}{8}\times\frac{W}{8}$. $\mathcal{R}^{\prime}_{il}$
is calculated by using $\mathcal{S}_{il}$ and $\mathcal{R}_{il}$:

$\mathcal{R}^{\prime}_{il}=reshape(\mathcal{S}^{\frac{HW}{64}\times\frac{HW}{64}}_{il}\otimes\mathcal{R}^{\frac{HW}{64}\times
C}_{il}),$ (7)

and $\mathcal{R}^{\prime}_{sl}$ is obtained as follows:

$\mathcal{R}^{\prime}_{sl}=reshape(\mathcal{S}^{\frac{HW}{64}\times\frac{HW}{64}}_{sl}\otimes\mathcal{R}^{\frac{HW}{64}\times
C}_{sl}),$ (8)

where $reshape$ is used to make $\mathcal{R}^{\prime}_{il}$ and
$\mathcal{R}^{\prime}_{sl}$ have size of
$C\times\frac{H}{8}\times\frac{W}{8}$. At last, $\mathcal{R}_{aug}$ is
leveraged to predict the labels of the pixels in $\mathcal{I}$:

$\mathcal{O}=Upsample_{8\times}(\mathscr{H}(\mathcal{R}_{aug})),$ (9)

where $\mathscr{H}$ is a classification head and $\mathcal{O}$ is a matrix of
size $K\times H\times W$ storing the predicted class probability distribution
of each pixel. $K$ is the number of the categories.

###  3.2 Image-Level Context Module

Image-level context module $\mathscr{M}_{il}$ is designed to capture the
contextual information from the perspective of the whole image. Since there
exist co-occurrent visual patterns [35], $\mathscr{M}_{il}$ is widely applied
in semantic segmentation task. Prior to this paper, there have been many
excellent structures of $\mathscr{M}_{il}$ such as ASPP [4], PPM [35] and OCR
[30]. Despite this, since there are two context modules in our framework, we
expect the designed $\mathscr{M}_{il}$ in this paper owning the least
computation complexity and the increased parameters. Following this
expectation, as indicated in Figure 2, we first calculate the channel-wise
mean values of the matrix tensor $\mathcal{R}$:

$\mathcal{G}=\frac{1}{\frac{H}{8}\times\frac{W}{8}}\sum_{ij}\mathcal{R}_{[*,i,j]},$
(10)

where we leverage the subscript $[i,j]$ or $[*,i,j]$ to index the element or
elements of a matrix. $\mathcal{G}$ is a matrix of size $C\times 1\times 1$
storing the global contextual information of corresponding channels. Then,
$\mathcal{G}$ is added into the pixel representations $\mathcal{R}$ to obtain
$\mathcal{R}_{il}$:

$\mathcal{R}_{il}=\mathscr{F}(repeat(\mathcal{G})\oplus\mathcal{R}),$ (11)

where $\mathscr{F}$ is a transform function used to fuse $\mathcal{G}$ and
$\mathcal{R}$, implemented by a $1\times 1$ convolutional layer. $repeat$ is
used to repeat the elements in the corresponding channels of $\mathcal{G}$ to
make $\mathcal{G}$ have the same shape as $\mathcal{R}$. Note that, the image-
level context module can be replaced by all of the existing method such as
ASPP [4] and PPM [35] for better modeling the image-level context when
pursuing the best segmentation performance. It does not affect the basic
motivation of this paper.

###  3.3 Semantic-Level Context Module

Semantic-level context module $\mathscr{M}_{sl}$ is proposed to aggregate the
contextual information within individual category regions. As shown in Figure
2, a classification head $\mathscr{H}^{\prime}$ is first introduced to predict
the category probability distribution $\mathcal{D}$ of the representations in
$\mathcal{R}$:

$\mathcal{D}=\mathscr{H}^{\prime}(\mathcal{R}),$ (12)

where the size of $\mathcal{D}$ is $K\times\frac{H}{8}\times\frac{W}{8}$ and
$\mathscr{H}^{\prime}$ is implemented by two $1\times 1$ convolutional layers.
According to $\mathcal{D}$, the representations in $\mathcal{R}$ can be
grouped into various category regions:

$\mathcal{R}_{c_{k}}=\\{\mathcal{R}_{[*,i,j]}~{}|~{}argmax(\mathcal{D}_{[*,i,j]})=c_{k}\\},$
(13)

where $c_{k}$ is between $1$ and $K$ standing for the category label and
$\mathcal{R}_{c_{k}}$ is a matrix of size $N_{c_{k}}\times C$. $N_{c_{k}}$
denotes for the number of representations belonging to category $c_{k}$. For
the convenience of presentation, we also define the $\mathcal{D}_{c_{k}}$ as:

$\mathcal{D}_{c_{k}}=\\{\mathcal{D}_{[c_{k},i,j]}~{}|~{}argmax(\mathcal{D}_{[*,i,j]})=c_{k}\\},$
(14)

where $\mathcal{D}_{c_{k}}$ is a matrix of size $N_{c_{k}}\times 1$. Next, to
aggregate the semantic-level contextual information for each pixel
representation according to their category, we calculate the region
representation for each semantic class $c_{k}$ as follows:

$\mathcal{R}^{\prime}_{c_{k}}=\sum_{n=1}^{N_{c_{k}}}\frac{e^{\mathcal{D}_{c_{k},[n,*]}}}{\sum
e^{\mathcal{D}_{c_{k}}}}\cdot\mathcal{R}_{c_{k},[n,*]}$ (15)

where $\mathcal{R}^{\prime}_{c_{k}}$ of size $1\times C$ is the composite
vector of the representations of the same category. After calculating all
region representations, we assign them to a matrix tensor according to the
class label of corresponding element:

$\mathcal{R}_{sl,[*,i,j]}=\mathcal{R}^{\prime}_{c_{k}}~{}if~{}argmax(\mathcal{D}_{[*,i,j]})=c_{k}$
(16)

where $\mathcal{R}_{sl}$ of size $C\times\frac{H}{8}\times\frac{W}{8}$ is the
semantic-level contextual information we demand.

###  3.4 Loss Function

A multi-task loss function of $\mathcal{D}$ and $\mathcal{O}$ is used to
jointly optimize the model parameters. In particular, the loss function of
$\mathcal{D}$ is defined as:

$\mathcal{L}_{\mathcal{D}}=\frac{1}{H\times
W}\sum_{i,j}L_{ce}(\mathcal{D}^{K\times H\times
W}_{[*,i,j]},~{}\S(\mathcal{GT}_{[ij]})),$ (17)

where $\S$ denotes for converting the ground truth class label stored in
$\mathcal{GT}$ into one-hot format and $\mathcal{D}^{K\times H\times W}$ is
calculated as follows:

$\mathcal{D}^{K\times H\times W}=Softmax(Upsample_{8\times}(\mathcal{D})).$
(18)

$L_{ce}$ denotes for the _cross entropy loss_ and $\sum_{i,j}$ denotes that
the summation is calculated over all locations on the input image $I$. To let
$\mathcal{O}$ contain the accurate category probability distribution of each
pixel, we define the loss function of $\mathcal{O}$ as follows:

$\mathcal{L}_{\mathcal{O}}=\frac{1}{H\times
W}\sum_{i,j}L_{ce}(\mathcal{O}_{[*,i,j]},~{}\S(\mathcal{GT}_{[ij]})).$ (19)

Finally, we formulate the multi-task loss function $\mathcal{L}$ as:

$\mathcal{L}=\alpha\mathcal{L}_{\mathcal{D}}+\mathcal{L}_{\mathcal{O}}$ (20)

where $\alpha$ is the hyper-parameters to balance the loss of
$\mathcal{L}_{\mathcal{D}}$ and $\mathcal{L}_{\mathcal{O}}$. We empirically
set $\alpha=0.4$ by default. With this joint loss function, the model
parameters are learned jointly through back propagation.

##  4 Experiments

###  4.1 Experimental Setup

Benchmarks. We conduct the experiments on four widely-used semantic
segmentation benchmarks.

  * •

ADE20K [37] is a scene parsing dataset including 150 categories and diverse
scenes with 1,038 image-level labels. This challenging benchmark is divided
into 20K/2K/3K images for training, validation and testing.

  * •

COCOStuff [2] is a challenging scene parsing dataset that provides rich
annotations for 91 thing classes and 91 stuff classes. The dataset contains
9K/1K images for training and testing, respectively.

  * •

LIP [13] is a large-scale benchmark that focuses on single human parsing. It
contains 50,426 single-person images, which are divided into 30,426 images for
training, 10,000 for validation and 10,000 for testing. The pixel-wise
annotations cover 19 semantic human part labels and one background label.

  * •

Cityscapes [9] is a benchmark for semantic urban scene understanding that
contains 19 semantic classes. There are 5K high quality pixel-level finely
annotated images and 20K coarsely annotated images in the dataset. The finely
annotated 5K images are divided into sets with numbers 2,975, 500, 1,525 for
training, validation and testing.

Training Details. We initialize the backbone network using the weights pre-
trained on ImageNet and two integrated context modules are initialized
randomly. “Poly” learning rate policy with factor
$(1-\frac{iter}{total\\_iter})^{0.9}$ is performed for training our framework.
Synchronized batch normalization implemented by pytorch is enabled during
training. And for the data augmentation, we augment each sample with random
scaling in the range of $[0.5,2]$, random cropping and left-right flipping
during training. More specifically, following previous works [30], the
training settings for different benchmarks are listed as follows:

  * •

ADE20K: The initial learning rate is set as $0.01$ and the weight decay is
$0.0005$. The crop size of the input image is set as $512\times 512$ and batch
size is set as $16$ by default. The models are fine-tuned for 160K iterations
if not specified.

  * •

COCOStuff: We set the initial learning rate as $0.001$, weight decay as
$0.0001$, crop size as $512\times 512$, batch size as $16$ and training
iterations as 60K by default.

  * •

LIP: The initial learning rate is set as $0.01$ and the weight decay is
$0.0005$. The crop size of the input image is set as $473\times 473$ and batch
size is set as $32$ by default. If not specified, the models are fine-tuned
for 160K iterations.

  * •

Cityscapes: The initial learning rate is set as $0.01$ and the weight decay is
$0.0005$. We set the crop size of the input image as $512\times 1024$, batch
size as $8$ and the training iterations as 80K if not specified.

Inference Settings. For ADE20K, COCOStuff and LIP, the size of the input image
during testing is the same as the size of the input image during training. And
for Cityscapes, the input image is zoomed to have its shorter side being
$1024$ pixels. By default, no tricks (_e.g._ , multi-scale with flipping
testing) will be adopted during testing.

Evaluation Metrics. Following the standard setting, mean intersection-over-
union (mIoU) is adopted for evaluation.

Reproducibility. The proposed framework is implemented on PyTorch
($version\geq 1.3$) and trained on four NVIDIA Tesla V100 GPUs with a 32 GB
memory per-card. And all the testing procedures are performed on a single
NVIDIA Tesla V100 GPU. To provide full details of our framework, our code will
be made publicly available.

###  4.2 Ablation Study

ILCM. Since there exist co-occurrent visual patterns, the image-level
contextual information is significant for semantic image segmentation. For
instance, the car is likely to be in the parking lot or on the highway while
not fly in sky. From Table 1, we can see that the image-level contextual
module (ILCM) brings an improvement of $5.54\%$ mIoU on the validation set of
ADE20K. This result demonstrates that ILCM owns the ability of modeling the
context from the perspective of the whole image and so that it helps the
network better classify the pixels by considering the long-range dependencies.

Table 1:  Ablation experiments on the image-level context module (ILCM) and
the semantic-level context module (SLCM). All methods are learned on the train
set of ADE20K and evaluated using single scale test protocal on the validation
set.

Baseline | ILCM | SLCM | Backbone | mIoU
---|---|---|---|---
✓ |  |  | ResNet-50 | 36.96
✓ | ✓ |  | ResNet-50 | 42.50
✓ |  | ✓ | ResNet-50 | 42.89
✓ | ✓ | ✓ | ResNet-50 | 44.09

Table 2:  Complexity comparison with existing context schemes. The feature map
of size $[1\times 2048\times 128\times 128]$ is adopted to evaluate their
complexity during inference. All the numbers are obtained on a single NVIDIA
Tesla V100 GPU with CUDA 11.0 and the smaller, the better. As seen, our method
requires the least Parameters and the least FLOPs.

Method | Parameters | FLOPs | Time
---|---|---|---
ASPP [5] (_our impl._) | 42.21M | 674.47G | 101.44ms
PPM [35] (_our impl._) | 23.07M | 309.45G | 29.57ms
CCNet [17] (_our impl._) | 23.92M | 397.38G | 56.90ms
OCRNet [30] (_our impl._) | 14.82M | 237.45G | 20.22ms
DANet [11] (_our impl._) | 23.92M | 392.02G | 62.64ms
ANN [38] (_our impl._) | 20.32M | 335.24G | 49.66ms
DNL [28] (_our impl._) | 24.12M | 395.25G | 68.62ms
APCNet [15] (_our impl._) | 30.46M | 413.12G | 54.20ms
ILCM (_ours_) | 10.36M | 169.77G | 42.56ms
SLCM (_ours_) | 10.10M | 165.47G | 53.12ms
ILCM+SLCM (_ours_) | 11.02M | 180.60G | 84.19ms

SLCM. Since the label of a pixel is essentially the category of the object the
pixel belongs to, the contextual information from the same semantic class
could further enhance the category representation ability of the original
pixel representations. Accordingly, the network can leverage the enhanced
representations to classify the pixels more accurately. As demonstrated in
Table 1, we can see that aggregating the semantic-level contextual information
can improve the performance of base framework by $5.93\%$ in terms of mIoU.
This improvement well demonstrates the effectiveness of the proposed semantic-
level context module.

ILCM+SLCM. Co-occurrent visual pattern makes image-level contextual
information be critical for semantic segmentation. However, capturing the
contextual information from the whole image will also cause some problems. For
instance, since the label of a pixel is decided by the category of the object
the pixel belongs to, aggregating too much contextual information from other
category regions may cause the network to mislabel the pixel as other
categories. To address this issue, this paper proposes to introduce the
semantic-level contextual information for each pixel representation
additionally, which only leverages the representations in the corresponding
category region to enhance each pixel representation. As illustrated in Table
1, we can find that combining ILCM and SLCM outperforms the base model by
$7.13\%$ in terms of mIoU. The improvement is much higher than applying single
ILCM ($7.13\%$ _v.s._ $5.54\%$) or single SLCM ($7.13\%$ _v.s._ $5.93\%$).
This result indicates that ILCM and SLCM can complement and promote each
other, which well demonstrates the reliability of the basic motivation, and
the effectiveness of the designed framework in this paper.

Table 3:  Comparison with the existing context schemes in terms of mIoU. All
the models here are learned on the train set of ADE20K and tested on the
validation set of ADE20K.

Method | Backbone | Stride | Iterations | mIoU
---|---|---|---|---
PPM [35] (_our impl._) | ResNet-50 | $8\times$ | 160K | 42.64
ASPP [5] (_our impl._) | ResNet-50 | $8\times$ | 160K | 43.19
OCR [30] (_our impl._) | ResNet-50 | $8\times$ | 160K | 42.47
ANN [38] (_our impl._) | ResNet-50 | $8\times$ | 160K | 41.75
NonLocal [26] (_our impl._) | ResNet-50 | $8\times$ | 160K | 42.15
DNL [28] (_our impl._) | ResNet-50 | $8\times$ | 160K | 43.50
CCNet [17] (_our impl._) | ResNet-50 | $8\times$ | 160K | 42.47
ISNet (_ours_) | ResNet-50 | $8\times$ | 160K | 44.09

Figure 3:  Qualitative results on the validation set of ADE20K. All the models
here are trained under the same setting with ResNet-50 as the backbone
network. Best viewed in color and zoom in.

Qualitative Results. Figure 3 shows some qualitative results to further prove
the reliability of our basic motivation. As seen, the segmentation performance
has been well improved after introducing the semantic-level context module
(SLCM). For instance, in the 2nd row, the painting with only a small visible
part on the right side of the image is still well segmented (the ground truth
is wrong). This result well indicates that aggregating too much contextual
information from other category regions may cause the network to mislabel one
pixel as other categories, and introducing SLCM can well alleviate this
problem.

Complexity. Table 2 demonstrates the complexity comparison with existing
context schemes, including the increased parameters, computation complexity
(measured by the number of FLOPs) and inference time. As seen, the proposed
context scheme requires the least parameters and the least computation
complexity. Specifically, ILCM+SLCM only requires $\frac{1}{4}$ and
$\frac{1}{2}$ of the parameters of ASPP and PPM respectively, which can
prevent our model from overfitting to a certain extent. Furthermore, ILCM+SLCM
only requires $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{2}$, $\frac{7}{10}$,
$\frac{1}{2}$, $\frac{1}{2}$, $\frac{1}{2}$, $\frac{2}{5}$ of the FLOPs based
on PPM, ASPP, CCNet, OCRNet, DANet, ANNet, DNL and APCNet respectively. These
results well prove the efficiency of the proposed method.

Performance Comparison. To further show the necessity of introducing the
semantic-level contextual information, we compare the performance of ISNet
with the existing context schemes under the same training and testing
settings. As illustrated in Table 3, we can see that ISNet outperforms all the
existing context modules by yielding a mIoU of $44.09\%$. Noted that, the
image-level context module integrated into ISNet only gains a mIoU of
$42.50\%$ which is much weaker than most of the existing image-level context
schemes. This result well demonstrates the effectiveness of introducing the
semantic-level contextual information.

Table 4:  Segmentation results on ADE20K validation set. Multi-scale and
flipping testing is employed here for fair comparison. The best score is
marked in bold.

Method | Backbone | Stride | mIoU
---|---|---|---
PSPNet [35] | ResNet-101 | $8\times$ | 43.29
PSANet [36] | ResNet-101 | $8\times$ | 43.77
EncNet [33] | ResNet-101 | $8\times$ | 44.65
OCNet [31] | ResNet-101 | $8\times$ | 45.08
OCRNet [30] | ResNet-101 | $8\times$ | 45.28
CCNet [17] | ResNet-101 | $8\times$ | 45.76
ANNet [38] | ResNet-101 | $8\times$ | 45.24
ACNet [12] | ResNet-101 | $8\times$ | 45.90
DMNet [14] | ResNet-101 | $8\times$ | 45.50
APCNet [15] | ResNet-101 | $8\times$ | 45.38
DANet [11] | ResNet-101 | $8\times$ | 45.22
OCRNet [30] | HRNetV2-W48 | $4\times$ | 45.66
ISNet (_ours_) | ResNet-50 | $8\times$ | 45.04
ISNet (_ours_) | ResNet-101 | $8\times$ | 47.31
ISNet (_ours_) | ResNeSt-101 | $8\times$ | 47.55

Table 5:  Comparison of performance on the test set of COCOStuff with state-
of-the-art approaches. Multi-scale and flipping testing is leveraged here for
fair comparison.

Method | Backbone | Stride | mIoU
---|---|---|---
OCRNet [30] | ResNet-101 | $8\times$ | 39.50
SVCNet [10] | ResNet-101 | $8\times$ | 39.60
DANet [11] | ResNet-101 | $8\times$ | 39.70
EMANet [20] | ResNet-101 | $8\times$ | 39.90
SpyGR [19] | ResNet-101 | $8\times$ | 39.90
ACNet [12] | ResNet-101 | $8\times$ | 40.10
OCRNet [30] | HRNetV2-W48 | $4\times$ | 40.50
ISNet (_ours_) | ResNet-50 | $8\times$ | 40.16
ISNet (_ours_) | ResNet-101 | $8\times$ | 41.60
ISNet (_ours_) | ResNeSt-101 | $8\times$ | 42.08

###  4.3 Comparison with State-of-the-Art

ADE20K. Results of other state-of-the-art semantic segmentation solutions on
ADE20K are summarized in Table 4. As is known, ADE20K is challenging due to
its various image scales, plenty of semantic classes and the gap between its
training and validation set. Even under such circumstance, ISNet employing
ResNet-50 achieves a mIoU of $45.04\%$, which is $1.75\%$, $1.27\%$ and
$0.39\%$ mIoU higher than PSPNet [35], PSANet [36] and EncNet [33] using a
stronger ResNet-101 backbone network, respectively. This result further shows
the importance of aggregating the semantic-level contextual information for
augmenting each pixel representation. Furthermore, as we can see, the previous
best method named ACNet achieves a mIoU of $45.90\%$. Our ISNet with
ResNet-101 achieves superior mIoU of $47.31\%$ which is $1.41\%$ mIoU higher
than the previous state-of-the-art. Besides, integrating ILCM and SLCM also
allows this paper to report new state-of-the-art performance on the validation
set of ADE20K, _i.e._ , $47.55\%$ by leveraging ResNeSt-101.

Table 6:  State-of-the-art comparison on the validation set of LIP. Flipping
testing is utilized here for fair comparison. $\ddagger$ means that we adopt
ASPP as the image-level context module.

Method | Backbone | Stride | mIoU
---|---|---|---
DeepLab [4] | ResNet-101 | - | 44.80
CE2P [23] | ResNet-101 | $16\times$ | 53.10
OCRNet [30] | ResNet-101 | $8\times$ | 55.60
OCNet [31] | ResNet-101 | $8\times$ | 54.72
CCNet [17] | ResNet-101 | $8\times$ | 55.47
HRNet [25] | HRNetV2-W48 | $4\times$ | 55.90
OCRNet [30] | HRNetV2-W48 | $4\times$ | 56.65
ISNet (_ours_) | ResNet-50 | $8\times$ | 53.41
ISNet (_ours_) | ResNet-101 | $8\times$ | 55.41
ISNet (_ours_) | ResNeSt-101 | $8\times$ | 56.81
ASPP (_our impl._) | ResNet-101 | $8\times$ | 55.34
ISNet$\ddagger$ (_ours_) | ResNet-101 | $8\times$ | 56.96

Table 7:  Segmentation results on Cityscapes validation set. Only single-scale
testing is adopted here.

Method | Backbone | Stride | mIoU
---|---|---|---
GCNet [3, 8] | ResNet-101 | $8\times$ | 79.03
PSPNet [35, 8] | ResNet-101 | $8\times$ | 79.76
PSANet [36, 8] | ResNet-101 | $8\times$ | 79.31
ANN [38, 8] | ResNet-101 | $8\times$ | 77.14
NonLocal [26, 8] | ResNet-101 | $8\times$ | 78.93
CCNet [17, 8] | ResNet-101 | $8\times$ | 78.87
EncNet [33, 8] | ResNet-101 | $8\times$ | 78.55
DANet [11, 8] | ResNet-101 | $8\times$ | 80.41
DNL [28, 8] | ResNet-101 | $8\times$ | 80.41
OCRNet [30, 8] | HRNetV2-W48 | $4\times$ | 80.70
ISNet (_ours_) | ResNet-50 | $8\times$ | 79.32
ISNet (_ours_) | ResNet-101 | $8\times$ | 80.56
ISNet$\ddagger$ (_ours_) | ResNet-101 | $8\times$ | 81.10

Figure 4:  Qualitative results on the validation set of ADE20K. All the models
here are trained under the same setting. Best viewed in color and zoom in.

COCOStuff. Since there are only 9K images in the train set of COCOStuff where
these images contain 182 semantic classes, COCOStuff is a very challenging
benchmark for scene parsing. Table 5 compares the performance of the state-of-
the-art methods. By leveraging ResNet-50 as the backbone network, ISNet
achieves a mIoU of $40.16\%$, which is already higher than the most of the
previous state-of-the-art methods. When leveraging the same backbone network
ResNet-101, our ISNet surpasses OCRNet [30], EMANet [20], DANet [11] and ACNet
[12] in a large margin, _i.e._ , $2.10\%$, $1.70\%$, $1.90\%$ and $1.50\%$
mIoU, respectively. Furthermore, because of the effectiveness of integrating
image-level and semantic-level context for semantic image segmentation, our
ISNet with ResNeSt-101 reports the new state-of-the-art performance on the
testing set of COCOStuff, _i.e._ , $42.08\%$.

LIP. LIP is a fine-grained semantic segmentation benchmark which has
additional challenges such as the complex clothes texture, the scale diversity
of different categories, the deformable human body, and the fine-grained
segmentation of labels. Therefore, it is hard to model the image-level context
by only leveraging the proposed ILCM, which simply concatenates output
features of an average pooling layer. Despite this, as demonstrated in Table
6, ISNet with ResNet-101 still achieves a mIoU of $55.41\%$ which is very
competitive among the previous state-of-the-art methods. To report a new
state-of-the-art performance, we replace the original ILCM with ASPP [4] here
to better model the image-level context. As seen, our ISNet$\ddagger$
outperforms the previous best method OCRNet with HRNetV2-W48 by $0.31\%$ mIoU
while ASPP only achieves $55.34\%$ in terms of mIoU which is $1.62\%$ lower
than our ISNet$\ddagger$. These results consistently prove the basic
motivation of this paper, _i.e._ , additionally introducing the semantic-level
contextual information is critical to improving the pixel representations.

Cityscapes. As shown in Table 7, we also show the comparative results with
other state-of-the-art methods on the validation set of Cityscapes. We can see
that our model ISNet$\ddagger$ with ResNet-101 is superior to previous best
method OCRNet with HRNetV2-W48. Specifically, integrating the image-level
context module ASPP and the proposed semantic-level context module SLCM makes
this paper report a new state-of-the-art with mIoU hitting $81.10\%$ under
single-scale testing. This result further proves the rationality of
aggregating the image-level and semantic-level context for augmenting each
pixel representation.

Qualitative Results. Figure 4 illustrates the qualitative results on the
validation set of ADE20K. We can see that our ISNet could achieve better
segmentation results than both FCN (_i.e._ , without context module) and
PSPNet (_i.e._ , using the image-level context module), which further shows
the effectiveness of our method (_i.e._ , adopting both image-level and
semantic-level context module).

##  5 Conclusion

This paper studies the context aggregation problem. Motivated by the fact that
the existing image-level context schemes may bring too much contextual
information of other categories into the pixel representations so that it
makes the network mislabel the pixel, we propose to integrate the image-level
contextual information and semantic-level contextual information,
respectively, to further boost the performance of semantic segmentation.
Specifically, we first design a simple yet effective image-level context
module as a common practice to capture the global semantic structured
information. Then, the semantic-level contextual information is also
aggregated for each pixel by leveraging the proposed semantic-level context
module. At last, the pixel representations are augmented by weighted
aggregating the image-level contextual information and the semantic-level
contextual information. Extensive experiments demonstrate the effectiveness of
our method. Integrating image-level and semantic-level context allows us to
report new-state-of-arts on four segmentation benchmarks, _i.e._ , ADE20K,
Cityscapes, LIP and COCOStuff.

## References

  * [1] Antoni Buades, Bartomeu Coll, and J-M Morel.  A non-local algorithm for image denoising.  In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), volume 2, pages 60–65. IEEE, 2005.
  * [2] Holger Caesar, Jasper Uijlings, and Vittorio Ferrari.  Coco-stuff: Thing and stuff classes in context.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1209–1218, 2018.
  * [3] Yue Cao, Jiarui Xu, Stephen Lin, Fangyun Wei, and Han Hu.  Gcnet: Non-local networks meet squeeze-excitation networks and beyond.  In Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, pages 0–0, 2019.
  * [4] Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L Yuille.  Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs.  IEEE transactions on pattern analysis and machine intelligence, 40(4):834–848, 2017.
  * [5] Liang-Chieh Chen, George Papandreou, Florian Schroff, and Hartwig Adam.  Rethinking atrous convolution for semantic image segmentation.  arXiv preprint arXiv:1706.05587, 2017.
  * [6] Liang-Chieh Chen, Yi Yang, Jiang Wang, Wei Xu, and Alan L Yuille.  Attention to scale: Scale-aware semantic image segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3640–3649, 2016.
  * [7] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In Proceedings of the European conference on computer vision (ECCV), pages 801–818, 2018.
  * [8] MMSegmentation Contributors.  MMSegmentation: Openmmlab semantic segmentation toolbox and benchmark.  https://github.com/open-mmlab/mmsegmentation, 2020.
  * [9] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3213–3223, 2016.
  * [10] Henghui Ding, Xudong Jiang, Bing Shuai, Ai Qun Liu, and Gang Wang.  Semantic correlation promoted shape-variant context for segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8885–8894, 2019.
  * [11] Jun Fu, Jing Liu, Haijie Tian, Yong Li, Yongjun Bao, Zhiwei Fang, and Hanqing Lu.  Dual attention network for scene segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3146–3154, 2019.
  * [12] Jun Fu, Jing Liu, Yuhang Wang, Yong Li, Yongjun Bao, Jinhui Tang, and Hanqing Lu.  Adaptive context network for scene parsing.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6748–6757, 2019.
  * [13] Ke Gong, Xiaodan Liang, Dongyu Zhang, Xiaohui Shen, and Liang Lin.  Look into person: Self-supervised structure-sensitive learning and a new benchmark for human parsing.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 932–940, 2017.
  * [14] Junjun He, Zhongying Deng, and Yu Qiao.  Dynamic multi-scale filters for semantic segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3562–3572, 2019.
  * [15] Junjun He, Zhongying Deng, Lei Zhou, Yali Wang, and Yu Qiao.  Adaptive pyramid context network for semantic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7519–7528, 2019.
  * [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [17] Zilong Huang, Xinggang Wang, Lichao Huang, Chang Huang, Yunchao Wei, and Wenyu Liu.  Ccnet: Criss-cross attention for semantic segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 603–612, 2019.
  * [18] Alexander Kirillov, Ross Girshick, Kaiming He, and Piotr Dollár.  Panoptic feature pyramid networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6399–6408, 2019.
  * [19] Xia Li, Yibo Yang, Qijie Zhao, Tiancheng Shen, Zhouchen Lin, and Hong Liu.  Spatial pyramid based graph reasoning for semantic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8950–8959, 2020.
  * [20] Xia Li, Zhisheng Zhong, Jianlong Wu, Yibo Yang, Zhouchen Lin, and Hong Liu.  Expectation-maximization attention networks for semantic segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9167–9176, 2019.
  * [21] Wei Liu, Andrew Rabinovich, and Alexander C Berg.  Parsenet: Looking wider to see better.  arXiv preprint arXiv:1506.04579, 2015.
  * [22] Jonathan Long, Evan Shelhamer, and Trevor Darrell.  Fully convolutional networks for semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3431–3440, 2015.
  * [23] Tao Ruan, Ting Liu, Zilong Huang, Yunchao Wei, Shikui Wei, and Yao Zhao.  Devil in the details: Towards accurate single and multiple human parsing.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4814–4821, 2019.
  * [24] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [25] Jingdong Wang, Ke Sun, Tianheng Cheng, Borui Jiang, Chaorui Deng, Yang Zhao, Dong Liu, Yadong Mu, Mingkui Tan, Xinggang Wang, et al.  Deep high-resolution representation learning for visual recognition.  IEEE transactions on pattern analysis and machine intelligence, 2020\.
  * [26] Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He.  Non-local neural networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7794–7803, 2018.
  * [27] Maoke Yang, Kun Yu, Chi Zhang, Zhiwei Li, and Kuiyuan Yang.  Denseaspp for semantic segmentation in street scenes.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3684–3692, 2018.
  * [28] Minghao Yin, Zhuliang Yao, Yue Cao, Xiu Li, Zheng Zhang, Stephen Lin, and Han Hu.  Disentangled non-local neural networks.  In European Conference on Computer Vision, pages 191–207. Springer, 2020.
  * [29] Fisher Yu, Vladlen Koltun, and Thomas Funkhouser.  Dilated residual networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 472–480, 2017.
  * [30] Yuhui Yuan, Xilin Chen, and Jingdong Wang.  Object-contextual representations for semantic segmentation.  arXiv preprint arXiv:1909.11065, 2019.
  * [31] Yuhui Yuan and Jingdong Wang.  Ocnet: Object context network for scene parsing.  arXiv preprint arXiv:1809.00916, 2018.
  * [32] Fan Zhang, Yanqin Chen, Zhihang Li, Zhibin Hong, Jingtuo Liu, Feifei Ma, Junyu Han, and Errui Ding.  Acfnet: Attentional class feature network for semantic segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6798–6807, 2019.
  * [33] Hang Zhang, Kristin Dana, Jianping Shi, Zhongyue Zhang, Xiaogang Wang, Ambrish Tyagi, and Amit Agrawal.  Context encoding for semantic segmentation.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 7151–7160, 2018.
  * [34] Hang Zhang, Chongruo Wu, Zhongyue Zhang, Yi Zhu, Zhi Zhang, Haibin Lin, Yue Sun, Tong He, Jonas Mueller, R Manmatha, et al.  Resnest: Split-attention networks.  arXiv preprint arXiv:2004.08955, 2020.
  * [35] Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia.  Pyramid scene parsing network.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2881–2890, 2017.
  * [36] Hengshuang Zhao, Yi Zhang, Shu Liu, Jianping Shi, Chen Change Loy, Dahua Lin, and Jiaya Jia.  Psanet: Point-wise spatial attention network for scene parsing.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 267–283, 2018.
  * [37] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba.  Scene parsing through ade20k dataset.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 633–641, 2017.
  * [38] Zhen Zhu, Mengde Xu, Song Bai, Tengteng Huang, and Xiang Bai.  Asymmetric non-local neural networks for semantic segmentation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 593–602, 2019.