# Keldysh Nonlinear Sigma Model for a Free-Fermion Gas under Continuous
Measurements

Qinghong Yang1<EMAIL_ADDRESS>Yi Zuo2 Dong E. Liu1,3,4,5
<EMAIL_ADDRESS>1State Key Laboratory of Low Dimensional Quantum
Physics, Department of Physics, Tsinghua University, Beijing, 100084, China
2Beijing National Laboratory for Condensed Matter Physics, and Institute of
Physics, Chinese Academy of Sciences, Beijing 100190, China  3Beijing Academy
of Quantum Information Sciences, Beijing 100193, China  4Frontier Science
Center for Quantum Information, Beijing 100184, China  5Hefei National
Laboratory, Hefei 230088, China

###### Abstract

Quantum entanglement phase transitions have provided new insights to quantum
many-body dynamics. Both disorders and measurements are found to induce
similar entanglement transitions. Here, we provide a theoretical framework
that unifies these two seemingly disparate concepts and discloses their
internal connections. Specifically, we analytically analyze a $d$-dimension
free-fermion gas subject to continuous projective measurements. By mapping the
Lindblad master equation to the functional Keldysh field theory, we develop an
effective theory termed as the time-local Keldysh nonlinear sigma model, which
enables us to analytically describe the physics of the monitored system. Our
effective theory resembles to that used to describe the disordered fermionic
systems. As an application of the effective theory, we study the transport
property and obtain a Drude-form conductivity where the elastic scattering
time is replaced by the inverse measurement strength. According to these
similarities, two different concepts, measurements and disorders, are unified
in the same theoretical framework. A numerical verification of our theory and
predictions is also provided.

##  I Introduction

The entanglement entropy, as a characteristic measure of quantum correlations,
has been intensively studied in many fields of physics Nielsen and Chuang
(2004); Laflorencie (2016); Calabrese and Cardy (2004); Ryu and Takayanagi
(2006). Subsystem entanglement entropies follow distinct scaling laws for
different dynamical phenomena in quantum many-body systems. By adjusting the
system parameters, different scaling laws can be mutually converted. One
typical example is the transition between the phase obeying the eigenstate
thermalization hypothesis (ETH) Deutsch (1991); Srednicki (1994) and the many-
body localized (MBL) phase Fleishman and Anderson (1980); Gornyi  _et al._
(2005); Basko  _et al._ (2006); Oganesyan and Huse (2007); Kjäll  _et al._
(2014); Vosk  _et al._ (2015). When quantum many-body systems obey ETH, the
entanglement entropy of subsystems presents a volume-law scaling . By
increasing the disorder strength, the systems will enter the MBL phase where
the subsystem entanglement entropy obeys the area law instead Pal and Huse
(2010); Bauer and Nayak (2013); Luitz  _et al._ (2015); Schreiber  _et al._
(2015); Khemani  _et al._ (2017); Abanin  _et al._ (2019). An alternative way
to obtain the entanglement transition has been proposed by using projective
measurements Nahum  _et al._ (2017); Li  _et al._ (2018). Intuitively, one can
imagine that local projective measurements will collapse a highly entangled
many-body state, thus enough measurements will convert the volume-law
entangled state to an area-law one. This phenomenon has been studied in a wide
variety of models Nahum  _et al._ (2017); Li  _et al._ (2018, 2019); Skinner
_et al._ (2019); Gullans and Huse (2020); Jian  _et al._ (2020); Choi  _et
al._ (2020); Szyniszewski  _et al._ (2020); Agrawal  _et al._ (2022); Cao  _et
al._ (2019); Fuji and Ashida (2020); Alberton  _et al._ (2021); Maimbourg  _et
al._ (2021); Chen  _et al._ (2020); Goto and Danshita (2020); Doggen  _et al._
(2022), and knowing the entanglement transition makes us relate the monitored
systems with quantum error correction Choi  _et al._ (2020).

Based on observations from the entanglement transition, one may wonder if
there are internal connections between these two different concepts,
measurements and disorders. In addition, the comprehensive knowledge of
monitored systems and identification of potential applications thereof are
contingent upon the disclosure of other properties that are currently
unexplored. For example, in the disorder-induced entanglement transition case,
we also know the transport property of corresponding systems. In the MBL
phase, degrees of freedom are indeed being localized, which is a manifestation
of the area-law entanglement, and in turn, this results in a zero DC
conductivity Basko  _et al._ (2006, 2007); Gopalakrishnan  _et al._ (2015);
Nandkishore and Huse (2015); Potter  _et al._ (2015). This property signifies
that the system has the capability to maintain its primary information,
thereby rendering it a noteworthy strategy for improving quantum memory. Since
in the measurement-induced transition counterpart, the dynamics will also be
hindered by continuous measurements and the subsystem entanglement entropy
also has an area-law scaling, it is natural to ask whether an analogous
localization effect exists and what is the behavior of the conductivity.

In this work, we develop an effective theory to analytically study properties
of a $d$-dimension free-fermion gas under continuous projective measurements,
and focus on the underlying connection between projective measurements and
disorders. In order to reveal the entanglement transition, previous studies
Nahum  _et al._ (2017); Li  _et al._ (2018, 2019); Skinner  _et al._ (2019);
Gullans and Huse (2020); Jian  _et al._ (2020); Choi  _et al._ (2020);
Szyniszewski  _et al._ (2020); Agrawal  _et al._ (2022); Cao  _et al._ (2019);
Fuji and Ashida (2020); Alberton  _et al._ (2021); Maimbourg  _et al._ (2021);
Chen  _et al._ (2020); Goto and Danshita (2020); Doggen  _et al._ (2022)
mostly focus on quantum trajectory dynamics conditioned on measurement
outcomes Jacobs and Steck (2006); Breuer  _et al._ (2002); Alberton  _et al._
(2021). In contrast to their calculations, our theoretical scheme directly
captures the unconditional dynamics generated by the full Lindblad master
equation Lindblad (1975); Breuer  _et al._ (2002). Note that if the quantity
is a linear function of the system’s state described by the density matrix,
the conditional and the unconditional approachs will give the same result.
Many physical observables including the conductivity are linear functions of
states. We then modify the Keldysh field theory mapping Sieberer  _et al._
(2016) to capture the Lindblad master equation for open fermionic systems.
Very surprisingly, the Keldysh Lindblad partition function for the monitored
case resembles to the partition function in the disordered fermionic case
Kamenev (2011); Kamenev and Andreev (1999); Horbach and Schön (1993); Liao and
Galitski (2018), although measurements and disorders look quite different in
the master equation formalism (see Fig. 1 for the comparison). Inspired by
this observation, we develop an effective theory termed as the time-local
Keldysh nonlinear sigma model (KNSM), to describe the physics of the monitored
free-fermion gas. As an application of our effective theory, we study the
transport property and obtain a Drude-form conductivity where the inverse
measurement strength plays the role of the elastic scattering time. This
result shows a slow-down effect or diffusive behavior Žnidarič (2010a, b);
Turkeshi and Schiró (2021); Jin  _et al._ (2022, 2023) due to measurements.

Sec. II sets the model under our consideration. The Keldysh Lindblad partition
function of the model is given in Sec. III. The effective KNSM and the time-
local diffuson are obtained in Sec. IV and Sec. V, respectively. In Sec. VI,
DC conductivity is derived from KNSM, and in Sec. VII, we perform a numerical
verification for our theory. Appendices A–C give detailed derivations of some
formulas in the main text.

##  II model

We consider a $d$-dimension spinless free-fermion gas, whose Hamiltonian reads

$H=\int
d\mathbf{x}\,c^{\dagger}\left(\mathbf{x}\right)\left(-\frac{1}{2m}\nabla^{2}-\epsilon_{F}\right)c\left(\mathbf{x}\right),$
(1)

where $c$ $(c^{\dagger})$ is the annihilation (creation) operator of fermions,
$m$ is the mass of fermions, and $\epsilon_{F}$ is the Fermi energy which
equals to the chemical potential. This free-fermion gas is subject to
continuous projective measurements, in which the projective operations can be
represented by the fermion density operator
$n(\mathbf{x})=c^{\dagger}(\mathbf{x})c(\mathbf{x})$. Note that
$n(\mathbf{x})$ satisfies
$n(\mathbf{x})(a|0_{\mathbf{x}}\rangle+b|1_{\mathbf{x}}\rangle)\propto|1_{\mathbf{x}}\rangle$
and $n^{2}(\mathbf{x})=n(\mathbf{x})$. For a unconditional continuous
measurement process, it can be described by the Lindblad master equation Fuji
and Ashida (2020); Jacobs and Steck (2006). Thus, for our case, the quantum
jump operator in the Lindblad master equation is the density operator
$n(\mathbf{x})$, and we have

$\partial_{t}\rho=-i\left[H,\rho\right]+\gamma\int
d\mathbf{x}\left[n(\mathbf{x})\,\rho\,n(\mathbf{x})-\frac{1}{2}\left\\{n(\mathbf{x}),\rho\right\\}\right],$
(2)

where $\rho$ is the density matrix of the free-fermion system, and $\gamma$ is
the measurement strength, which has the energy dimension and is assumed to be
uniform over the space. Intuitively, the measurement strength $\gamma$ can be
regarded as the number of measurement events in a unit time interval. For
convenience of following treatments, the initial state is chosen to be the
thermal state
$\rho_{0}=\exp[-\beta\sum_{\mathbf{k}}c_{\mathbf{k}}^{\dagger}(\epsilon_{\mathbf{k}}-\epsilon_{F})c_{\mathbf{k}}]$
with $\beta$ being the inverse temperature. Note that the Lindblad master
equation for the unconditional measurement process also describes the effect
of dephasing noise, thus our following results also have insights for open
quantum systems.

##  III Keldysh Lindblad partition function

In order to do analytical analyses, instead of focusing on the master equation
formalism, we resort to the functional Keldysh field theory Kamenev (2011);
Sieberer  _et al._ (2016). Following the procedures provided in Ref. Sieberer
_et al._ (2016), one can transform the fermionic Lindblad master equation Eq.
(2) to a Keldysh Lindblad partition function, which reads (see App. A for more
details and differences compared with Ref. Sieberer  _et al._ (2016))

$\begin{split}Z=\int\\!\mathcal{D}\left[\psi\right]\exp&\left\\{iS_{0}-\frac{\gamma}{2}\int\\!dx\boldsymbol{[}\bar{\psi}_{a}\left(x\right)\psi_{a}\left(x\right)\bar{\psi}_{b}\left(x\right)\psi_{b}\left(x\right)\right.\\\
&\qquad\qquad\qquad\;\left.\vphantom{\frac{\gamma}{2}\int
dx}-\bar{\psi}_{a}\left(x\right)\hat{\tau}_{1}^{ab}\psi_{b}\left(x\right)\boldsymbol{]}\right\\},\end{split}$
(3)

where $S_{0}$ is the free-fermion action in the $2\times 2$ Keldysh space,
$x=(\mathbf{x},t)$ throughout the paper, $a,b\in\\{1,2\\}$ are the Keldysh
indices, and the repeated indices imply the summation over all possible values
throughout the paper. Here,
$\mathcal{D}[\psi]\equiv\mathcal{D}[\bar{\psi}_{1},\psi_{1},\bar{\psi}_{2},\psi_{2}]$
with $\psi_{a}$ $(\bar{\psi}_{a})$ are Grassmann numbers after the Keldysh-
Lakin-Ovchinnikov transformation Kamenev (2011), and $\hat{\tau}_{\mu}$ with
$\mu=0,1,2,3$ are the identity and three Pauli matrices in the Keldysh space.
Since $Z\equiv\operatorname{tr}(\rho_{f})$, where $\rho_{f}$ is the density
matrix of the final state, the normalization condition $Z=1$ is self-evident
in the Keldysh formalism. In the following treatment, the time contour is
chosen to be $(-\infty,+\infty)$, such that all information of the system’s
evolution is imprinted in the partition function. To check the normalization
condition for Eq. (3), one can expand the partition function in powers of the
measurement strength $\gamma$, and treat each order with the help of Wick’s
theorem. By doing so, one will find that in order to preserve the
normalization condition, at least in the first order, the bare Green’s
function of free fermions should be in its full form, that is

$\hat{G}(\mathbf{k};t,t^{\prime})=\begin{bmatrix}G_{0}^{R}\left(\mathbf{k};t,t^{\prime}\right)&G_{0}^{K}\left(\mathbf{k};t,t^{\prime}\right)\\\
0&G_{0}^{A}\left(\mathbf{k};t,t^{\prime}\right)\end{bmatrix}-\frac{i}{2}\begin{bmatrix}0&1\\\
1&0\end{bmatrix}\delta_{t,t^{\prime}},$ (4)

where $G_{0}^{R/A/K}$ are three typical bare Green’s functions used in the
standard Keldysh field theory Kamenev (2011); Altland and Simons (2010), and
$\delta_{t,t^{\prime}}$ is the Kronecker delta symbol, which comes from the
discrete time version $\delta_{j,j^{\prime}}$ with $j,j^{\prime}$ standing for
the $j$th time slice and $j^{\prime}$th time slice. Note that in the
traditional Keldysh partition function derived from the Hamiltonian of a
closed system Altland and Simons (2010); Kamenev (2011), the extra term
$\propto\delta_{t,t^{\prime}}$ also exists. However, one usually omits it. One
argument is the $t=t^{\prime}$ line is a manifold of measure zero and omitting
it is inconsequential for most purposes Kamenev (2011). In our case, we
emphasize that this $\delta_{t,t^{\prime}}$ term cannot be directly omitted
due to the normalization condition mentioned above.

Figure 1: Comparisons between the disordered system and the monitored system
in the unconditional case. One finds that the connection between measurements
and disorders is not obvious in the master equation formalism, and can only be
found when one resorts to the Keldysh path integral formalism. KNSM is the
abbreviation of Keldysh nonlinear sigma model and TRS is that of time-reversal
symmetry.

