$\displaystyle\norm{{\bm{w}}}_{1}\leq\sqrt{d}\norm{{\bm{w}}}_{2}.$ (162)

This result enables us to show that vanishingly small variations in quantum
states correspond to vanishingly small variations in their Wigner
representations:

######  Lemma 19.

If $\norm{\rho-\sigma}_{1}\leq\epsilon$ then for any generalised Gross’s
Wigner representation $W$, we have

$\displaystyle\norm{W_{\rho}-W_{\sigma}}_{1}\leq\sqrt{d}\epsilon.$ (163)

###### Proof.

To simplify notation, we first define the state difference
$\Delta\coloneqq\rho-\sigma$ such that $W_{\Delta}=W_{\rho}-W_{\sigma}$. Since
the Schatten-$p$ norms are non-increasing with respect to $p$ [77], we obtain

$\displaystyle\norm{\rho-\sigma}_{1}$
$\displaystyle\geq\norm{\rho-\sigma}_{2}=\norm{\sum_{\bm{x}}W_{\Delta}({\bm{x}})A_{\bm{x}}}_{2}$
$\displaystyle=\sqrt{\sum_{{\bm{x}},{\bm{y}}}W_{\Delta}^{*}({\bm{x}})W_{\Delta}({\bm{y}})\mathrm{tr}[A_{\bm{x}}^{\dagger}A_{\bm{y}}]}$
$\displaystyle=\sqrt{\sum_{{\bm{x}},{\bm{y}}}W_{\Delta}^{*}({\bm{x}})W_{\Delta}({\bm{y}})d\delta_{{\bm{x}},{\bm{y}}}}$
$\displaystyle=\sqrt{d}\norm{W_{\Delta}}_{2}\geq\frac{1}{\sqrt{d}}\norm{W_{\Delta}}_{1},$
(164)

where in the second inequality we employ Lemma 18. Therefore
$\norm{W_{\rho}-W_{\sigma}}_{1}\leq\sqrt{d}\norm{\rho-\sigma}_{1}$. ∎

######  Lemma 20.

Let $\rho$ and $\sigma$ be two quantum states of a $d$-dimensional qudit such
that $\norm{\rho-\sigma}_{1}\leq\epsilon$. Then given any generalised Gross’s
Wigner representation $W$,

$\displaystyle\absolutevalue{H_{\alpha}[W_{\rho}]-H_{\alpha}[W_{\sigma}]}\leq\frac{\alpha}{\alpha-1}\log[1+\epsilon
d^{\frac{5}{2}}].$ (165)

###### Proof.

Theorem 7 (2) of Ref. [78] applies to quasiprobability distributions and tells
us that for two $d^{2}$-dimensional distributions
${\bm{w}},{\bm{w}}^{\prime}$, we have the following continuity statement on
the $\alpha$-Rényi entropies

$\displaystyle\absolutevalue{H_{\alpha}({\bm{w}})-H_{\alpha}({\bm{w}}^{\prime})}$
$\displaystyle\leq$ $\displaystyle\frac{\alpha}{\alpha-1}$
$\displaystyle\log[1+\norm{{\bm{w}}-{\bm{w}}^{\prime}}_{1}d^{2}].$ (166)

The proof of this just relies on the monotonicity of the $p$-norms
$\norm{{\bm{w}}}_{p}\coloneqq\left(\sum_{i=1}^{d^{2}}\absolutevalue{w_{i}}^{p}\right)^{1/p}$,
i.e., for $1\leq\alpha<\beta\leq\infty$,
$\norm{{\bm{w}}}_{\alpha}\geq\norm{{\bm{w}}}_{\beta}$, which also holds for
quasidistributions. The Lemma result then follows from Lemma 19. ∎

We are now in a position to prove Theorem 9, which we restate here for
clarity:

See 9

###### Proof.

Let $\mu_{k}$ dneote the maximally mixed state of $k$ qudits with Hilbert
space dimension $d$. Following the same proof strategy as that of Lemma 16, we
obtain

$\displaystyle
Q_{\alpha}(W_{\rho_{p}}||W_{\tau_{n,k}})\geq\frac{p^{\alpha}}{d^{(n-k)(1-\alpha)}}Q_{\alpha}(W_{\rho^{\prime}}||W_{\mu_{k}}).$
(167)

Since $\log(\cdot)/(\alpha-1)$ is a monotonically increasing function for
$\alpha>1$, it therefore follows that

$\displaystyle D_{\alpha}(W_{\rho_{p}}||W_{\tau_{n,k}})\geq$
$\displaystyle\frac{1}{\alpha-1}\log\left[\frac{p^{\alpha}}{d^{(n-k)(1-\alpha)}}Q_{\alpha}(W_{\rho^{\prime}}||W_{\mu_{k}})\right]$
$\displaystyle=D_{\alpha}(W_{\rho^{\prime}}||W_{\mu_{k}})+\frac{\alpha}{\alpha-1}\log
p+(n-k)\log d$ $\displaystyle=k\log
d-H_{\alpha}(W_{\rho^{\prime}})+\frac{\alpha}{\alpha-1}\log p+n\log d,$ (168)

where in the final equality we have used the identity
$D_{\alpha}(W_{\rho}||W_{\frac{\mathbbm{1}_{d}}{d}})=2\log
d-H_{\alpha}(W_{\rho})$.

We can now make use of the continuity of the Rényi entropy as stated in Lemma
20 to further lower-bound this divergence as

$\displaystyle D_{\alpha}(W_{\rho_{p}}||$ $\displaystyle W_{\tau_{n,k}})\geq
k\left[\log d-H_{\alpha}(W_{\psi})\right]$
$\displaystyle-\frac{\alpha}{1-\alpha}\log\frac{p}{1+\delta
d^{\frac{5}{2}}}+n\log d,$ (169)

where the equality follows from the factorisation of the $\alpha$-Rényi
entropy over subsystems. This gives rise to the following upper bound on the
relative entropy difference $\Delta D_{\alpha}\coloneqq
nD_{\alpha}(W_{\rho}||W_{\frac{\mathbbm{1}}{d}})-D_{\alpha}(W_{\rho_{p}}||W_{\tau_{n,k}})$,

$\displaystyle 0\leq\Delta D_{\alpha}$ $\displaystyle\leq n[\log
d-H_{\alpha}(W_{\rho})]+k\left[H_{\alpha}(W_{\psi})-\log d\right]$
$\displaystyle\hskip 20.0pt+\frac{\alpha}{1-\alpha}\log\frac{p}{1+\delta
d^{\frac{5}{2}}}.$ (170)

This gives a weaker but still necessary constraint on stochastic
transformations accomplishing $\rho^{\otimes n}\mapsto\rho_{p}$ and
$\left(\frac{\mathbbm{1}}{d}\right)^{\otimes n}\mapsto\tau_{n,k}$, which we
can rearrange as

$\displaystyle n[H_{\alpha}(W_{\rho})-\log d]$ $\displaystyle\leq
k\left[H_{\alpha}(W_{\psi})-\log d\right]$
$\displaystyle+\frac{\alpha}{1-\alpha}\log\frac{p}{1+\delta d^{\frac{5}{2}}}.$
(171)

For $H_{\alpha}(W_{\rho})<\log d$, we can rearrange Eq. (171) to obtain the
lower bound in Eq. (50). For $H_{\alpha}(W_{\rho})>\log d$, we obtain the
upper bound in Eq. (51). ∎

##  APPENDIX E DECOMPOSITION OF CSS MAGIC DISTILLATION INTO CODE PROJECTIONS

The goal of this appendix is to prove Theorem 21, which generalises Theorem 1
of Ref. [47] to an arbitrary number of output qubits in the CSS setting.

######  Theorem 21.

An $n$-to-$k$ CSS magic distillation protocol is any CSS circuit that takes in
$n\geq 2$ qubits and outputs onto the first $1\leq k<n$ qubits. Every
$n$-to-$k$ CSS magic distillation protocol ${\cal E}$ can be decomposed as a
sum of CSS code projections, followed by preparing CSS states and completely
CSS-preserving post-processing. Thus one can write

$\displaystyle{\cal E}(\rho)=\sum_{j}p_{j}{\cal E}_{j},\ {\cal
E}_{j}\coloneqq{\cal U}_{j}\circ\left({\cal
K}_{j}(\rho)\otimes\outerproduct{\varphi_{j}}{\varphi_{j}}\right),$ (172)

where $p_{j}$ is a probability, ${\cal U}_{j}$ is a completely CSS-preserving
unitary channel on $k$ qubits, ${\cal K}_{j}$ is the codespace projection of
an $[[n,k_{j}]]$ CSS code for some integer $k_{j}$ in the range $0\leq
k_{j}\leq k$, and $\ket{\varphi_{j}}$ is a CSS state on $(k-k_{j})$ qubits.

###### Proof.

To bring ${\cal E}$ into the desired form, we proceed in four steps (all
auxiliary lemmas used will be presented after this proof):

  1. 1.

By Lemma 23, any $n$-to-$k$ CSS magic distillation protocol ${\cal E}$ can be
decomposed as a sum of $n$-qubit operations

$\displaystyle{\cal E}(\rho)=\sum_{i}q_{i}{\cal E}_{i}(\rho)$ (173)

where $q_{i}$ is a probability and

$\displaystyle{\cal
E}_{i}(\rho)\coloneqq\mathrm{tr}_{k+1,\dots,n+m}\left[K_{i}(\rho\otimes\outerproduct{\psi_{i}}{\psi_{i}})K^{\dagger}_{i}\right]$
(174)

for a CSS state $\ket{\psi_{i}}$ on $m$ ancillary qubits and Kraus operator
$K_{i}$. This Kraus operator has the form

$\displaystyle K_{i}=U_{i}\left(\prod_{l=1}^{N}P(S_{i,l})\right),$ (175)

where $U_{i}$ is a completely CSS-preserving unitary and $P(S_{i,l})$ is the
projection onto the $+1$ eigenspace of a CSS observable $S_{i,l}$.

  2. 2.

By Lemma 24, each operation ${\cal E}_{i}$ can be decomposed into a sum

$\displaystyle{\cal E}_{i}(\rho)=\sum_{{\bm{s}}\in\\{0,1\\}^{n+m-k}}{\cal
E}_{i,{\bm{s}}}(\rho),$ (176)

where each operation ${\cal E}_{i,{\bm{s}}}$ first introduces $m$ ancillary
qubits in the CSS state $\ket{\psi_{i}}$, then post-selects the $+1$ outcome
in a sequence of projective measurements of CSS observables
$S_{i,N},\dots,S_{i,1}$, and then performs a CSS code projection on the input
and ancillary qubits. Thus one can write (note that ${\cal K}$ depends on $i$
and ${\bm{s}}$)

$\displaystyle{\cal E}_{i,{\bm{s}}}(\rho)={\cal K}\circ{\cal
P}(S_{i,1})\circ\dots\circ{\cal
P}(S_{i,N})[\rho\otimes\outerproduct{\psi_{i}}{\psi_{i}}],$ (177)

in which ${\cal P}(S_{i,j})$ post-selects the $+1$ outcome in a projective
measurement of the CSS observable $S_{i,j}$, and ${\cal K}$ is the code
projection of an $[[n+m,k]]$ CSS code.

  3. 3.

By repeated applications of Lemma 25, we find that ${\cal E}_{i,{\bm{s}}}$
performs a CSS code projection on the input and ancillary qubits, followed by
preparing a CSS state and completely CSS-preserving post-processing. Thus one
can write

$\displaystyle{\cal E}_{i,{\bm{s}}}(\rho)=q^{\prime}\ {\cal
U}^{\prime}\circ({\cal
K}^{\prime}(\rho\otimes\outerproduct{\psi_{i}}{\psi_{i}})\otimes\outerproduct{\varphi^{\prime}}{\varphi^{\prime}}),$
(178)

where $q^{\prime}$ is a probability, ${\cal U}^{\prime}$ is a completely CSS-
preserving unitary channel on $k$ qubits, $\ket{\varphi^{\prime}}$ is a CSS
state on $k-k^{\prime}$ qubits for some integer $k^{\prime}$ in the range
$0\leq k^{\prime}\leq k$, and ${\cal K}^{\prime}$ is a code projection for an
$[[n+m,k^{\prime}]]$ CSS code.

  4. 4.

By Lemma 27, each CSS code projection ${\cal K}^{\prime}$ on the input and
ancillary qubits from Eq. (178) can be reduced to a CSS code projection on the
input qubits alone, followed by preparing a CSS state and completely CSS-
preserving post-processing. Thus one can write

$\displaystyle{\cal
K}^{\prime}(\rho\otimes\outerproduct{\psi_{i}}{\psi_{i}})=q^{\prime\prime}\
{\cal U}^{\prime\prime}\circ({\cal
K}^{\prime\prime}(\rho)\otimes\outerproduct{\varphi^{\prime\prime}}{\varphi^{\prime\prime}}),$
(179)

where $q^{\prime\prime}$ is a probability, ${\cal U}^{\prime\prime}$ is a
completely CSS-preserving unitary channel on $k^{\prime}$ qubits, ${\cal
K}^{\prime\prime}$ is the code projection for an $[[n,k^{\prime\prime}]]$ CSS
code for some integer $k^{\prime\prime}$ in the range $0\leq
k^{\prime\prime}\leq k^{\prime}$, and $\ket{\varphi^{\prime\prime}}$ is a CSS
state on $k^{\prime}-k^{\prime\prime}$ qubits. Substituting back then
immediately yields the result. ∎

### Auxiliary lemmas

Before turning to the proofs of Lemmas used in each step of the main proof, we
first present a result that will be useful throughout.

######  Lemma 22.

Given any completely CSS-preserving unitary $U$ and CSS observable $S$ on $n$
qubits, ${S^{\prime}\coloneqq U^{\dagger}SU}$ is another CSS observable of the
same type as $S$. This further implies ${P(\pm S)U=UP(\pm S^{\prime})}$.

###### Proof.

For convenience, let us label the $n$ qubits as $1,\dots,n$. Let ${\bm{a}}$ be
an arbitrary $n$-bit string, and ${\bm{e}}_{j}$ be the $n$-bit string with 1
in its $j$th entry and 0 everywhere else. We then have the following
conjugation relations

$\displaystyle Z_{j}[X({\bm{a}})]Z_{j}=(-1)^{a_{j}}X({\bm{a}})$ (180)
$\displaystyle Z_{j}[Z({\bm{a}})]Z_{j}=Z({\bm{a}})$ (181) $\displaystyle
X_{j}[X({\bm{a}})]X_{j}=X({\bm{a}})$ (182) $\displaystyle
X_{j}[Z({\bm{a}})]X_{j}=X_{j}(-1)^{a_{j}}Z({\bm{a}})$ (183)
$\displaystyle\operatorname{CNOT}(i,j)[X({\bm{a}})]\operatorname{CNOT}(i,j)=X({\bm{a}}+a_{i}{\bm{e}}_{j})$
(184)
$\displaystyle\operatorname{CNOT}(i,j)[Z({\bm{a}})]\operatorname{CNOT}(i,j)=Z({\bm{a}}+a_{j}{\bm{e}}_{i}),$
(185)

