# House-Swapping with Objective Indifferences

Will Sandholtz and Andrew Tai
UC Berkeley

(June 2023)

###### Abstract

We study the classic house-swapping problem of [8] in a setting where agents
may have “objective” indifferences, i.e., indifferences that are shared by all
agents. In other words, if any one agent is indifferent between two houses,
then all agents are indifferent between those two houses. The most direct
interpretation is the presence of multiple copies of the same object. Our
setting is a special case of the house-swapping problem with general
indifferences. We derive a simple, easily interpretable algorithm that
produces the unique strict core allocation of the house-swapping market, if it
exists. Our algorithm runs in square-polynomial time, a substantial
improvement over the cubed time methods for the more general problem.

##  1 Introduction

The house-swapping problem originally studied by [8] assumes that agents have
a strict preference ordering over the set of the agents’ houses. Implicitly,
all houses are distinct. As [7] show, in this setting the strict core is
always non-empty and consists of a single allocation, which can identified
using the Top Trading Cycles algorithm (TTC).

In the more general setting where agents’ preference rankings may contain
indifferences, the strict core may be empty. Moreover, when the strict core is
non-empty, it may contain multiple allocations. [6] devised an algorithm, Top
Trading Segmentation (TTS), that finds a strict core allocation, when it
exists. [1] devise Top Trading Absorbing Sets (TTAS) which finds the strict
core when it exists and the weak core otherwise. They leave computational
complexity of their algorithm as an open question. [3] also solve the general
indifference problem with Top Cycle Rules (TCR), which has complexity
$O(n^{6})$. [2] present Generalized Absorbing Top Trading Cycle (GATTC),
generalizing TTAS and TCR and show that TTAS has exponential time complexity.
[5] develops a different mechanism to produce a strict core allocation with
time complexity $O(n^{3})$.

We study a more structured problem, where any indifferences are shared across
all agents. We use the phrase “objective indifferences” to describe this
setting. Conversely, we use the phrase “subjective indifferences” to describe
indifferences that are not necessarily shared by all agents. Objective
indifferences are the leading case of indifferences, since many objects we
encounter in daily life are commodified. This additional structure enables us
to develop a simple algorithm to find the strict core, when it exists, with
time complexity $O(n^{2})$.

Our setting can be thought of as an intermediate case between the original [8]
setting and the general setting studied first by [6]. With objective
indifferences, as in the house-swapping problem with subjective indifferences,
the strict core may be empty. However, when the strict core is non-empty it
contains a unique allocation. We propose a simple algorithm that finds the
strict core allocation of a house-swapping market with objective indifferences
in square-polynomial time. This algorithm is faster than the polynomial time
algorithms that are needed for house-swapping markets with subjective
indifferences.

##  2 Model

Let $I=\\{1,2,...,I\\}$ be a set of agents, each of whom is endowed with a
house. Let $H=\\{1,2,...,H\\}$ be the set of possible house types in the
market. Note that $H<I$ implies that some agents were endowed with houses of
the same type. The endowment function $E:I\to H$ maps each agent to the house
type he was endowed with.

Each agent $i\in I$ has strict preferences $\succsim_{i}$ over $H$.
Implicitly, all agents are indifferent between two houses of the same type. We
use $\succsim=\\{\succsim_{1},\succsim_{2},...,\succsim_{I}\\}$ to denote the
preference profile of all agents.

An allocation $\mu$ is a function $\mu:I\to H$ such that
$|\mu^{-1}(h)|=|E^{-1}(h)|$ for all $h\in H$. That is, $\mu(i)=h$ means agent
$i$ is assigned a house of type $h$, and the number of agents who are
allocated to a house type is equal to the supply of it.

The house-swapping market is summarized as the tuple $(I,H,E,\succsim)$. We
are interested in whether the strict core exists.

######  Definition 1.

An (sub-)allocation $\mu$ is feasible for a coalition of agents
$I^{\prime}\subseteq I$ if $\left|\mu^{-1}(h)\right|=\left|E^{-1}(h)\cap
I^{\prime}\right|$ for any $h\in E(I^{\prime})$. That is, the quantity of each
house type required in the (sub-)allocation is the same as the quantity in the
coalition’s endowment.

######  Definition 2.

A (feasible) allocation $\mu$ is in the strict core of the house-swapping
market $(I,H,E,\succsim)$ if there is no coalition $I^{\prime}\subseteq I$ and
no sub-allocation $\mu^{\prime}$ such that:

  1. 1.

$\mu^{\prime}$ is feasible for $I^{\prime}$

  2. 2.

$\mu^{\prime}(i)\succsim_{i}\mu(i)$ for all $i\in I^{\prime}$

  3. 3.

$\mu^{\prime}(i)\succ_{i}\mu(i)$ for at least one $i\in I^{\prime}$

We derive an algorithm that finds the strict core of a house-swapping market
$(I,H,E,\succsim)$ when it exists.

##  3 Directed Graphs

Before proceeding to our main results and the algorithm, we review some useful
concepts related to directed graphs. The definitions are standard, and a
familiar reader may skim this section.

A directed graph is given by $D(V,E)$ where $V$ is the set of vertices and $E$
is the set of arcs. An arc is a sequence of two vertices $(v,v^{\prime})$. We
allow for arcs of the form $(v,v)$, which we call self-loops. A
$(v_{1},v_{k})$-path is a sequence of vertices $(v_{1},v_{2},...,v_{k})$ where
each $v_{i}$ is distinct and $(v_{i-1},v_{i})\in E$ for all $i=2,3,...,k$. A
cycle is a path where $v_{1}=v_{k}$ is the only repeated vertex. A sink of a
directed graph is a vertex $v$ such that $(v,v^{\prime})\notin E$ for all
$v^{\prime}\in V$.

A strongly connected component (SCC) of a directed graph $D(V,E)$ is a maximal
set of vertices $S\subseteq V$ such that for all distinct vertices
$v,v^{\prime}\in S$, there is both a $(v,v^{\prime})$-path and a
$(v^{\prime},v)$-path. By convention, there is always a path from $v$ to
itself, regardless of whether $(v,v)\in E$. The collection of strongly
connected components of a directed graph forms a partition of $V$. (To see
this, note that the definition of an SCC implies that a vertex can be in
exactly one SCC.)

The condensation of a directed graph $D(V,E)$ is the directed graph
$D(V^{SCC},E^{SCC})$ where $V^{SCC}$ is the set of SCCs of $D(V,E)$ and
$(S,S^{\prime})\in E^{SCC}$ if and only if there exist $v\in S$ and
$v^{\prime}\in S^{\prime}$ such that $(v,v^{\prime})\in E$. In other words, it
is the arc-contraction of $D$ on each SCC – replace each SCC with a single
vertex, and keep any arcs between SCCs. Condensations of directed graphs are
always acyclic.

A topological ordering of a directed acyclic graph $D(V,E)$ is a total order
$\leq$ of the elements of $V$ such that if $(v,v^{\prime})\in E$, then $v\leq
v^{\prime}$. A directed graph has a topological ordering if and only if it is
acyclic.111See [4], Section 2.2. It is immediate that the vertex with the
highest topological ordering is a sink.

##  4 Results

In this section, we give our algorithm to determine whether a strict core of a
market $\left(I,H,E,\succsim\right)$ exists and to find it when it does.
First, we define a function $B_{i}$ that denotes the $i$’s most preferred
house type among a subset of house types. Let $B_{i}:I\times\mathcal{P}(H)\to
H$ be given by $B_{i}(H^{\prime})=h$ if $h\succsim_{i}h^{\prime}$ for all
$h^{\prime}\in H^{\prime}$.

We now give our algorithm.

######  Algorithm 1.

House Top Trading Segments (HTTS)

Step 1.

Let $R_{1}=H$. Construct the directed graph $D_{1}=D(R_{1},E_{1})$ where
$(h,h^{\prime})\in E_{1}$ if $B_{i}(R_{1})=h^{\prime}$ for some $i\in
E^{-1}(h)$. That is, draw an arc $(h,h^{\prime})$ exists if an owner of $h$
top-ranks $h^{\prime}$ among all house types $R_{1}=H$. Find an SCC $H_{1}$ of
$D_{1}$ with no outgoing arcs; i.e., for any $h\in H_{1}$ and
$h^{\prime}\notin H_{1}$, $(h,h^{\prime})\notin E_{1}$.222There always exists
an SCC with no outgoing arcs. To see this, consider the condensation (contract
each SCC to a single vertex). The result is a directed acyclic graph, which
has at least one sink. The sink is the (contracted) desired SCC with no
outgoing arcs. Note that there may be multiple SCCs with no outgoing arcs. If
so, pick any arbitrarily. We call $H_{1}$ a “house top trading segment”.

  1. 1.

Let $I_{1}=E^{-1}(H_{1})$. For all $i\in I_{1}$, set $\mu(i)=B_{i}(R_{1})$.
That is, assign every agent endowed with a house in $H_{1}$ to his favorite
house (also in $H_{1}$).

  2. 2.

Check that $\mu$ is feasible for $I_{1}$. If so, proceed to part c. Otherwise,
stop.

  3. 3.

Let $R_{2}=R_{1}\setminus H_{1}$. If $R_{2}=\emptyset$, stop; otherwise,
proceed to Step 2.

Step $d$.

Construct the directed graph $D_{d}=D(R_{d},E_{d})$ where $(h,h^{\prime})\in
E_{d}$ if $B_{i}(R_{d})=h^{\prime}$ for some $i\in E^{-1}(h)$. Find an SCC
$H_{d}$ of $D_{d}$ with no outgoing arcs.

  1. 1.

Let $I_{d}=E^{-1}(H_{d})$. For all $i\in I_{d}$, set $\mu(i)=B_{i}(R_{d})$.
That is, assign each agent in $I_{d}$ to his favorite remaining house. Since
$H_{d}$ has no outgoing arcs, this house is also in $H_{d}$.

  2. 2.

Check that $\mu$ is feasible for $I_{d}$. If so, proceed to part $c$.
Otherwise, stop.

  3. 3.

Let $R_{d+1}=R_{d}\setminus H_{d}$. If $R_{d+1}=\emptyset$, stop; otherwise,
proceed to Step $d+1$.

######  Remark 1.

Note that at each step, house types are removed, and thus agents owning them
are also removed. Since there are finitely many house types $H$, the algorithm
terminates in finite time.

######  Remark 2.

At part $b$ of each step, $\mu$ is feasible for $I_{d}$ if and only if for
each $h\in H_{d}$, $\left|E^{-1}(h)\cap
I_{d}\right|=\left|\left\\{i:B_{i}H_{d})=h,i\in I_{d}\right\\}\right|$. That
is, the number of copies of $h$ available in $I_{d}$ is equal to the number of
agents who top-rank $h$ among the remaining houses. Informally, “supply equals
demand.”