In the Keldysh Lindblad partition function Eq. (3), we add two extra terms
$\bar{\psi}_{a}\left(x\right)\psi_{a}\left(x\right)\bar{\psi}_{b}\left(x\right)\psi_{b}\left(x\right)$
with $a=b$, which are null due to the property of Grassmann numbers —
$\bar{\psi}_{a}^{2}=\psi^{2}_{a}=0$. After adding these two terms, one finds
that the four-fermion term in the partition function is similar with the four-
fermion term after doing disorder average in the Keldysh treatment of the
disordered fermionic problem Kamenev (2011); Kamenev and Andreev (1999);
Horbach and Schön (1993); Liao and Galitski (2018) (see also App. B for a
brief introduction). We emphasize that such a similarity is not obvious in the
master equation formalism, and can only be found when one resorts to the
Keldysh path integral formalism (see Fig. 1). However, there are also some
differences between these two problems. For example, the four-fermion term in
Eq. (3) only depends on one time variable, while in the disordered fermionic
problem, the four-fermion term depends on two time variables. In addition,
there is no time-reversal symmetry in our case due to the nature of open
quantum systems, while the time-reversal symmetry is present in the free-
fermion gas with disorders (see App. B for detailed discussions).

##  IV Time-local Keldysh nonlinear sigma model

We then try to derive an effective theory to capture and analyze the monitored
system. To this end, we employ the Hubbard-Stratonovich (HS) transformation
Kamenev (2011); Altland and Simons (2010); Yang  _et al._ (2021) by
introducing a time-local bosonic field $\hat{Q}$ to decouple the four-fermion
term, where $\hat{Q}$ is defined as

$\hat{Q}=\int dx\begin{bmatrix}Q^{11}\left(x\right)&Q^{12}\left(x\right)\\\
Q^{21}\left(x\right)&Q^{22}\left(x\right)\end{bmatrix}|x\rangle\langle x|,$

and it is Hermitian in the Keldysh space, i.e., $Q^{ab}(x)=[Q^{ba}(x)]^{*}$.
Note that due to the fact that the four-fermion term depends on two time
variables in the disordered fermionic case, the matrix HS field there is not
diagonal in the time basis (time-nonlocal). The HS transformation and Gaussian
integral lead the partition function Eq. (3) to an effective bosonic theory
(see App. C for details):

$\begin{split}Z=\int\mathcal{D}\left[\hat{Q}\right]\exp&\left\\{-\frac{\gamma}{2}\left(\pi\nu\right)^{2}\operatorname{tr}\left[\hat{Q}^{2}+\left(\frac{1}{2\pi\nu}\hat{\tau}_{1}\right)^{2}\right]\right.\\\
&\quad\left.+\operatorname{tr}\ln\left(-i\hat{G}^{-1}_{0}+\gamma\pi\nu\hat{Q}\right)\vphantom{\left[\hat{Q}^{2}+\left(\frac{1}{2\pi\nu}\hat{\tau}_{1}\right)^{2}\right]}\right\\},\end{split}$
(5)

where $\operatorname{tr}$ stands for the trace over the Keldysh space as well
as time and spatial integrations, $\nu$ is density of states (DOS) in the
vicinity of the Fermi surface and $\hat{G}_{0}^{-1}$ is the inverse of
$\hat{G}+(i/2)\delta_{t,t^{\prime}}\hat{\tau}_{1}$ (see Eq. (4)). In the
procedure of replacing $\hat{G}^{-1}$ with $\hat{G}_{0}^{-1}$, we have
employed the argument that the $t=t^{\prime}$ line is a manifold of measure
zero to higher-order ($\geq 2$) terms of $\gamma$. As mentioned in the
previous, the time-reversal symmetry is absent in our case, thus we just
decouple the four-fermion term in the density channel. In contrast, in the
disordered fermionic case, one can also decouple the four-fermion term in the
Cooper channel, and this procedure results in Cooperons, which accounts for
the weak localization effect in the one-loop level of the KNSM Finkel’shtein
(1983); Finkel’Stein (1984); Kamenev (2011); Kamenev and Andreev (1999);
Horbach and Schön (1993) (see App. B for discussions about the absence of weak
localization in measurement case).

To proceed, we need to find the saddle point configuration of the action in
Eq. (5), which contributes most to the functional integral. Taking the
variation over $\hat{Q}(x)$, one gets the saddle point equation:

$\gamma\pi^{2}\nu^{2}\hat{Q}\left(x\right)=\gamma\pi\nu\left(-i\hat{G}_{0}^{-1}+\gamma\pi\nu\hat{Q}\right)^{-1}\left(x,x\right).$
(6)

One can check that the constant configuration
$\hat{\Lambda}=\frac{1}{2\pi\nu}\hat{\tau}_{3}$, satisfies the saddle point
equation when $\gamma$ satisfies $\gamma\ll\epsilon_{F}$. Note that this
condition also validates the procedure of replacing $\hat{G}^{-1}$ with
$\hat{G}_{0}^{-1}$ in Eq. (5). Fluctuations around the saddle point can be
classified into two classes: the massive and the massless modes. For large-
scale physics, the dynamics is mostly contributed by the massless modes. Thus,
we here focus on fluctuations of the $\hat{Q}$-matrix along the massless
“direction”, and they can be generated through the similarity transformation:
$\hat{Q}=\hat{\mathcal{R}}^{-1}\hat{\Lambda}\hat{\mathcal{R}}$. In the
spacetime basis,
$\hat{Q}(x)=\hat{\mathcal{R}}^{-1}(x)\,\hat{\Lambda}\,\hat{\mathcal{R}}(x)$,
and $\hat{Q}(x)$ satisfies the nonlinear constraint:
$\hat{Q}^{2}(x)=(\frac{1}{2\pi\nu})^{2}\hat{\tau}_{0}$.

In order to derive an effective theory for the massless modes, one can further
employ the gradient expansion, that is, we expand the $\operatorname{tr}\ln$
term in Eq. (5) in powers of $\partial_{t}\hat{\mathcal{R}}^{-1}$ and
$\nabla\hat{\mathcal{R}}^{-1}$. Keeping terms up to the first order of
$\partial_{t}\hat{\mathcal{R}}^{-1}$ and the second order of
$\nabla\hat{\mathcal{R}}^{-1}$, one arrives at the time-local Keldysh
nonlinear sigma model (see App. C for details):

$iS\left[\hat{Q}\right]=\pi\nu\operatorname{tr}\left[\partial_{t}\hat{Q}\right]-\frac{1}{4}\pi\nu
D\operatorname{tr}\left[\left(\nabla\hat{Q}\right)^{2}\right],$ (7)

where we just keep those non-constant terms in the action. Here, $\hat{Q}$ is
redefined as
$\hat{Q}=\hat{\mathcal{U}}^{-1}\hat{\mathcal{R}}^{-1}\hat{\tau}_{3}\hat{\mathcal{R}}\hat{\mathcal{U}}$,
where $\hat{\mathcal{U}}$ encodes the statistical information and is defined
as

$\hat{\mathcal{U}}^{-1}=\hat{\mathcal{U}}=\sum_{\epsilon}\begin{bmatrix}1&F_{\epsilon}\\\
0&-1\end{bmatrix}|\epsilon\rangle\langle\epsilon|$

with $F_{\epsilon}=\tanh(\beta\epsilon/2)$ relating to the Fermi-Dirac
distribution. The statistical distribution comes from the initial condition
$\rho_{0}$. In Eq. (7), the constant $D$ is defined as $D=v_{F}^{2}/(\gamma
d)$ with $v_{F}$ being the Fermi velocity, and is named as the modified
diffusive constant. Comparing with the traditional diffusive constant in the
disordered fermionic systems, one finds that the inverse measurement strength
$1/\gamma$ plays the role of the elastic scattering time (see Fig. 1).
Intuitively, this makes sense, as the elastic scattering time represents the
mean time within which a fermion hits the disorder, or in other words, is
measured by the disorder. Associating with the fact that the disordered
fermionic system is also described by a similar nonlinear sigma model, we know
that the effect of the projective measurements has some similarities with that
of disorders. Indeed, in the following, we will show that up to the one-loop
level of the time-local KNSM, the conductivity is presented in the familiar
Drude form Altland and Simons (2010); Kamenev (2011). Note that in Ref. Jin
_et al._ (2022, 2023), authors consider a relevant problem in one-dimension
and ladder systems. They use the perturbation theory within the self-
consistent Born approximation. In fact, their treatment is the saddle point of
our time-local KNSM Altland and Simons (2010), and the similarity between
projective measurements and disorders can not be seen in their treatment.

##  V Gaussian fluctuation and time-local diffuson

Having derived the saddle point and the effective theory for our problem, we
are now in a position to draw the consequences from our effective theory. To
this end, we write the similarity transformation matrix $\hat{\mathcal{R}}$
through its generator $\hat{\mathcal{W}}$ as
$\hat{\mathcal{R}}=\exp(\hat{\mathcal{W}}/2)$. In the spacetime basis, we have
$\hat{\mathcal{R}}(x)=\exp[\hat{\mathcal{W}}(x)/2]$. To generate a non-trivial
transformation for $\hat{\tau}_{3}$, the generator $\hat{\mathcal{W}}(x)$
should be an off-diagonal matrix in the Keldysh space, and can be expressed as

$\hat{\mathcal{W}}\left(x\right)=\begin{bmatrix}0&d^{12}\left(x\right)\\\
d^{21}\left(x\right)&0\end{bmatrix},$ (8)

where $\\{\hat{\mathcal{W}}(x),\hat{\tau}_{3}\\}=0$, and $d^{12}$ and $d^{21}$
are two independent fields. Substituting Eq. (8) into the nonlinear sigma
model Eq. (7), and expanding the action in powers of $d^{12}$ and $d^{21}$, up
to the second order, one obtains the Gaussian action

$iS\left[d^{12},d^{21}\right]=\pi\nu\int
dx\,d^{21}\left(x\right)\left(\partial_{t}-\frac{1}{2}D\nabla^{2}\right)d^{12}\left(x\right).$
(9)

With the help of the Fourier transformation, one finds that this Gaussian
action will generate two types of correlators — $\langle
d^{12}_{\mathbf{k},\epsilon}d^{21}_{-\mathbf{k},-\epsilon}\rangle$ and
$\langle d^{21}_{\mathbf{k},\epsilon}d^{12}_{-\mathbf{k},-\epsilon}\rangle$,
which are defined as

$\begin{split}\langle
d^{12}_{\mathbf{k},\epsilon}d^{21}_{-\mathbf{k},-\epsilon}\rangle&=-\frac{1}{\pi\nu}\frac{1}{D^{\prime}\mathbf{k}^{2}-i\epsilon},\\\
\langle
d^{21}_{\mathbf{k},\epsilon}d^{12}_{-\mathbf{k},-\epsilon}\rangle&=-\frac{1}{\pi\nu}\frac{1}{D^{\prime}\mathbf{k}^{2}+i\epsilon},\end{split}$
(10)

where $D^{\prime}\equiv(1/2)D$, and $\langle\cdot\rangle$ stands for taking
expectation values with weight $\exp(iS[d^{12},d^{21}])$. We name these two
correlators in Eq. (10) time-local diffusons, as they are similar with those
diffusons in the disorder fermionic systems Kamenev (2011); Kamenev and
Andreev (1999); Horbach and Schön (1993). The time-local diffusons play the
role of bare Green’s functions and serve as the starting point to consider
higher-order interaction effects and other phenomena underneath Liao and
Galitski (2018); Patel  _et al._ (2017).

##  VI  Linear response: DC conductivity

Although the evolution according to the Lindbald master equation with
Hermitian jump operators will result in featureless steady state Fuji and
Ashida (2020); Buchhold  _et al._ (2021), due to the projection nature of the
quantum jump operator $n(\mathbf{x})$, one can imagine that continuous
projective measurements will have some impacts on the linear response. Here,
we consider the most common linear response function in the condensed matter
theory: the conductivity. For this purpose, we introduce the vector potential
$\mathbf{A}(x)$, to which the current couples, through the action
$S_{\mathbf{A}}=-\int
dx\,\bar{\psi}_{a}(x)\mathbf{v}_{F}\mathbf{A}^{\alpha}(x)\hat{\tau}_{\alpha}^{ab}\psi_{b}(x)$
Kamenev (2011); Kamenev and Andreev (1999); Horbach and Schön (1993), where
$a,b\in\\{1,2\\}$, $\alpha\in\\{0,1\\}$, and $\mathbf{A}^{0}$ stands for the
classical component of the vector potential while $\mathbf{A}^{1}$ for the
quantum component after the Keldysh transformation. Since the vector potential
is classical, the quantum component $\mathbf{A}^{1}$ is actually zero. In the
Keldysh field theory, it is preserved to generate observables by appropriate
variations and is set to zero in the end. Following the procedures of deriving
Eq. (7), one can get the KNSM in the presence of the vector potential:

$iS\left[\hat{Q},\mathbf{A}\right]=\pi\nu\operatorname{tr}\left[\partial_{t}\hat{Q}\right]-\frac{1}{4}\pi\nu
D\operatorname{tr}\left[\left(\hat{\partial}\hat{Q}\right)^{2}\right],$ (11)

where we have assumed that the vector potential is small enough such that it
does not alter the previous saddle point,
$\hat{\partial}\hat{Q}=\nabla\hat{Q}+i\left[\mathbf{A}^{\alpha}\hat{\tau}_{\alpha},\hat{Q}\right]$,
and $\hat{Q}$ is also defined as
$\hat{Q}=\hat{\mathcal{U}}^{-1}\hat{\mathcal{R}}^{-1}\hat{\tau}_{3}\hat{\mathcal{R}}\hat{\mathcal{U}}$.

The longitudinal AC conductivity can be derived through
$\sigma(\mathbf{q},\omega)=(-i/\omega)K^{R}(\mathbf{q},\omega)$, where
$K^{R}(\mathbf{q},\omega)$ is the retarded current-current response function,
and is defined as