for any $i,j$ from the range $1,\dots,n$, where arithmetic is modulo 2. Since
$S$ is of the form $\pm X({\bm{a}})$ or $\pm Z({\bm{a}})$, and $U$ is a
product of $\operatorname{CNOT}(i,j),Z_{j}$ and $X_{j}$ for $i,j$ in the range
$1,\dots,n$, we immediately arrive at the Lemma result. ∎

It is furthermore useful to recall that, given an $[[n,k]]$ CSS code
${\cal{C}}$ whose stabilizer group is generated by CSS observables
$S_{1},\dots,S_{n-k}$, Corollary 3 implies the code projection ${\cal K}$ of
${\cal{C}}$ can be represented using a completely CSS-preserving encoding
unitary $U$ as

$\displaystyle{\cal
K}(\rho)\coloneqq\mathrm{tr}_{k+1,\dots,n}\left[U^{\dagger}P(\rho)PU\right],$
$\displaystyle\text{ where }U^{\dagger}S_{i}U=\begin{cases}Z_{k+i}\text{ if
$S_{i}$ is $Z$-type}\\\ X_{k+i}\text{ if $S_{i}$ is $X$-type}\end{cases}$
$\displaystyle\text{ and }P=\prod_{i=1}^{n-k}P(S_{i}).$ (186)

We remark that in the $k=0$ case, ${\cal K}$ simply projects onto a pure
$n$-qubit CSS state and then discards it.

#### Step 1: Standard form for CSS magic distillation protocols

######  Lemma 23.

Any $n$-to-$k$ CSS magic distillation protocol ${\cal E}$ can be decomposed as
a sum of $n$-qubit operations

$\displaystyle{\cal E}(\rho)=\sum_{i}p_{i}{\cal E}_{i}(\rho),$ (187)

where $p_{i}$ is a probability and

$\displaystyle{\cal
E}_{i}(\rho)\coloneqq\mathrm{tr}_{k+1,\dots,n+m}\left[K_{i}(\rho\otimes\outerproduct{\psi_{i}}{\psi_{i}})K^{\dagger}_{i}\right],$
(188)

for a CSS state $\ket{\psi_{i}}$ on $m$ ancillary qubits and Kraus operator
$K_{i}$. Furthermore, $K_{i}$ has the form

$\displaystyle K_{i}=U_{i}\left(\prod_{l=1}^{N}P(S_{i,l})\right),$ (189)

where $U_{i}$ is a completely CSS-preserving unitary and $P(S_{i,l})$ projects
onto the $+1$ eigenspace of a CSS observable $S_{i,l}$.

###### Proof.

By Lemma 13, we can decomppose ${\cal E}$ as follows

$\displaystyle{\cal E}(\rho)=\sum_{i}q_{i}{\cal E}_{i}(\rho),$ (190)

where $q_{i}$ is a probability and

$\displaystyle{\cal
E}_{i}(\rho)=\mathrm{tr}_{k+1,\dots,n+m}\left[K_{i}(\rho\otimes\sigma_{i})K_{i}^{\dagger}\right]$
(191)

for a CSS state $\sigma_{i}$ on $m$ ancillary qubits and Kraus operator
$K_{i}$. Furthermore, $K_{i}$ has the form

$\displaystyle K_{i}=\prod_{l=1}^{N}P(S_{i,l})U_{i,l},$ (192)

where $U_{i,l}$ is a completely CSS-preserving unitary and $P(S_{i,l})$
projects onto the $+1$ eigenspace of the CSS observable $S_{(i,j),l}$. We then
conjugate every completely CSS-preserving unitary $U_{(i,j),l}$ to the
beginning of its Kraus operator $K_{i,j}$ as shown in Lemma 22, where we
compose them into a single completely CSS-preserving unitary $U_{i}$.
Decomposing each CSS state $\sigma_{i}$ on ancillary qubits into a statistical
mixture of pure CSS states then yields the Lemma result. ∎

#### Step 2: Exposing the decoding

######  Lemma 24.

Consider a channel ${\cal E}$ on $n\geq 2$ qubits that performs a completely
CSS-preserving unitary $U$ and then discards the final $n-k$ qubits where
$1\leq k<n$,

$\displaystyle{\cal
E}(\rho)=\mathrm{tr}_{k+1,\dots,n}\left[U^{\dagger}(\rho)U\right].$ (193)

Then ${\cal E}$ can be decomposed into a sum over CSS code projections
${\cal{C}}_{\bm{s}}$ indexed by the computational basis $\\{{\bm{s}}\\}$ on
the discarded qubits,

$\displaystyle{\cal E}(\rho)=\sum_{{\bm{s}}\in\\{0,1\\}^{n-k}}{\cal
K}_{\bm{s}}(\rho).$ (194)

###### Proof.

The channel ${\cal E}$ is unchanged by performing a measurement in the
computational basis $\\{\ket{{\bm{s}}}\\}$ of the final $n-k$ qubits before
discarding them. Thus one can write

$\displaystyle{\cal E}(\rho)=\sum_{{\bm{s}}\in\\{0,1\\}^{n-k}}{\cal
K}_{\bm{s}}(\rho),$ (195)

where we have defined

$\displaystyle{\cal
K}_{\bm{s}}(\rho)\coloneqq\mathrm{tr}_{k+1,\dots,n}\left[\mathbbm{1}^{\otimes
k}\otimes\outerproduct{{\bm{s}}}{{\bm{s}}}(U^{\dagger}(\rho)U)\mathbbm{1}^{\otimes
k}\otimes\outerproduct{{\bm{s}}}{{\bm{s}}}\right].$ (196)

Let $U_{\bm{s}}$ be a completely CSS-preserving unitary on the final $n-k$
qubits defined as
${U^{\dagger}_{\bm{s}}\coloneqq\bigotimes_{i=1}^{n-k}(X)^{s_{i}}}$. By the
cylic property of the trace, we obtain

$\displaystyle{\cal K}_{\bm{s}}(\rho)$
$\displaystyle=\mathrm{tr}_{k+1,\dots,n}\left[K(\rho)K^{\dagger}\right],$
(197)

for the Kraus operator

$\displaystyle K$ $\displaystyle\coloneqq\mathbbm{1}^{\otimes
k}\otimes\left(U^{\dagger}_{\bm{s}}\outerproduct{{\bm{s}}}{{\bm{s}}}\right)U^{\dagger}$
(198) $\displaystyle=\mathbbm{1}^{\otimes
k}\otimes\outerproduct{\bm{0}}{\bm{0}}\left([\mathbbm{1}^{\otimes k}\otimes
U^{\dagger}_{\bm{s}}]U^{\dagger}\right).$ (199)

Conjugating $U^{\prime}\coloneqq U\left(\mathbbm{1}^{\otimes k}\otimes
U_{\bm{s}}\right)$ past $\mathbbm{1}^{\otimes
k}\otimes\outerproduct{\bm{0}}{\bm{0}}=\prod_{i=1}^{n-k}P(Z_{k+i})$ in
accordance with Lemma 22, we see by comparison with Eq. (186) that ${\cal
K}_{\bm{s}}$ is a code projection for an $[[n,k]]$ CSS code stabilized by
$\langle
U^{\prime}Z_{k+1}U^{{}^{\prime}\dagger},\dots,U^{\prime}Z_{n}U^{{}^{\prime}\dagger}\rangle$.∎

#### Step 3: Removing the projections

######  Lemma 25.

Let ${\cal E}$ be an operation on $n$ qubits that projectively measures a CSS
observable $S$, post-selects the $+1$ outcome, and then carries out a code
projection ${\cal K}$ of an $[[n,k]]$ CSS code ${\cal{C}}$. Thus one can write

$\displaystyle{\cal E}(\rho)\coloneqq{\cal K}\circ{\cal P}(S)(\rho),\ {\cal
P}(S)(\cdot)\coloneqq P(S)(\cdot)P(S)$ (200)

There are three possibilities for how ${\cal E}$ transforms $\rho$:

  1. 1.

that ${\cal E}(\rho)=0$ for all $\rho$.

  2. 2.

that ${\cal E}$ is a code projection ${\cal K}^{\prime}$ for another $[[n,k]]$
CSS code ${\cal{C}}^{\prime}$, followed by completely CSS-preserving unitary
post-processing $\tilde{{\cal U}}$. Thus one can write

$\displaystyle{\cal E}(\rho)=p\ \tilde{{\cal U}}\circ{\cal K}^{\prime}(\rho),$
(201)

where $p>0$ is a probability. One can further find logical bases
$\left\\{\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}|{\bm{s}}\in\\{0,1\\}^{k}\right\\}$
and $\left\\{\ket{{\bm{s}}_{\cal{C}}}|{\bm{s}}\in\\{0,1\\}^{k}\right\\}$,
respectively generated by completely CSS-preseving encoding unitaries for the
new code ${\cal{C}}^{\prime}$ and the old code ${\cal{C}}$, such that

$\displaystyle
P(S)\ket{{\bm{s}}_{\cal{C}}}\propto\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}.$ (202)

  3. 3.

for $k\geq 1$, that ${\cal E}$ is a code projection ${\cal K}^{\prime}$ for an
$[[n,k-1]]$ CSS code ${\cal{C}}^{\prime}$, followed by preparing a CSS state
$\ket{\varphi}$ on a single qubit and completely CSS-preserving unitary post-
processing $\tilde{{\cal U}}$, i.e.

$\displaystyle{\cal E}(\rho)=\tilde{{\cal U}}\circ[{\cal
K}^{\prime}(\rho)\otimes\outerproduct{\varphi}{\varphi}].$ (203)

Furthermore, we can find logical bases
$\left\\{\ket{{\bm{s}}^{\prime}_{{\cal{C}}^{\prime}}}|{\bm{s}}\in\\{0,1\\}^{k-1}\right\\}$
and $\left\\{\ket{{\bm{s}}_{\cal{C}}}|{\bm{s}}\in\\{0,1\\}^{k}\right\\}$,
respectively generated by completely CSS-preseving encoding unitaries for the
new code ${\cal{C}}^{\prime}$ and the old code ${\cal{C}}$, such that

$\displaystyle
P(S)\ket{f({\bm{s}}^{\prime})_{\cal{C}}}\propto\ket{{\bm{s}}^{\prime}_{{\cal{C}}^{\prime}}},$
(204)

for some function $f:\\{0,1\\}^{k-1}\rightarrow\\{0,1\\}^{k}$.

###### Proof.

Let $S_{k+1},\dots,S_{n}$ be a set of $n-k$ CSS observables that generate the
stabilizer group of ${\cal{C}}$. Beginning with the representation for the
code projection ${\cal K}$ given by Eq. (186), we can conjugate the encoding
unitary past the codespace projector in accordance with Lemma 22, and arrive
at the alternative representation

$\displaystyle{\cal
K}(\rho)=\mathrm{tr}_{k+1,\dots,n}\left[PU^{\dagger}(\rho)UP\right],$ (205)

where $U$ is a completely CSS-preserving encoding unitary for ${\cal{C}}$ and
$P$ is now its no-error syndrome projector. Thus one can write

$\displaystyle U^{\dagger}S_{i}U=C_{i}\text{ and
}P\coloneqq\prod_{i=k+1}^{n}P(C_{i}),\text{ where }$ (206) $\displaystyle
C_{i}\coloneqq\begin{cases}Z_{i}&\text{ if $S_{i}$ is $Z$-type}\\\
X_{i}&\text{ if $S_{i}$ is $X$-type}\\\ \end{cases}\text{ for }i=k+1,\dots,n.$
(207)

Following Eq. (132), $U$ generates the following logical basis for
${\cal{C}}$:

$\displaystyle\forall{\bm{s}}\in\\{0,1\\}^{k}:$
$\displaystyle\ket{{\bm{s}}_{\cal{C}}}\coloneqq
U\left(\ket{{\bm{s}}}\bigotimes_{i=k+1}^{n}\ket{\phi_{i}}\right)$ (208) where
$\displaystyle\ket{\phi_{i}}\coloneqq\begin{cases}\ket{0}&\text{ if $S_{i}$ is
$Z$-type}\\\ \ket{+}&\text{ if $S_{i}$ is $X$-type.}\end{cases}$ (209)

By expressing $P$ in Eq. (205) as $P=\mathbbm{1}^{\otimes
k}\bigotimes_{i=1}^{n-k}\outerproduct{\phi_{i}}{\phi_{i}}$ and expanding
$\mathbbm{1}^{\otimes k}$ in the computational basis, we arrive at another
alternative form for ${\cal K}$,

$\displaystyle{\cal K}(\rho)=K(\rho)K^{\dagger},\text{ where
}K^{\dagger}\coloneqq\sum_{{\bm{s}}\in\\{0,1\\}^{k}}\outerproduct{{\bm{s}}_{\cal{C}}}{{\bm{s}}}.$
(210)

We now show how ${\cal E}$ can be manipulated into one of the forms stated by
the Lemma depending on the relationship between $S$ and the CSS observables
generating the stabilizer group for ${\cal{C}}$.

  1. (i)

$S$ does not commute with at least one generator $S_{k+1},\dots,S_{n}$. We
assume without loss of generality that $S$ does not commute with $S_{k+1}$. We
now show how ${\cal E}$ can be manipulated into the second form stated by the
Lemma.

Using the form of ${\cal K}$ given in Eq. (210), we can express ${\cal E}$ as

$\displaystyle{\cal E}(\rho)=M(\rho)M^{\dagger},$ (211)

where $M$ is the Kraus operator

$\displaystyle
M^{\dagger}\coloneqq\sum_{{\bm{s}}\in\\{0,1\\}^{k}}P(S)\outerproduct{{\bm{s}}_{\cal{C}}}{{\bm{s}}}.$
(212)

The stabilizer group ${\cal S}(\ket{{\bm{s}}}_{\cal{C}})$ for the logical
basis state $\ket{{\bm{s}}_{\cal{C}}}$ in ${\cal{C}}$ can be generated from
the set of $n$ CSS observables
$\\{(-1)^{s_{1}}UZ_{1}U^{\dagger},\dots,(-1)^{s_{k}}UZ_{k}U^{\dagger},S_{k+1},\dots,S_{n}\\}$.
We can multiply all other members of this set that do not commute with $S$ by
$S_{k+1}$ and, as all CSS observables that do not commute with $S$ are of the
same type, arrive at a set of $n$ CSS observables $\\{S_{1},\dots,S_{n}\\}$
such that

$\displaystyle{\cal
S}(\ket{{\bm{s}}_{\cal{C}}})=\langle(-1)^{s_{1}}S_{1},\dots,(-1)^{s_{k}}S_{k},S_{k+1},\dots,S_{n}\rangle.$
(213)

This implies

$\displaystyle
P(S)\ket{{\bm{s}}_{\cal{C}}}=\frac{1}{\sqrt{2}}\ket{\psi_{\bm{s}}}$ (214)

where $\ket{\psi_{\bm{s}}}$ is a CSS state stabilized by

$\displaystyle{\cal S}(\ket{\psi_{\bm{s}}})=\langle(-1)^{s_{1}}S_{1},\dots,$
$\displaystyle(-1)^{s_{k}}S_{k},S,S_{k+2}\dots,S_{n}\rangle.$ (215)