The house top trading segments we find in each step are analogous to TTC
trading cycles. At each step, agents “point” from their owned house to their
favorite house. We then find the trading segment and execute the trades, if
possible (“feasible”). For readers familiar with Quint and Wako (2004), these
are modified versions of top trading segments.

######  Theorem 1.

Let $\left(I,H,E,\succsim\right)$ be a market.

  1. 1.

The strict core exists if and only if Algorithm 1 terminates in part $c$ of a
step. That is, each step’s HTTS gives a feasible allocation, and the algorithm
did not terminate in part $b$ of a step.

  2. 2.

Algorithm 1 finds a strict core allocation, when one exists.

  3. 3.

The strict core allocation is unique, when it exists.333Recall the definition
of an allocation is a matching between agents and house types. The individual
identities of the houses do not matter.

  4. 4.

Algorithm 1 has time complexity $O(|H|^{2}+|H||I|)$.

Before the proof of Theorem 1, we give the following example to illustrate it
and Algorithm 1.

######  Example 1.

Consider the house-swapping market $\mathcal{}(I,H,E,\succsim)$ where

$\displaystyle I=\\{1,2,3,4,5\\}$ $\displaystyle
H=\\{h_{1},h_{2},h_{3},h_{4}\\}$ $\displaystyle
E(1)=h_{1},\;E(2)=E(3)=h_{2},\;E(4)=h_{3},\;E(5)=h_{4}$

and
$\succsim=\\{\succsim_{1},\succsim_{2},\succsim_{3},\succsim_{4},\succsim_{5}\\}$
is given by

$\displaystyle h_{2}$ $\displaystyle\succ_{1}...$ $\displaystyle h_{1}$
$\displaystyle\succ_{2}...$ $\displaystyle h_{3}$
$\displaystyle\succ_{3}h_{2}\succ_{3}...$ $\displaystyle h_{4}$
$\displaystyle\succ_{4}...$ $\displaystyle h_{3}$ $\displaystyle\succ_{5}...$

  1. 1.

Step 1: Set $R_{1}=H$. Construct the directed graph $D(R_{1},E_{1})$ where
$(h,h^{\prime})\in E_{1}$ if $B_{i}(R_{1})=h^{\prime}$ for some $i\in
E^{-1}(h)$. That is, some owner of $h$ top ranks $h^{\prime}$. There are two
SCCs in $D(R_{1},E_{1})$: $\\{h_{1},h_{2}\\}$ and $\\{h_{3},h_{4}\\}$. Only
$S=\\{h_{3},h_{4}\\}$ has no outgoing arcs. Then set $H_{1}=\\{h_{3},h_{4}\\}$
and $I_{1}=\\{4,5\\}$.

    1. (a)

Assign $\mu(4)=h_{4};\mu(5)=h_{3}$.

    2. (b)

Check that this is feasible for $I_{1}$. We have

$\displaystyle\left|E^{-1}(h_{3})\cap I_{1}\right|=\left|\\{4\\}\right|$
$\displaystyle=1$ $\displaystyle\left|\\{i:B_{i}(H_{1})=h_{3},i\in
I_{1}\\}\right|=\left|\\{5\\}\right|$ $\displaystyle=1$

and likewise for $h_{4}$, so this is feasible.

    3. (c)

Set $R_{2}=R_{1}\setminus H_{1}=\\{h_{1},h_{2}\\}$ and continue to Step 2.

  2. 2.

Step 2: Construct the directed graph $D(R_{2},E_{2})$ where $(h,h^{\prime})\in
E_{2}$ if $B_{i}(R_{2})=h^{\prime}$ for some $i\in E^{-1}(h)$. That is, some
owner of $h$ top ranks $h^{\prime}$ among the remaining houses
$R_{2}=\\{h_{1},h_{2}\\}$. The entire graph forms an SCC, so set
$H_{2}=\\{h_{1},h_{2}\\}$ and $I_{2}=\\{1,2,3\\}$.

    1. (a)

Assign $\mu(1)=h_{2};\mu(2)=h_{1};\mu(3)=h_{2}$.

    2. (b)

Check that this is feasible for $I_{2}$ (it is).

    3. (c)

Set $R_{3}=R_{2}\backslash H_{2}=\emptyset$. So the algorithm terminates.

Therefore, a House Top Trading Segmentation of $H$ is given by

$\mathcal{H}=\big{\\{}H_{1}=\\{h_{3},h_{4}\\},H_{2}=\\{h_{1},h_{2}\\}\big{\\}}.$

$h_{1}$$h_{2}$$h_{3}$$h_{4}$$H_{1}$$R_{2}$Step 1

$h_{1}$$h_{2}$$H_{2}$Step 2

Figure 1: Applying Algorithm 1 to Example 1.

By Theorem 1, the unique strict core of this market is given by

$\displaystyle\mu(1)$ $\displaystyle=h_{2}$ $\displaystyle\mu(2)$
$\displaystyle=h_{1}$ $\displaystyle\mu(3)$ $\displaystyle=h_{2}$
$\displaystyle\mu(4)$ $\displaystyle=h_{4}$ $\displaystyle\mu(5)$
$\displaystyle=h_{3}$

###  4.1 Proof of Theorem 1

The proofs for the strict core claims unsurprisingly follow Gale’s proof for
TTC. The first key insight is that by focusing on house types as nodes
(instead of agents), we ensure that we remove all copies of a house at the
same time. This lets us easily deal with objective indifferences. The second
key insight is that when we assign houses within an SCC without outgoing arcs,
we assign a set of houses and their owners at the same time.

###### Proof of Claim 2..

Let $\left(I,H,E,\succsim\right)$ be a market, and let $\mu^{HTTS}$ be the
allocation produced by Algorithm 1. That is, the algorithm terminated in part
$c$ of some step.

We first argue that $\mu^{HTTS}$ is indeed a feasible allocation. At each
step, we arrive at a house trading segment $H_{d}$. Note that $H_{d}$ has no
outgoing arcs in $D_{d}$. Thus all agents endowed with a house $h\in H_{d}$
(denoted $I_{d}$) top-rank a house in $H_{d}$ from among the remaining houses.
By our assumption that Algorithm 1 terminated in part c (and not part b) of
some step, we know that $\mu^{HTTS}$ is feasible for $I_{d}$. Part $c$ of this
step removes $H_{d}$ and thus $I_{d}$ from further consideration. Thus
$\\{H_{1},...,H_{d},...,H_{K}\\}$ and $\\{I_{1},...,I_{d},...,I_{K}\\}$
partition the house types and agents, respectively. If $\mu$ is feasible for
each $I_{d}$, then it is feasible for $I$.

Toward a contradiction, suppose there is a blocking coalition $I^{\prime}$ and
sub-allocation $\mu^{\prime}$.

For at least one agent $i\in I$, $\mu^{\prime}(i)\succ\mu^{HTTS}(i)$. Consider
the step $d$ at which $i$ was assigned in Algorithm 1. By construction,
$\mu^{HTTS}(i)=B_{i}(H_{d})=B_{i}\left(\cup_{d^{\prime}\geq
d}H_{d^{\prime}}\right)$. So it must be that
$\mu^{\prime}(i)\in\cup_{d^{\prime}<d}H_{d^{\prime}}$. Feasibility of
$\mu^{\prime}$ implies that there is some $i^{\prime}\in I_{k}$ for $k<d$ such
that $\mu^{\prime}(i^{\prime})\in\cup_{k^{\prime}>k}H_{k^{\prime}}$. But then
$\mu^{\prime}(i^{\prime})\prec\mu^{HTTS}(i^{\prime})$, so this is not a
blocking coalition. In other words, for $\mu^{\prime}(i)\succ\mu^{HTTS}(i)$,
$i$ must be assigned to a house from an earlier segment. But then an agent
from an earlier segment must be assigned to a house from a later segment,
which is strictly dispreferred. ∎

###### Proof of Claim 3..

Let $\left(I,H,E,\succsim\right)$ be a market, and let $\mu^{HTTS}$ be the
allocation produced by Algorithm 1. That is, the algorithm terminated in a
part $c$. Let $\mu^{\prime}$ be another strict core allocation. We again show
$\mu^{\prime}=\mu^{HTTS}$ by strong induction on the number of steps in HTTS.

Base claim.

Consider $H_{1}$ and $I_{1}$. We have
$\mu^{HTTS}(i)\succsim_{i}\mu^{\prime}(i)$ for all $i\in I_{1}$, since every
$i\in I_{1}$ receives his favorite house. Since $\mu^{HTTS}$ is feasible for
$I_{1}$ and $\mu^{\prime}$ is in the strict core, we must also have
$\mu^{\prime}(i)\succsim_{i}\mu^{HTTS}(i)$ for all $i\in I_{1}$. (Otherwise
$I_{1}$ can form a blocking coalition with sub-allocation
$\mu^{HTTS}|_{I_{1}}$.) But then $\mu^{HTTS}(i)=\mu^{\prime}(i)$ for $i\in
I_{1}$.

Claim $d$.

Assume $\mu^{HTTS}(i)=\mu^{\prime}(i)$ for all $i\in I_{1}\cup\cdots\cup
I_{d-1}$. Then $\mu^{\prime}(I_{d})\subseteq\cup_{d^{\prime}\geq
d}H_{d^{\prime}}$. That is, the houses assigned to agents in $I_{d}$ are drawn
from the houses that remain after step $d-1$. By construction, we have
$\mu^{HTTS}(i)\succsim_{i}h$ for any $h\in\cup_{d^{\prime}\geq
d}H_{d^{\prime}}$ for all $i\in I_{d}$, so we have
$\mu^{HTTS}(i)\succsim_{i}\mu^{\prime}(i)$ for $i\in I_{d}$. Since
$\mu^{HTTS}$ is feasible for $I_{k}$ and $\mu^{\prime}$ is in the strict core,
we must have $\mu^{\prime}(i)\succsim_{i}\mu^{HTTS}(i)$ for all $i\in I_{d}$.
But then $\mu^{HTTS}(i)=\mu^{\prime}(i)$ for $i\in I_{d}$.

∎

###### Proof of Claim 1..

We now have that $\mu^{HTTS}$ is the unique strict core allocation, when it
exists. Thus, if $\mu^{HTTS}$ is not feasible, there is no strict core
allocation. ∎

###### Proof of Claim 4..