$K^{R}\left(\mathbf{q},\omega\right)=\left.\frac{e^{2}}{2i}\frac{\delta^{2}Z\left[\mathbf{A}\right]}{\delta\mathbf{A}^{0}\left(\mathbf{q},\omega\right)\delta\mathbf{A}^{1}\left(-\mathbf{q},-\omega\right)}\right|_{\mathbf{A}=0}$
(12)

with $e$ being the electron charge and $Z[\mathbf{A}]$ now being
$Z[\mathbf{A}]=\int\mathcal{D}[\hat{Q}]\exp\\{iS[\hat{Q},\mathbf{A}]\\}$. To
calculate the retarded current-current response function, one may expand
$Z[\mathbf{A}]$ in powers of $\mathbf{A}$ and keep terms up to the second
order of $\mathbf{A}$. Then, one finds that, up to the one-loop level of the
nonlinear sigma model (Eq. (9)), the longitudinal DC conductivity for the
spatially-uniform vector potential, reads

$\sigma\left(\mathbf{q}\rightarrow 0,\omega\rightarrow 0\right)=e^{2}\nu D.$
(13)

Thus, we reproduce the conductivity of the Drude form in a monitored free-
fermion gas. Note that for a purely free-fermion gas, the conductivity is
infinite, but in a monitored free-fermion gas, the conductivity is finite and
is inversely proportional to the measurement strength $\gamma$. This Drude-
form conductivity in the monitored free-fermion gas again presents the
similarity with disorders (see Fig. 1).

As mentioned previously, the absence of the weak localization effect in the
measurement case results from the lack of time-reversal symmetry (TRS).
According to the Drude-form conductivity, one can also obtain an intuitive
picture of the lack of weak localization as following. Even though
measurements and disorders will have similar effect as indicated by the
similar form in the functional Keldysh field theory, the measurement case will
introduce an extra decoherence effect due to the nature of open systems (and
this is the origin of the lack of TRS). This decoherence effect will turn the
quantum system into a classical one, and then analogous exotic effects, such
as weak localization and many-body localization, are hidden in the measurement
case, as even a classical system with disorders will not be localized and only
Drude conductivity will be derived. Therefore, in order to reveal the
localization effect produced by measurements, one has to suppress the
decoherence effect by some means. This will be explored in the following work.

##  VII Numerical Verification

To support the theory and verify our predictions, we provide a numerical test
based on a one-dimensional discrete free-fermion gas subject to continuous
measurements. The Hamiltonian of the one-dimensional free-fermion gas reads

$H=\sum_{i=1}^{N-1}\;t(c^{\dagger}_{i+1}c_{i}+c^{\dagger}_{i}c_{i+1}),$ (14)

where $N$ is the number of sites, and $t$ is the hopping strength, which sets
an energy scale similar with the Fermi energy in the continuum free-fermion
gas model. The value of $N$ does not change the $1/\gamma$ scaling shown in
the following, thus we take $N=6$ for simplicity. The evolution is governed by

$\partial_{t}\rho=-i[H,\rho]+\gamma\sum_{i}^{N}\left[n_{i}\,\rho\,n_{i}-\frac{1}{2}\\{n_{i},\rho\\}\right],$
(15)

where $n_{i}=c^{\dagger}_{i}c_{i}$ is the local particle number operator. In
the following, we will let $t=1$ for simplicity. Thus, the condition in our
work $\gamma\ll\epsilon_{F}$ becomes $\gamma\ll 1$ in this discrete model. In
order to calculate the conductivity, we introduce the source and drain in the
dissipator, in analogy to the chemical potential difference in the electrical
transport experiment. Then, the master equation becomes

$\begin{split}\partial_{t}\rho=-i[H,\rho]&+\gamma\sum_{i}^{N}\left[n_{i}\,\rho\,n_{i}-\frac{1}{2}\\{n_{i},\rho\\}\right]\\\
&+\gamma_{s}\left[c_{1}^{\dagger}\,\rho\,c_{1}-\frac{1}{2}\\{c_{1}c^{\dagger}_{1},\rho\\}\right]\\\
&+\gamma_{d}\left[c_{N}\,\rho\,c^{\dagger}_{N}-\frac{1}{2}\\{c^{\dagger}_{N}c_{N},\rho\\}\right],\\\
\end{split}$ (16)

where $\gamma_{s}$ and $\gamma_{d}$ are the strengths of pump and loss,
respectively. The pump process simulates a source, while the loss process
simulate a drain. In order to study the system described by Eq. (15),
$\gamma_{s}$ and $\gamma_{d}$ should be very small, or else the property of
our considered system will be changed due to those additional dissipation
processes. The current operator between two neighboring sites is defined as
$J_{i,i+1}=i(c_{i}^{\dagger}c_{i+1}-c_{i}c^{\dagger}_{i+1})$, and the
expectation value of $J_{i,i+1}$ or the particle current $\langle
J_{i,i+1}\rangle$ at time $t$ can be calculated through $\langle
J_{i,i+1}\rangle(t)=\operatorname{tr}\left[\rho(t)J_{i,i+1}\right]$, where
$\rho(t)$ is the state of the considered system at time $t$.

According to the Fick’s law Žnidarič (2010b); Jin  _et al._ (2022), the
particle current can also be calculated through $\langle
J\rangle=-D\nabla\langle n(\mathbf{x})\rangle$, where $D$ is the diffusion
coefficient and $\nabla\langle n(\mathbf{x})\rangle$ is particle number
gradient. It is similar with the Ohm’s law $\langle J_{e}\rangle=-\sigma\nabla
V(\mathbf{x})$ with $\sigma$ being the electrical conductivity and $\nabla
V(\mathbf{x})$ being the electrical potential gradient. Once we ignore the
electron charge, the electrical potential gradient $\nabla V(\mathbf{x})$
reduces to the particle number gradient $\nabla\langle n(\mathbf{x})\rangle$,
and the electrical current $\langle J_{e}\rangle$ becomes the particle current
$\langle J\rangle$. Therefore, once we verify the $1/\gamma$ scaling of the
diffusion coefficient from the Fick’s law, the $1/\gamma$ scaling of the
conductivity is also verified.

We numerically solving the Lindblad master equation with source and drain, and
then calculated the particle current $\langle J_{i,i+1}\rangle$ through
$\langle J_{i,i+1}\rangle(t)=\operatorname{tr}\left[\rho(t)J_{i,i+1}\right]$.
We find that the pump and loss will produce a non-zero steady particle current
through the free-fermion chain for arbitrary finite measurement strength
$\gamma$, and thus $\langle J_{i,i+1}\rangle$ for different $i$ are the same
in the steady state. This indicates that finite measurement strength will not
result in the localization effect. Without loss of generality, we choose
$i=1$. Therefore, in the discrete version, after reaching the steady state,
the Fick’s law can be simplified as $\langle J_{1,2}\rangle=-D\left(\langle
n_{1}\rangle-\langle n_{N}\rangle\right)/N$. $\langle n_{1}\rangle$ and
$\langle n_{N}\rangle$ correspond to the left chemical potential and the right
chemical potential, respectively, in the experiment of measuring DC
conductivity. By numerically calculating $\langle J_{1,2}\rangle$, $\langle
n_{1}\rangle$, and $\langle n_{N}\rangle$ for different $\gamma$, we obtain
Fig. 2. The $\gamma\ll t$ case (in analogy with $\gamma\ll\epsilon_{F}$ in the
continuum free fermion model), where our methods works, along with the
$\gamma\gtrsim t$ case, are both considered in the numerics. We find that the
diffusion coefficients of two cases both take on a perfect $1/\gamma$ scaling.
This not only confirms the correctness of our theory and the used
approximations, but also implies that our theory may be able to predict
qualitative properties of the considered system in an extended parameter
regime. The $1/\gamma$ scaling behavior indicates that for an infinite
measurement strength ($\gamma\rightarrow\infty$), the system will be
localized. This is a manifestation of the quantum Zeno effect Misra and
Sudarshan (1977).

Actually, those data points slightly deviate from the perfect $1/\gamma$
curve, but in the log-log plot, this deviation can hardly be seen. Comparing
with our result, this deviation should come from higher order terms and fast
varying modes.

##  VIII Discussion and conclusion

Figure 2: Numerically calculating the diffusion coefficient $D$ of a one-
dimension discrete free-fermion gas. This figure is in the log-log plot. The
red crosses are results from the numerics, and the black straight line is a
fitting curve of those numerical data points. The fitting function in the log-
log plot is a straight line, thus the diffusion coefficient $D$ has a
$1/\gamma$ scaling behavior. In addition, according to the numerical results,
the $1/\gamma$ scaling holds not only for the small $\gamma$ ($\gamma\ll t$)
case, but also for the large $\gamma$ ($\gamma\gtrsim t$) case. In this
numerics, we set $t=1$ for simplicity.

In summary, we have derived a time-local KNSM for a free-fermion gas under
continuous projective measurements. Up to the one-loop level of the effective
theory, we obtain a Drude-form conductivity which is inversely proportional to
the measurement strength $\gamma$, and this shows that the projective
measurements cause a slow-down effect on the free-fermion gas. Interestingly,
the projective measurements manifest in a form that is comparable to that of
the disorders in the framework of the Keldysh field theory. Nevertheless, the
original Lindblad master equation formalism does not explicitly show this
connection. Thus, in some sense, these two different concept, measurements and
disorders, are unified in the framework of KNSM. Note that in the disordered
fermionic system case, the weak localization effect exists in the one-loop
level due to the time-reversal symmetry Kamenev (2011); Horbach and Schön
(1993), while in our case, we do not see the weak localization effect in the
one-loop level. The comparisons are summaried in Fig. 1. Numerical tests
further confirm our theory and predictions. For thoroughly understanding the
monitored system, other transport properties, hydrodynamics, and quantum
chaoticity are also need to be considered. Our theory is a promising method to
analytically study them, and we leave these to further works.

###### Acknowledgements.

Authors thank Jing-Yuan Chen and Sebastian Diehl for helpful discussions on
the functional Keldysh field theory obtaining from Lindblad master equations,
and Jing-Yuan Chen and Yunxiang Liao for helpful discussions on the Keldysh
nonlinear sigma model in disordered fermionic systems. The work is supported
by supported by the Innovation Program for Quantum Science and Technology
(Grant No. 2021ZD0302400), the National Natural Science Foundation of China
(Grant No. 11974198).

##  Appendix A From Lindblad Master Equation to Keldysh Field Theory

In order to introduce the mapping between the Lindblad master equation and the
Keldysh field theory, we consider a trivial one-site case. The detailed
procedure can be found in Ref. Sieberer  _et al._ (2016), and here we focus
mostly on the differences: 1) We introduce a method to make the continuum
limit mathematically rigorous; 2) We show that in order to preserve the
normalization condition, one should retain the $t=t^{\prime}$ contribution in
the bare Green’s function.

The Hamiltonian of the trivial one-site model reads $H=\mu c^{\dagger}c$,
where $\mu$ is the on-site energy and can be regarded as the chemical
potential. The projective quantum jump operator is the particle number
operator $c^{\dagger}c$. Thus, the Lindblad master equation describing the
evolution under the Hamiltonian and the unconditional continuous projective
measurements can be expressed as

$\partial_{t}\rho=-i\left[H,\rho\right]+\gamma\left(c^{\dagger}c\rho
c^{\dagger}c-\frac{1}{2}\left\\{c^{\dagger}c,\rho\right\\}\right).$ (17)

This equation can be formally expressed as
$\rho_{t_{f}}=\lim_{N\rightarrow\infty}\left(1+\delta_{t}\cdot\mathcal{L}\right)^{N}\rho_{0}$,
where we have divide the time interval into $N$ slices, and $\mathcal{L}$ is
Liouvillian superoperator, which is defined as

$\mathcal{L}\left(\rho\right)=-i\left[H,\rho\right]+\gamma\left(c^{\dagger}c\rho
c^{\dagger}c-\frac{1}{2}\left\\{c^{\dagger}c,\rho\left(t\right)\right\\}\right).$
(18)

Based on the recursion equation
$\rho_{n+1}=\left(1+\delta_{t}\cdot\mathcal{L}\right)\rho_{n}$, one can get
the final state $\rho_{t_{f}}$. In order to get the path integral based on the
fermionic coherent state, we should first expand the density matrix in the
fermionic coherent basis. Thus, we have

$\rho_{n}=\int
d\bar{\psi}_{+,n}d\psi_{+,n}d\bar{\psi}_{-,n}d\psi_{-,n}e^{-\bar{\psi}_{+,n}\psi_{+,n}}e^{-\bar{\psi}_{-,n}\psi_{-,n}}\langle\psi_{+,n}|\rho_{n}|-\psi_{-,n}\rangle|\psi_{+,n}\rangle\langle-\psi_{-,n}|,$
(19)

where $|\psi\rangle$ is the fermionic coherent state, and $\psi$, $\bar{\psi}$
are independent Grassmann numbers. We also have

$\begin{split}&\quad\langle\psi_{+,n+1}|\rho_{n+1}|\psi_{-,n+1}\rangle\\\
&=\int
d\bar{\psi}_{+,n}d\psi_{+,n}d\bar{\psi}_{-,n}d\psi_{-,n}e^{\left(\bar{\psi}_{+,n+1}-\bar{\psi}_{+,n}\right)\psi_{+,n}}e^{\bar{\psi}_{-,n}\left(\psi_{-,n+1}-\psi_{-,n}\right)}\langle\psi_{+,n}|\rho_{n}|-\psi_{-,n}\rangle\\\
&\quad+\delta_{t}\int
d\bar{\psi}_{+,n}d\psi_{+,n}d\bar{\psi}_{-,n}d\psi_{-,n}e^{-\bar{\psi}_{+,n}\psi_{+,n}}e^{-\bar{\psi}_{-,n}\psi_{-,n}}\langle\psi_{+,n+1}|\mathcal{L}\left(|\psi_{+,n}\rangle\langle-\psi_{-,n}|\right)|-\psi_{-,n+1}\rangle\langle\psi_{+,n}|\rho_{n}|-\psi_{-,n}\rangle.\end{split}$
(20)