Applying Lemma 14 to $S_{1},\dots,S_{k},S,S_{k+2},\dots,S_{n}$, we can find a
completely CSS-preserving encoding unitary $U^{\prime}$ for the $[[n,k]]$ CSS
code ${\cal{C}}^{\prime}$ stabilized by $\langle S,S_{k+2},\dots,S_{n}\rangle$
that generates a logical basis $\\{\ket{{\bm{s}}}_{{\cal{C}}^{\prime}}\\}$ in
${\cal{C}}^{\prime}$ such that $\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}$ shares
the stabilizer group of $\ket{\psi_{\bm{s}}}$. Therefore,
$\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}$ and $\ket{\psi_{\bm{s}}}$ only differ up
to a phase, and one can write

$\displaystyle
P(S)\ket{{\bm{s}}_{{\cal{C}}}}=\frac{1}{\sqrt{2}}e^{-i\theta_{\bm{s}}}\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}.$
(216)

Substituting into Eq. (211), we obtain

$\displaystyle{\cal E}(\rho)=\frac{1}{2}\tilde{U}\left[{\cal
K}^{\prime}(\rho)\right]\tilde{U}^{\dagger},$ (217)

where we have defined the following unitary on $k$ qubits to adjust for the
phase differences between $\ket{\psi_{\bm{s}}}$ and
$\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}$,

$\displaystyle\tilde{U}\coloneqq\sum_{{\bm{s}}\in\\{0,1\\}^{k}}e^{i\theta_{\bm{s}}}\outerproduct{{\bm{s}}}{{\bm{s}}},$
(218)

as well as the operation

$\displaystyle{\cal K}^{\prime}(\cdot)\coloneqq
K^{\prime}(\cdot)K^{{}^{\prime}\dagger},\
K^{{}^{\prime}\dagger}\coloneqq\sum_{{\bm{s}}\in\\{0,1\\}^{k}}\outerproduct{{\bm{s}}_{\cal{C}}^{\prime}}{{\bm{s}}}.$
(219)

By comparison withEq. (210), we see that ${\cal K}^{\prime}$ is the CSS code
projection of ${\cal{C}}^{\prime}$. Eq. (216) and Eq. (217) now match the
second statement of the Lemma provided that $\tilde{U}$ is completely CSS-
preserving, which we now proceed to show.

We first express ${\cal E}$ using the form of ${\cal K}$ given by Eq. (205) as

$\displaystyle{\cal
E}(\rho)=\mathrm{tr}_{k+1,\dots,n}\left[PU^{\dagger}P(S)\rho P(S)UP\right].$
(220)

Let $\ket{\psi}$ be a CSS state on $k$ qubits expressed as
$\ket{\psi}=\sum_{{\bm{s}}\in\\{0,1\\}^{k}}c_{\bm{s}}\ket{{\bm{s}}}$ in the
computational basis. Since $U^{\prime}$ is completely CSS-preserving, it
encodes $\ket{\psi}$ as another CSS state
$\ket{\psi_{{\cal{C}}^{\prime}}}=\sum_{\bm{s}}c_{\bm{s}}\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}$
in ${\cal{C}}^{\prime}$. By inputting
$\outerproduct{\psi_{{\cal{C}}^{\prime}}}{\psi_{{\cal{C}}^{\prime}}}$ into the
two forms of ${\cal E}$ given by Eq. (217) and Eq. (220) and equating their
outputs, we obtain

$\displaystyle\frac{1}{2}\tilde{U}\outerproduct{\psi}{\psi}\tilde{U}^{\dagger}=\mathrm{tr}_{k+1,\dots,n}\left[PU^{\dagger}P(S)(\outerproduct{\psi_{{\cal{C}}^{\prime}}}{\psi_{{\cal{C}}^{\prime}}})P(S)UP\right].$
(221)

We see from the proof of Lemma 3 that the right hand side carries out a
completely CSS-preserving operation. Therefore, since
$\ket{\psi_{{\cal{C}}^{\prime}}}$ is CSS, $\tilde{U}\ket{\psi}$ must also be
CSS. As this argument applies to any pure CSS state $\ket{\psi}$ on $k$
qubits, we conclude that $\tilde{U}$ is CSS-preserving.

From the proof of Lemma 11, we can express $\tilde{U}$ as
$\tilde{U}=\left[H^{\otimes k}\right]^{a}V$, where $V$ is a completely CSS-
preserving unitary and $a$ is a binary digit. While the
$\operatorname{CNOT}$-gate and single-qubit $X$\- and $Z$-gates map
computational basis states onto computational basis states, the collective
Hadamard gate does not. Since $\tilde{U}$ is diagonal in the computational
basis, we conclude that $a=0$, so $\tilde{U}$ is indeed completely CSS-
preserving.

  2. (ii)

$S$ commutes with $S_{k+1},\dots,S_{n}$ and is independent of them. This is
only possible when $k\geq 1$. In this case, we show that ${\cal E}$ can be
manipulated into the third form stated in the Lemma.

By conjugating $P(S)$ past $U$ in Eq. (220) using Lemma 22, we can express
${\cal E}$ as

$\displaystyle{\cal
E}(\rho)=\mathrm{tr}_{k+1,\dots,n}\left[PP(S^{\prime})U^{\dagger}(\rho)UP(S^{\prime})P\right],$
(222)

where $S^{\prime}\coloneqq U^{\dagger}SU$ is another CSS observable.

Consider the term

$\displaystyle P(S^{\prime})P=P(S^{\prime})P(C_{k+1})\dots P(C_{n})$ (223)

from Eq. (222). Since $S^{\prime}$ commutes with $C_{k+1},\dots,C_{n}$, and
$C_{i}$ is a CSS observable on qubit $i$ alone, $S^{\prime}$ must be trivial
on any qubit $i$ out of the last $n-k$ where $C_{i}$ is a different type of
CSS observable from $S^{\prime}$.

Given any two Pauli observables $O_{2}$ and $O_{2}$, we have that

$\displaystyle P(O_{1})P(O_{2})=P(O_{1}O_{2})P(O_{2}).$ (224)

We can therefore apply Eq. (224) to $S^{\prime}$ and the $C_{i}$ in Eq. (223)
to eliminate the part of $P(S^{\prime})$ that acts on the last $n-k$ qubits,
i.e., there exists a CSS observable $S^{\prime\prime}$ on the first $k$ qubits
alone such that

$\displaystyle
P(S^{\prime})P=[P(S^{\prime\prime})\otimes\mathbbm{1}^{\otimes(n-k)}]P.$ (225)

Since $S^{\prime}$ must also be independent of $C_{k}+1,\dots,C_{n}$, we
conclude that $S^{\prime\prime}$ is not proportional to the identity.

We now consider the cases where $S^{\prime\prime}$ is $Z$-type and $X$-type
separately. To this end, it is first useful to define a completely CSS-
preserving $k$-qubit unitary that moves the $j$th qubit in a block of $k$ to
the $k$th position,

$\displaystyle\operatorname{MV}(j\rightarrow
k)\coloneqq\begin{cases}\prod\limits_{i=j}^{k}\text{SWAP}(i,i+1)&\text{ if
}j<k\\\ \mathbbm{1}^{\otimes k}&\text{ otherwise,}\end{cases}$ (226)

where $\text{SWAP}(i,j)$ swaps qubits $i$ and $j$ and is carried out by
$\operatorname{CNOT}(i,j)\operatorname{CNOT}(j,i)\operatorname{CNOT}(i,j)$.

    1. (a)

$S^{\prime\prime}$ is $Z$-type. We therefore represent $S^{\prime\prime}$ as
$S^{\prime\prime}=(-1)^{b}Z({\bm{z}})$, where $b$ is a binary digit and
${\bm{z}}$ is an $k$-bit string of which at least one bit $j$ is such that
$z_{j}=1$.

Consider the following completely CSS-preserving unitary on $k$ qubits

$\displaystyle\tilde{U}^{\dagger}\coloneqq\operatorname{MV}(j\rightarrow
k)\circ X^{b}_{j}\circ U_{C},$ (227)

where $U_{C}$ is defined as

$\displaystyle
U_{C}\coloneqq\begin{cases}\prod\limits_{\begin{subarray}{c}i=1\\\
z_{i}=1,i\neq j\end{subarray}}^{k}\operatorname{CNOT}(i,j)&\text{ if }\exists
i\neq j:z_{i}=1,\\\ \mathbbm{1}^{\otimes k}&\text{ otherwise.}\end{cases}$
(228)

Because $U_{C}$ acts as $U_{C}[Z({\bm{z}})]U^{\dagger}_{C}=Z_{j}$, we have
that

$\displaystyle\tilde{U}^{\dagger}P(S^{\prime\prime})\tilde{U}=P(Z_{k}),$ (229)

Using Eq. (229) to substitute $P(S^{\prime\prime})$ in Eq. (225), we have by
Eq. (222) that

$\displaystyle{\cal
E}(\rho)=\tilde{U}\left(\mathrm{tr}_{k+1,\dots,n}\left[P^{\prime}U^{{}^{\prime}\dagger}(\rho)U^{\prime}P^{\prime}\right]\right)\tilde{U}^{\dagger},$
(230)

where we have defined

$\displaystyle P^{\prime}\coloneqq P(Z_{k})P\text{ and }U^{\prime}\coloneqq
U\tilde{U}\otimes\mathbbm{1}^{\otimes(n-k)}.$ (231)

Since $k$th qubit outputted by the part inside
$\tilde{U}(\cdot)\tilde{U}^{\dagger}$ is always $\ket{0}$, we can simply
discard the $k$th qubit as well and re-prepare it. Thus one can write

$\displaystyle{\cal E}(\rho)=\tilde{U}\left({\cal
K}^{\prime}(\rho)\otimes\outerproduct{0}{0}\right)\tilde{U}^{\dagger},$ (232)

where we have defined

$\displaystyle{\cal
K}^{\prime}(\rho)\coloneqq\mathrm{tr}_{k,\dots,n}\left[P^{\prime}U^{{}^{\prime}\dagger}(\rho)U^{\prime}P^{\prime}\right].$
(233)

From Eq. (205), we see that ${\cal K}^{\prime}$ is the code projection of an
$[[n,k-1]]$ CSS code ${\cal{C}}^{\prime}$ stabilized by $\langle
U^{\prime}Z_{k}U^{{}^{\prime}\dagger},U^{\prime}C_{k+1}U^{{}^{\prime}\dagger},\dots,U^{\prime}C_{n}U^{{}^{\prime}\dagger}\rangle$
with a completely CSS-preserving encoding unitary $U^{\prime}$. By Eq. (208),
$U^{\prime}$ generates the following logical basis for ${\cal{C}}^{\prime}$:

$\displaystyle\forall{\bm{s}}^{\prime}\in\\{0,1\\}^{k-1}:\ket{{\bm{s}}_{\cal{C}}^{\prime}}$
$\displaystyle\coloneqq U^{\prime}\ket{{\bm{s}}}\ket{0}\ket{\Phi}$ (234) where
$\displaystyle\ket{\Phi}\coloneqq\bigotimes_{i=1}^{n-k}\ket{\phi_{i}}.$ (235)

We can then relate the logical basis state
$\ket{{\bm{s}}^{\prime}_{{\cal{C}}^{\prime}}}$ to a logical basis state in the
old code ${\cal{C}}$ as

$\displaystyle\ket{{\bm{s}}^{\prime}_{{\cal{C}}^{\prime}}}$
$\displaystyle=\left[U\tilde{U}\otimes\mathbbm{1}^{\otimes(n-k)}\right]P(Z_{k})P\ket{{\bm{s}}^{\prime}}\ket{0}\ket{\Phi}$
$\displaystyle=UP\left(S^{\prime\prime}\right)\otimes\mathbbm{1}^{\otimes(n-k)}P\left[\left(\tilde{U}\ket{{\bm{s}}^{\prime}}\ket{0}\right)\ket{\Phi}\right]$
$\displaystyle=UP(S^{\prime})P\ket{f({\bm{s}}^{\prime})}\ket{\Phi}$
$\displaystyle=P(S)U\ket{f({\bm{s}}^{\prime})}\ket{\Phi}$
$\displaystyle=P(S)\ket{f({\bm{s}}^{\prime})_{\cal{C}}},$ (236)

where we have defined
$\ket{f({\bm{s}}^{\prime})}\coloneqq\tilde{U}\ket{{\bm{s}}^{\prime}}\ket{0}$,
used Eq. (229) to obtain the second equality and Eq. (225) to obtain the
third. Explicitly, $f$ is defined by

$\displaystyle f({\bm{s}}^{\prime})=$
$\displaystyle(s^{\prime}_{1},\dots,s^{\prime}_{j-1},s,s^{\prime}_{j},\dots,s^{\prime}_{k-1}),\text{where
}$ $\displaystyle
s\coloneqq\left(\sum_{i=1}^{j-1}s^{\prime}_{i}z_{i}\right)+b+\left(\sum_{i=j+1}^{k}s^{\prime}_{i-1}z_{i}\right),$
(237)

and arithmetic is modulo 2.

    2. (b)

$S^{\prime\prime}$ is $X$-type. We therefore represent $S^{\prime\prime}$ as
$S^{\prime\prime}=(-1)^{b}X({\bm{x}})$, where $b$ is a binary digit and
${\bm{x}}$ is an $k$-bit string of which at least one bit $j$ is such that
$x_{j}=1$.

Consider the following completely CSS-preserving unitary on $k$ qubits,

$\displaystyle\tilde{U}^{\dagger}\coloneqq\operatorname{MV}_{j\rightarrow
k}\circ Z^{b}_{j}\circ U_{C},$ (238)

in which $U_{C}$ is defined as

$\displaystyle
U_{C}\coloneqq\begin{cases}\prod\limits_{\begin{subarray}{c}i=1\\\
x_{i}=1,i\neq j\end{subarray}}^{k}\operatorname{CNOT}(j,i)&\text{ if }\exists
i\neq j:x_{i}=1,\\\ \mathbbm{1}^{\otimes k}&\text{ otherwise.}\end{cases}$
(239)

Because $U_{C}[X({\bm{x}})]U^{\dagger}_{C}=X_{j}$, we have that

$\displaystyle\tilde{U}^{\dagger}P(S^{\prime\prime})\tilde{U}=P(X_{k}).$ (240)

Using Eq. (240) to substitute $P(S^{\prime\prime})$ in Eq. (225), we have by
Eq. (222) that

$\displaystyle{\cal
E}(\rho)=\tilde{U}\left(\mathrm{tr}_{k+1,\dots,n}\left[P^{\prime}U^{{}^{\prime}\dagger}(\rho)U^{\prime}P^{\prime}\right]\right)\tilde{U}^{\dagger},$
(241)

where we have defined

$\displaystyle P^{\prime}\coloneqq P(X_{k})P,\ U^{\prime}\coloneqq
U\tilde{U}\otimes\mathbbm{1}^{\otimes(n-k)}.$ (242)

Since $k$th qubit outputted by the part inside
$\tilde{U}(\cdot)\tilde{U}^{\dagger}$ is always $\ket{+}$, we can simply
discard the $k$th qubit as well and re-prepare it. Thus one can write

$\displaystyle{\cal E}(\rho)=\tilde{U}\left({\cal
K}^{\prime}(\rho)\otimes\outerproduct{+}{+}\right)\tilde{U}^{\dagger},$ (243)

where we have defined

$\displaystyle{\cal
K}^{\prime}(\rho)\coloneqq\mathrm{tr}_{k,\dots,n}\left[P^{\prime}U^{{}^{\prime}\dagger}(\rho)U^{\prime}P^{\prime}\right].$
(244)