We apply Tarjan’s algorithm [9]. For any directed graph $G=D(V,E)$, the order
in which Tarjan’s algorithm returns the SCCs of $G$ is a reverse topological
ordering of the condensation $G^{SCC}=D(V^{SCC},E^{SCC})$ of $G$.444See [4],
Section 2.3. Concretely, suppose $\mathcal{S}=\\{S_{1},S_{2},...,S_{\ell}\\}$
is the set of SCCs of $G$ in the order in which they were returned by Tarjan’s
algorithm (i.e., $S_{1}$ is the first SCC returned, $S_{2}$ is the second,
etc.). Then $S_{1}$ must be a sink of $G^{SCC}$. Therefore, $S_{1}$ is an SCC
of $G$ with no outgoing arcs.

At each step $d$ of Algorithm 1, we perform two computations. First, we use
Tarjan’s algorithm to identify an SCC $H_{d}$ with no outgoing arcs.555We need
not find all SCCs. The first SCC returned by Tarjan’s algorithm will suffice.
Tarjan’s algorithm has time complexity $O(|H|+|I|)$. Second, we check whether
the strict core allocation is feasible for $I_{d}=E^{-1}(H_{d})$. That is, for
each $h\in H_{d}$, we check $\left|E^{-1}(h)\cap
I_{d}\right|=\left|\left\\{i:B_{i}(H_{d})=h,i\in I_{d}\right\\}\right|$. This
has time complexity $O(|H|)$. Therefore, each step of Algorithm 1 has time
complexity $O(|H|+|I|)$.

Since Algorithm 1 terminates in at most $|H|$ steps, it has time complexity
$O(|H|^{2}+|H||I|)$.

∎

##  5 Conclusion

In this paper, we study the house-swapping problem in a setting where agents’
preferences may contain “objective indifferences.” We assume that agents have
strict preferences over a set of house types and that multiple agents may be
endowed with copies of the same house type. We derive a square-polynomial time
algorithm that finds the unique strict core allocation of a house-swapping
market, if it exists. This is faster than the methods that are needed to find
strict core allocations in the setting where agents are allowed to have
subjective indifferences. Moreover, our algorithm is interpretable as a series
of “house top trading segments”, which are analogous to top trading cycles.
The condition for the non-emptiness of the strict core is readily
interpretable – within each house top trading segment, supply and demand for
each house type are equal.

## References

  * [1] Jorge Alcalde-Unzu and Elena Molis  “Exchange of indivisible goods and indifferences: The Top Trading Absorbing Sets mechanisms”  In _Games and Economic Behavior_ 73.1, 2011, pp. 1–16
  * [2] Haris Aziz and Bart de Keijzer  “Housing Markets with Indifferences: A Tale of Two Mechanisms”  In _Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence_ , 2012
  * [3] Paula Jaramillo and Vikram Manjunath  “The difference indifference makes in strategy-proof allocation of objects”  In _Journal of Economic Theory_ 147.5, 2012, pp. 1913–1946
  * [4] Bernhard Korte and Jens Vygen  “Combinatorial Optimization: Theory and Algorithms”  Bonn: Springer, 2008
  * [5] C. Plaxton  “A Simple Family of Top Trading Cycles Mechanisms for Housing Markets with Indifferences”  In _Proceedings of the 24th International Conference on Game Theory_ , 2013
  * [6] Thomas Quint and Jun Wako  “On Houseswapping, the Strict Core, Segmentation, and Linear Programming”  In _Mathematics of Operations Research_ 29.4, 2004, pp. 861–877
  * [7] Alvin E. Roth and Andrew Postlewaite  “Weak versus strong domination in a market with indivisible goods”  In _Journal of Mathematical Economics_ 4.2, 1977, pp. 131–137
  * [8] Lloyd Shapley and Herbert Scarf  “On cores and indivisibility”  In _Journal of Mathematical Economics_ 1.1, 1974, pp. 23–37
  * [9] Robert Tarjan  “Depth-First Search and Linear Graph Algorithms”  In _SIAM Journal on Computing_ 1.2, 1972, pp. 15


model is, the importance of theoretical guarantees and explainability, and the
available computational resources at training time and at test time. Bilevel
methods show particular promise for applications where training data is
limited and/or explainability is highly valued, such as in medical imaging.

###### Acknowledgements.

This work was made possible in part due to the support of NIH grant R01
EB023618, NSF grant IIS 1838179, and the Rackham Predoctoral Fellowship. The
authors would like to thank Lindon Roberts for helpful email discussion of
[ehrhardt:2021:inexactderivativefreeoptimization].

##  Appendix A Additional Running Example Results

This appendix derives some results that are relevant to the running example
used throughout the survey.

###  A.1 Derivatives for Convolutional Filters

This section proves the result

$\displaystyle\nabla_{c_{s}}\left(\tilde{{\bm{c}}}_{k}\circledast
f.({\bm{c}}_{k}\circledast{\bm{x}})\right)=f.({\bm{c}}_{k}\circledast{\bm{z}}^{\langle
s\rangle})+\tilde{{\bm{c}}}_{k}\circledast\left(\dot{f}.({\bm{c}}_{k}\circledast{\bm{x}})\odot{\bm{x}}^{\langle-s\rangle}\right),$
(A.1)

when considering $\mathbb{F}=\mathbb{R}$. This equation is key to finding
derivatives of the lower-level cost function in (Ex) with respect to the
filter coefficients.

To simplify notation, we drop the indexing over $k$, so $\bm{c}$ is a single
filter and $c_{s}$ denotes the ${\bm{s}}$th element in the filter for
${\bm{s}}\in\mathbb{Z}^{D}$. Here, ${\bm{s}}$ indexes every dimension of
$\bm{c}$, e.g., for a two-dimensional filter, we could equivalently write
${\bm{s}}$ as $\langle s_{1},s_{2}\rangle$. Recall that the notation
$\tilde{{\bm{c}}}$ signifies a reversed version of $\bm{c}$, as needed for the
adjoint of convolution.

Define the notation ${\bm{x}}^{\langle{\bm{i}}\rangle}$ as the vector $\bm{x}$
circularly shifted according to the index ${\bm{i}}$. Thus, if $\bm{x}$ is
0-indexed and we use circular indexing,

$({\bm{x}}^{\langle{\bm{s}}\rangle})_{\bm{i}}={\bm{x}}_{{\bm{s}}+{\bm{i}}}.$

As two concrete examples,

${\bm{x}}^{\langle-1\rangle}=\begin{bmatrix}x_{2}\\\ x_{3}\\\ \vdots\\\
x_{N}\\\ x_{1}\end{bmatrix},$

and, in two dimensions, if ${\bm{X}}\in\mathbb{F}^{M\times N}$

${\bm{X}}^{\langle
1,2\rangle}=\begin{bmatrix}x_{M,N-1}&x_{M,N}&x_{M,1}&\ldots&x_{M,3}\\\
x_{1,N-1}&x_{1,N}&x_{1,1}&\ldots&x_{1,3}\\\
x_{2,N-1}&x_{2,N}&x_{2,1}&\ldots&x_{2,3}\\\ \vdots&&\ddots&&\vdots\\\
x_{M-1,N-1}&x_{M-1,N}&x_{M-1,1}&\ldots&x_{M-1,3}\end{bmatrix}.$

Notice the element $x_{1,1}$ appears in the second row and third column of
${\bm{X}}^{\langle 1,2\rangle}$, since

$\underbrace{\langle 1,2\rangle}_{{\bm{s}}}+\underbrace{\langle
1,1\rangle}_{{\bm{i}}}=\langle 2,3\rangle.$

This circular shift notation is useful in the derivation and statement of the
desired gradient.

Define ${\bm{z}}={\bm{c}}\circledast{\bm{x}}$, where $\bm{c}$ and $\bm{x}$ are
both $N$-dimensional. By the definition of convolution, $\bm{z}$ is given by

${\bm{z}}=\sum_{i_{1}}\cdots\sum_{i_{N}}h_{i_{1},\ldots,i_{N}}{\bm{x}}^{\langle\text{-}i_{1},\ldots,\text{-}i_{N}\rangle}\mathrel{\hbox
to0.0pt{\raisebox{1.29167pt}{$\cdot$}\hss}\raisebox{-1.29167pt}{$\cdot$}}=\sum_{i_{1},\ldots,i_{N}}h_{i_{1},\ldots,i_{N}}{\bm{x}}^{\langle\text{-}{\bm{i}}\rangle},$

where, for each sum, the indexing variable $i_{n}$ iterates over the size of
$\bm{c}$ in the $i$th dimension and we simplify the index for circularly
shifting vectors, $i_{1},\ldots,i_{N}$, as simply $\langle{\bm{i}}\rangle$.
This expression shows that the derivative of ${\bm{c}}\circledast{\bm{x}}$
with respect to the ${\bm{s}}$th filter coefficient is the $-{\bm{s}}$th
coefficient in $\bm{x}$, i.e.,

$\nabla_{c_{s}}({\bm{c}}\circledast{\bm{x}})={\bm{x}}^{\langle-{\bm{s}}\rangle}.$
(A.2)

We can now find the gradient of interest:

$\displaystyle\tilde{{\bm{c}}}\circledast f.({\bm{z}})$
$\displaystyle=\sum_{i_{1},\ldots,i_{N}}(\tilde{{\bm{c}}})_{i_{1},\ldots,i_{N}}f.({\bm{z}})^{\langle\text{-}{\bm{i}}\rangle}$
by the convolution formula
$\displaystyle=\sum_{i_{1},\ldots,i_{N}}[\tilde{{\bm{c}}}]_{i_{1},\ldots,i_{N}}f.\left({\bm{z}}^{\langle\text{-}{\bm{i}}\rangle}\right)$
since $f$ operates point-wise
$\displaystyle=\sum_{i_{1},\ldots,i_{N}}c_{\text{-}i_{1},\ldots,\text{-}i_{N}}f.\left({\bm{z}}^{\langle\text{-}{\bm{i}}\rangle}\right)$
$\displaystyle\text{ by definition of }\tilde{{\bm{c}}}$
$\displaystyle=\sum_{i_{1},\ldots,i_{N}}c_{i_{1},\ldots,i_{N}}f.\left({\bm{z}}^{\langle{\bm{i}}\rangle}\right)$
reverse summation order.

Recall that $\bm{z}$ is a function of $c_{s}$. Therefore, using the chain rule
to take the derivative,

$\displaystyle\nabla_{c_{s}}$ $\displaystyle\left(\tilde{{\bm{c}}}\circledast
f.({\bm{z}})\right)$ $\displaystyle=f.({\bm{z}}^{\langle
s\rangle})+\sum_{i_{1}}\cdots\sum_{i_{N}}c_{i_{1},\ldots,i_{N}}\dot{f}.({\bm{z}}^{\langle
i_{1},\ldots,i_{N}\rangle})\odot\nabla_{c_{s}}\left({\bm{z}}^{\langle{\bm{i}}\rangle}\right)$
$\displaystyle=f.({\bm{z}}^{\langle{\bm{s}}\rangle})+\sum_{i_{1}}\cdots\sum_{i_{N}}c_{i_{1},\ldots,i_{N}}\dot{f}.({\bm{z}}^{\langle
i_{1},\ldots,i_{N}\rangle})\odot{\bm{x}}^{\langle{\bm{i}}+{\bm{s}}\rangle},$