Since the Keldysh Lindblad partition function is defined as
$Z=\operatorname{tr}(\rho_{t_{f}})$, we take the trace of $\rho_{n+1}$ in the
fermionic coherent basis, and we have

$\begin{split}&\quad\operatorname{tr}(\rho_{n+1})\\\
&=\int\prod_{j=n}^{n+1}d\bar{\psi}_{+,j}d\psi_{+,j}d\bar{\psi}_{-,j}d\psi_{-,j}e^{\bar{\psi}_{-,n+1}\psi_{+,n+1}}e^{-\bar{\psi}_{+,n+1}\psi_{+,n+1}}e^{-\bar{\psi}_{-,n+1}\psi_{-,n+1}}e^{\left(\bar{\psi}_{+,n+1}-\bar{\psi}_{+,n}\right)\psi_{+,n}}e^{\bar{\psi}_{-,n}\left(\psi_{-,n+1}-\psi_{-,n}\right)}\\\
&\qquad\times\langle\psi_{+,n}|\rho_{n}|-\psi_{-,n}\rangle\\\
&\quad+\int\prod_{j=n}^{n+1}d\bar{\psi}_{+,j}d\psi_{+,j}d\bar{\psi}_{-,j}d\psi_{-,j}e^{\bar{\psi}_{-,n+1}\psi_{+,n+1}}e^{-\bar{\psi}_{+,n+1}\psi_{+,n+1}}e^{-\bar{\psi}_{-,n+1}\psi_{-,n+1}}e^{\left(\bar{\psi}_{+,n+1}-\bar{\psi}_{+,n}\right)\psi_{+,n}}e^{\bar{\psi}_{-,n}\left(\psi_{-,n+1}-\psi_{-,n}\right)}\\\
&\qquad\times\delta_{t}\left\\{-i\left[H\left(\bar{\psi}_{+,n+1},\psi_{+,n}\right)-H\left(\bar{\psi}_{-,n},\psi_{-,n-1}\right)\right]+\gamma\bar{\psi}_{+,n+1}\psi_{+,n}\bar{\psi}_{-,n}\psi_{-,n+1}{\color[rgb]{1,0,0}-\frac{1}{2}}\gamma\left(\bar{\psi}_{+,n+1}\psi_{+,n}+\bar{\psi}_{-,n}\psi_{-,n+1}\right)\right\\}\\\
&\qquad\times\langle\psi_{+,n}|\rho_{n}|-\psi_{-,n}\rangle.\end{split}$ (21)

In Ref. Sieberer  _et al._ (2016), in the continuum limit,
$\bar{\psi}_{+,n+1}\psi_{+,n}\bar{\psi}_{-,n}\psi_{-,n+1}$,
$\bar{\psi}_{+,n+1}\psi_{+,n}$, and $\bar{\psi}_{-,n}\psi_{-,n+1}$ are
directly set to $\bar{\psi}_{+}(t)\psi_{+}(t)\bar{\psi}_{-}(t)\psi_{-}(t)$,
$\bar{\psi}_{+}(t)\psi_{+}(t)$, and $\bar{\psi}_{-,n}\psi_{-,n+1}$,
respectively. Here, in order to make the continuum limit rigorous, we make
those Grassmann numbers of the dissipation part be at the time argument
following the procedure:

$\begin{split}&\quad\int
d\bar{\psi}_{+,n}d\psi_{+,n}d\bar{\psi}_{-,n}d\psi_{-,n}e^{\bar{\psi}_{-,n}\left(\psi_{-,n+1}-\psi_{-,n}\right)}\bar{\psi}_{-,n}\psi_{-,n+1}\\\
&=\int
d\bar{\psi}_{+,n}d\psi_{+,n}d\bar{\psi}_{-,n}d\psi_{-,n}e^{\bar{\psi}_{-,n}\left(\psi_{-,n+1}-\psi_{-,n}\right)}\bar{\psi}_{-,n}\left(\psi_{-,n+1}-\psi_{-,n}+\psi_{-,n}\right)\\\
&=\int
d\bar{\psi}_{+,n}d\psi_{+,n}d\psi_{-,n}d\bar{\psi}_{-,n}\left[\frac{\delta}{\delta\bar{\psi}_{-,n}}e^{\bar{\psi}_{-,n}\left(\psi_{-,n+1}-\psi_{-,n}\right)}\right]\bar{\psi}_{-,n}+\int
d\bar{\psi}_{+,n}d\psi_{+,n}d\bar{\psi}_{-,n}d\psi_{-,n}e^{\bar{\psi}_{-,n}\left(\psi_{-,n+1}-\psi_{-,n}\right)}\bar{\psi}_{-,n}\psi_{-,n}\\\
&=\int
d\bar{\psi}_{+,n}d\psi_{+,n}d\bar{\psi}_{-,n}d\psi_{-,n}e^{\bar{\psi}_{-,n}\left(\psi_{-,n+1}-\psi_{-,n}\right)}\left(\bar{\psi}_{-,n}\psi_{-,n}+1\right).\end{split}$
(22)

$\bar{\psi}_{+,n+1}\psi_{+,n}\bar{\psi}_{-,n}\psi_{-,n+1}$ and
$\bar{\psi}_{+,n+1}\psi_{+,n}$ can be treated in the same way.

Therefore, we have

$\begin{split}Z&=\frac{1}{\operatorname{tr}\left(\rho_{0}\right)}\int\prod_{j=0}^{1}d\bar{\psi}_{+,j}d\psi_{+,j}d\bar{\psi}_{-,j}d\psi_{-,j}\\\
&\times\exp\left\\{\begin{bmatrix}\bar{\psi}_{+,0}&\bar{\psi}_{+,1}&\bar{\psi}_{-,1}&\bar{\psi}_{-,0}\end{bmatrix}\begin{bmatrix}-1&0&0&-\rho\\\
h_{-}&-1&0&0\\\ 0&1&-1&0\\\
0&0&h_{+}&-1\end{bmatrix}\begin{bmatrix}\psi_{+,0}\\\ \psi_{+,1}\\\
\psi_{-,1}\\\
\psi_{-,0}\end{bmatrix}+\gamma\delta_{t}\left[\bar{\psi}_{+,0}\psi_{+,0}\bar{\psi}_{-,0}\psi_{-,0}{\color[rgb]{1,0,0}+\frac{1}{2}}\left(\bar{\psi}_{+,0}\psi_{+,0}+\bar{\psi}_{-,0}\psi_{-,0}\right)\right]\right\\},\end{split}$
(23)

where we choose $N=1$ for simplicity, $h_{\mp}=1\mp i\mu\delta_{t}$,
$\rho=\langle\psi_{+,0}|\rho_{0}|-\psi_{-,0}\rangle$, and the initial state is
chosen to be an exponential form, such as a thermal state. One finds that
after doing the treatment shown in Eq. (22), the sign before the fator $1/2$
in the dissipation term is changed (see Eq. (22) and Eq. (23)). Note that the
dissipation part (the second term of the second line in Eq. (23)) depends on
the same time argument, thus one can directly take the continuum limit and
this procedure is mathematically rigorous now. The Keldysh-Lakin-Ovchinnikov
(KLO) transformation Kamenev (2011) leads Eq. (23) to

$Z=\frac{1}{\operatorname{tr}\left(\rho_{0}\right)}\int\prod_{j=0}^{1}d\bar{\psi}_{1,j}d\psi_{1,j}d\bar{\psi}_{2,j}d\psi_{2,j}\exp\left\\{-\bar{\Psi}\left(-i\hat{G}^{-1}\right)\Psi+\gamma\delta_{t}\left[-\bar{\psi}_{1,0}\psi_{1,0}\bar{\psi}_{2,0}\psi_{2,0}+\frac{1}{2}\left(\bar{\psi}_{1,0}\psi_{2,0}+\bar{\psi}_{2,0}\psi_{1,0}\right)\right]\right\\},$
(24)

where
$\bar{\Psi}=\begin{bmatrix}\bar{\psi}_{1,0}&\bar{\psi}_{1,0}&\bar{\psi}_{2,0}&\bar{\psi}_{2,0}\end{bmatrix}$,
$\Psi=\begin{bmatrix}\psi_{1,0}&\psi_{1,0}&\psi_{2,0}&\psi_{2,0}\end{bmatrix}^{t}$,
$\psi_{a,j}$ is the Grassmann number after the KLO transformation with
$a\in\\{1,2\\}$ being the Keldysh indices and $j\in\\{0,1\\}$ being the
discrete time indices, and

$-i\hat{G}^{-1}=-\frac{1}{2}\begin{bmatrix}-\rho&-h_{+}&h_{+}&-2+\rho\\\
h_{-}&-1&-3&h_{-}\\\ h_{-}&-1&1&h_{-}\\\
-2-\rho&h_{+}&-h_{+}&\rho\end{bmatrix}.$ (25)

The bare Green’s function in the discrete time version then reads

$\begin{split}i\hat{G}&=\left(-i\hat{G}^{-1}\right)^{-1}\\\
&=\begin{bmatrix}\frac{1}{2}&0&\frac{1-\rho}{1+\rho}h_{+}&\frac{1-\rho}{1+\rho}\\\
h_{-}&\frac{1}{2}&\frac{1-\rho}{1+\rho}&\frac{1-\rho}{1+\rho}h_{-}\\\
0&0&-\frac{1}{2}&0\\\
0&0&-h_{+}&-\frac{1}{2}\end{bmatrix}+\frac{1}{2}\begin{bmatrix}0&0&0&1\\\
0&0&1&0\\\ 0&1&0&0\\\ 1&0&0&0\end{bmatrix}.\end{split}$ (26)

In the continuum limit, Eq. (24) can be expressed as

$i\hat{G}\left(t,t^{\prime}\right)=\begin{bmatrix}iG_{0}^{R}\left(t,t^{\prime}\right)&iG_{0}^{K}\left(t,t^{\prime}\right)\\\
0&iG_{0}^{A}\left(t,t^{\prime}\right)\end{bmatrix}+\frac{1}{2}\begin{bmatrix}0&1\\\
1&0\end{bmatrix}\delta_{t,t^{\prime}},$ (27)

where $\delta_{t,t^{\prime}}$ should be interpreted as the Kronecker symbol.
In the standard Keldysh field theory Kamenev (2011), people usually omit the
term proportional to $\delta_{t,t^{\prime}}$ in Eq. (27), and only keep the
first term of Eq. (27). In order to check the normalization condition $Z=1$,
one can expand Eq. (24) in powers of $\gamma$, and treat each order with the
help of Wick’s theorem. In our problem here, one will find that this
$\delta_{t,t^{\prime}}$ term has to be kept so as to preserve the
normalization, as one will encounter the equal-time correlation:
$\langle\psi_{2}(t)\bar{\psi}_{1}(t)\rangle$.

Generalizing to the model considered in the main text, one can obtain the
Keldysh Lindblad partition function Eq. (3) of the main text.

##  Appendix B Keldysh Treatment of Disordered Fermionic systems and
Comparison with Our Problem

The Keldysh treatment of the disordered fermionic system can be found in Ref.
Horbach and Schön (1993); Kamenev (2011), and here we just quote some
discussions connected with our problem.

In the traditional studying of the disordered fermionic system or the weak
localization effect, one usually assume a static and spatial-dependent
disorder potential $V_{dis}(\mathbf{x})$ through the disorder action

$S_{dis}[V_{dis}]=\int
dx\,V_{dis}(\mathbf{x})\,\bar{\psi}_{a}(x)\hat{\tau}_{0}^{ab}\psi_{b}(x),$
(28)

where the configuration of $V_{dis}(\mathbf{x})$ satisfies the Gaussian
distribution and thus the disorder averaging takes the form

$\langle\cdots\rangle_{dis}=\int\mathcal{D}[V_{dis}]\exp\left\\{-\pi\nu\tau_{el}\int
d\mathbf{x}\,V_{dis}^{2}(\mathbf{x})\right\\}\cdots,$ (29)

where $\tau_{el}$ is the elastic scattering time. Performing the disorder
averaging for $\exp(iS_{dis})$, one can get

$\begin{split}\langle
e^{iS_{dis}}\rangle_{dis}&=\int\mathcal{D}[V_{dis}]\exp\left\\{-\int
d\mathbf{x}\,\pi\nu\tau_{el}V_{dis}^{2}(\mathbf{x})+iV_{dis}(\mathbf{x})\int
dt\;\bar{\psi}_{a}(\mathbf{x},t)\hat{\tau}_{0}^{ab}\psi_{b}(\mathbf{x},t)\right\\},\\\
&=\exp\left\\{-\frac{1}{4\pi\nu\tau_{el}}\int d\mathbf{x}\int
dtdt^{\prime}\;\bar{\psi}_{a}(\mathbf{x},t)\psi_{a}(\mathbf{x},t)\bar{\psi}_{b}(\mathbf{x},t^{\prime})\psi_{b}(\mathbf{x},t^{\prime})\right\\}.\end{split}$
(30)

And then, the partition function after disorder averaging reads

$Z=\int\mathcal{D}[\psi]\exp\left\\{iS_{0}-\frac{1}{4\pi\nu\tau_{el}}\int
d\mathbf{x}\int
dtdt^{\prime}\;\bar{\psi}_{a}(\mathbf{x},t)\psi_{a}(\mathbf{x},t)\bar{\psi}_{b}(\mathbf{x},t^{\prime})\psi_{b}(\mathbf{x},t^{\prime})\right\\},$
(31)

where $S_{0}$ is the free-fermion action. Note that the disorder averaging
introduce a four-fermion term into the action.

For convenience, we also put the Keldysh Lindblad partition function of our
problem here:

$Z=\int\\!\mathcal{D}\left[\psi\right]\exp\left\\{iS_{0}-\frac{\gamma}{2}\int
d\mathbf{x}dt\boldsymbol{[}\bar{\psi}_{a}\left(\mathbf{x},t\right)\psi_{a}\left(\mathbf{x},t\right)\bar{\psi}_{b}\left(\mathbf{x},t\right)\psi_{b}\left(\mathbf{x},t\right)-\bar{\psi}_{a}\left(\mathbf{x},t\right)\hat{\tau}_{1}^{ab}\psi_{b}\left(\mathbf{x},t\right)\boldsymbol{]}\right\\}.$
(32)

Comparing these two equations, Eq. (31) and Eq. (32), one can observe that the
two four-fermion terms are in a similar form. Thus, in some sense, these two
different problems are unified in the framework of the functional Keldysh
field theory. Here, we emphasize again that such a similarity is not obvious
in the master equation formalism, and can only be found when one resorts to
the Keldysh path integral formalism (see Fig. 2 in the main text).

Figure 3: Scattering of an electron along two time-reversed paths in the
disordered fermionic systems.

In the disordered fermionic systems, the time-reversal symmetry (TRS) is
present, thus the remarkable weak localization exists. A rudimentary
conceptual understanding of the weak localization is that it results from the
constructive interference of two time-reversed paths of an electron Coleman
(2015). Consider the amplitude of an electron to return to its starting point.
In general, it will encounter a sequence of scattering sites (see Fig. 3),
which are manifestations of disorders. For each path $p$, there is a time-
reversed path $\tilde{p}$ when the system is time-reversal symmetric.
Amplitudes of the electron around $p$ and $\tilde{p}$ are the same, while for
other paths, phases should be random. Therefore, the electron will have a
quantum mechanically enhanced probability of returning to its starting point
due to the time-reversal symmetry. From this argument, we know that the time-
reversal symmetry is significant to the weak localization in the disordered
case. Theoretically, the time-reversal symmetry will result in another set of
soft modes, known as Cooperons Horbach and Schön (1993); Altland and Simons
(2010); Kamenev (2011), in the effective theory—Keldysh nonlinear sigma model.
Those Cooperon modes will provide an infrared divergent correction to the DC
conductivity, and then imply a localization transition from the metallic
phase. If the system do not have time-reversal symmetry, the constructive
interference of two time-reversed paths does not exist, and thus the weak
localization disappears. Theoretically, the Cooperon modes disappear due to
the lack of TRS, and only diffuson modes contribute to the transport
properties. As a consequence, the DC conductivity will present in the Drude
form without divergent corrections.

In the measurement case or the dephasing system, the time-reversal symmetry is
obviously absent. Thus the soft modes analogous to Cooperons in the disordered
systems do not exist in the measurement case or the dephasing case. By this
comparison, we know that diffusons are the only dominant excitations or soft
modes in the Keldysh nonlinear sigma model, and there will not be localization
for weak measurement strength ($\gamma\ll\epsilon_{F}$). In Sec. VII of the
main text, we provide a numerical example to support our theory and verify our
predictions. From the numerics (see Fig. 3), we find that for all finite
measurement strengths, the weak localization does not exist. And for large
$\gamma$, the scaling of the diffusion coefficient (and thus the conductivity)
is also $1/\gamma$. The scaling behavior implies that for an infinite
measurement strength, the system will be localized. However, this is a
manifestation of the quantum Zeno effect instead of the weak localization. As
the measurement strength $\gamma$ can be regarded as the number of measurement
invents in a unit time interval ($\gamma\sim 1/\tau$ with $\tau$ being the
duration of one-shot measurement), $\gamma\rightarrow\infty$ means that the
system is measured all the time. In this sense, $\gamma\rightarrow\infty$
corresponds to the quantum Zeno limit.

##  Appendix C Bosonic Effective Theory and the Keldysh Nonlinear Sigma Model

###  C.1 Bosonic Effective Theory

Following the procedure introduced in Sec. A, one can get the Keldsyh Lindblad
partition function for our problem, that is Eq. (3) in the main text. For the
four-fermion term in the dissipation part, we introduce an auxiliary time-
local bosonic field $\hat{Q}$ to decouple it with the help of the identity

$\begin{split}\hat{1}&=\int\mathcal{D}\left[\hat{Q}\right]\exp\left[-\frac{\gamma}{2}\left(\pi\nu\right)^{2}\operatorname{tr}\left(\hat{Q}^{2}\right)\right]\\\
&=\int\mathcal{D}\left[\hat{Q}\right]\exp\left[-\frac{\gamma}{2}\left(\pi\nu\right)^{2}\int
dx\;\hat{Q}^{ab}\left(x\right)\hat{Q}^{ba}\left(x\right)\right].\end{split}$
(33)

The definition of $\hat{Q}$ is similar with the definition of an operator in
quantum mechanics. In quantum mechanics, an operator $\hat{\mathcal{O}}$ in
the position basis can be expressed as $\hat{\mathcal{O}}=\int
d\mathbf{x_{1}}d\mathbf{x_{2}}\hat{\mathcal{O}}(\mathbf{x}_{1},\mathbf{x}_{2})|\mathbf{x}_{1}\rangle\langle\mathbf{x}_{2}|$,
and $\hat{\mathcal{O}}(\mathbf{x}_{1},\mathbf{x}_{2})$ is the matrix element
of $\hat{\mathcal{O}}$. If $\hat{\mathcal{O}}$ is diagonal in the position
basis, then $\hat{\mathcal{O}}$ reduces to $\hat{\mathcal{O}}=\int
d\mathbf{x}\hat{\mathcal{O}}(\mathbf{x})|\mathbf{x}\rangle\langle\mathbf{x}|$.
More often, the matrix element
$\hat{\mathcal{O}}(\mathbf{x}_{1},\mathbf{x}_{2})$ is just a number. However,
one can always generalize it to the case that the matrix element is also a
matrix. Such a generalization is widely used in quantum field theories and
tensor network methods. In our work, the definition of $\hat{Q}$ is exactly
such a generalization. The non-zero matrix element of $\hat{Q}$ which is
diagonal in the position basis, can be expressed as

$\hat{Q}(x)=\left[\begin{array}[]{ll}Q^{11}(x)&Q^{12}(x)\\\
Q^{21}(x)&Q^{22}(x)\end{array}\right].$ (34)

After using this definition, the trace over $\hat{Q}$ becomes the trace over
both the Keldysh space and the spacetime basis. For example,
$\operatorname{tr}\left(\hat{Q}^{2}\right)$ in Eq. (33) is defined as

$\begin{split}\operatorname{tr}\left(\hat{Q}^{2}\right)&=\operatorname{tr}_{K}\left[\int
dx\langle x|\int dx_{1}dx_{2}\hat{Q}(x_{1})|x_{1}\rangle\langle
x_{1}|\cdot\hat{Q}(x_{2})|x_{2}\rangle\langle x_{2}|x\rangle\right]\\\
&=\operatorname{tr}_{K}\left[\int dx\langle x|\int
dx_{1}\hat{Q}^{2}(x_{1})|x_{1}\rangle\langle x_{1}|x\rangle\right]\\\
&=\operatorname{tr}_{K}\left[\int dx\hat{Q}^{2}(x)\right]\\\ &=\int
dx\hat{Q}^{ab}(x)\hat{Q}^{ba}(x),\end{split}$ (35)

where $\operatorname{tr}_{K}$ stands for the trace over the Keldysh space,
$a,b\in\\{1,2\\}$ are Keldysh indices and repeated indices imply summation.

After introducing the auxiliary fields $\hat{Q}$, one arrives at

$\begin{split}Z&=\int\mathcal{D}\left[\hat{Q}\right]\mathcal{D}\left[\psi\right]\exp\left\\{iS_{0}-\frac{\gamma}{2}\left(\pi\nu\right)^{2}\operatorname{tr}\left(\hat{Q}^{2}\right)-\gamma\int
dx\left[\pi\nu\bar{\psi}_{a}\left(x\right)\hat{Q}^{ab}\left(x\right)\psi_{b}\left(x\right)-\frac{1}{2}\bar{\psi}_{a}\left(x\right)\hat{\tau}_{1}^{ab}\psi_{b}\left(x\right)\right]\right\\}.\end{split}$
(36)

Using the Gaussian integration, one arrives at the effective bosonic theory
depending only on $\hat{Q}$:

$Z=\int\mathcal{D}\left[\hat{Q}^{\prime}\right]\exp\left\\{-\frac{\gamma}{2}\left(\pi\nu\right)^{2}\operatorname{tr}\left[\left(\hat{Q}^{\prime}+\frac{1}{2\pi\nu}\hat{\tau}_{1}\right)^{2}\right]+\operatorname{tr}\ln\left[-i\hat{G}^{-1}+\gamma\pi\nu\hat{Q}^{\prime}\right]\right\\},$
(37)

where we have let $\hat{Q}^{\prime}=\hat{Q}-\frac{1}{2\pi\nu}\hat{\tau}_{1}$,
and $\hat{Q}^{\prime}$ is still Hermitian. In the following, we will relabel
$\hat{Q^{\prime}}$ as $\hat{Q}$ again. For higher orders ($\geq 2$) of the
expansion in powers of $\gamma$, we can replace $\hat{G}$ with $\hat{G}_{0}$
(the first term in Eq. (27)) due to the fact that the $t=t^{\prime}$ line is
only a manifold of measure zero Kamenev (2011). Then, one gets the Keldysh
Lindblad Partition function shown in Eq. (5) of the main text:

$Z=\int\mathcal{D}\left[\hat{Q}\right]\exp\left\\{-\frac{\gamma}{2}\left(\pi\nu\right)^{2}\operatorname{tr}\left[\hat{Q}^{2}+\left(\frac{1}{2\pi\nu}\hat{\tau}_{1}\right)^{2}\right]+\operatorname{tr}\ln\left[-i\hat{G}^{-1}_{0}+\gamma\pi\nu\hat{Q}\right]\right\\}.$
(38)

###  C.2 Time-Local Keldysh Nonlinear Sigma Model

Taking the variation over $\hat{Q}(x)$, one gets the saddle point equation of
the action in Eq. (38), and one can check that the constant configuration
$\hat{\Lambda}=\frac{1}{2\pi\nu}\hat{\tau}_{3}$ satisfies the saddle point
equation. For large-scale physics, we just focus on the massless fluctuation,
which can be generated by
$\hat{Q}(x)=\hat{\mathcal{R}}^{-1}(x)\hat{\Lambda}\hat{\mathcal{R}}(x)$. Note
that now $\hat{Q}(x)$ is constrained by
$\hat{Q}^{2}(x)=(\frac{1}{2\pi\nu})^{2}\hat{\tau}_{0}$. And then one finds
that only the $\operatorname{tr}\ln$ term in Eq. (38) will contribute to the
dynamics, while other terms only contribute some constants. Thus, in the
following, we can just focus on the $\operatorname{tr}\ln$ term.

Note that the bare Green’s function $\hat{G}_{0}$ can be expressed as
$\hat{G}_{0}=\hat{\mathcal{U}}^{-1}\hat{G}_{0d}\,\hat{\mathcal{U}}$, where

$\begin{split}&\hat{\mathcal{U}}^{-1}=\hat{\mathcal{U}}=\sum_{\epsilon}\begin{bmatrix}1&F_{\epsilon}\\\
0&-1\end{bmatrix}|\epsilon\rangle\langle\epsilon|,\\\
&\hat{G}_{0d}=\sum_{\mathbf{k},\epsilon}\begin{bmatrix}G_{0}^{R}(\mathbf{k},\epsilon)&0\\\
0&G_{0}^{A}(\mathbf{k},\epsilon)\end{bmatrix}|\mathbf{k},\epsilon\rangle\langle\mathbf{k},\epsilon|,\end{split}$
(39)

and $F_{\epsilon}=1-2n_{F}(\epsilon)$ with $n_{F}(\epsilon)$ being the Fermi-
Dirac distribution function. Thus, the statistical information is actually
encoded in the matrix $\hat{\mathcal{U}}$. The statistical distribution in
$\hat{G}_{0}$ comes from the initial thermal state
$\rho_{0}=\exp[-\beta\sum_{\mathbf{k}}c_{\mathbf{k}}^{\dagger}(\epsilon_{\mathbf{k}}-\epsilon_{F})c_{\mathbf{k}}]$.
We would like to obtain an effective theory depending only on $\hat{Q}$ to
describe the physics of our problem. To this end, we first make a similarity
transformation to encode the statistical information in $\hat{Q}$ instead.
Note that due to the cyclic property of the trace operation, this similarity
does not change the theory. And then the $\operatorname{tr}\ln$ term in Eq.
(38) now becomes
$\operatorname{tr}\ln\left[-i\hat{G}^{-1}_{0d}+(\gamma/2)\hat{Q}\right]$,
where $\hat{Q}$ is redefined as
$\hat{Q}=\hat{\mathcal{U}}^{-1}\hat{\mathcal{R}}^{-1}\hat{\tau}_{3}\hat{\mathcal{R}}\hat{\mathcal{U}}$,
and in the spacetime basis,
$\hat{G}_{0d}^{-1}=i\partial_{t}+\frac{\nabla^{2}}{2m}+\epsilon_{F}+i0\hat{\tau}_{3}$.
Therefore, we have

$\begin{split}iS\left[\hat{Q}\right]&=\operatorname{tr}\ln\left[-i\hat{G}_{0d}^{-1}+(\gamma/2)\hat{\mathcal{U}}^{-1}\hat{\mathcal{R}}^{-1}\hat{\Lambda}\hat{\mathcal{R}}\hat{\mathcal{U}}\right]\\\
&=\operatorname{tr}\ln\left\\{\left[-i\hat{\mathcal{R}}\left(i\partial_{t}+\frac{\nabla^{2}}{2m}+\epsilon_{F}\right)\hat{\mathcal{R}}^{-1}-i\hat{\mathcal{U}}^{-1}i0\hat{\tau}_{3}\hat{\mathcal{U}}\right]+\frac{\gamma}{2}\hat{\tau}_{3}\right\\}\\\
&\approx\operatorname{tr}\ln\left[\hat{\mathcal{G}}^{-1}+i\hat{\mathcal{U}}^{-1}\hat{\mathcal{R}}\left(\partial_{t}\hat{\mathcal{R}}^{-1}\right)\hat{\mathcal{U}}+i\hat{\mathcal{U}}^{-1}\hat{\mathcal{R}}\left(\mathbf{v}_{F}\cdot\mathbf{\nabla}\hat{\mathcal{R}}^{-1}\right)\hat{\mathcal{U}}\right],\end{split}$
(40)