From Eq. (186), we see that ${\cal K}^{\prime}$ is a code projection for an
$[[n,k-1]]$ CSS code ${\cal{C}}^{\prime}$ stabilized by $\langle
U^{\prime}X_{k}U^{{}^{\prime}\dagger},U^{\prime}C_{k+1}U^{{}^{\prime}\dagger},\dots,U^{\prime}C_{n}U^{{}^{\prime}\dagger}\rangle$
with a completely CSS-preserving encoding unitary $U^{\prime}$. By Eq. (208),
$U^{\prime}$ generates the following logical basis for ${\cal{C}}^{\prime}$:

$\displaystyle\forall{\bm{s}}^{\prime}\in\\{0,1\\}^{k-1}:\ket{{\bm{s}}_{\cal{C}}^{\prime}}$
$\displaystyle\coloneqq U^{\prime}\ket{{\bm{s}}}\ket{+}\ket{\Phi}$ (245)
$\displaystyle\text{ where }\ket{\Phi}$
$\displaystyle\coloneqq\bigotimes_{i=1}^{n-k}\ket{\phi_{i}}.$ (246)

We can then relate the logical basis state
$\ket{{\bm{s}}^{\prime}_{{\cal{C}}^{\prime}}}$ in the new code
${\cal{C}}^{\prime}$ to a logical basis state in the old code ${\cal{C}}$ as

$\displaystyle\ket{{\bm{s}}^{\prime}_{{\cal{C}}^{\prime}}}$
$\displaystyle=\left[U\tilde{U}\otimes\mathbbm{1}^{(n-k)}\right]P(X_{k})P\ket{{\bm{s}}^{\prime}}\ket{+}\ket{\Phi}$
$\displaystyle=\sqrt{2}\left[U\tilde{U}\otimes\mathbbm{1}^{\otimes(n-k)}\right]P(X_{k})P\ket{{\bm{s}}^{\prime}}\ket{0}\ket{\Phi}$
$\displaystyle=\sqrt{2}\
UP(S^{\prime\prime})\otimes\mathbbm{1}^{\otimes(n-k)}P\left(\tilde{U}\ket{{\bm{s}}^{\prime}}\ket{0}\right)\ket{\Phi}$
$\displaystyle=\sqrt{2}\ UP(S^{\prime})P\ket{f({\bm{s}}^{\prime})}\ket{\Phi}$
$\displaystyle=\sqrt{2}\ P(S)U\ket{f({\bm{s}}^{\prime})}\ket{\Phi}$
$\displaystyle=\sqrt{2}\ P(S)\ket{f({\bm{s}}^{\prime})_{\cal{C}}},$ (247)

where we defined
$\ket{f({\bm{s}}^{\prime})}\coloneqq\tilde{U}\ket{{\bm{s}}^{\prime}}\ket{0}$,
used Eq. (240) to obtain the second equality and Eq. (225) to obtain the
third. Explicitly,
$f{({\bm{s}}^{\prime})=(s^{\prime}_{1},\dots,s^{\prime}_{j-1},0,s^{\prime}_{j},\dots,s^{\prime}_{k-1})}$.

  3. (iii)

$S$ is not independent of $S_{k+1},\dots,S_{n}$. This implies either $-S$ or
$S$ stabilizes ${\cal{C}}$. In the former case, we see from Eq. (211) that
${\cal E}(\rho)=0$ for all $\rho$. In the latter case, we have
$P(S)\ket{{\bm{s}}_{{\cal{C}}}}=\ket{{\bm{s}}_{{\cal{C}}}}$, which implies
${\cal E}={\cal K}$ by Eq. (211). Together these equations match the Lemma’s
second form. ∎

#### Step 4. Removing ancillary qubits

######  Lemma 26.

Let ${\cal{C}}$ be an ${[[n+m,k]]}$ CSS codes where $n\geq 1,n>k$ and $m>0$,
and let $\\{\ket{{\bm{s}}_{\cal{C}}}\\}$ be a logical basis for ${\cal{C}}$
generated by a completely CSS-preserving encoding unitary $U$ such that each
logical basis state $\ket{{\bm{s}}_{\cal{C}}}$ factorises over $n$ and $m$
qubits, i.e.,

$\displaystyle\ket{{\bm{s}}_{\cal{C}}}=\ket{\psi_{\bm{s}}}\otimes\ket{\psi},$
(248)

where $\ket{\psi}$ is a CSS state on $m$ qubits. We then have that

$\displaystyle\ket{\psi_{\bm{s}}}=e^{-i\theta_{\bm{s}}}\ket{{\bm{s}}_{{\cal{C}}^{\prime}}},$
(249)

where $\\{\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}\\}$ is a logical basis for an
$[[n,k]]$ CSS code ${\cal{C}}^{\prime}$ generated by a completely CSS-
preserving unitary.

###### Proof.

By Eq. (132), the stabilizer group for the logical basis state
$\ket{{\bm{s}}_{\cal{C}}}$ can be related to the stabilizer group ${\cal
S}({\cal{C}})$ of ${\cal{C}}$ as

$\displaystyle{\cal
S}(\ket{{\bm{s}}_{\cal{C}}})=\langle(-1)^{s_{1}}S_{1},\dots,(-1)^{s_{k}}S_{k}\rangle\times{\cal
S}({\cal{C}}),$ (250)

where we have defined $S_{i}\coloneqq UZ_{i}U^{\dagger}$ for $i=1,\dots,k$.

We observe that ${\cal S}({\cal{C}})$ is a direct sum of
$\mathbb{F}_{2}$-subspaces ${\cal S}_{X}({\cal{C}})$ and ${\cal
S}_{Z}({\cal{C}})$ corresponding to $X$\- and $Z$-type stabilizers for
${\cal{C}}$. Because $\ket{\psi}$ is a CSS state, its stabilizer group ${\cal
S}(\ket{\psi})$ is similarly a direct sum of $\mathbb{F}_{2}$-subspaces ${\cal
S}_{Z}(\ket{\psi})$ and ${\cal S}_{X}(\ket{\psi})$ corresponding to $X$\- and
$Z$-type stabilizers for $\ket{\psi}$.

Since $\\{\ket{{\bm{s}}_{\cal{C}}}\\}$ span ${\cal{C}}$, Eq. (248) implies
that, if $S$ stabilizes $\ket{\psi}$, then $\mathbbm{1}^{\otimes n}\otimes S$
stabilizes ${\cal{C}}$. Therefore, $\mathbbm{1}^{\otimes n}\otimes{\cal
S}_{Z}(\ket{\psi})$ and $\mathbbm{1}^{\otimes n}\otimes{\cal
S}_{X}(\ket{\psi})$ are $\mathbb{F}_{2}$-subspaces of ${\cal
S}_{Z}({\cal{C}})$ and ${\cal S}_{X}({\cal{C}})$ respectively. By applying the
basis extension theorem separately to the $Z$ and $X$ cases, we can represent
${\cal S}({\cal{C}})$ as

$\displaystyle{\cal S}({\cal{C}})=\langle
S_{k+1},\dots,S_{n},\mathbbm{1}^{\otimes n}\otimes
T_{1},\dots,\mathbbm{1}^{\otimes n}\otimes T_{m}\rangle,$ (251)

where $S_{k+1},\dots,S_{n}$ and $T_{1},\dots,T_{m}$ are all CSS observables
such that ${\cal S}(\ket{\psi})=\langle T_{1},\dots,T_{m}\rangle$.

The stabilizer group of $\ket{{\bm{s}}_{\cal{C}}}$ can then be represented as

$\displaystyle{\cal S}(\ket{{\bm{s}}_{\cal{C}}})=\langle(-1)^{s_{1}}S_{1},$
$\displaystyle\dots,(-1)^{s_{k}}S_{k},S_{k+1},\dots,S_{n},$
$\displaystyle\mathbbm{1}^{\otimes n}\otimes T_{1},\dots,\mathbbm{1}^{\otimes
n}\otimes T_{m}\rangle,$ (252)

from which we note that $S_{1},\dots,S_{n}$ are all members of ${\cal
S}(\ket{\bm{0}_{\cal{C}}})$, the stabilizer group for the zero logical basis
state in ${\cal{C}}$. Since $\ket{\bm{0}_{\cal{C}}}$ and $\ket{\psi}$ are CSS
(see Eq. (132)), $\ket{\psi_{\bm{0}}}$ must be CSS as well (as discarding the
last $m$ qubits is CSS-preserving). Therefore, ${\cal
S}(\ket{\bm{0}_{\cal{C}}})$ is a direct sum of $\mathbb{F}_{2}$-subspaces
$\mathbbm{1}^{\otimes n}\otimes{\cal S}(\ket{\psi})$ and ${{\cal
S}(\ket{\psi_{\bm{0}}})\otimes\mathbbm{1}^{\otimes m}}$, where ${\cal
S}(\ket{\psi_{\bm{0}}})$ is the stabilizer group of $\ket{\psi_{\bm{0}}}$.
Consequently, we can express $S_{i}$ as $S_{i}=S^{\prime}_{i}\otimes
T^{\prime}_{i}$, where $S^{\prime}_{i}$ and $T^{\prime}_{i}$ are CSS
observables of the same type as $S_{i}$ that respectively stabilize
$\ket{\psi_{\bm{0}}}$ and $\ket{\psi}$. Therefore, by multiplying each $S_{i}$
in Eq. (252) by appropriate generators of the same type in
${\\{\mathbbm{1}^{\otimes}\otimes T_{1},\dots\mathbbm{1}^{\otimes n}\otimes
T_{m}\\}}$, we can represent the stabilizer group of
$\ket{{\bm{s}}_{\cal{C}}}$ as

$\displaystyle{\cal S}(\ket{{\bm{s}}_{\cal{C}}})={\cal
S}(\ket{\psi_{\bm{s}}})\otimes{\cal S}(\ket{\psi}),$ (253)

where the stabilizer group ${\cal S}(\ket{\psi_{\bm{s}}})$ is generated by

$\displaystyle{\cal
S}(\ket{\psi_{\bm{s}}})=\langle(-1)^{s_{1}}S^{\prime}_{1},\dots,(-1)^{s_{k}}S^{\prime}_{k},S^{\prime}_{k+1},\dots,S^{\prime}_{n}\rangle,$
(254)

in which $S^{\prime}_{1},\dots,S^{\prime}_{k}$ are $Z$-type becausse
$S_{1},\dots,S_{k}$ are $Z$-type. By applying Lemma 14 to
$S^{\prime}_{1},\dots,S^{\prime}_{n}$, we can find a logical basis
$\\{\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}\\}$ for an $[[n,k]]$ CSS code
${\cal{C}}^{\prime}$ stabilized by $\langle
S^{\prime}_{k+1},\dots,S^{\prime}_{n}\rangle$, generated by a completely CSS-
preserving encoding unitary, such that $\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}$
shares the stabilizer group of $\ket{\psi_{\bm{s}}}$. Therefore,
$\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}$ and $\ket{\psi_{\bm{s}}}$ only differ up
to a phase, which implies the Lemma. ∎

######  Lemma 27.

Let ${\cal K}$ be the code projection for an ${[[n+m,k]]}$ CSS code
${\cal{C}}$ where $n\geq 1,n>k$ and $m>0$. Then given any $m$-qubit CSS state
$\ket{\psi}$, we have that
${\cal{C}}([\cdot]\otimes\outerproduct{\psi}{\psi})$ is equivalent to a CSS
code projection on $n$ qubits alone, followed by preparing a CSS state and
completely CSS-preserving post-processing, i.e.

$\displaystyle{\cal K}(\rho\otimes\outerproduct{\psi}{\psi})=p\ \tilde{{\cal
U}}\circ\left(\tilde{{\cal
K}}(\rho)\otimes\outerproduct{\varphi}{\varphi}\right),$ (255)

where $p$ is a probability, $\tilde{{\cal U}}$ is a completely CSS-preserving
unitary channel on $k$ qubits, $\tilde{{\cal K}}$ is a code projection for an
$[[n,k^{\prime}]]$ CSS code where $0\leq k^{\prime}\leq k$, and
$\ket{\varphi}$ is a CSS state on $k-k^{\prime}$ qubits.

###### Proof.

Let $\\{S_{n+1},\dots,S_{n+m}\\}$ be a set of CSS observables that generate
the stabilizer group defining $\ket{\psi}$. Then ${\cal
K}(\rho\otimes\outerproduct{\psi}{\psi})$ is equivalent to

$\displaystyle{\cal K}(\rho\otimes\outerproduct{\psi}{\psi})={\cal
K}(\mathbf{P}[\rho\otimes\outerproduct{\psi}{\psi}]\mathbf{P}),$ (256)

where $\mathbf{P}$ projects the last $m$ qubits onto $\ket{\psi}$, i.e.

$\displaystyle\mathbf{P}\coloneqq\mathbbm{1}^{\otimes
n}\otimes\outerproduct{\psi}{\psi}=\prod_{i=n+1}^{n+m}P(\mathbbm{1}^{\otimes
n}\otimes S_{i}).$ (257)

By applying Lemma 25 to each projection carried out by $\mathbf{P}$, we obtain

$\displaystyle{\cal K}(\rho\otimes\outerproduct{\psi}{\psi})=p\ {\cal
U}\circ{\cal
K}^{\prime}(\rho\otimes\outerproduct{\psi}{\psi})\otimes\outerproduct{\varphi}{\varphi},$
(258)

where $p$ is a probability, ${\cal U}$ is a completely CSS-preserving unitary
channel on $k$ qubits, ${\cal K}^{\prime}$ is a code projection for an
$[[n+m,k^{\prime}]]$ CSS code ${\cal{C}}^{\prime}$ where $0\leq k^{\prime}\leq
k$, and $\ket{\varphi}$ is a CSS state on $k-k^{\prime}$ qubits. Lemma 25
further implies there exists a logical basis
$\\{\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}|{\bm{s}}\in\\{0,1\\}^{k^{\prime}}\\}$
for the new code ${\cal{C}}^{\prime}$, generated by a completely CSS-
preserving encoding unitary, which can be related to some state
$\ket{\Psi_{\bm{s}}}$ on $n+m$ qubits as

$\displaystyle\mathbf{P}\ket{\Psi_{\bm{s}}}=\left(\mathbbm{1}^{\otimes
n}\otimes\outerproduct{\psi}{\psi}\right)\ket{\Psi_{\bm{s}}}\propto\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}.$
(259)

Eq. (259) immmediately implies

$\displaystyle\ket{{\bm{s}}^{\prime}_{{\cal{C}}^{\prime}}}=\ket{\psi_{\bm{s}}}\otimes\ket{\psi},$
(260)

where $\ket{\psi_{\bm{s}}}$ is a state on the first $n$ qubits alone. By Lemma
26, each $\ket{\psi_{\bm{s}}}$ is, up to a phase that may vary with
${\bm{s}}$, a logical basis state $\ket{{\bm{s}}_{{\cal{C}}^{\prime\prime}}}$
for an $[[n,k^{\prime}]]$ CSS code ${\cal{C}}^{\prime\prime}$ with only $n$
physical qubits. Thus one can write

$\displaystyle\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}=e^{-i\theta_{\bm{s}}}\ket{{\bm{s}}_{{\cal{C}}^{\prime\prime}}}\otimes\ket{\psi}.$
(261)

By Eq. (210), we can express the code projection ${\cal K}^{\prime}$ for
${\cal{C}}^{\prime}$ in terms of the logical basis
$\\{\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}\\}$ as