where the second equality follows from (A.2). Recognizing the convolution
formula in the second summand, the expression can be simplified to

$f.({\bm{z}}^{\langle{\bm{s}}\rangle})+\tilde{{\bm{c}}}\circledast\left(\dot{f}.({\bm{z}})\odot{\bm{x}}^{\langle-{\bm{s}}\rangle}\right).$

This proves the claim. Note that the provided formula is for a single element
in $\bm{c}$. One can concatenate the result for each value of ${\bm{s}}$ to
get the gradient for all elements in $\bm{c}$.

###  A.2 Evaluating Conditions for the Running Example

To better understand the conditions in Section 5.1.1, this section illustrates
how they apply to the filter learning example (Ex).

####  A.2.1 Upper-level Loss Conditions

Recall the upper-level loss function is mean square error:

$\displaystyle\ell({\bm{\upgamma}}\,;\,{\bm{x}})=\dfrac{1}{2}\|{\bm{x}}-{\bm{x}}^{\text{true}}\|^{2}_{2},$
(A.3)

where $\ell$ is typically evaluated at
${\bm{x}}={\bm{\hat{x}}}({\bm{\upgamma}})$.

The loss function (A.3) satisfies A$\ell$ 1. Because there is no dependence
on $\bm{\upgamma}$ in the upper-level,
$L_{{\bm{x}},\nabla_{\bm{\upgamma}}\ell}=0$. The gradient with respect to
$\bm{x}$ is
$\nabla_{\bm{x}}\ell({\bm{\upgamma}}\,;\,{\bm{x}})={\bm{x}}-{\bm{x}}^{\text{true}}$,
so $L_{{\bm{x}},\nabla_{\bm{x}}\ell}=1$.

The norm of the gradient with respect to $\bm{x}$,
$\left\lVert\nabla_{\bm{x}}\ell({\bm{\upgamma}}\,;\,{\bm{x}})\right\rVert=\left\lVert{\bm{x}}-{\bm{x}}^{\text{true}}\right\rVert$,
can grow arbitrarily large, so condition A$\ell$ 2 is not met in general.
However, in most applications, one can assume an upper bound (possibly quite
large) on the elements of ${\bm{x}}^{\text{true}}$ and impose that bound as a
box constraint when computing ${\bm{\hat{x}}}$. Then the triangle inequality
provides a bound on $\left\lVert{\bm{x}}-{\bm{x}}^{\text{true}}\right\rVert$
for all $\bm{x}$ within the constraint box.

Finally, A$\ell$ 3 is met by any loss function, including (A.3), that lacks
cross terms between $\bm{x}$ and $\bm{\upgamma}$. We are unaware of any
bilevel method papers using such cross terms.

####  A.2.2 Lower-level Cost Conditions

One property used below in many of the bounds for the lower-level cost
function is that

$\sigma_{1}({\bm{C}}_{k})=\left\lVert{\bm{c}}_{k}\right\rVert_{2},$ (A.4)

where $\sigma_{1}(\cdot)$ is a function that returns the first singular value
of a matrix argument. To derive this equality, we use the circular boundary
assumption on the convolutional filters. By the DFT convolution property,
multiplication by the convolutional matrix ${\bm{C}}_{k}$ is equivalent to
multiplication by the orthogonal discrete Fourier Transform (DFT) matrix,
${\bm{F}}^{\prime}$, filtering in the Fourier transform domain, and
multiplication with the inverse DFT matrix. This identity provides an
eigenvalue decomposition for the convolutional matrix,
${\bm{C}}_{k}={\bm{F}}{\bm{\Lambda}}{\bm{F}}^{\prime}$, where the eigenvalues
of ${\bm{C}}_{k}$ are simply the DFT of the first column of ${\bm{C}}_{k}$:

$\text{eig}({\bm{C}}_{k})=\left\\{\sum_{n=0}^{N-1}({\bm{c}}_{k})_{n}e^{-i2\pi
nm/N}\right\\}\text{ for }m\in\\{0,\ldots,N-1\\}.$

The largest singular value of ${\bm{C}}_{k}^{\prime}{\bm{C}}_{k}$ is the
squared magnitude of the largest eigenvalue of ${\bm{C}}_{k}$, which we can
simplify using the property that the magnitude of any complex exponential is
bounded by $1$:

$\displaystyle\sigma_{1}({\bm{C}}_{k}^{\prime}{\bm{C}}_{k})$
$\displaystyle=\max_{m=\\{0,\ldots,N-1\\}}\left(\sum_{n=0}^{N-1}({\bm{c}}_{k})_{n}e^{-i2\pi
nm/N}\right)^{2}$
$\displaystyle\leq\left(\sum_{n=0}^{N-1}({\bm{c}}_{k})_{n}\right)^{2}=\left\lVert{\bm{c}}_{k}\right\rVert^{2}_{2}.$

This inequality proves the claim.

As with the upper-level conditions, (Ex) meets most of the conditions if we
impose additional constraints on the maximum norm of variables. In addition to
bounding the elements in $\bm{x}$, as we did to ensure A$\ell$ 2, imposing
bounds on $\left\lVert{\bm{c}}_{k}\right\rVert$ and $\lvert\beta_{k}\rvert$ is
sufficient to meet all the lower-level conditions A$\Upphi$ 1-A$\Upphi$ 6.
We now examine each condition individually.

Recall from (Ex) that the example lower-level cost function is

$\displaystyle{\bm{\hat{x}}}({\bm{\upgamma}})$
$\displaystyle=\operatorname*{argmin}_{{\bm{x}}\in\mathbb{F}^{N}}\dfrac{1}{2}\left\lVert{\bm{A}}{\bm{x}}-{\bm{y}}\right\rVert^{2}_{2}+e^{\beta_{0}}\sum_{k=1}^{K}e^{\beta_{k}}{\bm{1}}^{\prime}\phi.({\bm{c}}_{k}\circledast{\bm{x}};\epsilon),$

where $\phi$ is a corner-rounded 1-norm (CR1N).

As described in Section 4.2, the minimizer approach requires $\Upphi$ to be
twice differentiable. Thus, $\Upphi$ satisfies A$\Upphi$ 1. This condition
limits the choices of $\phi$ to twice differentiable functions.

Considering A$\Upphi$ 2, the gradient of $\Upphi$ with respect to $\bm{x}$
is Lipschitz continuous in $\bm{x}$ if the norm of the Hessian,
$\left\lVert\nabla_{{\bm{x}}{\bm{x}}}\Upphi({\bm{x}}\,;{\bm{\upgamma}})\right\rVert_{2}$,
is bounded. Using (4.9) and assuming the Lipschitz constant of the derivative
of $\phi$ is $L_{\dot{\phi}}$ (for (CR1N),
$L_{\dot{\phi}}=\tfrac{1}{\epsilon}$), a Lipschitz constant for
$\nabla_{\bm{x}}\Upphi$ is

$\displaystyle L_{{\bm{x}},\nabla_{\bm{x}}\Upphi}$
$\displaystyle=\sigma_{1}^{2}({\bm{A}})+L_{\dot{\phi}}e^{\beta_{0}}\sum_{k}e^{\beta_{k}}\sigma_{1}{{\bm{C}}_{k}^{\prime}{\bm{C}}_{k}}$
$\displaystyle=\sigma_{1}^{2}({\bm{A}})+L_{\dot{\phi}}e^{\beta_{0}}\sum_{k}e^{\beta_{k}}\left\lVert{\bm{c}}_{k}\right\rVert^{2}\text{
by \eqref{eq: sigma1 Ck}}.$

The Lipschitz constant $L_{{\bm{x}},\nabla_{\bm{x}}\Upphi}$ depends on the
values in $\bm{\upgamma}$ and therefore does not strictly satisfy A$\Upphi$
2. Here if $\beta_{0}$, $\beta_{k}$, and ${\bm{c}}_{k}$ have upper bounds,
then one can upper bound $L_{{\bm{x}},\nabla_{\bm{x}}\Upphi}$. All of the
bounds below have similar considerations.

To consider the strong convexity condition in A$\Upphi$ 3, we again consider
the Hessian,

$\nabla_{{\bm{x}}{\bm{x}}}\Upphi({\bm{x}}\,;{\bm{\upgamma}})=\underbrace{{\bm{A}}^{\prime}{\bm{A}}}_{\text{From
data-\\\ fit
term}}+\underbrace{e^{\beta_{0}}\sum_{k}e^{\beta_{k}}{\bm{C}}_{k}^{\prime}\text{diag}({\ddot{\phi}}.({\bm{c}}_{k}\circledast{\bm{x}})){\bm{C}}_{k}}_{\text{From
regularizer}}.$ (A.5)

We assume that ${\ddot{\phi}}(z)\geq 0\,\forall z$, as is the case for the
corner rounded 1-norm. If ${\bm{A}}^{\prime}{\bm{A}}$ is positive-definite
with $\sigma_{N}({\bm{A}}^{\prime}{\bm{A}})>0$ (this is equivalent to $\bm{A}$
having full column rank), then the Hessian is positive-definite and
$\mu_{{\bm{x}},\Upphi}=\sigma_{N}^{2}({\bm{A}})$ suffices as a strong
convexity parameter.

In applications like compressed sensing, $\bm{A}$ does not have full column
rank. In such cases, $\sigma_{N}({\bm{A}}^{\prime}{\bm{A}})=0$ and as
$e^{\beta_{0}}\rightarrow 0$ the regularizer term vanishes, so there does not
exist any universal $\mu_{{\bm{x}},\Upphi}>0$ for all
${\bm{\upgamma}}\in\mathbb{F}^{R}$, so the strong convexity condition
A$\Upphi$ 3 is not satisfied. However, the condition is likely to hold in
practice for “good” values of $\bm{\upgamma}$. Specifically, the condition
will hold for any value of $\bm{\upgamma}$ such that the null-space of the
regularization term is disjoint from the null-space of $\bm{A}$ and the
regularization parameters are sufficiently large. To interpret this condition,
recall that regularization helps compensate for the under-determined nature of
$\bm{A}$ (Section 2.1). Values of $\bm{\upgamma}$ that do not sufficiently
“fill-in” the null-space of $\bm{A}$ will leave the lower-level cost function
under-determined; the task-based nature of the bilevel problem should
discourage these “bad” values. Nevertheless, how to adapt the complexity
theory to rigorously address these subtleties is an open question.