where
$\hat{\mathcal{G}}^{-1}=i\partial_{t}+\frac{\nabla^{2}}{2m}+\epsilon_{F}+i\frac{\gamma}{2}\hat{\mathcal{U}}\hat{\tau}_{3}\hat{\mathcal{U}}$,
and $\mathbf{v}_{F}\cdot\nabla$ comes from the linearization of the dispersion
relation near the Fermi energy:
$\mathbf{k}^{2}/(2m)-\epsilon_{F}\approx\mathbf{v}_{F}\cdot\mathbf{k}\rightarrow-i\mathbf{v}_{F}\cdot\mathbf{k}$
Horbach and Schön (1993); Kamenev (2011). Note that the saddle point
configuration $\propto\hat{\tau}_{3}$ plays the role of the self-energy. In
the energy-momentum basis, we have

$\hat{\mathcal{G}}(\mathbf{k},\epsilon)=\hat{\mathcal{U}}_{\epsilon}\begin{bmatrix}\frac{1}{\epsilon-\xi_{\mathbf{k}}+i\gamma/2}&0\\\
0&\frac{1}{\epsilon-\xi_{\mathbf{k}}-i\gamma/2}\end{bmatrix}\hat{\mathcal{U}}_{\epsilon},$
(41)

where $\xi_{\mathbf{k}}=\mathbf{k}^{2}/(2m)-\epsilon_{F}$. Expanding the
$\operatorname{tr}\ln$ term in powers of $\partial_{t}\hat{\mathcal{R}}^{-1}$
and $\nabla\hat{\mathcal{R}}^{-1}$ (similar with the Taylor expansion of the
function $\ln(1+x)$), one will arrive at the time-local Keldysh nonlinear
sigma model

$iS\left[\hat{Q}\right]=\pi\nu\operatorname{tr}\left[\partial_{t}\hat{Q}\right]-\frac{1}{4}\pi\nu
D\operatorname{tr}\left[\left(\nabla\hat{Q}\right)^{2}\right],$ (42)

where
$\partial_{t}\hat{Q}\equiv\partial_{t}(\hat{\mathcal{U}}\hat{\mathcal{R}}^{-1})\hat{\tau}_{3}\hat{\mathcal{R}}\hat{\mathcal{U}}$.
The linear order of the spatial gradient is zero due to the angular
integration. A similar calculation can be found in Chapter 11 of Ref. Kamenev
(2011). As our auxiliary field $\hat{Q}$ only depends on one time argument,
while in the disordered fermionic case, the auxiliary field depends on two
time variables, here we term our Keldysh nonlinear sigma model as the time-
local KNSM to distinguish from the KNSM in the disordered fermionic case. The
Keldysh nonlinear sigma model in the presence of the vector potential can be
derived from those similar calculations.

## References

  * Nielsen and Chuang (2004) M. A. Nielsen and I. L. Chuang,  _Quantum computation and quantum information_ , 1st ed. (Cambridge University Press, 2004).
  * Laflorencie (2016) N. Laflorencie, Physics Reports 646, 1 (2016).
  * Calabrese and Cardy (2004) P. Calabrese and J. Cardy, Journal of statistical mechanics: theory and experiment 2004, P06002 (2004).
  * Ryu and Takayanagi (2006) S. Ryu and T. Takayanagi, Phys. Rev. Lett. 96, 181602 (2006).
  * Deutsch (1991) J. M. Deutsch, Phys. Rev. A 43, 2046 (1991).
  * Srednicki (1994) M. Srednicki, Phys. Rev. E 50, 888 (1994).
  * Fleishman and Anderson (1980) L. Fleishman and P. W. Anderson, Phys. Rev. B 21, 2366 (1980).
  * Gornyi  _et al._ (2005) I. V. Gornyi, A. D. Mirlin, and D. G. Polyakov, Phys. Rev. Lett. 95, 206603 (2005).
  * Basko  _et al._ (2006) D. M. Basko, I. L. Aleiner, and B. L. Altshuler, Annals of Physics 321, 1126 (2006).
  * Oganesyan and Huse (2007) V. Oganesyan and D. A. Huse, Phys. Rev. B 75, 155111 (2007).
  * Kjäll  _et al._ (2014) J. A. Kjäll, J. H. Bardarson, and F. Pollmann, Phys. Rev. Lett. 113, 107204 (2014).
  * Vosk  _et al._ (2015) R. Vosk, D. A. Huse, and E. Altman, Phys. Rev. X 5, 031032 (2015).
  * Pal and Huse (2010) A. Pal and D. A. Huse, Phys. Rev. B 82, 174411 (2010).
  * Bauer and Nayak (2013) B. Bauer and C. Nayak, Journal of Statistical Mechanics: Theory and Experiment 2013, P09005 (2013).
  * Luitz  _et al._ (2015) D. J. Luitz, N. Laflorencie, and F. Alet, Phys. Rev. B 91, 081103(R) (2015).
  * Schreiber  _et al._ (2015) M. Schreiber, S. S. Hodgman, P. Bordia, H. P. Lüschen, M. H. Fischer, R. Vosk, E. Altman, U. Schneider, and I. Bloch, Science 349, 842 (2015).
  * Khemani  _et al._ (2017) V. Khemani, S. P. Lim, D. N. Sheng, and D. A. Huse, Phys. Rev. X 7, 021013 (2017).
  * Abanin  _et al._ (2019) D. A. Abanin, E. Altman, I. Bloch, and M. Serbyn, Rev. Mod. Phys. 91, 021001 (2019).
  * Nahum  _et al._ (2017) A. Nahum, J. Ruhman, S. Vijay, and J. Haah, Phys. Rev. X 7, 031016 (2017).
  * Li  _et al._ (2018) Y. Li, X. Chen, and M. P. A. Fisher, Phys. Rev. B 98, 205136 (2018).
  * Li  _et al._ (2019) Y. Li, X. Chen, and M. P. A. Fisher, Phys. Rev. B 100, 134306 (2019).
  * Skinner  _et al._ (2019) B. Skinner, J. Ruhman, and A. Nahum, Phys. Rev. X 9, 031009 (2019).
  * Gullans and Huse (2020) M. J. Gullans and D. A. Huse, Phys. Rev. X 10, 041020 (2020).
  * Jian  _et al._ (2020) C.-M. Jian, Y.-Z. You, R. Vasseur, and A. W. W. Ludwig, Phys. Rev. B 101, 104302 (2020).
  * Choi  _et al._ (2020) S. Choi, Y. Bao, X.-L. Qi, and E. Altman, Phys. Rev. Lett. 125, 030505 (2020).
  * Szyniszewski  _et al._ (2020) M. Szyniszewski, A. Romito, and H. Schomerus, Phys. Rev. Lett. 125, 210602 (2020).
  * Agrawal  _et al._ (2022) U. Agrawal, A. Zabalo, K. Chen, J. H. Wilson, A. C. Potter, J. H. Pixley, S. Gopalakrishnan, and R. Vasseur, Phys. Rev. X 12, 041002 (2022).
  * Cao  _et al._ (2019) X. Cao, A. Tilloy, and A. D. Luca, SciPost Phys. 7, 24 (2019).
  * Fuji and Ashida (2020) Y. Fuji and Y. Ashida, Phys. Rev. B 102, 054302 (2020).
  * Alberton  _et al._ (2021) O. Alberton, M. Buchhold, and S. Diehl, Phys. Rev. Lett. 126, 170602 (2021).
  * Maimbourg  _et al._ (2021) T. Maimbourg, D. M. Basko, M. Holzmann, and A. Rosso, Phys. Rev. Lett. 126, 120603 (2021).
  * Chen  _et al._ (2020) X. Chen, Y. Li, M. P. A. Fisher, and A. Lucas, Phys. Rev. Research 2, 033017 (2020).
  * Goto and Danshita (2020) S. Goto and I. Danshita, Phys. Rev. A 102, 033316 (2020).
  * Doggen  _et al._ (2022) E. V. H. Doggen, Y. Gefen, I. V. Gornyi, A. D. Mirlin, and D. G. Polyakov, Phys. Rev. Research 4, 023146 (2022).
  * Basko  _et al._ (2007) D. M. Basko, I. L. Aleiner, and B. L. Altshuler, Phys. Rev. B 76, 052203 (2007).
  * Gopalakrishnan  _et al._ (2015) S. Gopalakrishnan, M. Müller, V. Khemani, M. Knap, E. Demler, and D. A. Huse, Phys. Rev. B 92, 104202 (2015).
  * Nandkishore and Huse (2015) R. Nandkishore and D. A. Huse, Annual Review of Condensed Matter Physics 6, 15 (2015).
  * Potter  _et al._ (2015) A. C. Potter, R. Vasseur, and S. A. Parameswaran, Phys. Rev. X 5, 031033 (2015).
  * Jacobs and Steck (2006) K. Jacobs and D. A. Steck, Contemporary Physics 47, 279 (2006).
  * Breuer  _et al._ (2002) H.-P. Breuer, F. Petruccione, _et al._ ,  _The theory of open quantum systems_ (Oxford University Press, New York, US, 2002).
  * Lindblad (1975) G. Lindblad, Communications in Mathematical Physics 40, 147 (1975).
  * Sieberer  _et al._ (2016) L. M. Sieberer, M. Buchhold, and S. Diehl, Reports on Progress in Physics 79, 096001 (2016).
  * Kamenev (2011) A. Kamenev,  _Field Theory of Non-Equilibrium Systems_ (Cambridge University Press, 2011).
  * Kamenev and Andreev (1999) A. Kamenev and A. Andreev, Physical Review B 60, 2218 (1999).
  * Horbach and Schön (1993) M. L. Horbach and G. Schön, Annalen der Physik 505, 51 (1993).
  * Liao and Galitski (2018) Y. Liao and V. Galitski, Phys. Rev. B 98, 205124 (2018).
  * Žnidarič (2010a) M. Žnidarič, Journal of Statistical Mechanics: Theory and Experiment 2010, L05002 (2010a).
  * Žnidarič (2010b) M. Žnidarič, New Journal of Physics 12, 043001 (2010b).
  * Turkeshi and Schiró (2021) X. Turkeshi and M. Schiró, Physical Review B 104, 144301 (2021).
  * Jin  _et al._ (2022) T. Jin, J. a. S. Ferreira, M. Filippone, and T. Giamarchi, Phys. Rev. Research 4, 013109 (2022).
  * Jin  _et al._ (2023) T. Jin, J. a. Ferreira, M. Bauer, M. Filippone, and T. Giamarchi, Phys. Rev. Res. 5, 013033 (2023).
  * Altland and Simons (2010) A. Altland and B. D. Simons,  _Condensed Matter Field Theory_, 2nd ed. (Cambridge University Press, 2010).
  * Yang  _et al._ (2021) Q. Yang, Z. Yang, and D. E. Liu, Phys. Rev. B 104, 014512 (2021).
  * Finkel’shtein (1983) A. M. Finkel’shtein, Soviet Journal of Experimental and Theoretical Physics 57, 97 (1983).
  * Finkel’Stein (1984) A. Finkel’Stein, Zeitschrift für Physik B Condensed Matter 56, 189 (1984).
  * Patel  _et al._ (2017) A. A. Patel, D. Chowdhury, S. Sachdev, and B. Swingle, Phys. Rev. X 7, 031047 (2017).
  * Buchhold  _et al._ (2021) M. Buchhold, Y. Minoguchi, A. Altland, and S. Diehl, Phys. Rev. X 11, 041004 (2021).
  * Misra and Sudarshan (1977) B. Misra and E. G. Sudarshan, Journal of Mathematical Physics 18, 756 (1977).
  * Coleman (2015) P. Coleman,  _Introduction to Many-Body Physics_ (Cambridge University Press, 2015).