$\displaystyle{\cal K}^{\prime}(\cdot)=K(\cdot)K^{\dagger},\
K^{\dagger}\coloneqq\sum_{{\bm{s}}\in\\{0,1\\}^{k^{\prime}}}\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}\bra{{\bm{s}}}.$
(262)

We can then use Eq. (261) to show that

$\displaystyle{\cal
K}^{\prime}(\rho\otimes\outerproduct{\psi}{\psi})=U^{\prime}\left[\tilde{{\cal
K}}(\rho)\right]U^{{}^{\prime}\dagger},$ (263)

where we have defined the following unitary on $k^{\prime}$ qubits to adjust
for the phase differences between $\ket{{\bm{s}}_{{\cal{C}}^{\prime}}}$ and
$\ket{\psi_{\bm{s}}}$,

$\displaystyle
U^{\prime}\coloneqq\sum_{{\bm{s}}\in\\{0,1\\}^{k^{\prime}}}e^{i\theta_{\bm{s}}}\outerproduct{{\bm{s}}}{{\bm{s}}},$
(264)

as well as

$\displaystyle\tilde{{\cal
K}}(\cdot)\coloneqq\tilde{K}(\cdot)\tilde{K}^{\dagger},\
\tilde{K}^{\dagger}\coloneqq\sum_{{\bm{s}}\in\\{0,1\\}^{k^{\prime}}}\ket{{\bm{s}}_{{\cal{C}}^{\prime\prime}}}\bra{{\bm{s}}},$
(265)

By comparison with Eq. (210), we see that $\tilde{{\cal K}}$ is the code
projection for the $[[n,k^{\prime}]]$ CSS code ${\cal{C}}^{\prime\prime}$.
Following a similar argument to that at the end of case (iii) in the proof of
Lemma 25, we can demonstrate that $U^{\prime}$ is completely CSS-preserving.
Substituting back immeidately yields the Lemma result. ∎

##  APPENDIX F COMPLEX RELATIVE MAJORIZATION

In this appendix, we sketch how our entropic constraints can be extended to
arbitrary input and output states – i.e. those whose density matrices in the
computational basis may not be real.

We refer to any complex-valued distribution ${\bm{w}}$ on $N$ elements as a
complex quasidistribution if its components sum to 1, i.e.

$\displaystyle\sum_{i=1}^{N}{\bm{w}}^{(i)}=1.,$ (266)

Given complex quasidistributions ${\bm{w}},{\bm{w}}^{\prime}$ and reference
probability distributions ${\bm{r}},{\bm{r}}^{\prime}$, we can extend relative
majorization very naturally to a partial order $\succ_{C}$ defined by

$\displaystyle({\bm{w}},{\bm{r}})\succ_{C}({\bm{w}}^{\prime},{\bm{r}}^{\prime})\iff
A{\bm{w}}={\bm{w}}^{\prime},\ A{\bm{r}}={\bm{r}}^{\prime}.$ (267)

Any complex quasidistribution ${\bm{w}}$ on $N$ elements can be decomposed
into real and imaginary parts as

$\displaystyle{\bm{w}}={\bm{w}}_{R}+i{\bm{w}}_{I},$ (268)

where we have introduced the notation
$(\cdot)_{R}\coloneqq\mathfrak{Re}(\cdot)$ and
$(\cdot)_{I}\coloneqq\mathfrak{Im}(\cdot)$. By Eq. (266), we have

$\displaystyle\sum_{i=1}^{N}w^{(i)}_{R}=1,\ \sum_{i=1}^{N}w^{(i)}_{I}=0.$
(269)

Therefore, given any complex quasidistribution ${\bm{w}}$ on $N$ elements, we
can construct a valid quasiprobability distribution on $2N$ elements using the
map

$\displaystyle\mu({\bm{w}})\coloneqq{\bm{w}}_{R}\oplus{\bm{w}}_{I}.$ (270)

Furthermore, given any probability distribution ${\bm{r}}$ on $N$ elements, we
can also construct a probability distribution on $2N$ elements using the map

$\displaystyle\nu({\bm{r}})\coloneqq\frac{1}{2}({\bm{r}}\oplus{\bm{r}}).$
(271)

We can now prove the following theorem:

######  Theorem 28.

Given complex quasidistributions ${\bm{w}},{\bm{w}}^{\prime}$ and probability
distributions ${\bm{r}},{\bm{r}}^{\prime}$, we have that

$\displaystyle({\bm{w}},{\bm{r}})\succ_{C}({\bm{w}}^{\prime},{\bm{r}}^{\prime})\implies(\mu({\bm{w}}),\nu({\bm{r}}))\succ(\mu({\bm{w}}^{\prime}),\nu({\bm{r}}^{\prime})).$
(272)

###### Proof.

Since a stochastic matrix processes the real and imaginary parts of a vector
independently, we conclude that
$({\bm{w}},{\bm{r}})\succ_{C}({\bm{w}}^{\prime},{\bm{r}}^{\prime})$ implies

$\displaystyle\begin{bmatrix}{\bm{w}}_{R}^{\prime}\\\
{\bm{w}}_{I}^{\prime}\end{bmatrix}$ $\displaystyle=\begin{bmatrix}A&0\\\
0&A\end{bmatrix}\begin{bmatrix}{\bm{w}}_{R}\\\
{\bm{w}}_{I}\end{bmatrix},\begin{bmatrix}\frac{1}{2}{\bm{r}}^{\prime}\\\
\frac{1}{2}{\bm{r}}^{\prime}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}A&0\\\
0&A\end{bmatrix}\begin{bmatrix}\frac{1}{2}{\bm{r}}\\\
\frac{1}{2}{\bm{r}}\end{bmatrix}$ (273)

for some stochastic matrix A. Defining $\tilde{A}\coloneqq A\oplus A$, we can
rewrite this more compactly as

$\displaystyle\mu(\bm{w}^{\prime})=\tilde{A}\mu({\bm{w}}),\
\nu({\bm{r}}^{\prime})=\tilde{A}\nu({\bm{r}}),$ (274)

where $\tilde{A}$ is stochastic whenever $A$ is stochastic, completing the
proof. ∎

######  Corollary 5.

Let
$\mathbf{w}_{\rho}\coloneqq\mathfrak{Re}[W_{\rho}]\oplus\mathfrak{Im}[W_{\rho}]$
and $\mathbf{r}_{\tau}\coloneqq\frac{1}{2}(W_{\tau}\oplus W_{\tau})$. If there
exists a completely CSS-preserving channel ${\cal E}$ such that ${\cal
E}(\rho)=\rho^{\prime}$ and ${\cal E}(\tau)=\tau^{\prime}$, where $\tau$ and
$\tau^{\prime}$ are both in the interior of ${\cal D}_{css}$, then for all
$\alpha\in{\cal A}$,

$\displaystyle D_{\alpha}(\mathbf{w}_{\rho}||\mathbf{r}_{\tau})\geq
D_{\alpha}(\mathbf{w}_{\rho^{\prime}}||\mathbf{r}_{\tau^{\prime}}).$ (275)

## References

  * Campbell et al. [2017a] E. T. Campbell, B. M. Terhal, and C. Vuillot, Nature 549, 172 (2017a).
  * Raussendorf and Briegel [2001] R. Raussendorf and H. J. Briegel, Phys. Rev. Lett. 86, 5188 (2001).
  * Raussendorf et al. [2003] R. Raussendorf, D. E. Browne, and H. J. Briegel, Phys. Rev. A 68, 022312 (2003).
  * Nickerson et al. [2014] N. H. Nickerson, J. F. Fitzsimons, and S. C. Benjamin, Phys. Rev. X 4, 041041 (2014).
  * Nikahd et al. [2017] E. Nikahd, M. Sedighi, and M. Saheb Zamani, Phys. Rev. A 96, 032337 (2017).
  * Chao and Reichardt [2018] R. Chao and B. W. Reichardt, Npj Quantum Inf. 4, 1 (2018).
  * Lin et al. [2020] C. Lin, G. Yang, Q. Luo, and X. Li, Quantum Inf. Process. 19, 243 (2020).
  * Bourassa et al. [2021] J. E. Bourassa, R. N. Alexander, M. Vasmer, A. Patil, I. Tzitrin, T. Matsuura, D. Su, B. Q. Baragiola, S. Guha, G. Dauphinais, K. K. Sabapathy, N. C. Menicucci, and I. Dhand, Quantum 5, 392 (2021).
  * Chamberland et al. [2022] C. Chamberland, K. Noh, P. Arrangoiz-Arriola, E. T. Campbell, C. T. Hann, J. Iverson, H. Putterman, T. C. Bohdanowicz, S. T. Flammia, A. Keller, G. Refael, J. Preskill, L. Jiang, A. H. Safavi-Naeini, O. Painter, and F. G. Brandão, PRX Quantum 3, 010329 (2022).
  * Bravyi and Kitaev [1998] S. B. Bravyi and A. Y. Kitaev, arXiv:quant-ph/9811052 (1998).
  * Dennis et al. [2002] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, J. Math. Phys. 43, 4452 (2002).
  * Freedman [2001] M. H. Freedman, Found. Comput. Math. 1, 183 (2001).
  * Gottesman [1997] D. Gottesman, Stabilizer codes and quantum error correction, Ph.D. thesis, Caltech (1997).
  * Gottesman [1998] D. Gottesman, arXiv:quant-ph/9807006 (1998).
  * Eastin and Knill [2009] B. Eastin and E. Knill, Phys. Rev. Lett. 102, 110502 (2009).
  * Veitch et al. [2012] V. Veitch, C. Ferrie, D. Gross, and J. Emerson, New J. Phys. 14, 113011 (2012).
  * Campbell et al. [2012] E. T. Campbell, H. Anwar, and D. E. Browne, Phys. Rev. X 2, 041021 (2012).
  * Bravyi and Kitaev [2005] S. Bravyi and A. Kitaev, Phys. Rev. A 71, 022316 (2005).
  * Reichardt [2005] B. W. Reichardt, Quantum Inf. Process. 4, 251 (2005).
  * Bravyi and Haah [2012] S. Bravyi and J. Haah, Phys. Rev. A 86, 052329 (2012).
  * Haah et al. [2017] J. Haah, M. B. Hastings, D. Poulin, and D. Wecker, Quantum 1, 31 (2017).
  * Hastings and Haah [2018] M. B. Hastings and J. Haah, Phys. Rev. Lett. 120, 050504 (2018).
  * Calderbank and Shor [1996] A. R. Calderbank and P. W. Shor, Phys. Rev. A 54, 1098 (1996).
  * Steane [1996] A. Steane, Proc. R. Soc. Lond. A. 452, 2551 (1996).
  * Rengaswamy et al. [2020] N. Rengaswamy, R. Calderbank, M. Newman, and H. D. Pfister, IEEE Journal on Selected Areas in Information Theory 1, 499 (2020).
  * Litinski [2019] D. Litinski, Quantum 3, 205 (2019).
  * Koukoulekidis and Jennings [2022] N. Koukoulekidis and D. Jennings, Npj Quantum Inf. 8, 42 (2022).
  * Gross [2006] D. Gross, J. Math. Phys. 47, 122107 (2006).
  * Appleby [2005] D. M. Appleby, J. Math. Phys. 46, 052107 (2005).
  * Veinott [1971] A. F. Veinott, Manag. Sci. 17, 547 (1971).
  * Horodecki and Oppenheim [2013] M. Horodecki and J. Oppenheim, Nat. Commun. 4, 1 (2013).
  * Blackwell [1953] D. Blackwell, Ann. Math. Stat 24, 265 (1953).
  * Ruch and Mead [1976] E. Ruch and A. Mead, Theor. Chim. Acta 41, 95 (1976).
  * Lostaglio [2019] M. Lostaglio, Rep. Prog. Phys 82, 114001 (2019).
  * Gross [2005] D. Gross, Computational power of quantum many-body states and some results on discrete phase spaces, Ph.D. thesis, Imperial College London (2005).
  * Mari and Eisert [2012] A. Mari and J. Eisert, Phys. Rev. Lett. 109, 230503 (2012).
  * Galvão [2005] E. F. Galvão, Phys. Rev. A 71, 042302 (2005).
  * Cormick et al. [2006] C. Cormick, E. F. Galvão, D. Gottesman, J. P. Paz, and A. O. Pittenger, Phys. Rev. A 73, 012301 (2006).
  * Veitch et al. [2012] V. Veitch, C. Ferrie, D. Gross, and J. Emerson, New Journal of Physics 14, 113011 (2012).
  * Anwar et al. [2012] H. Anwar, E. T. Campbell, and D. E. Browne, New Journal of Physics 14, 063006 (2012).
  * Raussendorf et al. [2020] R. Raussendorf, J. Bermejo-Vega, E. Tyhurst, C. Okay, and M. Zurel, Phys. Rev. A 101, 012350 (2020).
  * Zurel et al. [2020] M. Zurel, C. Okay, and R. Raussendorf, Phys. Rev. Lett. 125, 260404 (2020).
  * Catani and Browne [2017] L. Catani and D. E. Browne, New J. Phys. 19, 073035 (2017).
  * Delfosse et al. [2015] N. Delfosse, P. Allard Guerin, J. Bian, and R. Raussendorf, Phys. Rev. X 5, 021003 (2015).
  * Catani and Browne [2018] L. Catani and D. E. Browne, Phys. Rev. A 98, 052108 (2018).
  * Regula [2022] B. Regula, Phys. Rev. Lett. 128, 110505 (2022).
  * Campbell and Browne [2009] E. T. Campbell and D. E. Browne, in Theory of Quantum Computation, Communication, and Cryptography, edited by A. Childs and M. Mosca (Springer Berlin Heidelberg, Berlin, Heidelberg, 2009) pp. 20–32.
  * Fang and Liu [2020] K. Fang and Z.-W. Liu, Phys. Rev. Lett. 125, 060405 (2020).
  * Bengtsson and Życzkowski [2006] I. Bengtsson and K. Życzkowski, Geometry of Quantum States: An Introduction to Quantum Entanglement (Cambridge University Press, 2006).
  * Bravyi et al. [2016] S. Bravyi, G. Smith, and J. A. Smolin, Phys. Rev. X 6, 021043 (2016).
  * Watrous [2018] J. Watrous, The Theory of Quantum Information (Cambridge University Press, 2018).
  * Wang et al. [2019] X. Wang, M. M. Wilde, and Y. Su, New J. Phys. 21, 103002 (2019).
  * Schmid et al. [2022] D. Schmid, H. Du, J. H. Selby, and M. F. Pusey, Phys. Rev. Lett. 129, 120403 (2022).
  * Allard Guérin [2015] P. Allard Guérin, Wigner Function Negativity and Contextuality in Quantum computation with Rebits, Master’s thesis, The University of British Columbia (2015).
  * Raussendorf and Harrington [2007] R. Raussendorf and J. Harrington, Phys. Rev. Lett. 98, 190504 (2007).
  * Veitch et al. [2014] V. Veitch, S. A. H. Mousavian, D. Gottesman, and J. Emerson, New J. Phys. 16, 013009 (2014).
  * Howard and Campbell [2017] M. Howard and E. Campbell, Phys. Rev. Lett. 118, 090501 (2017).
  * Wang et al. [2020] X. Wang, M. M. Wilde, and Y. Su, Phys. Rev. Lett. 124, 090505 (2020).
  * Fang and Liu [2022] K. Fang and Z.-W. Liu, PRX Quantum 3, 010337 (2022).
  * Raussendorf et al. [2017] R. Raussendorf, D. E. Browne, N. Delfosse, C. Okay, and J. Bermejo-Vega, Phys. Rev. A 95, 052334 (2017).
  * Note [1] Note that since the set ${\cal A}$ is dense in $\alpha\in(1,\infty)$, one could extend the definition of $D_{\alpha}(\mathbf{w}||\mathbf{r})$ to all $\alpha\geq 1$ by continuity.
  * Note [2] We note that an analogous set of magic monotones can be defined for systems of odd-prime dimension via:  $\Gamma_{\alpha}(\rho)=\mathop{inf}\displaylimits_{\tau\in STAB}D_{\alpha}(W_{\rho}||W_{\tau}).$ (276) .
  * Seddon et al. [2021] J. R. Seddon, B. Regula, H. Pashayan, Y. Ouyang, and E. T. Campbell, PRX Quantum 2, 010345 (2021).
  * Knill et al. [1996] E. Knill, R. Laflamme, and W. Żurek, arXiv:quant-ph/9610011 (1996).
  * Steane [1999] A. M. Steane, IEEE Transactions on Information Theory 45, 1701 (1999).
  * Campbell et al. [2017b] E. T. Campbell, B. M. Terhal, and C. Vuillot, Nature 549, 172 (2017b).
  * Note [3] Under the restriction to the rebit sub-theory of quantum computing subject to CSS circuits, the link between negativity and magic has been restored [44]. It therefore follows that mana is a monotone under the class of distillation protocols considered here. In fact, the monotonicity of mana is equivalent to $\Delta D_{\alpha}\geq 0$ in the limit $\alpha\rightarrow 1$.
  * Beigi [2013] S. Beigi, J. Math. Phys. 54, 122202 (2013).
  * Mosonyi [2014] M. Mosonyi, in 9th Conference on the Theory of Quantum Computation, Communication and Cryptography, May 21-23, 2014, Singapore, LIPIcs, Vol. 27, edited by S. T. Flammia and A. W. Harrow (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014) pp. 88–98.
  * Wilde et al. [2014] M. M. Wilde, A. Winter, and D. Yang, Communications in Mathematical Physics 331, 593 (2014).
  * Kitaev [2003] A. Kitaev, Ann. Phys. 303, 2 (2003).
  * Albarelli et al. [2018] F. Albarelli, M. G. Genoni, M. G. A. Paris, and A. Ferraro, Phys. Rev. A 98, 052350 (2018).
  * Moiseyev [2011] N. Moiseyev, Non-Hermitian Quantum Mechanics (Cambridge University Press, 2011).
  * Giovagnoli and Wynn [1996] A. Giovagnoli and H. P. Wynn, Linear Algebra Appl. 239, 215 (1996).
  * Giovagnoli and Wynn [1985] A. Giovagnoli and H. P. Wynn, Linear Algebra Appl. 67, 111 (1985).
  * Steerneman [1990] A. G. M. Steerneman, Linear Algebra Appl. 127, 107 (1990).
  * Bhatia [2013] R. Bhatia, Matrix analysis, Vol. 169 (Springer Science & Business Media, 2013).
  * Woods and Horodecki [2019] M. P. Woods and M. Horodecki, arXiv:quant-ph/1912.05562 (2019).