The fourth condition, A$\Upphi$ 4, is that
$\nabla_{{\bm{x}}{\bm{x}}}\Upphi({\bm{x}}\,;{\bm{\upgamma}})$ and
$\nabla_{{\bm{\upgamma}}{\bm{x}}}\Upphi({\bm{x}}\,;{\bm{\upgamma}})$ are
Lipschitz continuous with respect to $\bm{x}$ for all $\bm{\upgamma}$. For the
first part part, a Lipschitz constant results from bounding the difference in
the Hessian evaluated at two points, ${\bm{x}}^{(1)}$ and ${\bm{x}}^{(2)}$:

$\displaystyle\left\lVert\nabla_{{\bm{x}}{\bm{x}}}\Upphi({\bm{x}}^{(1)}\,;{\bm{\upgamma}})-\nabla_{{\bm{x}}{\bm{x}}}\Upphi({\bm{x}}^{(2)}\,;{\bm{\upgamma}})\right\rVert_{2}$
$\displaystyle\quad\quad=\left\lVert
e^{\beta_{0}}\sum_{k}e^{\beta_{k}}{\bm{C}}_{k}^{\prime}\text{diag}({\ddot{\phi}}.({\bm{c}}_{k}\circledast{\bm{x}}^{(1)})-{\ddot{\phi}}({\bm{c}}_{k}\circledast{\bm{x}}^{(2)})){\bm{C}}_{k}\right\rVert_{2}.$

Since every element of $\ddot{\phi}$is bounded in $(0,L_{\dot{\phi}})$, the
difference between any two evaluations of $\ddot{\phi}$is at most
$L_{\dot{\phi}}$. Thus

$\displaystyle\left\lVert\nabla_{{\bm{x}}{\bm{x}}}\Upphi({\bm{x}}^{(1)}\,;{\bm{\upgamma}})-\nabla_{{\bm{x}}{\bm{x}}}\Upphi({\bm{x}}^{(2)}\,;{\bm{\upgamma}})\right\rVert_{2}$
$\displaystyle\leq
e^{\beta_{0}}L_{\dot{\phi}}\sum_{k}e^{\beta_{k}}\left\lVert{\bm{C}}_{k}^{\prime}{\bm{C}}_{k}\right\rVert_{2}$
$\displaystyle\leq
e^{\beta_{0}}L_{\dot{\phi}}\sum_{k}e^{\beta_{k}}\left\lVert{\bm{c}}_{k}\right\rVert^{2}_{2}.$

The final simplification again uses (A.4). Thus,
$L_{{\bm{x}},\nabla_{{\bm{x}}{\bm{x}}}\Upphi}=e^{\beta_{0}}L_{\dot{\phi}}\sum_{k}e^{\beta_{k}}\left\lVert{\bm{c}}_{k}\right\rVert^{2}_{2}$.

For the second part of A$\Upphi$ 4, we must look at the tuning parameters
and filter coefficients separately. When considering learning a tuning
parameter, $\beta_{k}$,

$\displaystyle\nabla_{\beta_{k}{\bm{x}}}\Upphi({\bm{x}}\,;{\bm{\upgamma}})$
$\displaystyle=e^{\beta_{0}+\beta_{k}}{\bm{C}}_{k}^{\prime}{{\dot{\phi}}}.({\bm{C}}_{k}{\bm{x}}).$

To find a Lipschitz constant, consider the gradient with respect to $\bm{x}$:

$\displaystyle\nabla_{\bm{x}}\left(\nabla_{\beta_{k}{\bm{x}}}\Upphi({\bm{x}}\,;{\bm{\upgamma}})\right)$
$\displaystyle=e^{\beta_{0}+\beta_{k}}{\bm{C}}_{k}^{\prime}\text{diag}({\ddot{\phi}}.({\bm{C}}_{k}{\bm{x}})){\bm{C}}_{k}.$

A Lipschitz constant of
$\nabla_{\beta_{k}{\bm{x}}}\Upphi({\bm{x}}\,;{\bm{\upgamma}})$ is given by the
bound on the norm of this matrix (we chose to use the matrix 2-norm, also
called the spectral norm). Using similar steps as above to simplify the
expression,
$L_{{\bm{x}},\nabla_{\beta_{k}{\bm{x}}}\Upphi}=e^{\beta_{0}+\beta_{k}}L_{\dot{\phi}}\left\lVert{\bm{c}}_{k}\right\rVert^{2}_{2}$.

When considering learning the $s$th element of the $k$th filter,

$\displaystyle\nabla_{c_{k,s}{\bm{x}}}\Upphi({\bm{x}}\,;{\bm{\upgamma}})$
$\displaystyle=e^{\beta_{0}+\beta_{k}}\left({{\dot{\phi}}}.(({\bm{C}}_{k}{\bm{x}})^{\langle
s\rangle})+{\bm{C}}_{k}^{\prime}\left({\ddot{\phi}}.({\bm{C}}_{k}{\bm{x}})\odot{\bm{x}}^{\langle
s\rangle}\right)\right)$
$\displaystyle=e^{\beta_{0}+\beta_{k}}\left(\underbrace{{{\dot{\phi}}}.({\bm{R}}{\bm{C}}_{k}{\bm{x}})}_{\text{Expression
1}}+\underbrace{{\bm{C}}_{k}^{\prime}\left({\ddot{\phi}}.({\bm{C}}_{k}{\bm{x}})\odot{\bm{R}}{\bm{x}}\right)}_{\text{Expressions
2-3}}\right)\in\mathbb{F}^{N},$

where $\bm{R}$ is a rotation matrix that depends on $s$ such that
${\bm{R}}{\bm{x}}={\bm{x}}^{\langle s\rangle}$. For taking the gradient, it is
convenient to note that the last term can be expressed in multiple ways:

${\ddot{\phi}}.({\bm{C}}_{k}{\bm{x}})\odot{\bm{x}}^{\langle
s\rangle}=\underbrace{\text{diag}({\ddot{\phi}}.({\bm{C}}_{k}{\bm{x}})){\bm{x}}^{\langle
s\rangle}}_{\mathrm{Expression\,2}}=\underbrace{\text{diag}({\bm{x}}^{\langle
s\rangle}){\ddot{\phi}}.({\bm{C}}_{k}{\bm{x}})}_{\mathrm{Expression\,3}}.$

Using the alternate expressions to perform the chain rule with respect to the
$\bm{x}$ that is not in the $\text{diag}(\cdot)$ statement, the gradient with
respect to $\bm{x}$ is:

$\displaystyle\nabla_{\bm{x}}\left(\nabla_{c_{k,s}{\bm{x}}}\Upphi({\bm{x}}\,;{\bm{\upgamma}})\right)=e^{\beta_{0}+\beta_{k}}($
$\displaystyle\underbrace{{\bm{C}}_{k}^{\prime}{\bm{R}}^{\prime}\text{diag}({\ddot{\phi}}.({\bm{R}}{\bm{C}}_{k}{\bm{x}}))}_{\mathrm{Expression\,1}}$
$\displaystyle+\underbrace{{\bm{C}}_{k}^{\prime}\text{diag}({\ddot{\phi}}.({\bm{C}}_{k}{\bm{x}}))}_{\mathrm{Expression\,2}}$
$\displaystyle+\underbrace{{\bm{C}}_{k}^{\prime}\text{diag}(\dddot{\phi}({\bm{C}}_{k}{\bm{x}}))\text{diag}({\bm{R}}{\bm{x}})^{\prime}{\bm{C}}_{k}}_{\mathrm{Expression\,3}}).$

The bound on the spectral norm of the first and second expressions are both
$\sigma_{1}({\bm{C}}_{k})L_{\dot{\phi}}$ because, for any
${\bm{z}}\in\mathbb{F}^{N}$,

$\left\lVert\text{diag}({\ddot{\phi}}.({\bm{z}}))\right\rVert_{2}\leq\max_{z}\lvert{\ddot{\phi}}(z)\rvert=L_{\dot{\phi}}.$

The third expression is bounded by
$\sigma_{1}^{2}({\bm{C}}_{k})\left\lVert{\bm{x}}\right\rVert L_{\ddot{\phi}}$,
which requires a bound on the norm of $\bm{x}$, similar to A$\ell$ 2. Summing
the three expressions and including the tuning parameters gives the final
Lipschitz constant

$L_{{\bm{x}},\nabla_{c_{k,s}{\bm{x}}}\Upphi}=e^{\beta_{0}+\beta_{k}}\sigma_{1}({\bm{C}}_{k})(2L_{\dot{\phi}}+\sigma_{1}({\bm{C}}_{k})L_{\ddot{\phi}}\left\lVert{\bm{x}}\right\rVert).$
(A.6)

The fifth assumption, A$\Upphi$ 5 states that the mixed second gradient of
$\Upphi$ is bounded. For the tuning parameters, the mixed second gradient is
given in (4.9) as

$\nabla_{\beta_{k}{\bm{x}}}\Upphi({\bm{\hat{x}}}\,;{\bm{\upgamma}})=e^{\beta_{0}}e^{\beta_{k}}\tilde{{\bm{c}}}_{k}\circledast{{\dot{\phi}}}.({\bm{c}}_{k}\circledast{\bm{\hat{x}}}).$

The bound given in Section 5.1.1 follows easily by considering that

$\left\lVert\text{diag}({{\dot{\phi}}}.({\bm{c}}_{k}\circledast{\bm{\hat{x}}}))\right\rVert_{2}\leq\max_{z}\lvert{{\dot{\phi}}}(z)\rvert=L_{\phi}.$

For a filter coefficient, the mixed second gradient is more complicated:

$\nabla_{c_{k,s}{\bm{x}}}\Upphi({\bm{\hat{x}}}\,;{\bm{\upgamma}})=e^{\beta_{0}+\beta_{k}}\left(\underbrace{{{\dot{\phi}}}.(({\bm{c}}_{k}\circledast{\bm{\hat{x}}})^{\langle
s\rangle})}_{\text{Bounded by
$L_{\phi}$}}+\tilde{{\bm{c}}}_{k}\circledast\left(\underbrace{{\ddot{\phi}}.({\bm{c}}_{k}\circledast{\bm{\hat{x}}})}_{\text{Bounded
by $L_{\dot{\phi}}$}}\odot{\bm{\hat{x}}}^{\langle s\rangle}\right)\right).$

Under the assumption that the bounds $L_{\phi}$ and $L_{\dot{\phi}}$ exist
(they are $1$ and $\frac{1}{\epsilon}$ respectively for (CR1N)), a bound on
the norm of the mixed gradient is