11institutetext: School of Computing and Information Technology, University of
Wollongong, Wollongong, Australia
11email<EMAIL_ADDRESS>{fren<EMAIL_ADDRESS>
# Distributed Interaction Graph Construction for Dynamic DCOPs in Cooperative
Multi-agent Systems

Brighter Agyemang  Fenghui Ren  Jun Yan

###### Abstract

DCOP algorithms usually rely on interaction graphs to operate. In open and
dynamic environments, such methods need to address how this interaction graph
is generated and maintained among agents. Existing methods require
reconstructing the entire graph upon detecting changes in the environment or
assuming that new agents know potential neighbors to facilitate connection. We
propose a novel distributed interaction graph construction algorithm to
address this problem. The proposed method does not assume a predefined
constraint graph and stabilizes after disruptive changes in the environment.
We evaluate our approach by pairing it with existing DCOP algorithms to solve
several generated dynamic problems. The experiment results show that the
proposed algorithm effectively constructs and maintains a stable multi-agent
interaction graph for open and dynamic environments.

###### Keywords:

DCOP D-DCOP Multi-agent Systems Multi-agent Coordination.

##  1 Introduction

The complexities of computational problems in our world today make it
increasingly appealing to, where possible, address such problems using
collaborative autonomous agents. To this end, the domain of multi-agent
collaboration has been studied from different perspectives in recent years.
Some interesting application domains include power systems, mobile sensing
[1], disaster management [2], environment monitoring [3, 4], and traffic light
management [5].

In several of these application domains, the environment is dynamic [6], and
the interactions between the agents evolve over the problem horizon. Thus,
predefined interaction structures may not be useful. It is then significant to
address how the agents interact in a dynamic environment to facilitate the
application of algorithms that leverage such agent structures. In [7], this is
referred to as the Dynamic Distributed Multi-agent Hierarchy Generation
((DynDisMHG)) problem. There exist other works in the literature with similar
motivations [8, 9, 10, 11]. Multi-agent hierarchies enable the application of
certain Distributed Constraint Optimization Problem (DCOP) proposals for
multi-agent collaboration. Additionally, multi-agent hierarchies have
applications in mobile sensing agents and mobile ad-hoc networks.

One common assumption among existing approaches is that there is an expected
interaction graph to enable the generation of the multi-agent hierarchy. In
open and dynamic environments such as a multi-agent rescue system or a Mobile
Sensor Team (MST), an agent’s interactions can vary over time, and it may be
introduced or removed from the environment at arbitrary periods [1].
Therefore, the agents will have to be equipped to generate and maintain the
multi-agent hierarchy collaboratively.

In this study, we discuss the Ad-hoc Distributed Multi-agent Hierarchy
generation problem as an extension of the (DynDisMHG) problem and propose an
algorithm for this class of problems in Multi-Agent Systems (MASs). We focus
on applying our approach in the DCOP domain and show the proposed method’s
effectiveness via experiments. The proposed method has application in areas
such as DCOP_MSTs [12, 1] where agent positions or environment may change and
agent interactions have to be defined to enable the use of DCOP methods.

In what follows, we discuss related work in Section 2. Section 3 introduces
the background and problem formulation of this study. Section 4 discusses our
proposed approach. In Section 5, we first introduce the experiment setup and
then discuss the results. We draw our conclusions in Section 6.

##  2 Related Work

A well-known study in D-DCOP is the work in [13] where a Distributed DFS
(DDFS) algorithm was proposed for ordering variables (or agents) in a
Distributed Constraint Satisfaction Problem (DCSP). For each agent, DDFS
classifies a known neighbor list, retrieved from a predefined constraint
graph, into parent and children. In an open and dynamic environment where the
constraint graph changes, DDFS recomputes the interaction graph from scratch
[8].

The DDFS algorithm has been used in many notable D-DCOP algorithms. The work
in [8] proposed HARP for detecting agents affected by constraint changes and
then invokes DDFS to reconstruct the hierarchy. Other DFS proposals exist [14]
and have been used with algorithms in the DCOP domain [9, 15]. DDFS algorithms
generate the hierarchy from scratch with every change, which unnecessarily
causes unaffected parts of the hierarchy to be reconstructed.

Also, [7] proposed Mobed for maintaining multi-agent hierarchies. The proposed
algorithm ensures that an insertion point is unique for a joining agent and
that the resulting tree is valid, a concept we adopt in our proposal. Mobed
requires an expected interaction graph and an initial multi-agent hierarchy.

In summary, DDFS algorithms require a restart upon a change to generate valid
multi-agent hierarchies, whereas methods like Mobed and HARP are hierarchy
maintenance methods. The restart is necessary since the ordering heuristic may
be inconsistent with the hierarchy after a change, and there is no procedure
for introducing a new agent. Also, the methods mentioned above assume the
existence of an interaction graph applicable across the problem horizon. On
the other hand, we consider an ad-hoc multi-agent hierarchy generation problem
and propose a valid hierarchy generation and maintenance method.

##  3 Problem Formulation And Background

###  3.1 Problem Formulation

We extend the formulation in [7] to the domain where no fixed interaction
graph is guaranteed to be consistent across the horizon of the MAS. Let
$A_{t}$ be an ordered set of agents in a multi-agent system at time $t$ that
gives rise to an unordered, labeled, rooted tree. We call the tree
$T=\left<A,\pi:A\rightarrow A\right>$ a multi-agent hierarchy. $\pi$ is a
function that, given an agent $a_{j}\in A$, specifies the parent of $a_{j}$
already in the hierarchy. The neighbor set of $a_{j}$ is denoted as $N_{j}$.
We denote the children set of $a_{j}$ as $C_{j}\subseteq N_{j}$. The hierarchy
is valid if, after adding or removing agent $a_{i}$ to the hierarchy, it
continues to be acyclic after a finite number of steps. Such a hierarchy
enables agents in disjoint parts of the tree to execute in parallel.

###  3.2 Dynamic DCOP

We consider the operation of the ad-hoc multi-agent hierarchy in a dynamic
DCOP context. In multi-agent systems formulated as DCOPs, agents assign values
from a domain to their decision variables to optimize certain constraint
functions. It is assumed that the agents are fully cooperative and can fully
observe the environment [16, 17]. Also, the environment is static and
deterministic. The DCOP is modeled as a tuple
$P=\left<\mathbf{A},\mathbf{X},\mathbf{D},\mathbf{F},\alpha\right>$, where:

  * •

$\mathbf{A}=\left\\{a_{1},a_{2},...,a_{m}\right\\}$ is a finite set of agents,

  * •

$\mathbf{X}=\left\\{x_{1},x_{2},...,x_{n}\right\\}$ is a finite set of
variables,

  * •

$\mathbf{D}=\left\\{D_{1},D_{2},...,D_{n}\right\\}$ is a set of variable
domains such that, the domain of $x_{i}\in\mathbf{X}$ is $D_{i}$,

  * •

$\mathbf{F}=\left\\{f_{1},f_{2},...,f_{K}\right\\}$ is a set of constraint
functions defined on $\mathbf{X}$ where each $f_{k}\in\mathbf{F}$ is defined
over a subset
$\mathcal{X}_{k}=\left\\{x^{k}_{1},x^{k}_{2},...,x^{k}_{p}\right\\}$, with
$p\leq n$, determines the cost of value assignments of the variables in
$\mathcal{X}_{k}$ as $f_{k}:D_{1}\times D_{2}\times...\times
D_{p}\rightarrow\mathbb{R}\cup\\{\perp\\}$. Here, the cardinality of
$\mathcal{X}_{k}$ is the arity of $f_{k}$. The total cost of the values
assigned to variables in $\mathbf{X}$ is
$\mathbf{F}_{g}(\mathbf{X})=\sum_{k=1}^{K}f_{k}(\mathcal{X}_{k})$,

  * •

$\alpha:\mathbf{X}\rightarrow\mathbf{A}$ is an onto function that assigns the
control of a variable $x\in\mathbf{X}$ to an agent $\alpha(x)$.

We assume that $\alpha$ assigns only one variable per agent111Each variable
could be represented as an aggregation of sub-variables where its domain
constitutes the cartesian product of the domains of all the sub-variables. We
use agent and variable interchangeably since an agent controls only one
variable. and the use of binary constraint functions. A Current Partial
Assignment (CPA) or partial assignment is the assignment of values to a set of
variables $\overline{x}$ such that $\overline{x}\subset\mathbf{X}$. A complete
assignment $\sigma$ is when all variables in $\mathbf{X}$ are assigned a
value. A constraint function $f_{k}\in\mathbf{F}$ is satisfied if
$f_{k}(\sigma_{\mathcal{X}_{k}})\neq\perp$. The objective of a DCOP is to find
a complete assignment that minimizes the total cost:

$\displaystyle\sigma^{*}:=\underset{\sigma\in\mathbf{\Sigma}}{argmin}~{}\mathbf{F}_{g}(\sigma)=\underset{\sigma\in\mathbf{\Sigma}}{argmin}~{}\sum_{f_{k}\in\mathbf{F}}f_{k}(\sigma_{\mathcal{X}_{k}}),$
(1)

where $\mathbf{\Sigma}$ is the set of all possible complete assignments.

The Dynamic DCOP (D-DCOP) is an extension of the DCOP formulation to address
dynamic multi-agent environments. D-DCOP is modeled as a sequence of DCOPs,
$\mathcal{D}_{1},\mathcal{D}_{2},...,\mathcal{D}_{T}$. Here,
$\mathcal{D}_{t}=\left<\mathbf{A}^{t},\mathbf{X}^{t},\mathbf{D}^{t},\mathbf{F}^{t},\alpha^{t}\right>$
where $1\leq t\leq T$. D-DCOP aims to solve the arising DCOP problem at each
time step.

We consider adding an agent, removing an agent, and constraint function
modification as events that transition the environment from one DCOP to
another. Each agent $a_{i}$ has first to resolve its local neighbor list and
parent-child associations to solve the DCOP collaboratively.

##  4 Proposed Approach

###  4.1 Distributed Interaction Graph Construction Algorithm

This study’s proposed method assumes that the MAS agents can communicate via
message-passing. In this message-passing approach, each message contains the
sender’s ID and address which the receiver can use to send a response. Other
information could be contained in the message when needed. We further assume
that all agents are in a cooperative team and behave cooperatively to the
extent necessary for optimizing the team’s utility. The agents may execute in
asynchronous environments where arbitrary delay may be experienced even though
message delivery is guaranteed. Therefore, we use active and inactive states
to control agent procedure calls and race conditions.

The pseudocode of the proposed algorithm is presented in Algorithm 1. In our
discussion, agent $a_{i}$ (referenced as $i$) is the agent that executes a
procedure asynchronously. Agent $a_{j}$ (referenced as $j$) is an agent
already in the environment that $i$ interacts with.

The agent is set to an inactive state on initialization, and other initial
properties are set (line 1). The Connect function is scheduled as a process
that executes regularly or based on a schedule that may depend on the
application domain. When called, it first ensures that the agent is in an
inactive state and that it does not have a parent (line 3). Once the
connection conditions are satisfied, the agent broadcasts an Announce message
in the environment (line 4) and waits for a period, condition, or timeout
before proceeding (line 5). During this waiting period, an available agent in
the environment receives the Announce message and responds by sending an
AnnounceResponse message (lines 19-22). Before an agent can send an
AnnounceResponse, it must be inactive and a response determinant function
$\phi:A\rightarrow\mathbb{B}$ must be $\mathsf{TRUE}$. The function $\phi$ may
be defined based on the application domain (we discuss one such function in
Section 4.2).

When $i$ receives an AnnounceResponse message, it adds the sending agent to a
response list if it is still in an inactive state (lines 23-26). After the
waiting period (line 5), $i$ selects an agent in the response list using
$\vartheta$ (line 6). This selection function, $\vartheta$, could be defined
to examine each sender to determine a potential neighbor. Agent $i$ then sends
an AddMe message to the selected agent $j$ and goes into an active state while
it waits to hear from $j$ (lines 7-9). On line 10, it sets a timeout property
to enable resetting the state on a subsequent connect call if $j$ never
responds (lines 14-17), probably because it is no longer reachable. The
response list is cleared before ending the execution of the connect function
(line 12).

When $i$ receives an AddMe message from $j$, it adds $j$ to its children and
sends a ChildAdded message to $j$ if $i$ is in an inactive state (lines
28-30). Otherwise, it replies with an AlreadyActive message to $j$ (line 33).
When an AlreadyActive message is received by $i$, it sets its state to
inactive (line 45) to enable the next call to the connect procedure to pass
the condition on line 3.

After receiving a ChildAdded message from $j$, $i$ must be in an active state
and still without a parent to proceed (line 36). If so, it assigns $j$ as its
parent and goes into an inactive state (lines 37-38). Agent $i$ then sends a
ParentAssigned message to $j$ (line 39). Suppose the associated DCOP
algorithm’s execution order is a child-first or bottom-up approach. In that
case, $i$ may start the DCOP computation since its neighbor set has changed,
following the notion of affected agents in [8] (lines 40-42).

On the other hand, when $i$ receives a ParentAssigned message, it triggers the
DCOP computation if the execution order is a parent-first or top-down method
(lines 46-49).

Input: DCOP algorithm, stateTimeout

$state\leftarrow\mathsf{INACTIVE}$, $\mathcal{L}\leftarrow\emptyset$,
$C_{i}\leftarrow\emptyset$, $\pi(i)\leftarrow null$ ;

// initialization step

1

2 Procedure  _connect(__)_ Called by $i$ to find a neighbor to connect to

3 if  _$state$ is $\mathsf{INACTIVE}$ and $\pi(i)=null$_ then

4 Publish Announce{$i$}

5 Wait for AnnounceResponse from available agents for a period

$j\leftarrow\vartheta(\mathcal{L})$ ;

// Select an agent from the list of respondents, if any

6 if  _$j$ is found_ then

7 Send AddMe{$i$} to $j$

8 $state\leftarrow\mathsf{ACTIVE}$

9 set stateTimeout

10 end if

11 $\mathcal{L}\leftarrow\emptyset$

12 else

13 if  _stateTimeout elapses and $state$ is $\mathsf{ACTIVE}$ and
$\pi(i)=null$_ then

14 $state\leftarrow\mathsf{INACTIVE}$

15 clear stateTimeout

16 end if

17

18 end if

19

20

21

22 Procedure  _receiveAnnounce(_j_)_ When $i$ gets an Announce message from
$j$

23 if  _$state$ is $\mathsf{INACTIVE}$ and $\phi_{i}(j)$_ then

24 Send AnnounceResponse{$i$,} to $j$

25 end if

26

27

28

29 Procedure  _receiveAnnounceResponse(_j_)_ When $i$ gets AnnounceResp from
$j$

30 if  _$state$ is $\mathsf{INACTIVE}$_ then

31 add $j$ to $\mathcal{L}$

32 end if

33

34

35

36 Procedure  _receiveAddMe(_j_)_ When $i$ receives AddMe message from $j$

37 if  _$state$ is $\mathsf{INACTIVE}$_ then

38 add $j$ to $C_{i}$

39 Send ChildAdded{$i$} to $j$

40 end if

41 else

42 Send AlreadyActive{$i$} to $j$

43 end if

44

45

46

47 Procedure  _receiveChildAdded(_j_)_ When $i$ gets ChildAdded from $j$

48 if  _$state$ is $\mathsf{ACTIVE}$ and $\pi(i)=null$_ then

49 $\pi(i)\leftarrow j$

50 $state\leftarrow\mathsf{INACTIVE}$

51 Send ParentAssigned{$i$} to $j$

52 if  _DCOP algorithm’s execution order is $\mathsf{bottomUp}$_ then

53 start DCOP algorithm

54 end if

55

56 end if

57

58

59

60 Procedure  _receiveAlreadyActive(_j_)_ When $i$ gets AlreadyActive from $j$

61 $state\leftarrow\mathsf{INACTIVE}$

62

63

64 Procedure  _receiveParentAssigned(_j_)_ When $i$ gets ParentAssigned from
$j$

65 if  _DCOP algorithm’s execution order is $\mathsf{TopDown}$_ then

66 Start DCOP algorithm

67 end if

68

69

70

Algorithm 1 Distributed Interaction Graph Construction Algorithm

In Algorithm 1, $i$ is able to connect to another agent in the environment or
the multi-agent hierarchy described in Section 3.1. The question that must be
answered is how it discovers agents in its neighbor set that are currently
unreachable and update its registers accordingly. We adopt a keep-alive
message approach in Algorithm 2 to address this question.

Similar to Algorithm 1, the procedures in Algorithm 2 are executed
asynchronously. First, the inspectNeighbors and sendKeepAlive procedures are
executed as two background processes called at regular periods like the
connect procedure of Algorithm 1. Agent $i$ maintains a list neighbors to keep
alive (line 1). The sendKeepAlive procedure sends a message to all its
neighbors to inform them of its availability when called (lines 2-5). When $i$
receives a KeepAlive message, it adds the sender to the keep alive message
list $P$ (lines 6-9). When the inspectNeighbors procedure is executed, it
removes any neighbor $j$ that is not found in the keep-alive list (lines
11-20). If $j$ (a removed agent) was the parent, $i$ goes into an inactive
state. This state change is necessary to enable the connect procedure of
Algorithm 1 to find a new parent. If a change in neighborhood is detected, $i$
starts the associated DCOP computation (lines 26-28).

Since the execution order is a property of the DCOP algorithm, $i$ will be
able to know whether to execute or forward computations to its parent or
children. While we focus on DCOP computation with the multi-agent hierarchy,
other distributed computations that execute using hierarchies could also be
applied. Due to the asynchronous execution environment, there could be a quick
succession of computation invocations. Therefore, such an environment may
require computations to have an associated aborting scheme. Another approach
could be to defer the execution of computations till all graph-associated
message handling are complete.

Input: $N_{i}$,DCOP algorithm

$P\leftarrow\emptyset$ ;

// keep alive list

1

2 Procedure  _sendKeepAlive(__)_ Called by $i$ to inform $j$ of its
availability

3 for  _neighbor in $N_{i}$_ do

4 send KeepAlive{$i$} to $j$

5 end for

6

7

8

9 Procedure  _receiveKeepAlive(_j_)_ When $i$ gets a KeepAlive message from
$j$

10 if  _$j$ not in $P$_ then

11 Add $j$ to $P$

12 end if

13

14

15

16 Procedure  _inspectNeighbors(_j_)_ Called regularly by $i$ to remove
unreachable neighbors

17 $affected$ $\leftarrow$ False

18 for  _$j$ in $N_{i}$_ do

19 if  _$j$ not in $P$_ then

20 if  _$j$ == $\pi(i)$_ then

21 $\pi(i)\leftarrow null$

22 $state\leftarrow\mathsf{INACTIVE}$

23 end if

24 else

25 remove $j$ from $C_{i}$

26 end if

27 clear all information about $j$ in $i$’s registers

28 affected $\leftarrow$ True

29 end if

30

31 end for

32 $P\leftarrow\emptyset$

33 if  _affected_ then

34 start DCOP algorithm

35 end if

36

37

38

Algorithm 2 Disconnected Neighbor Removal Algorithm

We illustrate how an agent connects to another agent in Figure 1. This
illustration assumes a successful connection process on first try for didactic
purposes. However, we note that an agent may issue multiple connect calls in
the environment, and the frequency of such calls is application dependent.

Figure 1: An illustration of how an agent gets connected using the proposed
algorithm. When Agent 3 wants to connect/re-connect to the current interaction
graph, (1) it broadcasts Announce message to agents in range (2) Agents 1 and
2 respond to Agent 3 with AnnounceResponse, (3) Agent 3 selects agent 1 and
sends an AddMe message, (4) Agent 1 responds with a ChildAdded message, (5)
Agent 3 then sends a ParentAssigned message.

###  4.2 Defining The Response Determinant Function

Notice that using $\vartheta$ ensures that $i$ considers only a single
insertion point during the connection process. Nonetheless, since $j$ could
also be broadcasting Announce messages, there is a need for a mechanism that
avoids cyclic connections in the hierarchy. To this end, the result of
$\phi_{i}:A\rightarrow\mathbb{B}$ must be consistent and independent of the
problem horizon. We define an instance of $\phi$ in equation 2 based on the
ordered set of agents mentioned in Section 3.1.

$\phi_{i}(j)=\left\\{\begin{array}[]{ll}\mathsf{TRUE}&\quad\text{if }i<j,\\\
\mathsf{FALSE}&\quad\text{Otherwise }\end{array}\right.$ (2)

This definition has the intuition that the agent with the lowest index will be
the root. In the generation of the multi-agent hierarchy, two extreme cases
must be considered. The first is a situation where the hierarchy tends towards
a chain. Such a scenario may be helpful for synchronized computations but
undesirable when parallelism is desired. The second is when all agents are
connected to one root (tree of depth 1). While this encourages parallelism,
removing the root causes all other agents to be affected and the need to
invoke the connection algorithm. To balance these extremes, we use a max-
degree heuristic to limit the possible number of neighbors and define
$\vartheta$ to weight agents with a single or no child higher when selecting
from the response list.

##  5 Experiments

###  5.1 Setting

We used C-CoCoA [17] and applied similar non-linear optimization methods in
[17] to the SDPOP (C-SDPOP) to obtain representative top-down and bottom-up
DCOP algorithms, respectively, in our
experiments222https://github.com/bbrighttaer/ddcop-dynagraph. We defined a
binary constraint between two agents as $f_{k}(x,y)=ax^{2}+bxy+cy^{2}$ where
$x$ is the value of $i$ and $y$ is the value of $j$. The coefficients were
sampled randomly between the range $[-5,5]$. The lower and upper bounds for
each agent’s domain were set at $[-50,50]$ and each agent samples three values
from this range to constitute its domain. The change-constraint event randomly
selects a constraint between two agents and changes the coefficients of the
constraint $(a,b,c)$ by sampling randomly from the range $[-5,5]$.

We restricted the maximum number of children an agent could have in the multi-
agent hierarchy (max-out degree) to 3, 5, and 6 to create different experiment
settings for the evaluation. For each max-out degree, we generated five random
problems where the first 100 events add an agent into the environment, and the
subsequent 10 events were change-constraint events. Then 10 agent removal
events were executed in the environment. We applied a delay of 5 seconds in
between events to allow time for an applied event’s effect to propagate before
gathering the respective metrics. The metrics we considered in our experiments
are solution cost and the total number of messages. Each generated problem was
ran with 10 different random seeds. The reported results are averages across
the different settings of a given max-out degree.

Figure 2: Solution cost result after 120 events in the environment. The first
100 events are add-agent events, the next 10 events are change-constraint
events, and the remaining 10 events are remove-agent events.

###  5.2 Results

The solution cost results for the three experiment settings are shown in
Figure 2. Also, the average number of messages resulting from the interactions
over the horizon are shown in Table 1. The standard deviations are shown in
parenthesis. Generally, the solution cost performance of the DIGCA was stable
in the different experiment settings considered. In contrast, the C-CoCoA
algorithm performed poorly in all the experiments. On the solution cost, we
observed that pairing our proposed approach with the C-CoCoA reduced the cost
in all three experiments.

Similarly, we observed that C-CoCoA used almost twice as many messages during
the simulation compared to CoCoA-DIGCA in all experiment settings. This
observation is not surprising since the C-CoCoA algorithm is a classical DCOP
algorithm and therefore restarts for every event. Thus, this performance shows
the importance of having a well-defined structure for agent execution in an
open and dynamic environment as enabled by DIGCA. In the case of C-SDPOP,
while the solution cost was not as low, it used the fewest messages in all
experiments. Aside from interaction complexity reduction enabled by DIGCA, the
C-SDPOP algorithm also uses a fault-containment procedure [9] to reduce the
number of messages forwarded to the root agent. We realized in our experiments
that this fault-containment procedure was necessary to avoid the root agent
triggering the propagation of VALUE messages down the entire hierarchy once a
UTIL message percolates up. Thus, for algorithms that use multiple rounds of
message passing in the hierarchy for the optimization process, there is a need
for local agent mechanisms to determine which sub-trees receive change
propagation. We also note that the usage of DIGCA with different DCOP
algorithms highlights its effectiveness in facilitating the development of
multi-agent coordination approaches for an open and dynamic environment.

Table 1: Average number of messages by algorithms with standard deviations Algorithm | Maximum out degree
---|---
3 | 5 | 6
DIGCA and C-CoCoA | 4435.958 (273.067) | 4596.480 (412.163) | 4595.617 (324.378)
DIGCA and C-SDPOP | 4301.940 (407.647) | 4265.408 (392.879) | 4108.081 (361.208)
C-CoCoA | 74576 (2099.177) | 76066 (3682.198) | 74920 (3281.262)

##  6 Conclusion

In this paper, we have discussed the ad-hoc distributed multi-agent hierarchy
generation problem. We have also proposed a distributed algorithm for
constructing and maintaining a stable multi-agent hierarchy for interaction
when collaborating in a dynamic environment. Our proposed approach addresses a
vital issue in multi-agent operations in open and dynamic environments. Unlike
existing methods, DIGCA does not require an existing interaction graph or
reconstruction of the entire multi-agent hierarchy when changes are detected.
The method’s effectiveness has been shown using variants of well-known DCOP
proposals. Our future work would apply the proposed method to problems in
DCOP_MSTs and other practical domains.

## Acknowledgments

We thank David Livingstone Hini for designing the web interface for the
experiments.

## References

  * [1] Harel Yedidsion, Roie Zivan, and Alessandro Farinelli.  Applying max-sum to teams of mobile sensing agents.  Engineering Applications of Artificial Intelligence, 71:87–99, may 2018.
  * [2] P.E. Rybski, S.A. Stoeter, M. Gini, D.F. Hougen, and N. Papanikolopoulos.  Effects of limited bandwidth communications channels on the control of multiple robots.  In Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No.01CH37180), volume 1, pages 369–374 vol.1, 2001\.
  * [3] Paritosh Padhy, Rajdeep K. Dash, Kirk Martinez, and Nicholas R. Jennings.  A utility-based sensing and communication model for a glacial sensor network.  In Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS ’06, page 1353–1360, New York, NY, USA, 2006. Association for Computing Machinery.
  * [4] Marc Pujol-Gonzalez, Jesús Cerquides, Pedro Meseguer, Juan Antonio Rodríguez-Aguilar, and Milind Tambe.  Engineering the decentralized coordination of uavs with limited communication range.  In Concha Bielza, Antonio Salmerón, Amparo Alonso-Betanzos, J. Ignacio Hidalgo, Luis Martínez, Alicia Troncoso, Emilio Corchado, and Juan M. Corchado, editors, Advances in Artificial Intelligence, pages 199–208, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
  * [5] Robert Junges and Ana L. C. Bazzan.  Evaluating the performance of dcop algorithms in a real world, dynamic problem.  In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 2, AAMAS ’08, page 599–606, Richland, SC, 2008. International Foundation for Autonomous Agents and Multiagent Systems.
  * [6] Trung Thanh Nguyen and Xin Yao.  Continuous dynamic constrained optimization-the challenges.  IEEE Transactions on Evolutionary Computation, 16(6):769–786, 2012\.
  * [7] Evan A. Sultanik, Robert N. Lass, and William C. Regli.  Dynamic configuration of agent organizations.  IJCAI International Joint Conference on Artificial Intelligence, pages 305–311, 2009.
  * [8] William Yeoh, Pradeep Varakantham, Xiaoxun Sun, and Sven Koenig.  Incremental DCOP search algorithms for solving dynamic DCOP problems.  Proceedings - 2015 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, WI-IAT 2015, 2:257–264, 2015.
  * [9] Adrian Petcu and Boi Faltings.  Superstabilizing, fault-containing distributed combinatorial optimization.  Proceedings of the National Conference on Artificial Intelligence, 1:449–454, 2005.
  * [10] William Yeoh, Pradeep Varakantham, Xiaoxun Sun, and Sven Koenig.  Incremental DCOP Search Algorithms for Solving Dynamic DCOPs ( Extended Abstract ).  Artificial Intelligence, (Aamas):1069–1070, 2011.
  * [11] Jose Barambones, Ricardo Imbert, and Cristian Moral.  Applicability of multi-agent systems and constrained reasoning for sensor-based distributed scenarios: A systematic mapping study on dynamic DCOPs.  Sensors, 21(11), 2021.
  * [12] Roie Zivan, Harel Yedidsion, Steven Okamoto, Robin Glinton, and Katia Sycara.  Distributed constraint optimization for teams of mobile sensing agents.  Autonomous Agents and Multi-Agent Systems, 29(3):495–536, 2015\.
  * [13] Joel Quinqueton Youssef Hamadi Christian Bessiere.  Backtracking in Distributed Constraint Networks.  ECAI, pages 219–223, 1998.
  * [14] Zeev Collin and Shlomi Dolev.  Self-stabilizing depth-first search.  Information Processing Letters, 49(6):297–301, 1994.
  * [15] Adrian Petcu and Boi Faltings.  Optimal solution stability in dynamic, distributed constraint optimization.  Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IAT 2007, pages 321–327, 2007.
  * [16] Ferdinando Fioretto, Enrico Pontelli, and William Yeoh.  Distributed constraint optimization problems and applications: A survey.  Journal of Artificial Intelligence Research, 61:623–698, 2018.
  * [17] Md Mosaddek Sarker, Amit; Choudhury, Moumita; khan.  A Local Search Based Approach to Solve Continuous DCOPs.  Aamas 21, pages 1127–1135, 2021.