# Forward-Euler time-discretization for Wasserstein gradient flows can be
wrong

Yewei Xu, Qin Li  Department of Mathematics, University of Wisconsin-Madison,
Madison, WI 53706<EMAIL_ADDRESS><EMAIL_ADDRESS>
(Date: June 2024)

###### Abstract.

In this note, we examine the forward-Euler discretization for simulating
Wasserstein gradient flows. We provide two counter-examples showcasing the
failure of this discretization even for a simple case where the energy
functional is defined as the KL divergence against some nicely structured
probability densities. A simple explanation of this failure is also discussed.

Keywords. optimal transport, numerical PDEs, numerical methods

##  1\. Introduction

Minimizing a functional over the space of probability measures is a topic that
has garnered tremendous amount of interests over the past few years. The
optimization problems emerging from practice are increasingly challenging, and
many take the form over the probability measure space:

(1) $\min_{\rho\in\mathcal{P}(\Omega)}F[\rho]$

where $\mathcal{P}(\Omega)$ is the collection of all probability measure over
the domain $\Omega\subset\mathbb{R}^{d}$, $F$ is a functional that maps a
probability measure to a scalar. Our task is to find, among infinite many
possibilities, the probability measure that gives the least value for $F$.
This task can be viewed as an extension from the classical optimization
problem usually posed over the Euclidean space $\mathbb{R}^{d}$. As a
counterpart of the classical gradient descent over $\mathbb{R}^{d}$, we now
formulate the gradient flow:

(WGF)
$\partial_{t}\rho=-\nabla_{\mathfrak{m}}F[\rho]=\nabla\cdot\left(\rho\nabla\frac{\delta
F}{\delta\rho}\right)\,,$

where $\mathfrak{m}$ stands for the chosen metric over $\mathcal{P}$. If we
confine ourselves to $\mathcal{P}_{2}$, the class of probability measures
whose second moments are finite, the Wasserstein $W_{2}$ metric can be
deployed, and the gradient can be expressed explicitly.

The structure of the PDE strongly suggests a particle treatment on the
numerical level. Indeed the term $-\nabla\frac{\delta F}{\delta\rho}$ can be
simply interpreted as the velocity field. Let $X_{0}$ be drawn from
$\rho_{0}$, the initial distribution, then driven by this velocity field:

(2) $\dot{X}_{t}=-\nabla\left.\frac{\delta
F}{\delta\rho}\right|_{\rho_{t}}(X_{t})\quad\Rightarrow\quad\mathrm{Law}(X_{t})=\rho_{t}\,\quad\text{for
all time}\,.$

In the equation $\nabla\left.\frac{\delta F}{\delta\rho}\right|_{\rho_{t}}$
means the gradient is evaluated at $\rho_{t}$, the solution to (WGF) at time
$t$. Often in practice, this equation cannot be executed since $\rho_{t}$ is
not known ahead of time. So numerically the dynamics is replaced by an
ensemble of particles (sometimes also termed the particle method):

$\rho_{t}\approx\frac{1}{N}\sum_{i}\delta_{x_{i}(t)}\,,\quad\text{with}\quad\dot{x}_{i}=-\nabla\left.\frac{\delta
F}{\delta\rho}\right|_{\rho_{t}}(x_{i}(t))\,.$

This is now a coupled ODE system of size $Nd$. Running ODEs has been a
standard practice. Most literature choose an off-the-shelf solver, and the
simplest among them is the classical Forward Euler (shorthanded by FE
throughout the paper). Setting $h$ to be a very small time-stepping, we can
march the system forward in time:

(3) ${x}_{i}^{n+1}=x_{i}^{n}-h\nabla\left.\frac{\delta
F}{\delta\rho}\right|_{\rho^{n}}(x^{n}_{i})\,,$

where the superindex stands for the time step, and the lowerindex stands for
the choice of the particle. This numerical strategy is vastly popular:
Potentially for its simplicity and the lack of counter-argument, it has been
the go-to method in many engineering problems, see [1, 24, 27, 25, 13, 19, 9].

We would like to alarm, in our very short note, that this is probably a
dangerous practice. In particular, we will give two counter-examples, both
framed in the very simple setting where $F$ is a KL divergence against a
nicely constructed target distribution, and show that (3) could lead to
erroneous answer. In fact, we will go back to a even more fundamental formula
(2) and show the forward Euler conducted at this level is problematic.

Both examples use the KL divergence, with the target distribution being very
smooth, and log-concave. The specific introduction of the problem has
different origins, but they share similar features. FE brings the cascading
effect along iteration: It decreases the smoothness of the potential in each
iteration, and thus after finite rounds of iteration, the distribution at hand
is no longer smooth and no longer has finite Wasserstein derivative. This loss
of regularity can be introduced by the non-injectivity of the pushforward map,
or can be rooted in the consumption of two derivatives in the update, as will
be demonstrated in the two examples respectively.

This discovery might seem surprising at the first glance, but it really
resonates the classical discovery in numerical PDEs, where most of solvers
perform discretization in space before that in time [16]. This includes the
famous “Method of lines” [8] and “spectral method” [10]. At the heart of the
thought is usually termed the stability theory: time discretization is
restricted by the largest spectrum of the PDE operator at hand. Since PDE
operators are typically unbounded, discretization has to be done in space
first, to threshold the largest spectrum, allowing finite time-stepping. This
thinking is somewhat hidden in particle-method for gradient-flow, but the
restriction should not be overlooked.

This discovery also brings us back to the classical proposal in the seminar
work of [14], where the authors essentially proposed an implicit Euler solver
for advancing (WGF). Largely recognized as non-solvable, efforts have been
made towards developing alternatives [20, 22, 17, 18, 12, 4, 6, 15, 26]. Many
such alternatives need to go through similar test on stability, but this task
is beyond the scope of the current note.

Section 2 collects some classical derivation on Wasserstein derivative.
Readers familiar with the matter should feel safe to skip it. Section 3
provides the two counter-examples and the shared general theory that we
summarize.

##  2\. Basics and notations for gradient flow

We start off with some quick summary of preliminary results.

The problem under study (1) is an optimization over the probability measure
space, and it is viewed as an extension of optimization over the Euclidean
space, $\min_{x\in\mathbb{R}^{d}}E(x)$. As a consequence, it is expected that
many techniques for $\min_{x\in\mathbb{R}^{d}}E(x)$ can be carried over. The
simplest gradient descent finds $x$ by evolving the following ODE:

$\dot{x}=\frac{{\mathrm{d}}}{{\mathrm{d}}t}x=-\nabla_{x}E\,,\quad\text{so}\quad\lim_{t\to\infty}E(x(t))=\min_{x}E(x)\,,$

when some properties of $E$ are taken into account, non-asymptotic convergence
rate can also be derived.

To translate this strategy to solve problem (1) is not entirely
straightforward. The challenge here is two-folded:

  * –

$\mathcal{P}(\Omega)$ is infinite dimensional. In the classical optimization
problem, $x\in\mathbb{R}^{d}$ and is finite-dimensional.
$\rho\in\mathcal{P}(\Omega)$ is an infinite dimensional object. To push $\rho$
around necessitates the language of partial differential equation. The PDE
will characterize the evolution of $\rho(t,\cdot)$ over $\mathcal{P}(\Omega)$
in time.

  * –

$\mathcal{P}(\Omega)$ is a nonlinear space. Unlike the Euclidean space and the
Hilbert function space that can be “normed,” $\mathcal{P}(\Omega)$ is
nonlinear, and thus is a manifold. Without a proper definition of the metric,
even the term “gradient” is not valid. Due to the nonlinearity, metrics have
to be defined locally to measure the distance between two probability
measures. Many choices are available [11, 21]. Among them it has been
prevalent to deploy the Wasserstein metric [5, 23, 3, 7]. It is a term that is
derived from optimal transport theory that measures the length of geodesics
between two probability measures. On this metric, one can define the local
tangent plane and gradient with respect to this metric. This is the metric
that we will use throughout the paper.

Under this metric, it is a standard practice to lift up gradient descent to
gradient flow, and we arrive at (WGF).

###  2.1. Basic Notations

Throughout the paper, we study objects within
$\mathcal{P}_{2}(\mathbb{R}^{d})$, the collection of probability measures of
finite second moment on $\mathbb{R}^{d}$. This space has an important subset
$\mathcal{P}_{2}^{r}(\mathbb{R}^{d})$ that collects all probability measures
that are Lebesgue absolutely continuous. Then for any
$\rho\in\mathcal{P}_{2}^{r}(\mathbb{R}^{d})$, we can associate it with a
probability density function (pdf) $p:\mathbb{R}^{d}\to[0,+\infty)$ such that
${\mathrm{d}}\rho=p{\mathrm{d}}{x}$. For easier notation, we write
$p\propto\exp(-U)$ for some $U:\mathbb{R}^{d}\to\mathbb{R}$. We may use $\rho$
and $\exp(-U)$ interchangeably when the context is clear. The measure $\rho$
is said to be log-concave if $U$ is convex, and log-smooth if $U$ is smooth.

Over the space of $\mathcal{P}_{2}$, we define a functional
$F:\mathcal{P}_{2}(\mathbb{R}^{d})\to\mathbb{R}$. For every $\rho$ define the
$W_{2}$ subgradient of $F$ as:

$\nabla\left.\frac{\delta F}{\delta\rho}\right|_{\rho}\,,$

i.e., the gradient of the first variation of $F$ with respect to the measure
$\rho$. We denote $D(|\partial F|)$ the collection of $\rho$ whose subgradient
has finite slope in $L_{2}(\rho)$([2, Lemma 10.1.5]), and for $\rho_{t}\in
D(|\partial F|)$, gradient descent continuous-in-time over the Wasserstein
metric gives (WGF).

When FE discretization is deployed, we have the updates:

(FE) $\rho_{k+1}=(\text{Id}-h\left.\nabla\frac{\delta
F}{\delta\rho}\right|_{\rho_{k}})_{\sharp}\rho_{k}\quad\text{ for }\quad
k=0,1,2,\dots\,.$

with $\rho_{k}$ standing for the $k$-th iteration solution, $h$ is the time-
stepping step-size. Id is the identity map, and $\sharp$ is the classical
pushforward operator. This is the most standard numerical solver used for
(WGF), and has been deployed vastly in literature.

According to the definition of the pushforward operator, for any Borel measure
$\sigma$ on $X$, $T_{\sharp}\sigma$ denotes a new probability measure that
satisfies:

$(T_{\sharp}\sigma)(A)=\sigma(T^{-1}(A))\quad\text{ for any}\quad A\subseteq
Y\,,$

when the given $T:X\to Y$. Here $T$ does not have to be invertible, and
$T^{-1}$ only refers to the pre-image. As a consequence, if both measures have
densities that are denoted by
${\mathrm{d}}\left(T_{\sharp}\sigma\right)=q{\mathrm{d}}y$ and
${\mathrm{d}}\sigma=p{\mathrm{d}}x$, then:

$(T_{\sharp}\sigma)(A)=\int_{A}q(y){\mathrm{d}}{y}=\int_{T^{-1}(A)}p(x){\mathrm{d}}x=\sigma(T^{-1}(A))\,,$

When $T$ is a diffeomorphism, by the change of variable formula for measures,

(4) $q(y)=p(T^{-1}(y))|{\mathrm{J}}_{T^{-1}}(y)|\,.$

where ${\mathrm{J}}_{T^{-1}}$ stands for the Jacobian of the inverse map of
$T$, and $|\cdot|$ means taking the absolute value of the determinant of the
given matrix.

###  2.2. KL Divergence as the energy functional

We pay a special attention to the energy functional that has the form of the
Kullback-Leibler(KL) divergence.

Given two probability measures $\mu,\gamma\in\mathcal{P}_{2}(\mathbb{R}^{d})$,
the Kullback-Leibler(KL) divergence of $\mu$ with respect to $\gamma$ is
defined as:

(5)
$\text{KL}(\mu|\gamma):=\begin{cases}\int_{\mathbb{R}^{d}}\frac{d\mu}{d\gamma}\ln(\frac{d\mu}{d\gamma})d\gamma&\text{if
}\mu\ll\gamma\,,\\\ +\infty&\text{Otherwise}\,,\end{cases}$

where $\frac{d\mu}{d\gamma}$ is understood in the sense of Radon-Nikodym
derivatives. If in addition, $\mu$ and $\gamma$ are absolutely continuous with
density functions denoted as $e^{-V}$ and $e^{-U}$ respectively for some
differentiable $U$ and $V$, then

$F(\mu):=\text{KL}(\mu|\gamma)=\int_{\mathbb{R}^{d}}(U-V)\exp(-V){\mathrm{d}}x\,,$

and the subgradient (velocity field) is explicitly solvable:

(6) $\nabla\left.\frac{\delta F}{\delta\mu}\right|_{\mu}(x)=-\nabla
V(x)+\nabla U(x)\ .$

##  3\. Counter-examples

We provide two counter-examples in subsection 3.1 to invalidate the approach
of (FE). The failure of (FE) is rooted in the loss of regularity. According to
[2] Section 10, only when $\rho\in D(|\partial F|)$ can we properly define the
differential and thus run (WGF) forward in time. We will show that $\rho_{k}$
will drop out of the set even if $\rho_{0}$ is prepared within, putting (WGF)
to halt. There are two sources of this error, and the two examples showcase
them respectively. One reason for the loss of regularity is the non-
injectivity of the pushforward map used to march to $\rho_{k+1}$ from
$\rho_{k}$. The map sends multiple $x$’s to the same $y$, the density
accumulates in a certain region, and a jump discontinuity is introduced at the
boundary. The second reason for the loss of regularity is the consumption of
two derivatives in the pushforward map. As a consequence, every $\rho_{k}$ has
two fewer derivatives than its prior. If $\rho_{0}$ has finite regularity,
then in finite time, $\rho_{k}$ drops out of $D(|\partial F|)$, halting the
running of (WGF). This argument can be made more precise and we discuss a
proposition in subsection 3.2.

These results suggest that even though FE discretization is intuitive, the
failure is universal.

###  3.1. Examples

The two examples shown below respectively point towards two sources of loss of
regularity.

#### Example 1: Loss of regularity due to the noninjectivity of the
pushforward map

In the first example, we set

$F(\rho)={\mathrm{KL}}(\rho|e^{-U})\,,\quad\text{with}\quad
U(x)=\frac{x^{2}}{2}+\frac{x^{4}}{4}+C_{0}\,.$

This functional is well defined over $\mathcal{P}_{2}^{r}(\mathbb{R})$, and
the constant $C_{0}$ is chosen to normalize the measure:

$C_{0}=\ln\left(\int_{\mathbb{R}}\exp(-\frac{x^{2}}{2}-\frac{x^{4}}{4}){\mathrm{d}}x\right)\,.$

We will show the failure of the (FE) approach. Setting the initial condition
$\rho_{0}$ to be the very simple Gaussian function, by marching forward by
just one step of size $h$, we demonstrate that $\rho_{1}\not\in D(|\partial
F|)$.

######  Proposition 1.

Assume the initial distribution $\rho_{0}(x)$ has the density of

$p_{0}(x)=\frac{1}{\sqrt{2\pi}}\exp(-\frac{x^{2}}{2})\,,$

then for any $h>0$, the one-time-step solution $\rho_{1}$ also has a density
$p_{1}$, with $p_{1}$ being discontinuous, and thus $\rho_{1}\not\in
D(|\partial F|)$, stopping the application of (FE) to produce $\rho_{2}$.

###### Proof.

According to (FE),

$\rho_{1}=T_{\sharp}\rho_{0}\quad\text{ with }\quad
T(x):=x-h\left.\nabla\frac{\delta F}{\delta\rho}\right|_{\rho_{0}}(x)\ .$

We can explicitly compute $p_{1}$. In particular, calling (6), and noticing

$V(x)=\frac{x^{2}}{2}+\ln(2\sqrt{\pi})\ ;\
U(x)=\frac{x^{2}}{2}+\frac{x^{4}}{4}+C_{0}\,,$

we have:

(7) $T(x)=x-h(\nabla U(x)-\nabla V(x))=x-hx^{3}\,.$

It is important to notice that $T$ is not one-to-one, as seen in Figure 1.

Figure 1. The plot on the left shows the pushforward function $T$. Note that
every $y\in(0,\frac{2}{3}\sqrt{\frac{1}{3h}})$ has three pre-image points of
$x$. For example, for $y\in[0,\frac{2}{3}\sqrt{\frac{1}{3h}}]$, the different
parts of pre-image are bold-lined: $(-\infty,-\sqrt{\frac{1}{3h}}]$,
$[-\sqrt{\frac{1}{3h}},\sqrt{\frac{1}{3h}}]$ and
$[\sqrt{\frac{1}{3h}},\infty)$ respectively. The plot on the right shows the
mapping of $T$. When $T$ is confined in three parts of the region, denoted as
$T_{1},T_{2},T_{3}$, injectivity is resumed.

In particular, every point in the range of
$y\in(0,\frac{2}{3}\sqrt{\frac{1}{3h}})$ has three pre-image points of $x$.
Only confined in smaller $x$-regions, injectivity is resumed and inversion of
$T$ is well-defined, see Table 1. Recall that $T(x)=x-hx^{3}$, so for any
given pair $(x,y)$ such that $T_{i}(x)=T(x)=y$, we have the determinant of the
Jacobian being $|\text{J}_{T_{i}}(x)|=|\text{J}_{T}(x)|=|1-3hx^{2}|$. When
$x\neq\pm\sqrt{\frac{1}{3h}}$, we define:

$|\text{J}_{i}(y)|\doteq|\text{J}_{T^{-1}_{i}(y)}|=\frac{1}{|\text{J}_{T_{i}}(x)|}=\frac{1}{|1-3hx^{2}|}\
.$

Map | domain of $x$ | range of $y$
---|---|---
$T_{1}$ | $(-\infty,-\sqrt{\frac{1}{3h}})$ | $y\in(-\frac{2}{3}\sqrt{\frac{1}{3h}},+\infty)$
$T_{2}$ | $(-\sqrt{\frac{1}{3h}},\sqrt{\frac{1}{3h}})$ | $y\in(-\frac{2}{3}\sqrt{\frac{1}{3h}},\frac{2}{3}\sqrt{\frac{1}{3h}})$
$T_{3}$ | $(\sqrt{\frac{1}{3h}},+\infty)$ | $y\in(-\infty,\frac{2}{3}\sqrt{\frac{1}{3h}})$
Table 1. Range of $T$ in different parts of domains of injectivity.

The loss of such injectivity prevents us to directly apply (4), however,
similar derivative nevertheless can be carried out. We focus on $y>0$ and
summarize the calculations here:

  * •

At $y=\frac{2}{3}\sqrt{\frac{1}{3h}}$, there are two points in the pre-image.
Since $\rho_{0}$ is Lebesgue absolutely continuous,
$\rho_{1}(\\{\frac{2}{3}\sqrt{\frac{1}{3h}}\\})=0$.

  * •

In $(\frac{2}{3}\sqrt{\frac{1}{3h}},\infty)$, every $y$ has one pre-image
point given by $T_{1}^{-1}$. Deploying (4), we have:

(8) $p_{1}(y)=p_{0}(T_{1}^{-1}(y))|{\mathrm{J}}_{1}(y)|\,.$

  * •

In $(0,\frac{2}{3}\sqrt{\frac{1}{3h}})$, every $y$ has three pre-image points
given by $T_{1}^{-1}$, $T_{2}^{-1}$ and $T_{3}^{-1}$ respectively 111The
pushforward measure on $(0,\frac{2}{3}\sqrt{\frac{1}{3h}})$ is equal to
$(T_{1})_{\sharp}(\rho_{0}\left.\right|_{T_{1}^{-1}(\frac{2}{3}\sqrt{\frac{1}{2h}},-\sqrt{\frac{1}{h}})})+(T_{2})_{\sharp}(\rho_{0}\left.\right|_{(0,\sqrt{\frac{1}{3h}})})+(T_{3})_{\sharp}(\rho_{0}\left.\right|_{(\sqrt{\frac{1}{3h}},\sqrt{\frac{1}{h}})})$,
where $\rho_{0}\left.\right|_{A})$ denotes the measure confined on the set
$A$. Each of $T_{1},T_{2},T_{3}$ confined on their domains is a
diffeomorphism, and therefore we may apply the change of variable formula to
compute the densities of the pushforward measures.. The new density is:

(9) $\displaystyle p_{1}(y)=$ $\displaystyle
p_{0}(T_{1}^{-1}(y))|{\mathrm{J}}_{1}(y)|+p_{0}(T_{2}^{-1}(y))|{\mathrm{J}}_{2}(y)|+p_{0}(T_{3}^{-1}(y))|{\mathrm{J}}_{3}(y)|\,.$

Noting that
$\lim_{y\uparrow\frac{2}{3}\sqrt{\frac{1}{3h}}}T_{2}^{-1}(y)=\sqrt{\frac{1}{3h}}=\lim_{y\uparrow\frac{2}{3}\sqrt{\frac{1}{3h}}}T_{3}^{-1}(y)$,
so

(10)
$\lim_{y\uparrow\frac{2}{3}\sqrt{\frac{1}{3h}}}p_{0}(T_{2}^{-1}(y))=p_{0}(\sqrt{\frac{1}{3h}})=\lim_{y\uparrow\frac{2}{3}\sqrt{\frac{1}{3h}}}p_{0}(T_{3}^{-1}(y))>0\,,$

and

(11)
$\lim_{y\uparrow\frac{2}{3}\sqrt{\frac{1}{3h}}}|{\mathrm{J}}_{2}(y)|=\lim_{x\uparrow\sqrt{\frac{1}{3h}}}\frac{1}{|1-3hx^{2}|}=+\infty=\lim_{x\downarrow\sqrt{\frac{1}{3h}}}\frac{1}{|1-3hx^{2}|}=\lim_{y\uparrow\frac{2}{3}\sqrt{\frac{1}{3h}}}|{\mathrm{J}}_{3}(y)|\,.$

Plugging (10)-(11) back in (9), we notice a blow-up solution at
$y=\frac{2}{3}\sqrt{\frac{1}{3h}}$222We should note that it roughly behaves as
$\frac{1}{\sqrt[3]{\epsilon}}$ for small $\epsilon$ and is an integrable
singularity.. Comparing (8) and (9), it is now immediate that $p_{1}(y)$ has a
jump discontinuity at $y=\frac{2}{3}\sqrt{\frac{1}{3h}}$, which means the
density associated with the probability measure $\rho_{1}$, $p_{1}\notin
W_{\text{loc}}^{1,1}(\mathbb{R})$. By [2, Theorem 10.4.9], $\rho_{1}\not\in
D(|\partial F|)$. The same derivation applies to
$p_{1}(-\infty,-\frac{2}{3}\sqrt{\frac{1}{3h}})$. ∎

In this example, the initial condition is a very nice distribution, and the
target distribution is log-concave and smooth. Problem is introduced by the
non-injectivity of the pushforward map $T$. More precisely, for
$y\in(\frac{2}{3}\sqrt{\frac{1}{3h}},+\infty)$, only the part $T_{1}$
contributes to the density here. For $y=(0,\frac{2}{3}\sqrt{\frac{1}{3h}})$,
however, all of $T_{1},T_{2},T_{3}$ contribute to the measure. Since the
pushforward densities of $T_{2}$ and $T_{3}$ are not vanishing at the border
of $y=\frac{2}{3}\sqrt{\frac{1}{3h}}$, a jump discontinuity is introduced.
Such jump discontinuity is observed for any finite $h$. As $h\to 0$, according
to (7), $T=x$, also seen in Figure 2. The map converges to the identity map,
and the distribution does not move. The problem only occurs to discrete-in-
time setting introduced by running (FE).

Figure 2. Plot of pushforward functions $T$ for different step sizes $h$. In
the $h\to 0$ limit, $T(x)=x$.

#### Example 2: Loss of regularity due to the consumption of derivatives.

The second example share similar features as the first, but the irregularity
is introduced through a different manner. The problem is set as:

$F(\rho)={\mathrm{KL}}(\rho|e^{-U})\,,\quad\text{with}\quad
U(x)=\frac{x^{2}}{2}+\ln(2\sqrt{\pi})\,.$

Here the constant $\ln(2\sqrt{\pi})$ takes care of the normalization. As in
the previous example, the energy function is well defined over
$\mathcal{P}_{2}^{r}(\mathbb{R})$. According to (FE), the pushforward for
every iteration is:

(12) $\rho_{k+1}=(T_{k})_{\sharp}\rho_{k}\quad\text{ with }\quad
T_{k}(x):=x-h_{k}\left.\nabla\frac{\delta
F}{\delta\rho}\right|_{\rho_{k}}(x)\,,$

where $h_{k}\in(0,1)$ is the step-size at $k$-th iteration. We initialize our
iteration at $\rho_{0}$ with the density

(13) $p_{0}(x)=\frac{1}{D_{0}}\exp(-V_{0}(x))\,,\quad\text{with}\quad
V_{0}(x):=\begin{cases}\frac{x^{2}}{2}&x\in(-1,1)\\\
|x|-\frac{1}{2}&\text{Otherwise}\end{cases}\,,$

where $D_{0}$ stands for the normalization coefficient

(14)
$D_{0}=\int_{\mathbb{R}}V_{0}(x)dx=\sqrt{2\pi}\text{Erf}(\frac{1}{\sqrt{2}})+\frac{2}{\sqrt{e}}$

. The following proposition holds true:

######  Proposition 2.

Under the conditions stated above:

  * •

$F$ is $1$-convex over $\mathcal{P}_{2}^{r}(\mathbb{R})$ with its unique
minimizer being $\rho_{*}=e^{-U}$. The minimum value $F_{*}=F(\rho_{*})=0$.

  * •

The density function $p_{1}$ of $\rho_{1}$, is discontinuous. In addition,
$\rho_{1}\not\in D(|\partial F|)$.

  * •

There are constants $a_{k},c_{k}\in[1,\infty)$ and $b_{k}\in\mathbb{R}$ so
that $p_{k}(x)$ has the following form:

(15) $p_{k}(x)=\begin{cases}\frac{1}{D_{0}}\exp(-\frac{x^{2}}{2})&x\in[0,1)\\\
0&x\in[1,c_{k})\\\ \exp(-a_{k}x+b_{k})&x\in[c_{k},+\infty)\\\
p_{k}(-x)&x\in(-\infty,0)\end{cases}\,.$

This proposition immediately evokes our theorem:

######  Theorem 1.

Under the conditions as in Proposition 2, $F(\rho_{k})>0.019$ for all $k$.

###### Proof.

According to the Pinsker’s inequality, we have