$\displaystyle\left\lVert\nabla_{c_{k,s}{\bm{x}}}\Upphi({\bm{\hat{x}}}\,;{\bm{\upgamma}})\right\rVert$
$\displaystyle\leq
e^{\beta_{0}+\beta_{k}}\left(L_{\phi}+L_{\dot{\phi}}\left\lVert{\bm{c}}_{k}\right\rVert\left\lVert{\bm{x}}\right\rVert\right).$

The sixth assumption, A$\Upphi$ 6, is that
$L_{{\bm{\upgamma}},\nabla_{{\bm{\upgamma}}{\bm{x}}}\Upphi}$ and
$L_{{\bm{\upgamma}},\nabla_{{\bm{x}}{\bm{x}}}\Upphi}$ exist. Lipschitz
constants for the tuning parameters are

$L_{\beta_{k},\nabla_{\beta_{k}{\bm{x}}}\Upphi}=e^{\beta_{0}+\beta_{k}}\left\lVert{\bm{c}}_{k}\right\rVert_{2}L_{\phi}\text{
and
}L_{\beta_{k},\nabla_{{\bm{x}}{\bm{x}}}\Upphi}=e^{\beta_{0}+\beta_{k}}\left\lVert{\bm{c}}_{k}\right\rVert^{2}_{2}L_{\dot{\phi}}.$

Using similar derivations as shown above, corresponding Lipschitz constants
for the filter coefficients are

$\displaystyle L_{c_{k,s},\nabla_{c_{k,s}{\bm{x}}}\Upphi}$
$\displaystyle=e^{\beta_{0}+\beta_{k}}\left(L_{\phi}+\left\lVert{\bm{x}}\right\rVert\left(L_{\dot{\phi}}+L_{\ddot{\phi}}\left\lVert{\bm{c}}_{k}\right\rVert\left\lVert{\bm{x}}\right\rVert\right)\right)$
$\displaystyle L_{c_{k,s},\nabla_{{\bm{x}}{\bm{x}}}\Upphi}$
$\displaystyle=e^{\beta_{0}+\beta_{k}}\left(2L_{\dot{\phi}}\left\lVert{\bm{c}}_{k}\right\rVert+L_{\ddot{\phi}}\left\lVert{\bm{c}}_{k}\right\rVert^{2}\left\lVert{\bm{x}}\right\rVert\right).$

This is the last lower-level condition.


# Causal Emergence in Quantum Mechanics

Romeu Rossi Jr<EMAIL_ADDRESS>Federal University of Viçosa (UFV) - Campus
Florestal, LMG818 Km6, Minas Gerais, Florestal, Brazil  Leonardo A. M. Souza
<EMAIL_ADDRESS>Federal University of Viçosa (UFV) - Campus Florestal,
LMG818 Km6, Minas Gerais, Florestal, Brazil

###### Abstract

Causal emergence is brought about when a coarse-grained description of a
physical system is more effective (more deterministic and/or less degenerate)
than the fine-grained corresponding model. We show, for the first time to our
knowledge, a causal emergence in a quantum system: a atomic Mach-Zehnder
interferometer with two which-path detectors. The atomic wave-like or
particle-like descriptions are related, respectively, to _coarse-grained_ and
_fine-grained_ models. The predictions of the atomic position after the
passage through the interferometer when the to _coarse-grained_ description is
considered are more effective than the corresponding _fine-grained_ model. We
conclude that quantum eraser measurements yields the causal emergence in this
system.

Causality; Causal Emergence

Generally it is assumed that once a fine-grained, detailed and exhaustive
description of a physical system is formulated, all the features of a
corresponding coarse-grained model are also established. This assumption is
based on the idea that fine-grained descriptions can capture the essence of
the phenomena, whereas by coarse-graining the result would leat to a lost of
predictive and descriptive power. In some cases, when a fine-grained
description is not yet available, a coarse-grained model is employed for
practical purpose. Nevertheless, one can consider that the aim of scientific
research is to unveil the detailed structure of the phenomena through fine-
grained description.

Recently E.P. Hoel et. al. pnas  have shown that this reductionist approach
can not be considered as a general feature of scientific explanation. They
have introduced a quantity, so called Effective Information (EI) defEI , that
measure _the effectiveness degree of a theoretical model_ , and also they
showed some examples in which a coarse-grained description is more effective
(more deterministic and/or less degenerate) than the fine-grained
corresponding modelcom . The authors call this feature “Causal Emergence”.

In the mentioned work pnas , causal models are employed in order to make the
comparison between fine and coarse-grained descriptions. A causal explanation
of a phenomena can be formulated with different levels of details, in relation
to the number of variables used in the causal description, or to the time
scale considered in the evolution of the system. A detailed causal model,
associated to a fine-grained description of a system, determines the structure
of the causal model of the corresponding less detailed model, that is
constructed by coarse-graining the first structure. However, as shown in pnas
; ent , the EI calculated to the coarse-grained description can exceed the
value of EI for the corresponding fine-grained causal model. Their conclusion
implies, at least for the examples studied in pnas , that the effectiveness of
the theoretical model of the coarse-grained description can be greater than
the fine-grained.

The systematic approach to causality given by the theory of causal Bayesian
network pearl  made this a topic of increasing interest among physicists. The
possibility of applying causal models in quantum systems is a current subject
of debate in the literature, examples of incompatibility between causal models
and quantum systems are shown in References rossi ; wood , and in Reference
chaves  it was shown a quantum system that is compatible with causal
description. Alternative approaches that aim to formulate causal models more
suitable for quantum systems have also been considered in the Literature art1
; art2 ; art3 ; art4 ; art5 ; art6 ; art7 .

In the study of causal emergence, a causal model can, as mentioned explicitly
here, “represent state transitions, like Markov chains, or may represent the
influence or connectivity of elements, such as circuit diagrams, directed
graphs (also called causal Bayesian networks), networks of interconnected
mechanisms, or neuron diagrams”ent . These causal models are well suitable to
describe classical systems, and rigorous investigations on the adequacy of the
use of causal models in the representation of the present quantum system is
not part of the scope of this work. Here, we consider a classical causal model
(Markov chain) in which the states are composed by classical variables whose
values are determined by the results of measurements in the quantum system.
The value of these variables in the initial state are defined by the quantum
state preparation. The transition probabilities, which are indicated in the
Markov chains, are given by quantum evolution of the initial state. It is
important to notice that the Markov chains considered here are not quantum
Markov chains.

Here we show, for the first time to our knowledge, a causal emergence yield by
quantum features. We consider a Mach Zehnder interferometer with two which-
path detector and show that probabilities corresponding to atomic wave-like or
particle-like behaviour constitute a case of causal emergence.

We consider two causal models, a fine-grained and a coarse-grained, for the
same experimental setup. Each model responds differently for the classical
question: “what is the trajectory of a photon in a Mach-Zehnder
interferometer?” In the fist model, three variables are considered and they
completely reveal the which-path information. We call this the fine-grained
description. In the second model, only two variables are considered and the
which-path information is not completely given, and we call this description
the coarse-grained one. We show that a genuine quantum effect, the quantum
eraser, can bring about causal emergency. In this system the coarse-grained
description is more effective (more deterministic and/or less degenerate) than
the fine-grained with respect to the prediction of the atomic position after
the passage through the interferometer.

This contribution is organized as follow: in section I we introduce the
notions of causal emergence that we will use throughout the paper; in section
II we detail the physical system we are interested; in sections III and IV we
show our results explicitly, for the fine and coarse-grained description of
our model, respectively. Finally, in section V we conclude our work, and give
some perspectives within this approach.

##  I Causal Emergence

To characterize a causal emergence, causal models that corresponds to fine-
grained and coarse-grained descriptions need to be considered. A quantitative
analysis of the causal effectiveness of each model must be performed and a
causal emergence occurs when the effectiveness calculated to the coarse-
grained model is greater than the effectiveness of the fine-grained model.

In the quantitative analysis we considered a system $S$, composed by classical
random variables that are relevant to the description. A particular state of
$S$ is represented by $s_{i}$. To measure causal effectiveness, the
statistical relations between the initial state ($s_{0}$) and the state at a
later instant ($s_{F}$) are studied. The initial state is set by interventions
represented by the operator $do(s_{0})$ (defined in pearl ).

In Ref. pnas , state-dependent and state-independent investigations are given.
In the first case, the quantity used to measure causal effectiveness is the
“effect information” ($Ei$) that is defined as:

$Ei(s_{0})=D_{KL}(p(s_{F}|do(s_{0}))||p(s_{F}))=\sum_{s_{F}}p(s_{F}|do(s_{0}))\log_{2}\frac{p(s_{F}|do(s_{0}))}{p(s_{F})},$
(1)

where $D_{KL}$ is the Kullback-Leibler divergence kull  that measures the
difference between two probability distributions, in the present case between
the constrained and unconstrained probabilities of $s_{F}$. It has been proven
that $Ei(s_{0})$ can be written as a function of the “determinism coefficient”
and the “degeneracy coefficient” (proof and the definitions of the
coefficients are detailed in Reference pnas ), which correspond respectively
to: (i) determinism coefficient $\rightarrow$ a measure of how
deterministically the evolution of $s_{0}$ will bring the system to the state
$s_{F}$; (ii) degeneracy coefficient $\rightarrow$ how exclusive is the state
transition from $s_{0}$ to $s_{F}$. For a given model, higher values of
$Ei(s_{0})$ indicate that the model is more deterministic and less
degenerated.

In the state-independent analysispnas , the quantity called “effective
information” ($EI$) is used. It is defined as the mean value of effect
information over all initial states $s_{0}$:

$EI=\sum_{s_{0}}p(do(s_{0}))D_{KL}(p(s_{F}|do(s_{0}))||p(s_{F}))=\sum_{s_{0},s_{F}}p(do(s_{0}))p(s_{F}|do(s_{0}))\log_{2}\frac{p(s_{F}|do(s_{0}))}{p(s_{F})},$
(2)

In this work we have used the quantities mentioned in this section in order to
study the physical model detailed in the next section.

##  II The Quantum System

The quantum system we study here is composed by a two level atom that goes
through a Mach-Zehnder interferometer with two which-path detectors, as it is
shown in Figure 1. The detectors are two QED cavities ($C_{1}$ and $C_{2}$),
resonant with the atomic transition, as in the first quantum eraser gedanken
experiment scully . The cavities are prepared in the vacuum state and the atom
in the excited state, while the interaction time is chosen such that the atom
makes a transition to the ground level when passing through the cavity. Atomic
which-path information is available in the entangle state after the
interaction with the cavities. The atoms are detected in each exit of the
second beam splitter by the atomic detector $D_{1}$ and $D_{2}$. The detection
probabilities (in $D_{1}$ and $D_{2}$) characterizes the wave-like or
particle-like phenomena: they depend on the measurements performed in the
cavities subsystem. Following the definitions given in Ref. bergou , two types
of measurement are of particular interest: which-alternative measurement and
the quantum-erasure measurement. The first aims to reveal information about
the atomic path, therefore it yield atomic detection probabilities that are
associated with particles-like behavior. The latter aims to increase the
visibility in the atomic subsystem, it produces atomic detection probabilities
that are associated with wave-like behavior.

A detailed description can be written as follows: the source S emits two level
atoms (prepared initially in the excited state $|e_{a}\rangle$) into the Mach-
Zehnder interferometer, along the direction denoted by $|1_{a}\rangle$ or
$|2_{a}\rangle$, with equal probability, as shown in Figure 1. The interaction
time between the atom and each cavity correspond to a $\pi$ pulse, therefore,
after the interaction with the cavity modes the atomic excitation is
transferred to the cavities subsystem. The photon number in each cavity mode
reveal the atomic which-path information, where the state
$|1_{C_{1}},0_{C_{2}}\rangle$ ($|0_{C_{1}},1_{C_{2}}\rangle$) is associated
with the atomic path $|1_{a}\rangle$ ($|2_{a}\rangle$).

Figure 1: Detailed system. A Mach-Zehnder interferometer with a which-path
detector ($C_{1}$ and $C_{2}$) in each arm.

When the system is prepared in the initial state
$|\psi(0)\rangle=|e_{a}\rangle|1_{a},0_{C_{1}},0_{C_{2}}\rangle$ the state of
the global system after the second beam splitter and before the atomic
detection is:

$|\psi(t)\rangle_{1}=\frac{1}{2}\left[-|1_{a}\rangle\left(e^{i\phi}|1_{C_{1}},0_{C_{2}}\rangle+|0_{C_{1}},1_{C_{2}}\rangle\right)+i|2_{a}\rangle\left(e^{i\phi}|1_{C_{1}},0_{C_{2}}\rangle-|0_{C_{1}},1_{C_{2}}\rangle\right)\right].$
(3)

On the other hand, when the system is prepared in the initial state
$|\psi(0)\rangle=|e_{a}\rangle|2_{a},0_{C_{1}},0_{C_{2}}\rangle$, the state
(before atomic detection) is:

$|\psi(t)\rangle_{2}=\frac{1}{2}\left[i|1_{a}\rangle\left(-e^{i\phi}|1_{C_{1}},0_{C_{2}}\rangle+|0_{C_{1}},1_{C_{2}}\rangle\right)-|2_{a}\rangle\left(e^{i\phi}|1_{C_{1}},0_{C_{2}}\rangle+|0_{C_{1}},1_{C_{2}}\rangle\right)\right],$
(4)

We consider $\phi=0$ and omit the atomic excitation degree of freedom in (3)
and (4) since this term is factored throughout the evolution.

After the interaction with the atom, the excitation is transferred to the
cavities subsystem, that were initially in the vacuum state. The subsystem
$(C_{1},C_{2})$ is then restricted to the one excitation subspace
$\\{|1_{C_{1}},0_{C_{2}}\rangle,|0_{C_{1}},1_{C_{2}}\rangle\\}$, and Pauli
matrices can be defined for this two level subsystem. We consider, in the
cavities subsystem, the observable:

$\hat{\sigma}=\vec{n}\cdot\vec{\sigma},$ (5)

where $\vec{n}=\left(\sin 2\theta~{}\cos 2\theta,~{}\sin 2\theta~{}\sin
2\theta,~{}\cos 2\theta\right)$ and
$\vec{\sigma}=\left(\sigma_{x},~{}\sigma_{y},~{}\sigma_{z}\right)$ are the
Pauli spin operators within the two cavities subsystem. The eigenvectors and
eigenvalues of $\hat{\sigma}$ are:

$\displaystyle\hat{\sigma}|M_{+}\rangle$ $\displaystyle=$
$\displaystyle|M_{+}\rangle$ (6) $\displaystyle\hat{\sigma}|M_{-}\rangle$
$\displaystyle=$ $\displaystyle-|M_{-}\rangle,$ (7)

where
$|M_{+}\rangle=\alpha|1_{C_{1}},0_{C_{2}}\rangle+e^{i\gamma}\beta|0_{C_{1}},1_{C_{2}}\rangle$,
$|M_{-}\rangle=\beta|1_{C_{1}},0_{C_{2}}\rangle-e^{i\gamma}\alpha|0_{C_{1}},1_{C_{2}}\rangle$,
with $\alpha=\cos\theta$ and $\beta=\sin\theta$.

In the cavities subsystem, which-alternative and the quantum-erasure
measurements may be performed. Formally, the quantity $K(\sigma)$, defined in
Ref. bergou , is a quantitative measure of what one can learn about the which-
way information from a measurement of the observable $\sigma$. For the present
system:

$K(\sigma)=|\cos 2\theta|.$ (8)

A which-alternative measurement corresponds to $\theta=0,~{}\pi/2$, when the
maximum which-way information is revealed. When $\theta=\pi/4$, a measurement
of $\sigma$ gives no information about the alternative of the atomic
“trajectory” (where by trajectory we the mean arms $1$ or $2$), and this is
called a quantum-erasure measurement.

##  III Fine-Grained Description

First we analyse a description that reveals, at each step of the evolution in
the interferometer of Figure 1, which path the atom takes. For this purpose,
one must consider the case of which-alternative measurement, where
$\theta=0,~{}\pi/2$. Therefore, the observable is
$\hat{\sigma}=\hat{\sigma_{z}}$, and the eigenstates that correspond to the
measurement results $1$ and $-1$ are, respectively,
$|1_{C_{1}},0_{C_{2}}\rangle$ and $|0_{C_{1}},1_{C_{2}}\rangle$. After a
measurement of the observable $\hat{\sigma}=\hat{\sigma_{z}}$, the number of
excitations in $C_{1}$ and $C_{2}$, and consequently the atomic path, are
known. For both results ($1$ or $-1$) the atomic detection probabilities in
$D_{1}$ or $D_{2}$ are $P(D_{1})=P(D_{2})=0.5$. We will show that, for this
case, such uncertainty about the detection possibilities imply a zero value
for the Effective Information (EI).

Formally, we consider that, after the measurement in the cavities, each result
is associated with a binary classical variable $\mathbf{c_{1}}=\\{0,1\\}$ and
$\mathbf{c_{2}}=\\{0,1\\}$ which express the value of the number of
excitations measured in each cavity. A detection of an excitation in one
cavity, which corresponds to $\mathbf{c_{1}}=1$ or $\mathbf{c_{2}}=1$, imply
the revelation of the path the atom takes after the first beam splitter. This
description, that considers $\mathbf{c_{1}}$ and $\mathbf{c_{2}}$, is here
classified as _fine-grained_ , because it holds two variables that allows the
knowledge of the atomic path (between the first and second beam splitter), in
opposition to the coarse-grained description (considered later in this work),
that holds a number of variables that is insufficient to reveal such
knowledge.

We also define a classical variable $\mathbf{a}=\\{1,2\\}$ that is associated
to the atomic position in the preparation stage and after the measurement: the
first one corresponds to the input direction $1$ or $2$ shown in Figure 1; the
latter corresponds to a detection in $D_{1}$ or $D_{2}$. The atomic excitation
degree of freedom can be ignored in this analysis.

The possible initial states are:
$s_{0}=\\{(a(0)=1,c_{1}(0)=0,c_{2}(0)=0),(a(0)=2,c_{1}(0)=0,c_{2}(0)=0)\\}$
and the possible final states are
$s_{F}=\\{(a(t)=1,c_{1}(t)=1,c_{2}(t)=0),(a(t)=1,c_{1}(t)=0,c_{2}(t)=1),(a(t)=2,c_{1}(t)=1,c_{2}(t)=0),(a(t)=2,c_{1}(t)=0,c_{2}(t)=1)\\}$.
The probability distribution of $s_{0}$ is $p(do(s_{0}))=0.5$, which
correspond to the preparation of all initial states with the same probability
(as required in Ref. pnas ). Each classical state of $s_{0}$ and $s_{F}$ is
associated to a quantum states
$|\psi(0)\rangle=|a(0),c_{1}(0),c_{2}(0)\rangle$ or
$|\psi(t)\rangle=|a(t),c_{1}(t),c_{2}(t)\rangle$ where the values of $a$,
$c_{1}$ and $c_{2}$ are equal to the corresponding values of the classical
variables in the initial and final classical states. Notice that this complete
correspondence between classical and quantum states are considered only after
a measurement or a preparation of the system, during the evolution (in the
time between a preparation and a measurement) the quantum states have no
correspondence with classical states. The Markov chain associated is
represented in Figure 2.

Figure 2: Markov chain associated with a _fine-grained_ description of our
model.

Quantum theory is used in the calculation of the conditional probability
distribution. It gives the result
$p(s_{F}|do(s_{0}))=|\langle\psi(t)|U|\psi(0)\rangle|^{2}=1/4$, which is equal
(in this case) to the final state probability distribution
$p(s_{F})=\sum_{s_{0}}p(s_{F}|do(s_{0}))p(do(s_{0}))=1/4$. Therefore, the
_fine-grained_ description results:

$Ei(s_{0})=\sum_{s_{F}}p(s_{F}|do(s_{0}))\log_{2}\frac{p(s_{F}|do(s_{0}))}{p(s_{F})}=0,$
(9)

and consequently $EI=0$. This result should be compared with the _coarse-
grained_ description, detailed hereafter.

##  IV Coarse-Grained Description

In this section we consider measurements of the observable $\hat{\sigma}$ with
$0<\theta<\pi/2$. In this case, which-alternative information is not
completely revealed, for instance, when $\theta=\pi/4$ any which-alternative
information is completely removed (a quantum-erasure measurement), and the
interference pattern can, therefore, be reconstructed. We show that the
evolution of a quantum system in a Mach-Zehnder interferometer, when a
quantum-erasure measurement is performed, corresponds to a model in which the
value of $EI$ is maximum. In addition, we also show that this system is
associated to a _coarse-grained_ description. These results, when compared to
the ones shown in the last section, reveal causal emergence in a quantum
system.

Formally, the _coarse-grained_ model is constructed from the substitution of
the two variables $\mathbf{c_{1}}$ and $\mathbf{c_{2}}$ by a single variable
$\mathbf{c}$. The classical variable $\mathbf{c}=\\{0,1\\}$ represents the
results of a measurement of the excitation number in the cavities subsystem.
Notice that when $\mathbf{c}=0$ both cavities are empty. However, when
$\mathbf{c}=1$ one of the cavities has a single photon but it is not possible
to identify in which cavity whatsoever. We also consider the variable
$\mathbf{a}=\\{1,2\\}$, defined in the previous section, associated to the
atomic position in the preparation stage and after the measurement.