$\displaystyle F(\rho_{k})-F_{*}$
$\displaystyle={\mathrm{KL}}(\rho_{k}|e^{-U})\geq
2\left(\text{TV}(\rho_{k},e^{-U})\right)^{2}$ $\displaystyle\geq
2\left(\int_{-1}^{1}(p_{k}(x)-p(x)){\mathrm{d}}x\right)^{2}$
$\displaystyle=2\left((\frac{1}{\sqrt{2\pi}}-\frac{1}{D_{0}})\int_{-1}^{1}\exp(-\frac{x^{2}}{2}){\mathrm{d}}x\right)^{2}$
$\displaystyle=4\pi\left(\text{Erf}(\frac{1}{\sqrt{2}})\right)^{2}\left(\frac{1}{\sqrt{2\pi}}-\frac{1}{\sqrt{2\pi}\text{Erf}(\frac{1}{\sqrt{2}})+\frac{2}{\sqrt{e}}}\right)^{2}>0.019\,.$

Here the second inequality comes from lower bounding the total variation using
the total variation on the subset $(-1,1)$; the third line comes from plugging
in Equation (13) and Equation (15); the last line comes from using the
definition of the normalization constant $D_{0}$ in Equation (14); and the
last inequality comes from a numerical computation. ∎

###### Proof for Proposition 2.

The first bullet point of the proposition is a direct derivation from [2,
Theorem 9.4.11]. To show the second bullet point, we compute $p_{1}$
explicitly. Following (6), the $W_{2}$-subgradient at $\rho_{0}$ is

$\left.\nabla\frac{\delta F}{\delta\rho}\right|_{\rho_{0}}(x)=-\nabla
V_{0}(x)+\nabla U(x)=\begin{cases}x+1&x\in(-\infty,-1]\\\ 0&x\in(-1,1)\\\
x-1&x\in[1,\infty)\end{cases}\,,$

meaning the pushforward map is

$T_{0}(x)=x-h_{0}\left.\nabla\frac{\delta
F}{\delta\rho}\right|_{\rho_{0}}=\begin{cases}(1-h_{0})x-h_{0}&x\in(-\infty,-1]\\\
x&x\in(-1,1)\\\ (1-h_{0})x+h_{0}&x\in[1,\infty)\end{cases}\,,$

for step-size $h_{0}$. The inverse and the Jacobian can also be computed
explicitly:

$T_{0}^{-1}(x)=\begin{cases}\frac{x+h_{0}}{1-h_{0}}\\\ x\\\
\frac{x-h_{0}}{1-h_{0}}\end{cases}\,,\quad\text{J}_{T_{0}^{-1}}(x)=\begin{cases}\frac{1}{1-h_{0}}&x\in(-\infty,-1]\\\
1&x\in(-1,1)\\\ \frac{1}{1-h_{0}}&x\in[1,\infty)\end{cases}\ .$

Using the change of variable formula for measures, Equation (4) gives

$\displaystyle p_{1}(x)$
$\displaystyle=p_{0}(T_{0}^{-1}(x))|{\mathrm{J}}_{T_{0}^{-1}}(x)|$
$\displaystyle=\frac{1}{D_{0}}\begin{cases}\frac{1}{1-h_{0}}\exp(-\frac{x+h_{0}}{1-h_{0}}+\frac{1}{2})&x\in(-\infty,-1]\\\
\exp(-\frac{x^{2}}{2})&x\in(-1,1)\\\
\frac{1}{1-h_{0}}\exp(-\frac{x-h_{0}}{1-h_{0}}+\frac{1}{2})&x\in[1,\infty)\end{cases}\,.$

It is immediate that $p_{1}$ has jump discontinuity at $\\{-1,1\\}$ two points
as long as $h_{0}>0$, and therefore it is not in
$W_{\text{loc}}^{1,1}(\mathbb{R})$. Hence $\rho_{1}\not\in D(|\partial F|)$
according to [2, Theorem 10.4.9].

To prove the third bullet point, we first notice that due to the symmetry, we
only need to show the validity of this formula for $x\geq 0$. When $k=0$, from
the definition in Equation (13),
$a_{0}=1,b_{0}=\frac{1}{2}-\ln(D_{0}),c_{0}=1$. Suppose that the claim is true
for $k$, then using (6) and (12):

$T_{k}(x)=x-h_{k}\left.\nabla\frac{\delta
F}{\delta\rho}\right|_{\rho_{k}}(x)=\begin{cases}x&x\in[0,1)\\\
(1-h_{k})x+a_{k}h_{k}&x\in[c_{k},\infty)\end{cases}\,.$

Noting the monotonicity of $T_{k}$ allows us to compute the image of $T$
explicitly. In particular:

$\text{Imag}(\left.T_{k}\right|_{[c_{k},\infty)})=[c_{k+1},\infty)\,,\quad\text{with}\quad
c_{k+1}=(1-h_{k})c_{k}+a_{k}h_{k}\geq 1+(a_{k}-1)h_{k}\geq 1\,.$

As a consequence, inverse and Jacobian can be computed:

$T_{k}^{-1}(x)=\begin{cases}x&x\in[0,1)\\\
\frac{x-a_{k}h_{k}}{1-h_{k}}&x\in[c_{k+1},\infty)\end{cases}\,,\quad\
\text{J}_{T_{k}^{-1}}(x)=\begin{cases}1&x\in[0,1)\\\
\frac{1}{1-h_{k}}&x\in[c_{k+1},\infty)\end{cases}\,,$

leading to

$p_{k+1}(x)=\begin{cases}\frac{1}{D_{0}}\exp(-\frac{x^{2}}{2})&x\in[0,1)\\\
0&x\in[1,c_{k+1})\\\ \exp(-a_{k+1}x+b_{k+1})&x\in[c_{k+1},+\infty)\\\
p_{k+1}(-x)&x\in(-\infty,0)\end{cases}\,,$

where $a_{k}$ and $b_{k}$ solve:

$\displaystyle\exp(-a_{k+1}x+b_{k+1})$
$\displaystyle=p_{k}(T_{k}^{-1}(x))|{\mathrm{J}}_{T_{k}^{-1}}(x)|$
$\displaystyle=\frac{1}{1-h_{k}}\exp(-a_{k}\frac{x-a_{k}h_{k}}{1-h_{k}}+b_{k})$
$\displaystyle=\exp\left(-\frac{a_{k}}{1-h_{k}}x+b_{k}+\frac{a_{k}^{2}h_{k}}{1-h_{k}}-\ln(1-h_{k})\right)\,,$

meaning

$b_{k+1}=b_{k}+\frac{a_{k}^{2}h_{k}}{1-h_{k}}-\ln(1-h_{k})\,,\quad
a_{k+1}=\frac{a_{k}}{1-h_{k}}>a_{k}\geq 1\,.$

This finishes the proof of induction. ∎

###  3.2. Loss of regularity through (FE) is generic

Both examples showcase the reduced regularity as one propagates $\rho_{k}$
forward in time according to (FE). This is a generic property that can be
shared across FE solver for gradient flow for all functionals of KL divergence
type. We extract this property and formulate the following:

######  Proposition 3.

Let $F(\rho)={\mathrm{KL}}(\rho|e^{-U})$ with
$U\in\mathcal{C}^{\infty}(\mathbb{R}^{d})$. Assume $U$ is gradient Lipschitz,
meaning ${\mathrm{Hess}}[U]\preceq MI$ for some $M\in(0,+\infty)$. Let
$\rho_{0}=e^{-V_{0}}$ for a smooth potential that is
$V_{0}\in\mathcal{C}^{m+2}(\mathbb{R})$ and
$-M_{0}I\preceq{\mathrm{Hess}}[V_{0}]$ for some $M_{0}\in(0,+\infty)$, then
the one-step pushforward

$\rho_{1}=({\mathrm{Id}}-h_{0}\left.\nabla\frac{\delta
F}{\delta\rho}\right|_{\rho_{0}})_{\sharp}\rho_{0}=e^{-V_{1}}$

has to have reduced regularity. Namely, for $h_{0}\in(0,\frac{1}{M+M_{0}})$,
$V_{1}\in\mathcal{C}^{m}$ has two fewer derivatives than $V_{0}$.

###### Proof.

According to the formula (FE) and (12):

$T_{0}(x)=x-h_{0}\left.\nabla\frac{\delta
F}{\delta\rho}\right|_{\rho_{0}}(x)=x+h_{0}\nabla V_{0}(x)-h_{0}\nabla
U(x)\,.$

Since $V_{0}\in\mathcal{C}^{m+2}$, $T_{0}\in\mathcal{C}^{m+1}$ and its
Jacobian is

${\mathrm{J}}_{T_{0}}(x)=I+h_{0}{\mathrm{Hess}}[V_{0}](x)-h_{0}{\mathrm{Hess}}[U](x)\succ
0\,.$

The positivity of the Jacobian comes from the choice of $h_{0}$. It also
implies that $T_{0}$ is injective, and thus by the Global Inverse Function
Theorem, $T_{0}^{-1}$ is well-defined and $T_{0}^{-1}\in\mathcal{C}^{m+1}$.
Using the change of variable between pushforward measures Equation (4)

$\displaystyle\exp\left(-V_{1}\left(x\right)\right)$
$\displaystyle=\left(\exp\left(-V_{0}\left(T_{0}^{-1}\left(x\right)\right)\right)\right)\left|{\mathrm{J}}_{T_{0}^{-1}}\left(x\right)\right|$
$\displaystyle=\exp\left(-\left(V_{0}\left(T_{0}^{-1}\left(x\right)\right)-\ln\left(\left|{\mathrm{J}}_{T_{0}^{-1}}\left(x\right)\right|\right)\right)\right)\,,$

namely:

$V_{1}\left(x\right)=V_{0}\left(T_{0}^{-1}\left(x\right)\right)-\ln\left(\left|{\mathrm{J}}_{T_{0}^{-1}}\left(x\right)\right|\right)\,.$

Recall that $T_{0}^{-1}\in\mathcal{C}^{m+1}$ and $V_{0}\in\mathcal{C}^{m+2}$,
and the Jacobian is taking one higher order of derivative on $V_{0}$, so
$\ln\left(\left|{\mathrm{J}}_{T_{0}^{-1}}\left(x\right)\right|\right)\in\mathcal{C}^{m+1}$,
and we conclude that $V_{1}\in\mathcal{C}^{m}$. ∎

This proposition is generic: as long as (FE) is applied through the form of
the gradient flow (WGF), $2$ derivatives are lost in every iteration. Any
initial data that has finite amount of derivatives will quickly lose hold of
their regularity, and falls in the regime where Wasserstein gradient is not
even defined. As a consequence, the simple FE stepping should be utilized with
caution for gradient flow.

## References

  * [1] D. Alvarez-Melis and N. Fusi.  Dataset dynamics via gradient flows in probability space.  In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 219–230. PMLR, 18–24 Jul 2021.
  * [2] L. Ambrosio, N. Gigli, and G. Savareé.  Gradient flows in metric spaces and in the space of probability measures.  Lectures in Mathematics. ETH Zürich. Birkhäuser, 2008.
  * [3] E. Bernton, P. E. Jacob, M. Gerber, and C. P. Robert.  On parameter estimation with the Wasserstein distance.  Information and Inference: A Journal of the IMA, 8(4):657–676, 10 2019.
  * [4] J. A. Carrillo, D. Matthes, and M.-T. Wolfram.  Chapter 4 - lagrangian schemes for wasserstein gradient flows.  In A. Bonito and R. H. Nochetto, editors, Geometric Partial Differential Equations - Part II, volume 22 of Handbook of Numerical Analysis, pages 271–311. Elsevier, 2021.
  * [5] C. Frogner, C. Zhang, H. Mobahi, M. Araya, and T. A. Poggio.  Learning with a wasserstein loss.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
  * [6] G. Fu, S. Osher, and W. Li.  High order spatial discretization for variational time implicit schemes: Wasserstein gradient flows and reaction-diffusion systems.  Journal of Computational Physics, 491:112375, 2023.
  * [7] R. Gao and A. Kleywegt.  Distributionally robust stochastic optimization with wasserstein distance.  Mathematics of Operations Research, 48(2):603–655, 2023.
  * [8] S. Hamdi, W. E. Schiesser, and G. W. Griffiths.  Method of lines.  Scholarpedia, 2(7):2859, 2009.  Retrieved from http://www.pdecomp.net/Scholarpedia/MOLfinal.pdf.
  * [9] J. Han, C. T. Ryan, and X. T. Tong.  Wasserstein gradient flow for optimal probability measure decomposition, 2024.
  * [10] J. S. Hesthaven, S. Gottlieb, and D. Gottlieb.  Spectral Methods for Time-Dependent Problems.  Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2007.
  * [11] S. ichi Amari.  Information Geometry and Its Applications, volume 194 of Applied Mathematical Sciences.  Springer Tokyo, Tokyo, 1 edition, 2016.
  * [12] Jacobs, Matt, Lee, Wonjun, and Léger, Flavien.  The back-and-forth method for wasserstein gradient flows.  ESAIM: COCV, 27:28, 2021.
  * [13] Y. Jin, S. Liu, H. Wu, X. Ye, and H. Zhou.  Parameterized wasserstein gradient flow, 2024.
  * [14] R. Jordan, D. Kinderlehrer, and F. Otto.  The variational formulation of the fokker–planck equation.  SIAM Journal on Mathematical Analysis, 29(1):1–17, 1998.
  * [15] W. Lee, L. Wang, and W. Li.  Deep jko: time-implicit particle methods for general nonlinear gradient flows, 2023.
  * [16] R. J. LeVeque.  Finite Difference Methods for Ordinary and Partial Differential Equations.  Society for Industrial and Applied Mathematics, 2007.
  * [17] W. Li, J. Lu, and L. Wang.  Fisher information regularization schemes for wasserstein gradient flows.  Journal of Computational Physics, 416:109449, 2020.
  * [18] P. Mokrov, A. Korotin, L. Li, A. Genevay, J. M. Solomon, and E. Burnaev.  Large-scale wasserstein gradient flows.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 15243–15256. Curran Associates, Inc., 2021.
  * [19] S. Neumayer, V. Stein, G. Steidl, and N. Rux.  Wasserstein gradient flows for moreau envelopes of f-divergences in reproducing kernel hilbert spaces, 2024.
  * [20] G. Peyré.  Entropic approximation of wasserstein gradient flows.  SIAM Journal on Imaging Sciences, 8(4):2323–2351, 2015.
  * [21] Y. Polyanskiy and Y. Wu.  Information Theory: From Coding to Learning.  Cambridge University Press, 2024.
  * [22] A. Salim, A. Korba, and G. Luise.  The wasserstein proximal gradient algorithm.  In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12356–12366. Curran Associates, Inc., 2020.
  * [23] J. Shen, Y. Qu, W. Zhang, and Y. Yu.  Wasserstein distance guided representation learning for domain adaptation.  Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018.
  * [24] Y. Wang, P. Chen, and W. Li.  Projected wasserstein gradient descent for high-dimensional bayesian inference.  SIAM/ASA Journal on Uncertainty Quantification, 10(4):1513–1532, 2022.
  * [25] Y. Yang, S. Eckstein, M. Nutz, and S. Mandt.  Estimating the rate-distortion function by wasserstein gradient descent.  In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 2768–2794. Curran Associates, Inc., 2023.
  * [26] R. Yao, L. Huang, and Y. Yang.  Minimizing convex functionals over space of probability measures via KL divergence gradient flow.  In S. Dasgupta, S. Mandt, and Y. Li, editors, Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 2530–2538. PMLR, 02–04 May 2024.
  * [27] M. Yi, Z. Zhu, and S. Liu.  MonoFlow: Rethinking divergence GANs via the perspective of Wasserstein gradient flows.  In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 39984–40000. PMLR, 23–29 Jul 2023.