The possible initial sates are: $s_{0}=\\{(a(0)=1,c(0)=0),(a(0)=2,c(0)=0)\\}$
and the possible final states are $s_{F}=\\{(a(t)=1,c(t)=1)$ and
$(a(t)=2,c(t)=1)$. As in the previous section, the probability distribution of
$s_{0}$ is $p(do(s_{0}))=0.5$, which correspond to the preparation of all
initial states with the same probability (as required in pnas ). Each
classical state of $s_{0}$ and $s_{F}$ is associated to a quantum states
$|\psi(0)\rangle=|a(0),c(0)\rangle$ or $|\psi(t)\rangle=|a(t),c(t)\rangle$
where the values of $a$ and $c$ are equal to the corresponding values of the
classical variables in the initial and final classical states.

As it is done in quantum eraser experiments and models scully ; souza2013 ;
walborn ; Rueckner ; Torres ; ma , let us analyze separately fringes and anti-
fringes: if a measurement of $\hat{\sigma}$ gives the result $1$, fringes are
obtained. When $\theta=\pi/4$, $\gamma=0$ and $\phi=0$ the conditional
probabilities $p(s_{F}|do(s_{0}))=|\langle\psi(t)|U|\psi(0)\rangle|^{2}$ are:

$\displaystyle p(s_{F}=1,1|s_{0}=1,0)$ $\displaystyle=$ $\displaystyle 1,$
(10) $\displaystyle p(s_{F}=2,1|s_{0}=1,0)$ $\displaystyle=$ $\displaystyle
0,$ (11) $\displaystyle p(s_{F}=1,1|s_{0}=2,0)$ $\displaystyle=$
$\displaystyle 0,$ (12) $\displaystyle p(s_{F}=2,1|s_{0}=2,0)$
$\displaystyle=$ $\displaystyle 1.$ (13)

The values of these probabilities reflect the quantum eraser, and the
interference pattern is reconstructed when the which-path information is
erased. In the Mach-Zehnder interferometer shown in Figure 1, with equal
optical path length ($\phi=0$), an atom sent in direction $a(0)=1$ ($a(0)=2$)
will exit in the direction $a(t)=1$ $(a(t)=2)$, characterizing the
interference pattern of this system. The probabilities
$p(s_{F})=\sum_{s_{0}}p(s_{F}|do(s_{0}))p(do(s_{0}))$ are:

$\displaystyle p(s_{F}=1,1)$ $\displaystyle=$ $\displaystyle 0.5,$ (14)
$\displaystyle p(s_{F}=2,1)$ $\displaystyle=$ $\displaystyle 0.5.$ (15)

Therefore, the Effect Information and the Effective Information are,
respectively, $Ei(s_{0})=1$ and $EI=1$ for the _coarse-grained_ description.
The values are greater than the values of $Ei$ and $EI$ calculated for the
_fine-grained_ model, an explicity expression of causal emergence in the
present quantum system. The wave-like behavior allow us to construct a more
deterministic and/or less degenerate causal model (show in Figure 3), and this
behavior is recovered by _coarse-graining_ the first description, or in other
words by erasing which-path information. The quantum eraser phenomena plays a
constitutive role in this case of causal emergence: it is responsible for the
recovery of the wave-like behavior, and correspondingly to a coarse-grained
description.

Figure 3: Markov chain associated with a _coarse-grained_ description of our
model.

We consider now a general case, with no specific values of $\theta$, and show
that causal emergence also arises. We can associate a measurement of the
operator $\hat{\sigma}$ with result $\\{1\\}(\\{-1\\})$ returning fringes
(anti-fringes). Let us consider fringes and the initial state
$s_{0}=(a(0)=1,c(0)=0)$. The conditional probabilities
$p(s_{F}|do(s_{0}))=|\langle\psi(t)|U|\psi(0)\rangle|^{2}$ are:

$\displaystyle p(s_{F}=1,1|s_{0}=1,0)$ $\displaystyle=$
$\displaystyle\left|\frac{-e^{i\phi}\alpha-e^{-i\gamma}\beta}{N_{1,+}}\right|^{2},$
(16) $\displaystyle p(s_{F}=2,1|s_{0}=1,0)$ $\displaystyle=$
$\displaystyle\left|\frac{e^{i\phi}\alpha-e^{-i\gamma}\beta}{N_{1,+}}\right|^{2},$
(17) $\displaystyle p(s_{F}=2,1|s_{0}=1,0)$ $\displaystyle=$
$\displaystyle\left|\frac{e^{i\phi}\alpha-e^{-i\gamma}\beta}{N_{1,+}}\right|^{2},$
(18) $\displaystyle p(s_{F}=2,1|s_{0}=2,0)$ $\displaystyle=$
$\displaystyle\left|\frac{-e^{i\phi}\alpha-e^{-i\gamma}\beta}{N_{2,+}}\right|^{2}$
(19)

where $\alpha=\cos\theta,\beta=\sin\theta$, and $N_{1,+},N_{2,+}$ are
normalization factors due to measurement processes.

The probabilities for the final states are calculated as
$p(s_{F})=\sum_{s_{0}}p(s_{F}|do(s_{0}))p(do(s_{0}))$. The Effect Information
for the initial state $s_{0}=(a(0)=1,c(0)=0)$ is:

$Ei(s_{0})=\sum_{s_{F}}p(s_{F}|s_{0})\log_{2}\frac{p(s_{F}|s_{0})}{p(s_{F})},$
(20)

and is plotted in Figure 4, in function of $\theta$. In previews sections we
study the cases with $\theta=\pi/2$ (_fine-grained_ description) and $\pi/4$
(_coarse-grained_ description), this cases are associated respectively to the
maximum and minimum value of $K(\sigma)$. Every intermediate value of $\theta$
corresponds also to a coarse-grained description, since the measurements of
the observable $\sigma$ do not reveal complete which-path information in these
cases, and one can not consider a classical causal model with $c_{1}$ and
$c_{2}$ that describes the presence or absence of the atom in each path. The
relation between $Ei(s_{0})$ and $K(\sigma)$ shows that when more which-path
information is given (when $K(\sigma)$ increases) the value of $Ei(s_{0})$
decreases.

Figure 4: Effective Information (EI) in function of $\theta$ for different
values of $\phi$. If $\theta$ is a multiple of $\pi/4(\pi/2)$, the EI aquires
its maximum(minimum) value.

##  V Conclusions

Here we have presented for the first time (to our knowledge) a causal
emergence yield by a quantum system. We consider a Mach-Zehnder interferometer
with two which-path detector. Our results show that probabilities
corresponding to atomic wave-like or particle-like behaviour can be related,
respectively, to _coarse-grained_ and _fine-grained_ models. The which-way
information is completely available in the _fine-grained_ and this makes the
model less effective with respect to the prediction of the position of the
atoms after the passage through the interferometer. For this model, the
coarse-grained description is more effective (more deterministic and/or less
degenerate) than the fine-grained. Our work paves way to further discussions
related to causal emergency and fine/coarse-graining of multipartite systems
in (closed and open) quantum systems, and how this concept can be tested.

###### Acknowledgements.

The authors thanks Brazilian agencies CNPq and FAPEMIG for finantial support.
LAMS also acknowledges INCT-IQ.

## References

  * (1) E. P. Hoel, L. Albantakis, G. Tononi, Quantifying causal emergence shows that macro can beat micro, Proceedings of the National Academy of Sciences 110, 19790 (2013).
  * (2) G. Tononi, O. Sporns, Measuring information integration, BMC Neuroscience 4, 31 (2003).
  * (3) In pnas  the authors use the expressions “micro-level” or “macro-level” descriptions, but in the quantum context this could lead to confusion. Therefore, we use alternatively the nomenclature _coarse-grained_ or _fine-grained_ description.
  * (4) E. P. Hoel, When the map is better than the territory, Entropy 19, 188 (2017).
  * (5) J. Pearl, Causality: Models, Reasoning, and Inference. 2nd ed. Cambridge: Cambridge University Press (2009).
  * (6) R. Rossi, Restrictions for the causal inferences in an interferometric system, Physical Review A 96, 012106 (2017).
  * (7) C. J. Wood, R. W. Spekkens, The lesson of causal discovery algorithms for quantum correlations: causal explanations of Bell-inequality violations require fine-tuning, New Journal of Physics 17, 033002 (2015).
  * (8) R. Chaves, G. B. Lemos, J. Pienaar, Causal Modeling the Delayed-Choice Experiment, Physical Review Letters 120, 190401 (2018).
  * (9) R. R. Tucci, Quantum Bayesian Nets, International Journal of Modern Physics B 09, 295 (1995).
  * (10) M. S. Leifer, Quantum dynamics as an analog of conditional probability, Physical Review A 74, 042310 (2006).
  * (11) K. B. Laskey, Quantum Causal Networks, arXiv:0710.1200 [quant-ph].
  * (12) M. S. Leifer, R. W. Spekkens, Towards a formulation of quantum theory as a causally neutral theory of Bayesian inference, Physical Review A 88, 052130 (2013).
  * (13) J. Henson, R. Lal, M. F. Pusey, Theory independent limits on correlations from generalized Bayesian networks, New Journal of Physics 16, 113043 (2014).
  * (14) J. Pienaar, C. Brukner, A graph-separation theorem for quantum causal models, New Journal of Physics 17, 073020 (2015).
  * (15) F. Costa, S. Shrapnel, Quantum causal modelling, New Journal of Physics 18, 063032 (2016).
  * (16) S. Kullback, Information Theory and Statistics, Dover Publications Inc.: Mineola, NY, USA, (1997).
  * (17) M. O. Scully, B. G. Englert, H. Walther, Quantum optical tests of complementarity, Nature 351, 111 (1991).
  * (18) B. G. Englert, J. A. Bergou, Quantitative Quantum Erasure, Optics Communications 179, 337 (2000).
  * (19) R. Rossi, J. P. Souza, L. A. M. Souza, and M. C. Nemes, Multipartite quantum eraser in cavity QED, Physical Review A 88, 062102 (2013).
  * (20) S. P. Walborn, M. O. Terra Cunha, S. Pádua, and C. H. Monken, Double-slit quantum eraser, Physical Review A 65, 033818 (2002).
  * (21) W. Rueckner and J. Peidle, Young’s double-slit experiment with single photons and quantum eraser, American Journal of Physics 81, 951 (2013).
  * (22) F. A. Torres-Ruiz, G. Lima, A. Delgado, S. Pádua, and C. Saavedra, Decoherence in a double-slit quantum eraser, Physical Review A 81, 042104 (2010).
  * (23) X.-a. Ma, J. Kofler, and A. Zeilinger, Delayed-choice gedanken experiments and their realizations, Reviews of Modern Physics 88, 015005 (2016).