# General entropic constraints on CSS codes within magic distillation
protocols

Rhea Alexander  Department of Physics, Imperial College London, London SW7
2AZ, UK  School of Physics and Astronomy, University of Leeds, Leeds, LS2 9JT,
UK  Si Gvirtz-Chen  School of Physics and Astronomy, University of Leeds,
Leeds, LS2 9JT, UK  Nikolaos Koukoulekidis  Department of Physics, Imperial
College London, London SW7 2AZ, UK  David Jennings  Department of Physics,
Imperial College London, London SW7 2AZ, UK  School of Physics and Astronomy,
University of Leeds, Leeds, LS2 9JT, UK

###### Abstract

Magic states are fundamental building blocks on the road to fault-tolerant
quantum computing. CSS codes play a crucial role in the construction of magic
distillation protocols. Previous work has cast quantum computing with magic
states for odd dimension $d$ within a phase space setting in which universal
quantum computing is described by the statistical mechanics of
quasiprobability distributions. Here we extend this framework to the important
$d=2$ qubit case and show that we can exploit common structures in CSS
circuits to obtain distillation bounds capable of out-performing previous
monotone bounds in regimes of practical interest. Moreover, in the case of CSS
code projections, we arrive at a novel cut-off result on the code length $n$
of the CSS code in terms of parameters characterising a desired distillation,
which implies that for fixed target error rate and acceptance probability, one
needs only consider CSS codes below a threshold number of qubits. These
entropic constraints are not due simply to the data-processing inequality but
rely explicitly on the stochastic representation of such protocols.

##  I Introduction

Work towards achieving fault-tolerant quantum computing is currently seeing
rapid progress on qubit systems on many computational platforms [1, 2, 3, 4,
5, 6, 7, 8, 9]. In particular, the surface code [10, 11, 12] is a leading
framework that allows Clifford operations to be implemented transversally on
blocks of physical qubits. However, Clifford operations are not universal for
quantum computing [13, 14], and in fact it is impossible to encode any
universal gateset transversally [15]. A prominent method of circumventing this
problem is the magic state injection model, wherein the Clifford group is
promoted to a universal gateset by injecting copies of special non-stabilizer
states known as magic states [16, 17]. While magic states can only be prepared
in surface codes with relatively high error rates, it is possible to reduce
the noise per copy by converting many noisy magic states into fewer higher-
fidelity magic states using only stabilizer operations [18]. This process,
known as magic state distillation, allows magic states to be produced with
arbitrarily high purity, and thereby enables universal quantum computation
within surface code models.

Almost all protocols [18, 19, 20, 21, 22] to-date for qubit magic distillation
are based on a subclass of stabilizer codes known as Calderbank-Shor-Steane
(CSS) codes [23, 24]. CSS codes can be constructed from two classical linear
codes, allowing one to draw on a plethora of results from classical coding
theory to construct quantum codes with desirable properties. For instance, it
has been shown that CSS codes are optimal when it comes to constructing
quantum error correcting codes that support a transversal $T$-gate [25], a key
feature in many of the aforementioned distillation protocols. Although
significant progress has been made to reduce the overhead of such protocols
[26], distillation is still estimated to dominate the total resource cost of
performing a computation in the magic state injection model. Therefore, a
better understanding of the extent to which this cost can be reduced is of
great practical interest.

Recent work [27] has developed a framework for analysing magic distillation in
odd-dimensional systems by taking key insights from a rich literature of
majorization theory and applying them to discrete phase space representations
of magic states. In odd dimensions, Gross’s Wigner function [28] provides a
representation wherein distillable magic states correspond to quasiprobability
distributions containing negativity on a discrete phase space [16]. By
contrast, stabilizer states correspond to probability distributions, and
stabilizer operations in general are represented by stochastic transformations
[28, 29]. Thus when computation is restricted to the stabilizer setting, one
obtains a classical stochastic model that can be studied using entropic theory
and in particular relative majorization [30, 31, 32, 33, 34]. Ref. [27]
extended majorization tools to negatively-represented magic states, and found
that a dense subset of $\alpha$-Rényi entropies $H_{\alpha}$ remain well-
defined and meaningful as quantifiers of disorder on quasiprobability
distributions under stochastic processing, leading to fundamental constraints
on magic distillation protocols in the form of thermodynamic laws.

Since most quantum algorithms are formulated for systems of qubits, the
important question of whether this framework can be extended to qubit systems
remains. There are, however, many well-known obstacles in constructing valid
Wigner representations for qubits (related to the fact that $2^{-1}$ does not
exist modulo 2 [29]). Many constructions for Wigner functions, including
Gross’s, cannot be extended to qubits [35, 36], while others represent some
pure stabilizer states negatively [37, 38], which breaks the link established
in odd dimensions between Wigner negativity and quantum computational speed-up
[39, 40]. While substantial work has been done to develop phase space
representations wherein all qubit stabilizer operations are non-negatively
represented [41, 42], channels are typically not mapped to linear, let alone
stochastic, transformations under such representations.

Progress can be made by identifying subsets of qubit stabilizer operations
that can be represented stochastically, while nevertheless remaining capable
of universal quantum computation via magic state injection. In this paper, we
make use of a Wigner representation for qubits introduced in Ref. [43] that
shares many desirable features with Gross’s representation, such as the linear
representation of channels. Drawing on results from Ref. [44], we show that
CSS circuits – the subset of stabilizer circuits wherein CSS states play the
role of stabilizer states – remain stochastic in this representation. Since
CSS circuits are known to be capable of universal quantum computation via
magic state injection [44, 45], they provide a setting where we can extend the
statistical mechanics framework for universal quantum computing developed in
Ref. [27] to qubits.

The structure of our paper is as follows. In Section III, we introduce the
phase space representation of qubit states and channels we will use, and
identify some regimes where this representation becomes stochastic. Building
from this, in Section IV we develop majorization techniques to analyse
stochastically-represented magic distillation protocols on qubits. Finally, in
Section V, we apply these tools to derive general entropic constraints (in the
form of upper and lower bounds on code length) for distillation protocols that
project onto CSS codes, which exploit structures basic to this distillation
strategy.

##  II Main results

Figure 1: (Finite range on CSS code lengths for magic state distillation
protocols). We plot upper and lower bounds on the number of copies $n$ of the
noisy Hadamard state
$(1-\epsilon)\outerproduct{H}{H}+\epsilon\frac{\mathbbm{1}}{2}$ required to
distil a single output qubit $\ket{H}$ with output error rate $\delta=10^{-9}$
by projecting onto an $[[n,1]]$ CSS code. The shaded purple region shows the
range of code lengths allowed by the tightest numeric upper bound (red curve)
from Theorem 8 and the lower bound from projective robustness (PR) introduced
in Ref. [46] (blue curve). The analytic upper bound $n^{*}$ (dashed yellow
curve) defined in Eq. (2) is shown to form a good approximation to the numeric
bound. (a) When target acceptance probability $p$ is low ($p=0.1$) the upper
bounds are less constraining; (b) By increasing to $p=0.9$, the upper bounds
become considerably tighter. In both cases, there is a cut-off input error
$\epsilon$ beyond which no CSS code projection protocol can achieve the
desired combination of output error and acceptance probability.

We show that CSS circuits can be represented by stochastic maps on a well-
defined multiqubit phase space. By exploiting techniques from majorization, in
Theorem 5 we extend the statistical mechanical framework of Ref. [27] to CSS
qubit quantum computation.

We further find that, similar to Ref. [47], every CSS circuit can be
decomposed in terms of protocols that project onto CSS codes, which therefore
constitute the core machinery for magic distillation in CSS circuits. For such
CSS code projection protocols, we obtain novel upper bounds on the code length
$n$ as a function of the number of output qubits $k$, acceptance probability
$p$ and input and output error rates $\epsilon$ and $\delta$ respectively
(which are typically related to the code distance $D$ via
$\delta=O(\epsilon^{D})$). Our main result is the following, which we
generalise to odd dimensional systems and arbitrary stabilizer codes in
Theorem 9.

######  Result 1.

Consider the distillation of $k$ copies of a pure qubit magic state $\psi$
from a supply of the noisy magic state $\rho$, where both $\psi$ and $\rho$
have real density matrices in the computational basis. Any magic distillation
protocol that projects onto the codespace of an $[[n,k]]$ CSS code and can use
$n$ copies of $\rho$ to distil out a $k$-qubit state $\rho^{\prime}$ at output
error ${\delta\geq\norm{\rho^{\prime}-\psi^{\otimes k}}_{1}}$ and acceptance
probability $p$ must have a code length $n$ such that

$\displaystyle
n\geq\frac{k\left[1-H_{\alpha}(W_{\psi})\right]-\frac{\alpha}{1-\alpha}\log\big(\frac{p}{1+\delta
2^{5/2}}\big{missing})}{\left[1-H_{\alpha}(W_{\rho})\right]}$ (1)

for all $\alpha\in{\cal A}$ for which $H_{\alpha}(W_{\rho})<1$, and

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

for all $\alpha\in{\cal A}$ for which $H_{\alpha}(W_{\rho})>1$, where
$H_{\alpha}(W_{\rho})$ is a Rényi entropy measure computed on the Wigner
representation of the quantum state $\rho$ defined in Eq. (8).

Combining these bounds with prior work on projective robustness of magic [46],
we constrain the code length of any $[[n,k]]$ CSS code projection that could
achieve a desired distillation process to lie within a finite range. An
example for the distillation of a single Hadamard state are shown in Fig. 1.
In this case, our analytic upper bounds on the number of noisy magic states
needed to distil out a single copy at the output take on the particularly
simple form:

$\displaystyle
n\leq\log_{f(\epsilon)}\left[\frac{1+6\delta}{p}\right]^{2}\eqqcolon n^{*},$
(3)

where the base of the logarithm is given by
${f(\epsilon)\coloneqq[1-\epsilon+\frac{\epsilon^{2}}{2}]^{-1}\geq 1}$. In the
spirit of Ref. [48], Eq. (3) and more generally Theorem 9, can be viewed as
expressing trade-off relations between various distillation parameters. These
fundamental no-go results may be instructive when constructing stabilizer code
projection protocols with optimized parameters.

##  III Stochastic representation for CSS circuits on qubits

In this section, we review the qubit representation $W_{\rho}$ introduced in
Ref. [43] that forms the backbone of our work. We expand upon its properties
and confirm that it respects all sequential and parallel composition of
processes, the former of which crucially gives rise to a well-defined input-
output relation $W_{{\cal E}(\rho)}=W_{\cal E}W_{\rho}$. Moreover, the latter
implies that the representation of product states factorizes over subsystems,
a property which will prove computationally advantageous given that inputs to
magic distillation protocols typically take on the form $\rho^{\otimes n}$.
Furthermore, we show that all magic distillation protocols executed by CSS
circuits are stochastically represented, which means that such protocols can
be analysed using majorization theory and admit a description in terms of
classical statistical mechanics on quasiprobability distributions.

###  III.1 Phase space representation of qubit states

We first establish some convenient notation. Let
${{\bm{u}}\coloneqq(u_{1},\dots,u_{n})\in\mathbb{Z}^{n}_{2}}$ denote a binary
vector. Furthermore, given any single qubit operator $O$, let us denote

$O({\bm{u}})\coloneqq O^{u_{1}}\otimes\dots\otimes O^{u_{n}}.$ (4)

With this in place, consider an $n$-qubit quantum system with total Hilbert
space ${\cal H}_{2}^{n}:={\cal H}_{2}^{\otimes n}$. We associate to this
system a phase space ${\cal
P}_{n}:=\mathbb{Z}_{2}^{n}\times\mathbb{Z}_{2}^{n}$, where ${\cal P}_{n}$
consists of all vectors $({\bm{u}}_{x},{\bm{u}}_{z})$, and has a symplectic
inner product $[{\bm{u}},{\bm{v}}]$ defined as

$\displaystyle[{\bm{u}},{\bm{v}}]\coloneqq{\bm{u}}_{z}\cdot{\bm{v}}_{x}-{\bm{v}}_{z}\cdot{\bm{u}}_{x}\equiv{\bm{u}}_{z}\cdot{\bm{v}}_{x}+{\bm{v}}_{z}\cdot{\bm{u}}_{x},$
(5)

where arithmetic is carried out modulo 2.

We are now in a position to define our chosen representation over ${\cal
P}_{n}$ (we refer the reader to Appendix A for further details and proofs of
the properties presented). We first define $n$-qubit displacement operators
$\\{D_{\bm{u}}\\}$, where
${\bm{u}}\coloneqq({\bm{u}}_{x},{\bm{u}}_{z})\in{\cal P}_{n}$, via strings of
single qubit Pauli operators $X$ and $Z$ as

$\displaystyle D_{{\bm{u}}}\coloneqq Z({\bm{u}}_{z})X({\bm{u}}_{x}),$ (6)

which generate the Heisenberg-Weyl group ${H(2)^{\times n}}$ on $n$-qubits
modulo phase factors [49]. These displacement operators satisfy

$\displaystyle
D_{\bm{u}}D_{\bm{v}}=(-1)^{[{\bm{u}},{\bm{v}}]}D_{\bm{v}}D_{\bm{u}}.$ (7)

Using these displacement operators, we can construct the following
representation

$\displaystyle
W_{\rho}({\bm{u}})\coloneqq\frac{1}{2^{n}}\mathrm{tr}[A^{\dagger}_{\bm{u}}\rho]$
(8)

for any $n$-qubit state $\rho$, where $\\{A_{\bm{u}}\\}$ are the set of
$2^{2n}$ phase point operators on $n$-qubits, which are defined as

$\displaystyle A_{\bm{u}}=\frac{1}{2^{n}}\sum_{{\bm{v}}\in{\cal
P}_{n}}(-1)^{[{\bm{u}},{\bm{v}}]}D_{\bm{v}}.$ (9)

It can be shown (see Appendix A.1) that these phase point operators share the
following properties with those defining Gross’s Wigner representation of $n$
qudits with Hilbert space dimension $d$ on a phase space ${\cal
P}\coloneqq\mathbb{Z}^{n}_{d}\times\mathbb{Z}^{n}_{d}$:

  1. (A1)

$A_{{\bm{u}}_{X}\oplus{\bm{u}}_{Y}}=A_{{\bm{u}}_{X}}\otimes A_{{\bm{u}}_{Y}}$
on a bipartite system $XY$, where ${\bm{u}}_{X}$ and ${\bm{u}}_{Y}$ are
respectively points in the phase spaces of subsystems $X$ and $Y$.

  2. (A2)

$\mathrm{tr}[A^{\dagger}_{\bm{u}}A_{\bm{v}}]=d^{n}\delta_{{\bm{u}},{\bm{v}}}$,

  3. (A3)

$\mathrm{tr}[A_{\bm{u}}]=1$,

  4. (A4)

$\sum_{{\bm{u}}\in{\cal P}}A_{\bm{u}}=d^{n}\mathbbm{1}^{\otimes n}$.

These properties imply that $W_{\rho}$ provides an informationally complete
and normalized representation of general $n$-qubit states, i.e.,

$\sum_{{\bm{u}}}W_{\rho}({\bm{u}})=1,$ (10)

for any quantum state $\rho$. Like Gross’s Wigner function, an immediate
consequence of Eq. (7) is that the representation $W_{\rho}$ transforms
covariantly under the displacement operators, namely,

$W_{D_{{\bm{v}}}^{\dagger}\rho
D_{{\bm{v}}}}({\bm{u}})=W_{\rho}({\bm{u}}+{\bm{v}}),$ (11)

for all ${\bm{u}},{\bm{v}}\in{\cal P}_{n}$. In fact, everything in the
construction of this representation has proceeded in direct analogy to
Gross’s, except for the lack of phase factors ensuring the Hermiticity of the
displacement operators. As a result, the phase point operators in Eq. (9) are
no longer Hermitian, which in turn implies that $W_{\rho}$ is generally
complex.

However, it turns out that the real and imaginary parts of $W_{\rho}$ are
related to the quantum state in the following simple way (a proof is given in
Appendix A.2):

######  Lemma 1.

Given any $n$-qubit quantum state $\rho$,

$\displaystyle\mathfrak{Re}[W_{\rho}({\bm{u}})]=W_{\mathfrak{Re}(\rho)}({\bm{u}})$
(12)
$\displaystyle\mathfrak{Im}[W_{\rho}({\bm{u}})]=W_{\mathfrak{Im}(\rho)}({\bm{u}})$
(13)

for all ${\bm{u}}\in{\cal P}_{n}$, where $\mathfrak{Re}(\rho)$ and
$\mathfrak{Im}(\rho)$ are respectively the real and imaginary parts of the
density matrix of $\rho$ in the computational basis.

This immediately implies

######  Corollary 1.

The representation $W_{\rho}$ of an $n$-qubit state $\rho$ is a
quasiprobability distribution if and only if $\rho$ is an $n$-rebit state,
i.e., the density matrix $\rho$ is real in the computational basis.

To simplify our analysis, we will therefore focus on rebit states for the
majority of this work, although in Section VI we show how we can handle
arbitrary qubit states by treating the real and imaginary components
separately resulting in an overcomplete quasiprobability representation.
Typically, however, we will consider the case of distilling the following
Hadamard state

$\displaystyle\ket{H}\coloneqq\cos\frac{\pi}{8}\ket{0}+\sin\frac{\pi}{8}\ket{1},$
(14)

which is equivalent to the canonical magic state ${\ket{A}\coloneqq
T\ket{+}=\frac{1}{\sqrt{2}}(\ket{0}+e^{i\frac{\pi}{4}}\ket{1}}$ up to a
Clifford unitary [50], where $T\coloneqq\text{diag}(1,e^{i\frac{\pi}{4}})$ is
the $T$-gate. The Hadamard state can thus be used in a stabilizer
gadgetisation circuit to implement the $T$-gate [18].

###  III.2 Phase space representation of channels

The representation of qubit states induces a corresponding representation of
qubit channels. Let ${\cal E}$ be an arbitrary channel from $n$ to $m$ qubits,
and

${\cal J}({\cal E})=(\mathcal{I}\otimes{\cal
E})(\outerproduct{\phi^{+}_{n}}{\phi^{+}_{n}})$ (15)

be its associated Choi state [51], where $|\phi^{+}_{n}\rangle$ is the
canonical maximally entangled state on two copies of the input system. We now
define a representation [52] of a quantum channel ${\cal E}$ as

$\displaystyle W_{{\cal E}}({\bm{v}}|{\bm{u}})\coloneqq 2^{2n}W_{{\cal
J}({\cal E})}({\bm{u}}\oplus{\bm{v}}),$ (16)

for all ${\bm{v}}\in{\cal P}_{m}$, and ${\bm{u}}\in{\cal P}_{n}$. Under this
representation, every channel becomes a matrix mapping the representation of
an input state to the representation of the output state. More precisely, if
$\sigma={\cal E}(\rho)$, then

$\displaystyle W_{\sigma}({\bm{v}})=\sum_{{\bm{u}}\in{\cal P}_{n}}W_{\cal
E}({\bm{v}}|{\bm{u}})W_{\rho}({\bm{u}}),$ (17)

for all ${\bm{v}}\in{\cal P}_{m}$.

Furthermore, the representation $W_{\cal E}$ respects the sequential and
parallel composition of channels, i.e.,

$\displaystyle W_{{\cal E}\circ{\cal F}}$ $\displaystyle=W_{\cal E}W_{\cal
F},$ (18) $\displaystyle W_{{\cal E}\otimes{\cal F}}$ $\displaystyle=W_{\cal
E}\otimes W_{\cal F}.$ (19)

One useful implication of Eq. (19) is that when ${\cal E}$ and ${\cal F}$
respectively prepare states $\rho$ and $\sigma$, we obtain

$W_{\rho\otimes\sigma}=W_{\rho}\otimes W_{\sigma},$ (20)

which informs us that our chosen representation factorizes over subsystems for
product states.

The transition matrix formed by $W_{\cal E}({\bm{v}}|{\bm{u}})$ preserves
normalization since

$\displaystyle\sum_{{\bm{v}}\in{\cal P}_{m}}W_{\cal E}({\bm{v}}|{\bm{u}})=1,$
(21)

for any ${\bm{u}}\in{\cal P}_{n}$ and any quantum channel ${\cal E}$. (Proofs
of Eqs. (17) through (21) can be found in Appendix A.3). Therefore, a quantum
channel ${\cal E}$ from $n$ qubits to $m$ qubits is represented by a
stochastic matrix if and only if $W_{{\cal E}}({\bm{v}}|{\bm{u}})\geq 0$ for
all ${\bm{u}},{\bm{v}}$. By inspection of Eq. (16) we equivalently have that
the quantum channel ${\cal E}$ is stochastically represented if and only if
its Choi state ${\cal J}({\cal E})$ on $n+m$ qubits is represented by a
genuine probability distribution on the phase space ${\cal P}_{n+m}$.

Unlike the odd-dimensional case, the channel ${\cal E}$ is not guaranteed a
stochastic representation whenever ${\cal J}({\cal E})$ is a stabilizer state.
This is an immediate consequence of the sequential and parallel composition
rules of Eqs. (18) and (19), which imply that our qubit representation cannot
be non-negative over the full stabilizer subtheory [53]. However, we will show
in the next section that ${\cal E}$ is stochastically represented if ${\cal
J}({\cal E})$ belongs to an important subset of stabilizer states known as CSS
states.

Figure 2:  (Schematic of our approach). We find that the set of completely
CSS-preserving protocols ${\cal O}$ are stochastically represented. Such
protocols contain the family of CSS code projections as subset, examples of
which include $7$-$1$ and $23$-$1$ protocols based respectively on the Steane
$[[7,1]]$ and Golay $[[23,1]]$ codes [19].

###  III.3 CSS states and circuits

We now identify a class of qubit distillation protocols that arise naturally
in fault-tolerant quantum computing, are sufficiently large to enable
universal quantum computation, and admit a stochastic representation. In
particular, we show that a channel is stochastically represented if its Choi
state is CSS. Building on this result, we construct a stochastically-
represented subset of stabilizer circuits wherein CSS states play the role of
stabilizer states, which has been shown to be capable of universal quantum
computation with magic state injection.

A pure CSS state on $n$ qubits is any stabilizer state whose stabilizer group
can be generated by $n$ Pauli observables that are individually of $X$-type or
$Z$-type only. For instance,
$\ket{\phi^{+}}\coloneqq\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$ has the
stabilizer group

$\displaystyle{\cal S}(\ket{\phi^{+}})=\langle X_{1}X_{2},Z_{1}Z_{2}\rangle,$
(22)

and is therefore CSS. By contrast, $\ket{\psi}\coloneqq\mathbbm{1}\otimes
H\ket{\phi^{+}}$ is stabilized by

$\displaystyle{\cal S}(\ket{\psi})=\langle X_{1}Z_{2},Z_{1}X_{2}\rangle,$ (23)

and is not CSS because its stabilizer generators necessarily mix $X$ and $Z$.
As they are generators of stabilizer groups defining CSS states, we group
$X$\- and $Z$-type Pauli observables together as CSS observables. Letting the
set of all pure CSS states be denoted $\Omega_{css}$, we further define the
set of all CSS states ${\cal D}_{css}$ as the convex hull of $\Omega_{css}$.

The representation we have chosen coincides on all rebit states with an
earlier one introduced by Ref. [44] (see Appendix A.2), in which it was shown
that a Discrete Hudson’s theorem [28] can be recovered for qubits when one
restricts to rebits. More precisely, it was shown that any pure $n$-rebit
state is non-negatively represented if and only if it is CSS. Therefore,
$W_{\rho}$ is a valid probability distribution for all $\rho\in{\cal
D}_{css}$, and we conclude that

######  Theorem 2.

A quantum channel ${\cal E}$ from $n$ to $m$ qubits is stochastically
represented if ${\cal J}({\cal E})$ is a CSS state on $n+m$ qubits.

Theorem 2 can be leveraged to identify stochastically-represented qubit
stabilizer operations in a systematic way. A channel ${\cal E}$ from a system
of qubits $B$ is CSS-preserving if ${\cal E}(\rho)$ is a CSS state for all
$\rho\in{\cal D}_{css}$, and completely CSS-preserving if, given any CSS state
$\rho_{AB}$ on another system of qubits $A$ as well as $B$,
$\mathcal{I}_{A}\otimes{\cal E}_{B}(\rho_{AB})$ is always CSS. We now note
that the maximally entangled state $\ket{\phi^{+}_{n}}$ over two sets of $n$
qubits is CSS for all $n$ (see Appendix A.3). Therefore, if ${\cal E}$ is
completely CSS-preserving, ${\cal J}({\cal E})$ must be CSS. By Theorem 2, it
follows that every completely CSS-preserving channel is stochastically
represented.

To motivate the class of completely CSS-preserving channels as operationally
significant, we highlight that they cover at least the following subset of
stabilizer circuits (see Appendix B.3 for proof):

######  Lemma 3 (CSS circuits).

Any sequence of the following stabilizer operations:

  1. 1.

introducing a CSS state on any number of qubits,

  2. 2.

performing a completely CSS-preserving gate on any number $n$ of qubits, i.e.,
a member of the group

${\cal
G}(n)\coloneqq\langle\operatorname{CNOT}(i,j),Z_{i},X_{i}\rangle_{i,j=1,\dots,n,i\neq
j}.$ (24)

  3. 3.

projectively measuring a CSS observable (with the possibility of classical
control conditioned on outcome),

  4. 4.

discarding any number of qubits,

as well as statistical mixtures of such sequences, is completely CSS-
preserving.

By using CSS-preserving rather than completely CSS-preserving gates, channels
covered by Lemma 3 can be promoted to the subset of stabilizer circuits where
CSS states play the role of stabilizer states. However, both groups of gates
are equally powerful for magic distillation (see discussion in Appendix
B.3.1). Thus we directly refer to the set of channels covered by Lemma 3 as
“CSS circuits”, and conclude that all such circuits are stochastically
represented.

We emphasise the computational power of CSS circuits. Firstly, they are
capable of universal quantum computation when supplemented by rebit magic
states [44, 45] they can also distil [54]. Moreover, the gateset ${\cal G}(n)$
constitutes all gates that can be implemented fault-tolerantly using defect
braiding in surface codes [55]. Finally, we will see in Section V that CSS
circuits form the basis of many existing magic distillation protocols
constructed around CSS codes.

##  IV Entropic constraints on completely CSS-preserving protocols

The standard approach to obtaining constraints on magic distillation is
tracking a magic monotone [56, 57, 58, 48, 59], which is any property of a
quantum system that cannot be increased under some class of magic non-
generating operations (e.g. stabilizer operations). The paradigmatic example
is mana [56], the total negativity in the Wigner representation of a state.
However, this approach operates at the state level and therefore does not
incorporate any additional distinguishing physics of distillation protocols.
In contrast, the recent work [27] considers how a class of magic distillation
protocols transform a pair of quantum states – one a noisy magic state, the
other a stabilizer state singled out by the characteristic physics of those
protocols.

Here we briefly review the approach taken in Ref. [27] to extend relative
majorization to quasiprobability distributions, and how that leads to the
extension of a dense subset of $\alpha$-Rényi divergences from classical
statistical mechanics to quantify the non-classical order in magic states
under distillation. We then adapt this work for rebit magic state distillation
using CSS circuits.

###  IV.1 Statistical mechanics of quasiprobability distributions

At the heart of statistical mechanics are the notions of disorder and
deviations from equilibrium. In classical statistical mechanics, this leads to
the thermodynamic entropy ${H(\mathbf{p})=-\sum_{i}p_{i}\log p_{i}}$, which is
essentially the unique measure of disorder of a statistical distribution
${\mathbf{p}=(p_{1},\dots,p_{N})}$.

In odd-dimensional systems [16] or restricted qubit models [44, 45, 60], magic
states that promote an efficiently simulable part of quantum mechanics to
universal quantum computation must have negativities in their representation
within a phase space model. Despite this negativity, it is still possible to
arrive at a well-defined statistical mechanical description that circumvents
the fact that the Boltzmann entropy is not well-defined. The key observation
we exploit is that the framework of majorization remains well-defined when
extended to quasiprobability distributions, and is a more fundamental concept
than the traditional entropy.

Given two probability distributions $\mathbf{p}=(p_{1},\dots,p_{N})$ and
${\mathbf{p}^{\prime}=(p_{1}^{\prime},\dots,p_{M}^{\prime})}$, we would like
to determine which of them is “more disordered” than the other. This can be
done by comparing $\mathbf{p}$ to some reference probability distribution
${\mathbf{r}=(r_{1},\dots,r_{N})}$ of our choice, and $\mathbf{p}^{\prime}$ to
some other reference probability distribution
$\mathbf{r}^{\prime}=(r^{\prime}_{1},\dots,r^{\prime}_{M})$, also of our
choice. We then say that $(\mathbf{p},\mathbf{r})$ relatively majorizes
$(\mathbf{p}^{\prime},\mathbf{r}^{\prime})$ and write
$(\mathbf{p},\mathbf{r})\succ(\mathbf{p}^{\prime},\mathbf{r}^{\prime})$ if
there exists a stochastic map $A$ that sends the first pair of distributions
into the second, namely

$\displaystyle(A\mathbf{p},A\mathbf{r})$
$\displaystyle=(\mathbf{p}^{\prime},\mathbf{r}^{\prime}).$ (25)

It was shown in Ref. [27] that this definition can be extended to the case of
quasiprobability distributions in the first argument, and the following result
was established to provide an entropic measure in terms of the $\alpha$-Rényi
divergences.

######  Theorem 4 ([27]).

Let $\mathbf{w}=(w_{1},\dots,w_{N})$ and
${\mathbf{w}^{\prime}=(w^{\prime}_{1},\dots,w^{\prime}_{M})}$ be any two
quasiprobability distributions and let $\mathbf{r}=(r_{1},\dots,r_{N})$ and
$\mathbf{r}^{\prime}=(r^{\prime}_{1},\dots,r^{\prime}_{M})$ be any two
probability distributions with non-zero components. If
$(\mathbf{w},\mathbf{r})\succ(\mathbf{w}^{\prime},\mathbf{r}^{\prime})$ then

$D_{\alpha}(\mathbf{w}||\mathbf{r})\geq
D_{\alpha}(\mathbf{w}^{\prime}||\mathbf{r}^{\prime}),$ (26)

for all $\alpha\in{\cal A}=\left\\{\frac{2a}{2b-1}\,:\,a,b\in\mathbb{N},a\geq
b\right\\}\cup\left\\{\infty\right\\}$.

Here $D_{\alpha}(\mathbf{w}||\mathbf{r})$ is an extension of the classical
$\alpha$-Rényi divergence to the case of $\mathbf{w}$ being a quasiprobability
distribution. This extension requires $\alpha\in{\cal A}$ in order for the
expression

$D_{\alpha}(\mathbf{w}||\mathbf{r})\coloneqq\frac{1}{\alpha-1}\log\sum_{i=1}^{N}w_{i}^{\alpha}r_{i}^{1-\alpha},$
(27)

to be well-defined111Note 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.. In
the case of $\mathbf{r}$ being the uniform distribution
$\mathbf{r}=(1/N,1/N,\dots,1/N)$, we have that

$D_{\alpha}(\mathbf{w}||\mathbf{r})=\log N-H_{\alpha}(\mathbf{w}),$ (28)

where
$H_{\alpha}(\mathbf{w})\coloneqq(1-\alpha)^{-1}\log\sum_{i}w_{i}^{\alpha}$ is
the $\alpha$-Rényi entropy evaluated on $\mathbf{w}$. Another result of Ref.
[27] is that $\mathbf{w}$ has negativity if and only if
$H_{\alpha}(\mathbf{w})$ is negative for $\alpha$ close to $1$ and diverges to
$-\infty$ in the limit $\alpha\rightarrow 1^{+}$. This provides a well-defined
and meaningful notion of negative entropy in a statistical mechanical setting.

###  IV.2 Application to completely CSS-preserving magic distillation

Since completely CSS-preserving protocols are stochastically represented, the
following family of entropic constraints on rebit magic distillation applies
them all (see Appendix C for proof):

######  Theorem 5.

Let $\rho$ be a noisy rebit magic state and $\tau$ be a CSS state in the
interior of ${\cal D}_{css}$. If there exists a completely CSS-preserving
protocol ${\cal E}$ such that ${{\cal E}(\rho^{\otimes n})=\rho^{\prime}}$ and
$\tau^{\prime}\coloneqq{\cal E}(\tau^{\otimes n})$ is also in the interior of
${\cal D}_{css}$, then

$\displaystyle\Delta D_{\alpha}\geq 0$ (29)

for all $\alpha\in{\cal A}$, where

$\displaystyle\Delta D_{\alpha}\coloneqq
nD_{\alpha}(W_{\rho}||W_{\tau})-D_{\alpha}(W_{\rho^{\prime}}||W_{\tau^{\prime}}).$
(30)

The reference process $\tau^{\otimes n}\mapsto\tau^{\prime}$ in Theorem 5 can
be used in three different ways: (1) as a variational parameter, (2) to
account for limitations the physical hardware carrying out magic distillation,
or (3) to capture structure distinctive to a family of protocols and thereby
produce entropic constraints specific to that family, which we now elaborate
on in turn.

For (1), we simply treat $\tau$ as a variational parameter, which can be
optimized over ${\cal D}_{css}$ to obtain the following set of monotones 222We
note that an analogous set of magic monotones can be defined for systems of
odd-prime dimension via:  $\Gamma_{\alpha}(\rho)=\inf_{\tau\in
STAB}D_{\alpha}(W_{\rho}||W_{\tau}).$ (31) on completely CSS-preserving
protocols

$\displaystyle\Lambda_{\alpha}(\rho)\coloneqq\inf_{\tau\in{\cal
D}_{css}}D_{\alpha}(W_{\rho}||W_{\tau}),$ (32)

for all $\alpha\in{\cal A}$. To see this, we note that we have
$D_{\alpha}(W_{\rho}||W_{\tau})\geq 0$ for all $\rho$, $\tau$, with equality
if and only if $\rho=\tau$ (see Lemma 15). Given any rebit state $\rho$, let
$\tau_{\rho}$ be a solution to the optimization problem in Eq. (32). Then if
there exists a completely CSS-preserving protocol ${\cal E}$ such that ${{\cal
E}(\rho)=\rho^{\prime}}$, we obtain

$\displaystyle\Lambda_{\alpha}(\rho)=D_{\alpha}(W_{\rho}||W_{\tau_{\rho}})$
$\displaystyle\geq D_{\alpha}(W_{\rho^{\prime}}||W_{{\cal E}(\tau_{\rho})})$
$\displaystyle\geq\Lambda_{\alpha}(\rho^{\prime}),$ (33)

where the first inequality follows from generalised relative majorization and
the second inequality follows by the definition in Eq. (32). Therefore
$\\{\Lambda_{\alpha}\\}_{\alpha\in{\cal A}}$ form an infinite set of monotones
on all completely CSS-preserving protocols. It is straightforward to verify
that $\Lambda_{\alpha}$ are sub-additive, i.e.,
$\Lambda_{\alpha}(\rho^{\otimes n})\geq n\Lambda_{\alpha}(\rho)$ (this follows
from the additivity of the generalized $\alpha$-Rényi divergences). Therefore,
these $\Lambda_{\alpha}$-monotones allow us to set global bounds on any
completely CSS-preserving protocol. More precisely, if there exists a
completely CSS-preserving protocol ${\cal E}$ such that ${\cal
E}(\rho^{\otimes n})=\rho^{\prime}$, then the overhead $n$ is lower bounded as

$\displaystyle
n\geq\frac{\Lambda_{\alpha}(\rho^{\prime})}{\Lambda_{\alpha}(\rho)}.$ (34)

For (2), we can use the reference process to take into account limitations in
the hardware carrying out magic distillation. For instance, Ref. [27] uses the
reference process to preserve the Gibbs state in order to encode a background
temperature or free energy production in the distillation hardware.

The final way (3) of using the reference process is demonstrated in the next
section. We show explicitly how to the reference process may be chosen to
produce entropic constraints specialised for CSS code projection protocols.

##  V Entropic constraints on CSS code projection protocols

In this section, we apply Theorem 5 to CSS code projection protocols, and
obtain lower and upper bounds on their code length ($\sim$ resource cost). In
some parameter regimes, the new lower bounds outperform those due to magic
monotones such as generalised robustness [63] and projective robustness [46].
To our knowledge, these constitute the first set of trade-off relations on
distillation parameters that act as fundamental upper bounds on the resource
cost for a family of distillation protocols.

###  V.1 CSS code projections

An elementary protocol for magic distillation, proposed in the seminal work of
Bravyi and Kitaev [18], uses projection onto a quantum error correcting code.
This protocol begins by taking in $n$ copies of a noisy magic state $\rho$ and
post-selecting the no-error outcome from the syndrome measurement of an
$[[n,k]]$ stabilizer code ${\cal{C}}$. Doing so has the effect of projecting
onto ${\cal{C}}$, so the protocol proceeds to decode onto $k$ output qubits
and discard the remaining syndrome qubits. In general, any such code
projection protocol only succeeds probabilistically with some acceptance
probability $p$. Nevertheless, if the likelihood of an undetectable error is
less than the input error rate $\epsilon$, the post-selected output state will
have a higher fidelity per qubit with respect to the target magic state than
$\rho$. Many existing magic distillation protocols are based on CSS codes,
such as the 15-to-1 protocol [18] based on the $[[15,1]]$ punctured Reed-
Muller code [64, 65], as well as straightfoward code projection protocols
based on the $[[7,1]]$ Steane and $[[23,1]]$ Golay CSS codes analysed in [19].

It has long been known that any $n$-to-1 magic distillation protocol can be
decomposed as a sum of stabilizer code projections followed by Clifford post-
processing [47]. This result implies that the optimal fidelity with respect to
a target magic state, though not necessarily optimal acceptance probability,
can always be achieved by a stabilizer code projection. In a similar way, we
can show (Theorem 21) that any CSS circuit carrying out an $n$-to-$k$ magic
distillation protocol is a sum of CSS code projections followed by completely
CSS-preserving post-processing. (In fact, the proof line we give also allows
one to generalise the result of Ref. [47] to arbitrary $n$-$k$ stabilizer
protocols).

An $n$-to-$k$ CSS code projection protocol is an operation ${\cal K}$ from $n$
to $k$ qubits that acts as

${\cal K}(\cdot)\coloneqq\mathrm{tr}_{k+1,\dots,n}[{\cal U}\circ{\cal
P}(\cdot)],$ (35)

where ${\cal U}$ and ${\cal P}$ are respectively a unitary decoding channel
and codespace projection for an $[[n,k]]$ CSS code. Given $n$ copies of a
noisy magic state $\rho$, ${\cal K}$ acts as

${\cal K}(\rho^{\otimes n})=p\rho^{\prime},$ (36)

where $\rho^{\prime}$ is the output magic state on $k$ qubits and we have
defined the acceptance probability ${p\coloneqq\mathrm{tr}[P\rho^{\otimes
n}]}$ for a single successful run of ${\cal K}$. Distillation is successful if
the output $\rho^{\prime}$ from a successful run has a greater fidelity per
qubit with respect to a target (pure) magic state of choice than $\rho$.

Since code projection protocols are not trace-preserving, the majorization
constraints do not immediately apply. However, this can be remedied by
preparing a specially designated CSS state $\sigma$ on $k$ qubits whenever an
$n$-to-$k$ code projection protocol fails, while continuing to distinguish
between successful (labelled ‘0’) and unsuccessful (labelled ‘1’) runs of the
protocol by recording this information in an ancillary qubit. We can therefore
extend ${\cal K}$ into the following trace-preserving operation ${\cal E}$:

$\displaystyle{\cal E}(\cdot)\coloneqq{\cal
K}(\cdot)\otimes\outerproduct{0}{0}+\mathrm{tr}[\overline{{\cal
P}}(\cdot)]\sigma\otimes\outerproduct{1}{1},$ (37)

where ${\overline{{\cal
P}}\coloneqq\overline{P}(\cdot)\overline{P}\coloneqq(\mathbbm{1}^{\otimes
n}-P)(\cdot)(\mathbbm{1}^{\otimes n}-P)}$ performs the projection onto the
orthogonal complement of ${\cal{C}}$, and $\sigma$ is an arbitrary CSS state.
We conclude that there exists an $n$-to-$k$ CSS code projection such that
$\rho^{\otimes n}\mapsto p\rho^{\prime}$ if and only if there exists a trace-
preserving $n$-to-$k$ CSS code projection ${\cal E}$ identified in Eq. (37)
such that

$\displaystyle{\cal E}[\rho^{\otimes n}]$
$\displaystyle=p\rho^{\prime}\otimes\outerproduct{0}{0}+(1-p)\sigma\otimes\outerproduct{1}{1}\coloneqq\rho_{p}.$
(38)

###  V.2 General constraints on CSS code projections

We now exploit Theorem 5 to derive majorization conditions that apply across
all $n$-to-$k$ CSS code projection protocols. Crucially, the trace-preserving
CSS code projection identified in Eq. (37) can be implemented as a CSS circuit
(see Appendix B.4 for proof), which leads to the following Lemma:

######  Lemma 6.

Every trace-preserving CSS code projection can be executed as a sequence of
completely CSS preserving operations, and is therefore stochastically
represented.

A natural reference process can be chosen for all trace-preserving CSS code
projections by exploiting the fact that their successful components are sub-
unital. To see this, we first note that the identity operator on $n$ qubits
can be decomposed as $\mathbbm{1}^{\otimes n}=P+\overline{P}$ for the
codespace projector $P$ of any $[[n,k]]$ CSS code ${\cal{C}}$. The successful
component ${\cal K}$ in the trace-preserving code projection of ${\cal{C}}$
therefore acts as

$\displaystyle{\cal K}(\mathbbm{1}^{\otimes n})={\cal K}(P+\overline{P})={\cal
K}(P).$ (39)

Since $P$ is the logical identity on $k$ logical qubits, i.e.,

$P=\sum_{{\bm{k}}\in\\{0,1\\}^{k}}\outerproduct{{\bm{k}}_{L}}{{\bm{k}}_{L}}\equiv\mathbbm{1}_{L},$
(40)

the decoding of $P$ in Eq. (35) must give an output state that is proportional
to the maximally mixed state on $k$ physical qubits, so we obtain ${\cal
K}(\mathbbm{1}^{\otimes n})\propto\mathbbm{1}^{\otimes k}$. This confirms the
successful component of any trace-preserving CSS code projection to be sub-
unital. Furthermore, since $P$ is a rank-$2^{k}$ projector, the acceptance
probability associated with this protocol is
$p=\mathrm{tr}\left[P\frac{\mathbbm{1}^{\otimes n}}{2^{n}}\right]=2^{k-n}$.
Putting everything together, we find that every $n$-to-$k$ trace-preserving
CSS code projection ${\cal E}$ maps the maximally mixed state to

$\displaystyle{\cal E}\left[\left(\frac{\mathbbm{1}}{2}\right)^{\otimes
n}\right]$ $\displaystyle=\tau_{n,k}$ (41)

where we have defined the output state

$\displaystyle\tau_{n,k}$ $\displaystyle\coloneqq
2^{k-n}\frac{\mathbbm{1}^{\otimes
k}}{2^{k}}\otimes\outerproduct{0}{0}+(1-2^{k-n})\sigma\otimes\outerproduct{1}{1}.$
(42)

Since $\frac{\mathbbm{1}}{2}$ and $\tau_{n,k}$ are both full-rank CSS states
(for the appropriate choice of $\sigma\in{\cal D}_{CSS}$), Eq. (41) is a valid
reference process for all trace-preserving CSS code projections.

We therefore conclude that, if there exists an $n$-to-$k$ CSS code projection
such that $\rho^{\otimes n}\mapsto p\rho^{\prime}$, then

$\displaystyle\Delta D_{\alpha}\coloneqq
nD_{\alpha}\left(W_{\rho}\bigg{|}\bigg{|}W_{\frac{\mathbbm{1}}{2}}\right)-D_{\alpha}\left(W_{\rho_{p}}||W_{\tau_{n,k}}\right)\geq
0$ (43)

for all $\alpha\in{\cal A}$. We define $\Delta D_{\alpha}$ over the restricted
domain $n\in[k,\infty]$ (as the number of logical qubits cannot exceed the
number of physical qubits). We highlight the satisfying fact that $\Delta
D_{\alpha}$ is independent of the choice of CSS state $\sigma$ in Eq. (37).
This follows from resource-theoretic arguments as well as properties of the
$\alpha$-Rényi divergence (see Appendix D.2 for details).

###  V.3 Bounds on the code length of CSS code projection protocols

Figure 3: (Lower bound comparison). We plot lower bounds on the number of
copies $n$ of the noisy Hadamard state
$(1-\epsilon)\outerproduct{H}{H}+\epsilon\frac{\mathbbm{1}}{2}$ required to
distil a single output qubit $\ket{H}$ with output error rate $\delta=10^{-9}$
and acceptance probability $p=0.9$ under a CSS code projection protocol as a
function of input error rate $\epsilon$. Our tightest lower bound from
majorization (maj.) is shown to be tighter those from mana [56] and
generalized robustness (GR) [63]. However, it only outperforms the lower bound
from projective robustness (PR) [46] in the high $p$, high $\epsilon$ regime.

The entropic constraints of Eq. (43) on CSS code projections can be used to
bound many metrics on their performance as magic distillation protocols. In
this section, we apply these constraints to bounding the code length of any
CSS code projection protocol that could achieve some target combination of
noise reduction and acceptance probability from a given supply of noisy magic
states.

We first highlight some properties of the relative entropy difference $\Delta
D_{\alpha}$ in the following lemma, proofs of which can be found in Appendix
D.3.

######  Lemma 7.

The following properties of the relative entropy difference $\Delta
D_{\alpha}$ hold for any noisy input rebit magic state $\rho$, output
$k$-rebit magic state $\rho^{\prime}$, acceptance probability $p<1$ and
$\alpha\in{\cal A}$:

  1. (i)

$\Delta D_{\alpha}$ is concave over the domain $n\in[k,\infty]$.

  2. (ii)

$\Delta D_{\alpha}$ is negative in the limit where $n=k$:

$\lim_{n\rightarrow k^{+}}\Delta D_{\alpha}<0.$ (44)

.

  3. (iii)

If $H_{\alpha}[W_{\rho}]>1$, then $\Delta D_{\alpha}$ is also negative in the
asymptotic limit

$\lim_{n\rightarrow\infty}\Delta D_{\alpha}<0.$ (45)

An immediate consequence of Lemma 7 is that $\Delta D_{\alpha}$ is either
negative for all $n$, which implies no CSS code projection protocol can distil
$\rho^{\prime}$ from a supply of $\rho$ with acceptance probability $p$, or
$\Delta D_{\alpha}$ has one or two roots located at $n^{\alpha}_{L}$ and
$n^{\alpha}_{U}$. These roots therefore constitute lower and upper bounds on
the code length $n$ of any CSS code projection that can carry out the desired
distillation. We formalise these observations in the following Theorem:

######  Theorem 8.

Let $\rho$ be a noisy rebit magic state. Any $n$-to-$k$ CSS code projection
can distil out the $k$-rebit magic state $\rho^{\prime}$ from a supply of
$\rho$ at acceptance probability $p$ must have a code length $n$ such that

$\displaystyle n$ $\displaystyle\geq
n_{L}^{\alpha}\coloneqq\begin{cases}\inf_{n}\\{n:\Delta D_{\alpha}\geq
0\\}&\text{ if }\exists n:\Delta D_{\alpha}\geq 0,\\\ \infty&\text{
otherwise.}\end{cases}$ (46) $\displaystyle n$ $\displaystyle\leq
n_{U}^{\alpha}\coloneqq\begin{cases}\sup_{n}\\{n:\Delta D_{\alpha}\geq
0\\}&\text{ if }\exists n:\Delta D_{\alpha}\geq 0,\\\ -\infty&\text{
otherwise.}\end{cases}$ (47)

for all $\alpha\in{\cal A}$. Moreover, given any $\alpha$ such that
${H_{\alpha}[W_{\rho}]>1}$, the second expression yields a finite upper bound
on $n$.

For sufficiently low $k$, these bounds can be computed numerically using basic
root-finding methods. However, we also find analytic upper and lower bounds on
$n$ in Section V.3.1. The values of $n^{\alpha}_{L}$ and $n^{\alpha}_{U}$ when
$D_{\alpha}<0$ for all $n$ were chosen to indicate that no $n$-to-$k$ CSS code
projection can carry out the desired distillation.

We emphasise that $n$ in Theorem 8 refers to the code length (related to the
resource cost $C$ by $C=\frac{n}{pk}$) in a single run of a distillation
protocol, as opposed to the the asymptotic overhead. However, single-run $n$
still constitutes a useful metric for analysing the actual resource cost of a
given stage of a protocol. Moreover, distillation costs are typically
dominated by the final round of a multi-stage distillation protocol (see Ref.
[66] and references contained therein), so we expect the above bounds to be
particularly informative in this context.

In Fig. 3, we plot the tighest lower bound produced by Theorem 8 on the code
length of $n$-to-1 CSS code projection protocols for Hadamard state
distillation. We consider input magic states of the form
${\rho(\epsilon)\coloneqq(1-\epsilon)\outerproduct{H}{H}+\epsilon\frac{\mathbbm{1}}{2}}$,
which can be generally assumed irrespective of the particular error model.
This is because any state $\rho$ can be converted into this canonical form by
applying the pre-processing channel

${\cal E}(\rho)\coloneqq\frac{1}{2}(\mathbbm{1}\rho\mathbbm{1}+H\rho H),$ (48)

i.e. twirling with respect to the Clifford subgroup generated by the single
Hadamard gate. In all parameter regimes, our lower bound is observed to be
tighter than mana 333Under 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$., and the generalized robustness bound in Theorem 13 of
Ref. [63]. Furthermore, in the high $p$, high $\epsilon$ regime our lower
bound gives tighter constraints than the projective robustness bound [46]. In
particular, there is a cut-off input error rate $\epsilon\approx 0.12$ at
which our lower bound shoots up to infinity because, for any input error
greater than this cut-off, one can always find some $\alpha$ such that $\Delta
D_{\alpha}<0$ for all $n$, so no CSS code projection can carry out the desired
distillation given a higher input error rate (see Section V.3.2 for physical
intuition on the origin of this behaviour). In the low $p$ regime, our upper
bounds are still able to give additional constraints on code length beyond
those given by the projective robustness bound. In particular, Fig. 1 puts
together information from our upper bounds and the lower bound from projective
robustness to show that no CSS code projection can achieve some target
combinations of output error and acceptance probability beyond a cut-off input
error rate.

####  V.3.1 Extension to non-qubit code projection

Figure 4:  (Wigner-Rényi entropies & magic distillation) We plot the condition
in Theorem 8 for the existence of finite upper bounds on $n$ in an $n$-to-1
CSS distillation for the qubit Hadamard state distillation, signified by
region where $H_{\alpha}[W_{\rho(\epsilon)}]>1$. Even in the limit of zero
input error $\epsilon=0$ we obtain a valid set of permissible $\alpha$, which
implies that Hadamard state distillation under $n$-to-$1$ CSS code projection
is ruled out in the asymptotic limit $n\rightarrow\infty$. We further
highlight that the error rate $\epsilon=0.3$ (dashed curve) is outside of the
region where $\rho(\epsilon)$ is magic ($0\leq\epsilon<1-\frac{1}{\sqrt{2}}$),
and therefore $W_{\rho(\epsilon)}$ is a proper probability distribution at
$\epsilon=0.3$, which is why $H_{\alpha}$ is only seen to satisfy standard
monotonicity properties at this input error. We also highlight that the
$\alpha\rightarrow 1$ divergence corresponds to a pole in
$H_{\alpha}[W_{\rho}]$ for magic state $\rho$, and its residue is the mana of
the state.

Mathematically, the appearance of upper bounds on the code length of qubit CSS
code projection protocols comes from the concavity of the objective function
$\Delta D_{\alpha}$ in $n$. We now demonstrate that this feature is not
peculiar to qubits, and in fact arises whenever stabilizer code projections on
any quantum system are stochastic under a Wigner representation sufficiently
similar to Gross’s.

More precisely, we say that a Wigner representation $W$ of $n$ qudits with
Hilbert space dimension $d$ is a generalised Gross’s Wigner representation if
it represents each state $\rho$ as the function $W_{\rho}$ on a phase space
$\mathbb{Z}^{n}_{d}\times\mathbb{Z}^{n}_{d}$,

$\displaystyle
W_{\rho}({\bm{u}})\coloneqq\frac{1}{d^{n}}\mathrm{tr}\left[A^{\dagger}_{\bm{u}}\rho\right],$
(49)

via phase point operators $\\{A_{\bm{u}}\\}$ satisfying (A1)-(A4). For all
stabilizer code projections on odd-dimensional systems, $W$ can simply be
Gross’s Wigner representation [27]. For CSS code projections on qubits, $W$
can be the representation from Eq. (8). We then have the following analytic
upper and lower bounds on the resource cost of code projection protocols:

######  Theorem 9 (Qudit code bounds).

Consider the distillation of $k$ copies of a pure magic state $\psi$ from a
supply of the noisy magic state $\rho$, where $\psi$ and $\rho$ are
$d$-dimensional qudit states that are real-represented under a generalised
Gross’s Wigner representation $W$. Any stochastically-represented distillation
protocol that projects onto the codespace of an $[[n,k]]$ stabilizer code and
can use $n$ copies of $\rho$ to distil out a $k$-qudit state $\rho^{\prime}$
with acceptance probability $p$ and output error
$\delta\geq\norm{\rho^{\prime}-\psi^{\otimes k}}_{1}$ must have a code length
$n$ such that

$\displaystyle n\geq\frac{k\left[\log
d-H_{\alpha}(W_{\psi})\right]-\frac{\alpha}{1-\alpha}\log\big(\frac{p}{1+\delta
d^{5/2}}\big{missing})}{\left[\log d-H_{\alpha}(W_{\rho})\right]},$ (50)

for all $\alpha\in{\cal A}$ for which $H_{\alpha}(W_{\rho})<\log d$, and

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

for all $\alpha\in{\cal A}$ for which $H_{\alpha}(W_{\rho})>\log d$.

One might be concerned that the conditions
${H_{\alpha}(W_{\rho(\epsilon)})>\log d}$ given in Theorems 8 and 9 for the
existence of a finite upper bound on $n$ are never actually satisfied. This
turns out not to be the case. For ${n\text{-to-}1}$ CSS code projection
protocols for Hadamard distillation, there always exists a valid set of
$\alpha$-values such that $H_{\alpha}[W_{\rho(\epsilon)}]>1$ for all
$\epsilon$, so we always obtain a finite upper bound on $n$. This can be seen
by upper bounding the Rényi entropy of $W_{\rho(\epsilon)}$ as

$\displaystyle H_{\alpha}\left[W_{\rho(\epsilon)}\right]$ $\displaystyle\geq
H_{\alpha}\left[W_{\rho(0)}\right],$ (52)

and then examining Fig. 4, which shows that there exists finite range of
$\alpha$ such that $H_{\alpha}>1$ at $\epsilon=0$.

The trade-off relations given in Theorem 9 can be rearranged to bound other
parameters such as the acceptance probability $p$. In Fig. 5, we compare the
tightest upper bound on $p$ produced by Theorem 9 for $n$-to-1 Hadamard
distillation to those attained in existing protocols based on CSS codes given
in Refs. [18] and [19]. We see that the acceptance probabilities of basic code
projection protocols using the $[[7,1]]$ Steane and $[[23,1]]$ Golay codes in
Fig. 5(a) are orders of magnitude less than our upper bounds, suggesting that
substantial room for improvement is not ruled out. Interestingly, in Fig. 5(b)
our upper bound is very close to the actual acceptance probability of the
protocol based on the $[[15,1]]$ Reed-Muller code in Ref. [18], which we
speculate may hint at something fundamental about the role of the intermediate
Clifford corrections used in that protocol.

Figure 5: (Explicit protocol comparison). (a) We compare the majorization
upper bounds (dashed lines) on the acceptance probability $p$ with which one
can distil a noisy Hadamard state
$(1-\epsilon)\outerproduct{H}{H}+\epsilon\frac{\mathbbm{1}}{2}$ via an
$n$-to-1 code projection against actual acceptance probabilities attained
using the Steane code (purple) at $n=7$ and the Golay code (green) at $n=23$
(detailed in Ref.[19]). Attained acceptance probabilities are orders of
magnitude less than our upper bounds. (b) We plot the majorization upper bound
(dashed line) on the acceptance probability $p$ of any 15-to-1 CSS code
projection protocol with which one can distil the noisy magic state
$(1-\epsilon)\outerproduct{A}{A}+\epsilon\frac{\mathbbm{1}}{2}$.
Interestingly, our bound is very close to the actual acceptance probability
for the 15-to-1 protocol (blue line) given in [18], though we emphasise this
latter protocol is not a straightforward CSS code projection.

Theorem 9 takes on a particularly simple form in the particular case of
$n$-to-$1$ CSS code projection protocols for Hadamard state distillation. By
evaluating the $\alpha=2$ condition explicitly, we find that, if there exists
a CSS code projection that sends $n$ copies of $\rho(\epsilon)$ to a $k$-qubit
state $\rho^{\prime}$ with acceptance probability $p$ and output error
$\delta\geq\norm{\rho^{\prime}-\outerproduct{H}{H}^{\otimes k}}_{1}$, then $n$
is upper bounded as

$\displaystyle n\leq n^{*}$ $\displaystyle\coloneqq
2\log_{f(\epsilon)}\left[\frac{1+6\delta}{p}\right],$ (53)

where the logarithm base is
${f(\epsilon)\coloneqq[1-\epsilon+\frac{\epsilon^{2}}{2}]^{-1}}$. This
expression captures the fact that under a CSS code projection protocol, there
is a fundamental trade-off between acceptance probability and output fidelity.
For instance, Eq. (53) shows that given a supply of noisy magic states
($\epsilon>0$), we cannot use CSS code projection to distil a perfect magic
state ($\delta=0)$ with certainty ($p=1$), which was first shown in Ref. [48].
To further investigate this trade-off, in Fig. 6(b) we plot the maximum
achievable fidelity with respect to the Hadamard state that can be achieved by
an $n$-to-$1$ CSS code projection ${\cal K}$ via

$F_{\max}(\rho)=\max_{{\cal K}}\left\\{\bra{H}\rho^{\prime}\ket{H}\,:\,{\cal
K}(\rho^{\otimes n})\mapsto p\rho^{\prime}\right\\},$ (54)

where the maximization is performed over the set of all $n$-to-1 CSS code
projection protocols.

####  V.3.2 Why do we expect upper bounds?

Taking CSS circuits as our free operations, the appearance of upper bounds on
$n$ might first seem to contradict a resource theory perspective, where we
might expect $n+1$ copies of a noisy magic state to be at least as good as $n$
copies at distilling magic, since discarding subsystems is itself a CSS
circuit. However, by specialising to stabilizer code projection protocols, we
necessarily introduce a trade-off between $n$ and acceptance probability $p$,
which we now show in a simple calculation. For any $n$-to-$k$ stabilizer code
projection protocol for $d$-dimensional qudit distillation, the acceptance
probability $p$ is given by how much of $n$ copies of the noisy input magic
state $\rho$ projects onto the $d^{k}$-dimensional codespace spanned by the
logical basis $\\{\ket{j_{L}}\\}_{j=0,\dots,d^{k}-1}$ of the code. Letting
$\lambda_{\max}(\cdot)$ denote a state’s largest eigenvalue, we immediately
identify the following upper bound on $p$,

$\displaystyle p=$ $\displaystyle\sum_{j=0}^{d^{k}-1}\bra{j_{L}}\rho^{\otimes
n}\ket{j_{L}}$ $\displaystyle\leq d^{k}\lambda_{\max}(\rho^{\otimes
n})=d^{k}[\lambda_{\max}(\rho)]^{n},$ (55)

which falls monotonically towards $0$ as $n\rightarrow\infty$. At an intuitive
level, the trade-off between $n$ and $p$ occurs because the codespaces of
$[[n,k]]$ stabilizer codes remain the same size as we increase $n$, and so
take up a vanishingly small part in the support of all the noisy input magic
states used. Under the requirement that we have some threshold acceptance
probability (below which the expected overhead would be too large), a
corresponding upper bound on $n$ is then expected.

####  V.3.3 Comparison with the data-processing inequality (DPI)

We have seen that stochastically represented CSS code projection protocols
give rise to a set of upper bounds on $n$ (Theorem 9). By comparing to the
data-processing inequality (DPI), we see that although the existence of upper
bounds is a general feature of code projection protocols, exploiting the
stochasticity in the representation of CSS code projections gives strictly
stronger bounds.

According to the DPI, if there exists a code projection (CSS or otherwise)
that can distil out the $k$-qubit magic state $\rho^{\prime}$ from $n$ copies
of the noisy magic state $\rho$ with acceptance probability $p$, then

$\Delta\tilde{D}_{\alpha}\coloneqq
n\tilde{D}_{\alpha}\left(\rho\bigg{|}\bigg{|}\frac{\mathbbm{1}}{2}\right)-\tilde{D}_{\alpha}\left(\rho_{p}||\tau_{n,k}\right)\geq
0,$ (56)

for all $\alpha\in(1,\infty)$ [68], where $\tilde{D}_{\alpha}(\rho||\tau)$ is
the sandwiched $\alpha$-Rényi divergence [69, 70] on the normalized quantum
states $\rho$ and $\tau$, which is defined as

$\displaystyle\tilde{D}_{\alpha}(\rho||\tau)\coloneqq\frac{1}{\alpha-1}\log\mathrm{tr}\left[\left(\tau^{\frac{1-\alpha}{2\alpha}}\rho\tau^{\frac{1-\alpha}{2\alpha}}\right)^{\alpha}\right].$
(57)

We then have the following upper bound on $n$:

$\displaystyle n\leq
n^{DPI}_{U}\coloneqq\min_{\alpha\in(1,\infty)}\max_{n}\\{n:\Delta\tilde{D}_{\alpha}\geq
0\\}.$ (58)

which is finite whenever $\alpha$ is such that $H_{\alpha}(\rho)>1$ (proof
essentially identical to that of Theorem 8).

Given that we also obtain upper bounds on code length from simple data
processing of quantum states, we should ask: does majorization give genuinely
new constraints on magic state distillation beyond the DPI? Since our
majorization conditions are a consequence of the stochastic representation of
stabilizer circuits, while the DPI arises from the fact that all quantum
channels are CPTP, this question may be loosely rephrased as asking whether
stochasticity imposes any additional constraints beyond those imposed by CPTP
on magic state distillation by stabilizer code projection.

Fig. 6 allows us to answer this question in the affirmative, since the upper
bound on code length due to majorization is observed to be stronger than that
due to the DPI over a wide range of parameter regimes for CSS code projection
protocols. In particular, extracting
$n^{maj}_{U}\coloneqq\min_{\alpha}n^{\alpha}_{U}$ as the tightest bound due to
majorization from Theorem 8, we find that, in the low acceptance probability
$p$ and low input error $\epsilon$ regime of Fig. 6(a), the difference in
upper bounds $\Delta n_{U}\coloneqq n_{U}^{DPI}-n_{U}^{maj}$ (the amount by
which majorization “beats” DPI) is of the order $\Delta n_{U}=O(10^{4})$. We
thus conclude that the constraints on CSS protocols stemming from majorization
go beyond those from the DPI.

Figure 6: (Majorization gives independent constraints over DPI). (a) Shown is
how (scaled) $\Delta n_{U}\coloneqq n^{DPI}_{U}-n^{maj}_{U}$ varies over all
possible values of acceptance probability $p$ and a realistic range of input
error $\epsilon$, with fixed $\delta=10^{-9}$. Whenever we have
$\log_{10}(\Delta n_{U}+1)>0$ means that upper bounds from majorization give
tighter constraints than the DPI, reaching $\Delta n_{U}=O(10^{4})$ in the low
$p$, low $\epsilon$ regime. (b) We show the trade-off relation given by bounds
on the maximum achievable fidelity $F_{\max}(\rho)$ vs. target acceptance
probability $p$, under an $n$-$1$ CSS code projection, where
$\rho=\frac{3}{4}\outerproduct{H}{H}+\frac{1}{8}\mathbbm{1}$. For $p$ above a
given threshold ($\approx 0.6$) no perfect distillation is theoretically
possible, even for $n\rightarrow\infty$ copies of the input state.
Majorization (maj.) is shown to give stronger constraints than that of DPI.

##  VI Beyond rebit distillation

We have simplified our analysis thus far by restricting our attention to rebit
magic states such as $\ket{H}$. However, many protocols such as the seminal
15-to-1 Bravyi-Kitaev protocol [18] distil magic states such as
$\ket{A}\propto\ket{0}+e^{i\frac{\pi}{4}}\ket{1}$, which have complex density
matrices in the computational basis. An argument can be made that since
$\ket{A}$ is Clifford-equivalent to $\ket{H}$, this state should be considered
equally resourceful for magic distillation. However, to address this concern
more directly, we extend our majorization relations to states with complex
Wigner representations. A discussion of how this can be achieved is given in
Appendix F. The basic idea is that we can define valid $2d^{2}$-dimensional
quasiprobability distributions by forming the direct sum of the real and
imaginary parts of the original distribution:

$\displaystyle\mathbf{w}_{\rho}$
$\displaystyle\coloneqq\Re{W_{\rho}}\oplus\Im{W_{\rho}},$ (59)

while for our reference CSS states we can simply take:

$\displaystyle\mathbf{r}_{\tau}$
$\displaystyle\coloneqq\frac{1}{2}W_{\tau}\oplus W_{\tau}.$ (60)

It then follows that if there exists a completely CSS preserving operation
${\cal E}$ such that ${\cal E}(\rho)=\rho^{\prime}$ and ${\cal
E}(\tau)=\tau^{\prime}$, then

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

for all $\alpha\in{\cal A}$. Further study of the significance of these
complex relative majorization conditions may be of foundational interest, but
we leave this for future work.

##  VII Discussion and Outlook

We have shown that the statistical mechanical framework of Ref. [27] can be
extended to the experimentally significant case of qubit systems by focusing
on the processing of magic states under CSS circuits – i.e., the subset of
stabilizer circuits where CSS states play the role of stabilizer states. To
achieve this, we made use of a Wigner representation first introduced in Ref.
[43] wherein completely CSS-preserving channels correspond to stochastic
transformations on phase space. This set of channels include CSS circuits,
which are sufficient for universal quantum computing [44, 45] and consist
precisely of the gateset that can be performed fault-tolerantly on surface
code constructions [71].

Within this framework, we showed that relative majorization can be used to
encode particular properties of an important class of distillation protocols
that project onto CSS codes, in terms of which all protocols carried out by
CSS circuits can be decomposed. We established general entropic constraints on
such protocols in terms of upper and lower bounds on the code length $n$.

In the context of achieving full fault-tolerance, a natural extension of this
work would be to generalize our results to more sophisticated protocols. For
instance, we might ask how the use of $m$ intermediate Clifford corrections in
between the measurements of stabilizer generators might affect these
fundamental constraints. One would expect to be able to obtain more refined
bounds as a function of $m$. Moreover, while many protocols are based on CSS
codes in part due to their relative ease of construction via tri-orthogonal
matrices [20], from an operational perspective it would be of interest to see
whether we can extend to the complete set of stabilizer operations on qubit
systems.

We have also obtained a set of monotones $\\{\Lambda_{\alpha}\\}$ for
completely CSS-preserving magic distillation, each of which forms a convex
optimization problem. We speculate that an analogous monotone can be
constructed for any resource theory for which the free operations are a subset
of operations that completely preserve Wigner positivity. From the perspective
of quantum optics experiments, wherein Gaussian operations and probabilistic
randomness are readily available, it may be of interest to consider the case
of continuous variable systems under the set of Gaussian operations and
statistical mixtures [72]. Since the individual $\alpha$-Rényi divergences on
quasiprobability distributions were seen in Section V.3.3 to typically produce
stronger constraints than the corresponding constraints given by
$\alpha$-Rényi divergences on quantum states, it would be interesting to see
how well these quasidistribution-based monotones perform relative to known
state-based counterparts.

On a technical note regarding majorization theory, we point to two interesting
directions for further study. Firstly, complex majorization constraints arise
naturally when we extend our setup from rebit to all qubit states, where
Wigner representations can become complex due to the non-Hermiticity of the
operator basis $\\{A_{\bm{u}}\\}$. We expect such constraints to take the form
of a duplet of constraints applying separately to the real parts and imaginary
parts of the Wigner function. In the context of non-Hermitian quantum
mechanics [73], results on complex majorization would also benefit theories
that require an ordering between Hamiltonian eigenvalues, such as quantum
thermodynamics. Secondly, the Wigner representation of Ref. [43] recovers the
covariance over symplectic affine transformations on qubit phase spaces, a
property shared by Gross’s Wigner function on odd-dimensional systems. This
added structure on the phase space was ignored by our analysis, but could be
utilised to tighten the obtained bounds in future work. In particular, as
explained in the discussion of Ref. [27], the stochastic majorization used in
our analysis is only a special case of $G$-majorization, where $G$ can be
taken as a subgroup of the stochastic group such as the symplectic group. It
can then be shown [74, 75, 76] that one should expect to obtain a set of
finite lower bound constraints on distillation, which will be tighter than
stochastic majorization constraints.

## Acknowledgements

RA and NK are supported by the EPSRC Centre for Doctoral Training in
Controlled Quantum Dynamics. SGC is supported by the Bell Burnell Graduate
Scholarship Fund. DJ is supported by the Royal Society and a University
Academic Fellowship.

##  APPENDIX A WIGNER REPRESENTATION

For any $n$-qubit state $\rho$, we define the following complex-valued
function $W_{\rho}:{\cal P}_{n}\mapsto\mathbb{C}$ as

$\displaystyle
W_{\rho}({\bm{u}})\coloneqq\frac{1}{2^{n}}\mathrm{tr}[A^{\dagger}_{\bm{u}}\rho],$
(62)

where $\\{A_{\bm{u}}\\}$ are the set of $2^{2n}$ phase point operators on
$n$-qubits, which are defined as follows

$\displaystyle A_{\bm{0}}\coloneqq\frac{1}{2^{n}}\sum_{{\bm{u}}\in{\cal
P}_{n}}D_{\bm{u}},\quad A_{{\bm{u}}}\coloneqq
D_{\bm{u}}A_{\bm{0}}D^{\dagger}_{\bm{u}}.$ (63)

As a consequence of Eq. (7), these phase-point operators can alternatively be
expressed as

$\displaystyle A_{\bm{u}}=\frac{1}{2^{n}}\sum_{{\bm{v}}\in{\cal
P}_{n}}(-1)^{[{\bm{u}},{\bm{v}}]}D_{\bm{v}},$ (64)

which further reveals that every $A_{\bm{u}}$ is real in the computational
basis.

Despite being complex-valued, $W_{\rho}$ transforms covariantly under the
displacement operators - informally speaking, $\rho$ is shifted by the
displacement operators around phase space - just like Gross’ representation in
odd dimensions. Concretely, we consider the Wigner representation of
$D_{\bm{v}}\rho D_{\bm{v}}^{\dagger}$ for an arbitrary phase space
displacement ${\bm{v}}$, which is

$\displaystyle W_{D_{\bm{v}}\rho D^{\dagger}_{\bm{v}}}({\bm{u}})$
$\displaystyle=\frac{1}{2^{n}}\mathrm{tr}[A^{\dagger}_{\bm{u}}D_{\bm{v}}\rho
D_{\bm{v}}^{\dagger}]=\frac{1}{2^{n}}\mathrm{tr}[D_{\bm{v}}^{\dagger}A^{\dagger}_{\bm{u}}D_{\bm{v}}\rho]$
$\displaystyle=\frac{1}{2^{n}}\mathrm{tr}\left[\sum_{{\bm{a}}\in{\cal
P}_{n}}(-1)^{[{\bm{u}},{\bm{a}}]}(D_{\bm{a}}D_{\bm{v}})^{\dagger}D_{\bm{v}}\rho\right].$
(65)

Inserting the commutation relation for the displacement operators in Eq. (7)
into Eq. (65), we obtain

$\displaystyle W_{D_{\bm{v}}\rho D^{\dagger}_{\bm{v}}}({\bm{u}})$
$\displaystyle=\frac{1}{2^{n}}\mathrm{tr}\left[\left(\sum_{{\bm{a}}\in{\cal
P}_{n}}(-1)^{[{\bm{u}}+{\bm{v}},{\bm{a}}]}D^{\dagger}_{\bm{a}}\right)\rho\right]$
$\displaystyle=W_{\rho}({\bm{u}}+{\bm{v}}),$ (66)

which confirms that $W_{\rho}$ transforms covariantly under the action of the
displacement operators.

###  A.1 Properties of qubit phase point operators and Wigner function

We first establish that the phase point operators of a joint system are simply
tensor products of phase point operators on its subsystems:

  1. (A1)

(Factorization). On a bipartite system with subsystems $X$ and $Y$,
$A_{{\bm{u}}_{X}\oplus{\bm{u}}_{Y}}=A_{{\bm{u}}_{X}}\otimes A_{{\bm{u}}_{Y}}$.

###### Proof.

From the definition of $D_{\bm{u}}$ in Eq. (6), it is clear that

$\displaystyle D_{\bm{u}}=D_{{\bm{u}}_{X}}\otimes D_{{\bm{u}}_{Y}}.$ (67)

Let $n_{X}$ and $n_{Y}$ be the numbers of qubits in subsystems $X$ and $Y$
respectively. Then the zero phase point operator on the bipartite system,
$A_{\bm{0}}$, is

$\displaystyle A_{\bm{0}}$
$\displaystyle\coloneqq\frac{1}{2^{n_{X}+n_{Y}}}\sum_{{\bm{u}}\in{\cal
P}_{XY}}D_{\bm{u}}$
$\displaystyle=\frac{1}{2^{n_{X}+n_{Y}}}\sum_{{\bm{u}}_{X}\in{\cal
P}_{X},{\bm{u}}_{Y}\in{\cal P}_{Y}}D_{{\bm{u}}_{X}\oplus{\bm{u}}_{Y}}$
$\displaystyle=\frac{1}{2^{n_{X}+n_{Y}}}\sum_{{\bm{u}}_{X}\in{\cal
P}_{X}}\sum_{{\bm{u}}_{Y}\in{\cal P}_{Y}}D_{{\bm{u}}_{X}}\otimes
D_{{\bm{u}}_{Y}}$ $\displaystyle=A_{\bm{0}_{X}}\otimes A_{\bm{0}_{Y}},$ (68)

which in turn implies that any phase point operator $A_{\bm{u}}\coloneqq
A_{{\bm{u}}_{X}\oplus{\bm{u}}_{Y}}$ for some ${\bm{u}}_{X}\in{\cal P}_{X}$ and
${\bm{u}}_{Y}\in{\cal P}_{Y}$ is

$\displaystyle A_{{\bm{u}}}$ $\displaystyle\coloneqq
A_{{\bm{u}}_{X}\oplus{\bm{u}}_{Y}}=D_{{\bm{u}}_{X}\oplus{\bm{u}}_{Y}}A_{\bm{0}}D^{\dagger}_{{\bm{u}}_{X}\oplus{\bm{u}}_{Y}}$
$\displaystyle=\left(D_{{\bm{u}}_{X}}A_{\bm{0}_{X}}D_{{\bm{u}}_{X}}^{\dagger}\right)\otimes\left(D_{{\bm{u}}_{Y}}A_{\bm{0}_{Y}}D_{{\bm{u}}_{Y}}^{\dagger}\right)$
$\displaystyle=A_{{\bm{u}}_{X}}\otimes A_{{\bm{u}}_{Y}},$ (69)

as claimed. ∎

Property (A1) enables us to break down any $n$-qubit phase-point operator
$A_{\bm{u}}$ as a tensor product of single-qubit phase-point operators,

$\displaystyle
A_{\bm{u}}=\bigotimes_{i=1}^{n}A_{{\bm{u}}_{j}},\quad{\bm{u}}=\bigoplus_{i=1}^{n}{\bm{u}}_{j},$
(70)

where ${\bm{u}}_{j}\in\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ is a co-ordinate in
the phase space of the $j$th qubit only. It is therefore instructive to
calculate the single-qubit phase point operators, which are

$\displaystyle A_{0,0}$ $\displaystyle=\frac{1}{2}(\mathbbm{1}+X+Z+iY),$
$\displaystyle A_{0,1}$ $\displaystyle=\frac{1}{2}(\mathbbm{1}-X+Z-iY),$
$\displaystyle A_{1,0}$ $\displaystyle=\frac{1}{2}(\mathbbm{1}+X-Z-iY),$
$\displaystyle A_{1,1}$ $\displaystyle=\frac{1}{2}(\mathbbm{1}-X-Z+iY).$ (71)

We next demonstrate how the explicit forms of single-qubit phase point
operators can be leveraged via Eq. (70) to prove two further properties for
general $n$-qubit phase point operators. In particular, we show how distinct
$n$-qubit phase point operators are orthogonal under the Hilbert-Schmidt inner
product:

  1. (A2)

(Orthogonality). Let $A_{\bm{u}}$ and $A_{\bm{v}}$ be two $n$-qubit phase
point operators. Then
$\mathrm{tr}[A^{\dagger}_{{\bm{u}}}A_{{\bm{v}}}]=2^{n}\delta_{{\bm{u}},{\bm{v}}}$.

###### Proof.

Let us first decompose ${\bm{u}}$ and ${\bm{v}}$ as
${\bm{u}}=\bigoplus_{i=1}^{n}{\bm{u}}_{j}$ and
${{\bm{v}}=\bigoplus_{i=1}^{n}{\bm{v}}_{j}}$, where ${\bm{u}}_{j}$ and
${\bm{v}}_{j}$ are phase point co-ordinates on the $j$th qubit only. By Eq.
(71),

$\displaystyle\mathrm{tr}[A^{\dagger}_{{\bm{u}}_{j}}A_{{\bm{v}}_{j}}]=2\delta_{{\bm{u}}_{j},{\bm{v}}_{j}}.$
(72)

Therefore,

$\displaystyle\mathrm{tr}[A^{\dagger}_{\bm{v}}A_{\bm{u}}]=\prod_{j=1}^{n}\mathrm{tr}[A^{\dagger}_{{\bm{u}}_{j}}A_{{\bm{v}}_{j}}]$
$\displaystyle=\prod_{j=1}^{n}2\delta_{{\bm{v}}_{j},{\bm{u}}_{j}}$
$\displaystyle=2^{n}\delta_{{\bm{u}},{\bm{v}}}.$ (73)

as claimed. ∎

There are
$\absolutevalue{P_{n}}=\absolutevalue{\mathbb{Z}_{2}^{n}\times\mathbb{Z}_{2}^{n}}=4^{n}$
phase point operators on $n$-qubits. Property (A2) thus implies
$\\{A_{\bm{u}}\\}_{{\bm{u}}\in{\cal P}_{n}}$ forms an orthogonal complex basis
for the complex vector space $\mathbb{C}^{2^{n}\times 2^{n}}$ of $2n\times 2n$
complex matrices under the Hilbert-Schmidt inner product. Therefore,
$W_{\rho}$ is an informationally complete representation of $n$-qubit states.
More precisely, any $n$-qubit quantum state $\rho$ can be uniquely decomposed
as

$\rho=\sum_{{\bm{u}}}W_{\rho}({\bm{u}})A_{{\bm{u}}},$ (74)

where
$W_{\rho}({\bm{u}})\coloneqq\frac{1}{2^{n}}\mathrm{tr}[A_{\bm{u}}^{\dagger}\rho]$
is a complex function on ${\cal P}_{n}$.

Furthermore, every phase point operator has trace 1:

  1. (A3)

(Unit trace). Let $A_{\bm{u}}$ be any $n$-qubit phase point operator. Then we
have $\mathrm{tr}[A_{{\bm{u}}}]=1$.

###### Proof.

Let us first decompose ${\bm{u}}$ as
${\bm{u}}=\bigoplus_{j=1}^{n}{\bm{u}}_{j}$, where ${\bm{u}}_{j}$ is a point in
the phase space of the $j$th qubit. We see that
$\mathrm{tr}[A_{{\bm{u}}_{j}}]=1$ from Eq. (71). Therefore,

$\displaystyle\mathrm{tr}[A_{\bm{u}}]=\prod_{j=1}^{n}\mathrm{tr}[A_{{\bm{u}}_{j}}]=\prod_{j=1}^{n}1=1,$
(75)

which completes the proof.∎

Property (A3) implies that all $n$-qubit functions are normalized. Since any
$n$-qubit state $\rho$ has trace 1,

$\displaystyle 1=\mathrm{tr}[\rho]$
$\displaystyle=\mathrm{tr}\left[\sum_{{\bm{u}}\in{\cal
P}_{n}}W_{\rho}({\bm{u}})A_{\bm{u}}\right]$
$\displaystyle=\sum_{{\bm{u}}\in{\cal
P}_{n}}W_{\rho}({\bm{u}})\mathrm{tr}[A_{\bm{u}}]$
$\displaystyle=\sum_{{\bm{u}}\in{\cal P}_{n}}W_{\rho}({\bm{u}}),$ (76)

where the last equality is established by the unit trace of phase point
operators.

We will also find it useful to identify the following property of phase point
operators:

  1. (A4)

(Completeness Relation).

$\displaystyle\sum_{{\bm{u}}\in{\cal P}_{n}}A_{\bm{u}}=2^{n}\mathbbm{1}_{n}$
(77)

###### Proof.

Adopting the decomposition of each $A_{\bm{u}}$ in Eq. (70), we see that

$\displaystyle\sum_{{\bm{u}}\in{\cal P}_{n}}A_{\bm{u}}$
$\displaystyle=\sum_{{\bm{u}}_{1}\in{\cal
P}_{1}},\dots,\sum_{{\bm{u}}_{n}\in{\cal
P}_{1}}\left(\bigotimes_{j=1}^{n}A_{{\bm{u}}_{j}}\right)$
$\displaystyle=\bigotimes_{j=1}^{n}\left(\sum_{{\bm{u}}_{j}\in{\cal
P}_{1}}A_{{\bm{u}}_{j}}\right).$ (78)

Using the explicit forms of single-qubit phase-point operators in Eq. (71), we
calculate that

$\displaystyle\sum_{{\bm{v}}\in{\cal P}_{1}}A_{\bm{v}}=2\mathbbm{1},$ (79)

from which the result immediately follows. ∎

###  A.2 Wigner representation for rebits

Any $n$-qubit state $\rho$ can be decomposed as

$\rho=\left[\frac{1}{2}\left(\rho+\rho^{T}\right)\right]+i\left[\frac{-i}{2}\left(\rho-\rho^{T}\right)\right],$
(80)

where the transposition is taken with respect to the computational basis.
Because $\rho^{*}=\rho^{T}$ in any basis, we can identify

$\displaystyle\rho^{(0)}$
$\displaystyle\coloneqq\frac{1}{2}(\rho+\rho^{T})=\mathfrak{Re}(\rho),$ (81)
$\displaystyle\rho^{(1)}$
$\displaystyle=i\left[\frac{-i}{2}(\rho-\rho^{T})\right]=\mathfrak{Im}(\rho),$
(82)

i.e., $\rho^{(0)}$ and $\rho^{(1)}$ are respectively the real and imaginary
components of the density matrix of $\rho$ in the computational basis.

We first prove Lemma 1, which shows there is a direct correspondence between
the real/imaginary components of a state’s Wigner representation and those of
its density matrix in the computational basis. See 1

###### Proof.

Adopting the identification $\rho^{(0)}=\mathfrak{Re}(\rho)$ and
${\rho^{(1)}=\mathfrak{Im}(\rho)}$, we can then decompose $W_{\rho}({\bm{u}})$
as

$\displaystyle
W_{\rho}({\bm{u}})=\frac{1}{2^{n}}\mathrm{tr}\left[A^{\dagger}_{\bm{u}}\rho^{(0)}\right]+i\frac{1}{2^{n}}\mathrm{tr}\left[A^{\dagger}_{\bm{u}}\rho^{(1)}\right].$
(83)

Since $A_{\bm{u}}$ is real, and both $\rho^{(0)}$ and $\rho^{(1)}$ are real by
construction, we conclude that
$\mathrm{tr}\left[A^{\dagger}_{\bm{u}}\rho^{(0)}\right]$ and
$\mathrm{tr}\left[A^{\dagger}_{\bm{u}}\rho^{(1)}\right]$ are both real for all
${\bm{u}}\in{\cal P}_{n}$. Therefore,

$\displaystyle\mathfrak{Re}(W_{\rho}({\bm{u}}))=\frac{1}{2^{n}}\mathrm{tr}\left[A^{\dagger}_{\bm{u}}\rho^{(0)}\right]=W_{\rho^{(0)}}({\bm{u}})$
(84)
$\displaystyle\mathfrak{Im}(W_{\rho}({\bm{u}}))=\frac{1}{2^{n}}\mathrm{tr}\left[A^{\dagger}_{\bm{u}}\rho^{(1)}\right]=W_{\rho^{(1)}}({\bm{u}})$
(85)

∎

An $n$-rebit Wigner representation $W^{(0)}_{\rho}$ was introduced by Delfosse
et al. [44], which is defined as

$\displaystyle
W^{(0)}_{\rho}({\bm{u}})\coloneqq\frac{1}{2^{n}}\mathrm{tr}\left[A^{(0)\dagger}_{\bm{u}}\rho\right],$
(86)

for all ${\bm{u}}\in{\cal P}_{n}$, where

$\displaystyle A_{{\bm{u}}}^{(0)}$
$\displaystyle\coloneqq\frac{1}{2^{n}}\sum_{{\bm{a}}\in{\cal
P}^{0}_{n}}(-1)^{[{\bm{u}},{\bm{a}}]}D_{{\bm{a}}}$ (87)

for the subset of phase space

$\displaystyle{\cal
P}^{0}_{n}\coloneqq\left\\{{\bm{u}}\,:\,{\bm{u}}_{x}\cdot{\bm{u}}_{z}=0\right\\}.$
(88)

The definition of qubit displacement operators in Eq. (6) implies the
relations

$\displaystyle{\bm{u}}_{x}\cdot{\bm{u}}_{z}=0\Leftrightarrow
D^{\dagger}_{\bm{u}}=D^{T}_{\bm{u}}=D_{\bm{u}}$ (89)
$\displaystyle{\bm{u}}_{x}\cdot{\bm{u}}_{z}=1\Leftrightarrow
D^{\dagger}_{\bm{u}}=D^{T}_{\bm{u}}=-D_{\bm{u}},$ (90)

We then see from Eq. (89) that ${\cal P}^{(0)}_{n}$ is the subset of phase
space co-ordinates for real symmetric displacement operators. The difference
between $W_{\rho}$ and $W^{(0)}_{\rho}$ thus comes down to the fact that
$A_{\bm{u}}$ sums over all displacement operators whereas $A^{(0)}_{\bm{u}}$
only sums over real symmetric ones, which implies $A^{(0)}_{\bm{u}}$ is itself
real symmetric.

We further observe from Eq. (90) that the complement of ${\cal P}^{(0)}_{n}$
in ${\cal P}_{n}$,

$\displaystyle{\cal P}^{(1)}_{n}$
$\displaystyle\coloneqq\\{{\bm{u}}\,:\,{\bm{u}}_{x}\cdot{\bm{u}}_{z}=1\\},$
(91)

is the subset of phase space co-ordinates for real anti-symmetric displacement
operators. Paralleling Eq. (87), we then introduce the set of real anti-
symmetric phase point operators

$\displaystyle
A^{(1)}_{{\bm{u}}}\coloneqq\frac{1}{2^{n}}\sum_{{\bm{a}}\in{\cal
P}^{(1)}_{n}}(-1)^{[{\bm{u}},{\bm{a}}]}D_{{\bm{a}}}\text{ for any
}{\bm{u}}\in{\cal P}_{n},$ (92)

By Eq. (87) and Eq. (92), each $A_{\bm{u}}$ splits up as

$\displaystyle A_{\bm{u}}=A^{(0)}_{\bm{u}}+A^{(1)}_{\bm{u}}.$ (93)

We can correspondingly split up the Wigner representation of $\rho$ as

$\displaystyle W_{\rho}({\bm{u}})$
$\displaystyle=\frac{1}{2^{n}}\mathrm{tr}[A^{\dagger}_{\bm{u}}\rho]=\frac{1}{2^{n}}\mathrm{tr}\left[\left(A^{(0)}_{{\bm{u}}}+A^{(1)}_{\bm{u}}\right)^{\dagger}\rho\right]$
$\displaystyle=\frac{1}{2^{n}}\mathrm{tr}\left[A^{(0)\dagger}_{{\bm{u}}}\rho\right]+\frac{1}{2^{n}}\mathrm{tr}\left[A^{(1)\dagger}_{{\bm{u}}}\rho\right]$
$\displaystyle\eqqcolon W_{\rho}^{(0)}({\bm{u}})+W_{\rho}^{(1)}({\bm{u}}),$
(94)

where we have defined

$W_{\rho}^{(1)}({\bm{x}}):=\frac{1}{2^{n}}\mathrm{tr}\left[A^{(1)\dagger}_{\bm{x}}\rho\right]=-\frac{1}{2^{n}}\mathrm{tr}\left[A^{(1)}_{\bm{x}}\rho\right].$
(95)

We can then prove

######  Lemma 10.

Given any $n$-qubit state $\rho$,

$\displaystyle\mathfrak{Re}(W_{\rho}({\bm{u}}))=W^{(0)}_{\rho}({\bm{u}})$ (96)
$\displaystyle i\mathfrak{Im}(W_{\rho}({\bm{u}}))=W^{(1)}_{\rho}({\bm{u}})$
(97)

###### Proof.

Because $A^{(0)}_{\bm{u}}$ and $A^{(1)}_{\bm{u}}$ are respectively real
symmetric and real anti-symmetric, we have
${A^{(0)\dagger}_{\bm{u}}=A^{(0)T}_{\bm{u}}=A^{(0)}_{\bm{u}}}$ and
$A^{(1)\dagger}_{\bm{u}}=A^{(1)T}_{\bm{u}}=-A_{\bm{u}}$. Thus for $k=0,1$, we
obtain

$\displaystyle\left[W^{(k)}_{\rho}({\bm{u}})\right]^{*}$
$\displaystyle=\frac{1}{2^{n}}\mathrm{tr}\left[A^{(k)\dagger}_{{\bm{u}}}\rho\right]^{*}$
$\displaystyle=\frac{1}{2^{n}}\mathrm{tr}\left[(A^{(k)\dagger}_{{\bm{u}}}\rho)^{\dagger}\right]$
$\displaystyle=\frac{1}{2^{n}}\mathrm{tr}\left[(-1)^{k}(A^{(k)\dagger}_{{\bm{u}}}\rho)\right]$
$\displaystyle=(-1)^{k}W^{(k)}_{\rho}({\bm{u}}).$ (98)

This implies $W^{(0)}_{\rho}({\bm{u}})$ is the real component of
$W_{\rho}({\bm{u}})$ while $W^{(1)}_{\rho}({\bm{u}})$ is its imaginary
component. ∎

By combining Lemmas 1 and 10, we arrive at

$\displaystyle W_{\mathfrak{Re}[\rho]}({\bm{u}})=W^{(0)}_{\bm{u}}(\rho).$ (99)

When $\rho$ is an $n$-rebit state, $\mathfrak{Re}(\rho)=\rho$, which implies
${W_{\rho}({\bm{u}})=W^{(0)}_{\rho}({\bm{u}})}$.

###  A.3 Wigner representation of qubit channels

We recall from the main text that the Wigner representation of a channel
${\cal E}:{\cal B}({\cal H}^{n}_{2})\rightarrow{\cal B}({\cal H}^{m}_{2})$ is
the linear map $W_{\cal E}:{\cal P}_{n}\rightarrow{\cal P}_{m}$ on phase space
defined as

$\displaystyle W_{{\cal E}}({\bm{v}}|{\bm{u}})\coloneqq 2^{2n}W_{{\cal
J}({\cal E})}({\bm{u}}\oplus{\bm{v}}),$ (100)

for all ${\bm{v}}\in{\cal P}_{m},{\bm{u}}\in{\cal P}_{n}$, where the Choi
state [51] of ${\cal E}$, ${\cal J}({\cal E})$, is defined as ${\cal J}({\cal
E})=(\mathcal{I}\otimes{\cal E})\outerproduct{\phi^{+}_{n}}{\phi^{+}_{n}}$ for
the canonical maximally entangled state $\ket{\phi^{+}_{n}}$ on two sets of
$n$ qubits,

$\displaystyle\ket{\phi^{+}_{n}}\coloneqq\frac{1}{\sqrt{2n}}\left(\sum_{{\bm{k}}\in\\{0,1\\}^{n}}\ket{{\bm{k}}}\otimes\ket{{\bm{k}}}\right).$
(101)

One can straightforwardly verify that $\ket{\phi^{+}_{n}}$ is stabilized by
$\langle Z_{i}Z_{n+i},X_{i}X_{n+i}\rangle_{i=1,\dots,n}$ and is therefore a
CSS state.

The factorization property ((A1)) of phase point operators implies that

$\displaystyle W_{{\cal
E}}({\bm{v}}|{\bm{u}})=\frac{2^{n}}{2^{m}}\mathrm{tr}\left[\left(A^{\dagger}_{{\bm{u}}}\otimes
A^{\dagger}_{{\bm{v}}}\right){\cal J}({\cal E})\right].$ (102)

Using the identity ${{\cal
E}(X)=2^{n}\mathrm{tr}_{1,\dots,n}\left[(X^{T}\otimes\mathbbm{1}^{\otimes
m}){\cal J}({\cal E})\right]}$ for transposition taken with respect to the
computational basis, and recalling that $A_{\bm{u}}$ is real in the
computational basis, we then conclude

$\displaystyle W_{{\cal
E}}({\bm{v}}|{\bm{u}})=\frac{1}{2^{m}}\mathrm{tr}[A^{\dagger}_{{\bm{v}}}{\cal
E}(A^{*}_{{\bm{u}}})]=\frac{1}{2^{m}}\mathrm{tr}[A^{\dagger}_{{\bm{v}}}{\cal
E}(A_{{\bm{u}}})].$ (103)

Therefore, if $\sigma={\cal E}(\rho)$, then we obtain Eq. (17) from the main
text, i.e.,

$\displaystyle W_{\sigma}({\bm{v}})$
$\displaystyle=\frac{1}{2^{m}}\mathrm{tr}\left[A^{\dagger}_{{\bm{v}}}{\cal
E}(\rho)\right]$ $\displaystyle=\frac{1}{2^{m}}\mathrm{tr}\left[{\cal
E}\left(\sum_{{\bm{u}}\in{\cal
P}_{n}}W_{\rho}({\bm{u}})A_{{\bm{u}}}\right)A^{\dagger}_{{\bm{v}}}\right]$
$\displaystyle=\frac{1}{2^{m}}\sum_{{\bm{u}}\in{\cal
P}_{n}}\mathrm{tr}\left[A^{\dagger}_{{\bm{v}}}{\cal
E}\left(A_{{\bm{u}}}\right)\right]W_{\rho}({\bm{u}})$
$\displaystyle=\sum_{{\bm{u}}\in{\cal P}_{n}}W_{\cal
E}({\bm{v}}|{\bm{u}})W_{\rho}({\bm{u}}).$ (104)

We thereby see that if ${\cal E}$ maps $\rho$ to $\sigma$, then $W_{\cal E}$
is a matrix that maps $W_{\rho}$ to $W_{\sigma}$, which justifies regarding
$W_{\cal E}$ as the representation of ${\cal E}$ on phase space.

By property (A4) of the phase point operators, we have that
$\sum_{{\bm{v}}\in{\cal P}_{m}}A_{\bm{v}}=2^{m}\mathbbm{1}_{m}$. By applying
this to the alternative formulation of $W_{\cal E}$ in Eq. (103), we see that

$\displaystyle\sum_{{\bm{v}}\in{\cal P}_{m}}W_{\cal E}({\bm{v}}|{\bm{u}})$
$\displaystyle=\frac{1}{2^{m}}\sum_{{\bm{v}}\in{\cal
P}_{m}}\mathrm{tr}\left[A^{\dagger}_{{\bm{v}}}{\cal E}(A_{{\bm{u}}})\right]$
$\displaystyle=\frac{1}{2^{m}}\mathrm{tr}\left[\left(\sum_{{\bm{v}}\in{\cal
P}_{m}}A_{{\bm{v}}}\right)^{\dagger}{\cal E}(A_{{\bm{u}}})\right]$
$\displaystyle=\frac{1}{2^{m}}\mathrm{tr}[2^{m}\mathbbm{1}_{m}{\cal
E}(A_{\bm{u}})]$ $\displaystyle=\mathrm{tr}[{\cal E}(A_{\bm{u}})].$ (105)

Then recalling that $\mathrm{tr}[A_{\bm{u}}]=1$ (property (A3)), we obtain Eq.
(21) from the main text, i.e.,

$\displaystyle\sum_{{\bm{v}}\in{\cal P}_{m}}W_{\cal
E}({\bm{v}}|{\bm{u}})=\mathrm{tr}[A_{\bm{u}}]=1.$ (106)

This means every column of $W_{\cal E}$ sums up to 1.

Finally, we show that the representation we have chosen respects sequential
and parallel composition of processes.

Let ${\cal E}:{\cal B}({\cal H}^{l}_{2})\rightarrow{\cal B}({\cal H}^{k}_{2})$
and ${\cal F}:{\cal B}({\cal H}^{n}_{2})\rightarrow{\cal B}({\cal H}^{m}_{2})$
be two multiqubit channels. Since $\\{A_{{\bm{x}}}\\}_{{\bm{x}}\in{\cal
P}_{m}}$ are a complex orthogonal basis for $2^{m}\times 2^{m}$ complex
matrices under the Hilbert-Schmidt inner product, we have that ${{\cal
F}(A_{\bm{u}})=\frac{1}{2^{m}}\sum_{{\bm{x}}\in{\cal
P}_{m}}\mathrm{tr}[A^{\dagger}_{{\bm{x}}}{\cal F}(A_{\bm{u}})]}A_{{\bm{x}}}$.
Therefore, when $m=l$, we obtain

$\displaystyle W_{[{\cal E}\circ{\cal F}]}({\bm{v}}|{\bm{u}})$
$\displaystyle=\frac{1}{2^{k}}\mathrm{tr}[A^{\dagger}_{\bm{v}}{\cal
E}\circ{\cal F}(A_{\bm{u}})]$
$\displaystyle=\frac{1}{2^{k}}\mathrm{tr}\left[A^{\dagger}_{\bm{v}}{\cal
E}\left(\frac{1}{2^{m}}\sum_{{\bm{x}}\in{\cal
P}_{m}}\mathrm{tr}[A^{\dagger}_{\bm{x}}{\cal
F}(A_{\bm{u}})]A_{\bm{x}}\right)\right]$ $\displaystyle=\sum_{{\bm{x}}\in{\cal
P}_{m}}\frac{1}{2^{k}}\mathrm{tr}[A^{\dagger}_{\bm{v}}{\cal
E}(A_{\bm{x}})]\frac{1}{2^{m}}\mathrm{tr}[A^{\dagger}_{\bm{x}}{\cal
F}(A_{\bm{u}})]$ $\displaystyle=\sum_{{\bm{x}}\in{\cal P}_{m}}W_{\cal
E}({\bm{v}}|{\bm{x}})W_{\cal F}({\bm{x}}|{\bm{u}}),$ (107)

or in matrix notation,

$\displaystyle W_{{\cal E}\circ{\cal F}}=W_{\cal E}W_{\cal F}.$ (108)

Furthermore, due to the factorization property of the phase point operators,
we have that

$\displaystyle W_{{\cal E}\otimes{\cal
F}}({\bm{x}}\oplus{\bm{y}}|{\bm{u}}\oplus{\bm{v}})$
$\displaystyle=\frac{1}{2^{(m+k)}}\mathrm{tr}[A^{\dagger}_{\bm{x}}\otimes
A^{\dagger}_{\bm{y}}{\cal E}\otimes{\cal F}(A_{\bm{u}}\otimes A_{\bm{v}})]$
$\displaystyle=\frac{1}{2^{k}}\mathrm{tr}[A^{\dagger}_{\bm{x}}{\cal
E}(A_{\bm{u}})]\frac{1}{2^{m}}\mathrm{tr}[A^{\dagger}_{\bm{y}}{\cal
F}(A_{\bm{v}})]$ $\displaystyle=W_{\cal E}({\bm{x}}|{\bm{u}})W_{\cal
F}({\bm{y}}|{\bm{v}}),$ (109)

or in matrix notation

$\displaystyle W_{{\cal E}\otimes{\cal F}}=W_{\cal E}\otimes W_{\cal F}.$
(110)

##  APPENDIX B COMPLETELY CSS-PRESERVING OPERATIONS

###  B.1 Completely CSS-preserving unitaries

The group of CSS-preserving unitaries on $n$ qubits [44] can be generated as

${\cal G}_{+}(n)\coloneqq\langle H^{\otimes
n},\operatorname{CNOT}(i,j),X_{i},Z_{i}\rangle_{i,j=1,\dots,n,i\neq j}.$ (111)

We will also find it useful to note the following conjugation relations of the
collective Hadamard gate,

$\displaystyle H^{\otimes n}\operatorname{CNOT}(i,j)$
$\displaystyle=\operatorname{CNOT}(j,i)H^{\otimes n}$ (112) $\displaystyle
H^{\otimes n}X({\bm{a}})$ $\displaystyle=Z({\bm{a}})H^{\otimes n},$ (113)

which respectively hold for all $i,j\in\\{1,\dots n\\}$ where $i\neq j$ and
$n$-bit strings ${\bm{a}}\in\\{0,1\\}^{n}$.

######  Lemma 11.

The group of completely CSS-preserving unitaries on $n$ qubits is

${\cal
G}(n)\coloneqq\langle\operatorname{CNOT}(i,j),Z_{i},X_{i}\rangle_{i,j=1,\dots,n,i\neq
j}.$ (114)

###### Proof.

Let $U_{+}$ be any CSS-preserving unitary on $n$ qubits. We first observe that
$U_{+}$ is either in ${\cal G}(n)$ or is a unitary from ${\cal G}(n)$ followed
by the collective Hadamard gate on $n$ qubits, i.e., $U_{+}=\left[H^{\otimes
n}\right]^{b}U$ for some binary digit $b\in\\{0,1\\}$ and unitary $U\in{\cal
G}(n)$. This follows from the conjugation relations Eq. (112) and Eq. (113)
alongside the fact that $H^{\otimes n}$ is self-inverse.

If $U_{+}$ is in ${\cal G}(n)$, then because ${\cal G}(n)$ is a subset of
${\cal G}_{+}(n^{\prime})$ for all $n^{\prime}\geq n$, $U_{+}$ must be
completely CSS-preserving. If $U_{+}$ is not in ${\cal G}(n)$, then we must
have $U_{+}=H^{\otimes n}U$ for some $U\in{\cal G}(n)$, which implies $U_{+}$
cannot be completely CSS-preserving since $H^{\otimes n}$ is not completely
CSS-preserving. Therefore, $U_{+}$ is completely CSS-preserving if and only if
it is in ${\cal G}(n)$. ∎

###  B.2 Completely CSS-preserving measurements

Throughout the rest of this appendix, we extend, wherever necessary, the
notion of being completely CSS-preserving to trace-decreasing operations –
i.e., a trace-decreasing operation ${\cal E}$ from $n$ to $n^{\prime}$ qubits
is completely CSS-preserving if, given any CSS state $\rho$ on $m+n$ qubits,
we have that $(\mathcal{I}_{m}\otimes{\cal E})(\rho)$ is always a (possibly
subnormalised) CSS state on $(m+n^{\prime})$ qubits.

The projective measurement of any $n$-qubit Pauli observable $S$ is carried
out using projectors ${P(\pm S)\coloneqq\frac{1}{2}(\mathbbm{1}_{n}\pm S)}$
corresponding to the $\pm 1$ outcomes. Post-selection for the $\pm 1$ outcome
is then carried out by the operation ${{\cal P}(\pm S)\coloneqq P(\pm
S)(\cdot)P(\pm S)}$.

######  Lemma 12.

Post-selecting the $\pm 1$ outcome in the projective measurement of a CSS
observable is completely CSS-preserving.

###### Proof.

Let $S$ be a CSS observable on $n$ qubits and $\ket{\psi}$ be a CSS state on
$m+n$ qubits for any $m\geq 0$. Then let $S_{1},\dots,S_{m+n}$ be a set of
$m+n$ CSS observables that generate the stabilizer group ${\cal
S}(\ket{\psi})$ of $\ket{\psi}$.

Post-selecting the $\pm 1$ outcome in a projective measurement of $S$ on the
last $n$ qubits of $\ket{\psi}$ yields the possibly subnormalised output

$\displaystyle\ket{\phi_{\pm}}$
$\displaystyle\coloneqq\left[\mathbbm{1}^{\otimes m}\otimes P(\pm
S)\right]\ket{\psi}$
$\displaystyle=\left[\frac{1}{2}\left(\mathbbm{1}^{\otimes
m+n}\pm\mathbbm{1}_{m}\otimes S\right)\right]\ket{\psi}$ $\displaystyle=P(\pm
S^{\prime})\ket{\psi},$ (115)

where we have defined the CSS observable
$S^{\prime}\coloneqq\mathbbm{1}^{\otimes m}\otimes S$. There are now two
possibilities:

  1. (a)

that $S^{\prime}$ commutes with every generator of ${\cal S}(\ket{\psi})$, so
$S^{\prime}$ or $-S^{\prime}$ must stabilize $\ket{\psi}$. Therefore, either
$\ket{\phi_{+}}=\ket{\psi}$ and $\ket{\phi_{-}}=0$ or vice versa, so
$\ket{\phi_{\pm}}$ are possibly subnormalised CSS states.

  2. (b)

that, without loss of generality, $S^{\prime}$ does not commute with just one
CSS observable $S_{1}$ that generates ${\cal S}(\ket{\psi})$. This follows
from the fact that, in any set of $m+n$ CSS observables that generate ${\cal
S}(\ket{\psi})$, those that do not commute with $S^{\prime}$ must all be $X$
or $Z$-type, so by picking one such generator and multiplying all others by
it, we obtain another set of $m+n$ CSS observables generating ${\cal
S}(\ket{\psi})$ in which only one generator does not commute with
$S^{\prime}$. Then the states $\ket{\phi_{\pm}}$ have norm
$\frac{1}{\sqrt{2}}$ and are stabilized respectively by $\langle\pm
S,S_{2},\dots,S_{m+n}\rangle$, so $\ket{\phi_{\pm}}$ are subnormalised CSS
states.

Therefore, given any pure CSS state $\ket{\psi}$ on $m+n$ qubits, post-
selecting the $\pm 1$ outcome in the projective measurement of a CSS
observable on the last $n$ qubits of $\ket{\psi}$ always produces a (possibly
subnormalised) CSS state. Since every CSS state is a statistical mixture of
pure CSS states, we arrive at the Lemma result. ∎

###  B.3 CSS circuits

In this section, we show that the subset of stabilizer operations covered by
Lemma 3, which we referred to as CSS circuits, are completely CSS-preserving.

To reiterate, a CSS circuit is any sequence of the following four primitive
CSS channels:

  1. 1.

Introducing a CSS state on any number of qubits,

  2. 2.

Performing a completely CSS-preserving unitary,

  3. 3.

Projective measurement of any CSS observable, with the possibility of
performing different sequences of primitive CSS channels depending on outcome,

  4. 4.

Discarding any number of qubits,

as well as statistical mixtures of such sequences. We emphasise that all CSS
circuits are trace-preserving.

Any sequence of primitive CSS channels can be executed as a binary tree where
the root node represents inputting qubits, the leaf nodes represent outputting
qubits, and internal nodes represent primitive CSS channels. An illustrative
example is provided in Fig. 7, from which we see that a sequence of primitive
CSS channels can produce outputs distinguished by the sequences of measurement
outcomes leading up to them.

Figure 7: The sequence of primitive CSS channels on the top can be executed as
the binary tree on the bottom.

Different numbers of ancillary qubits may be introduced on different branches
of a tree representing a sequence of primitive CSS channels. However, one can
arbitrarily increase the number of qubits introduced on any branch, without
affecting what it does, by introducing the maximally mixed state on qubits
that are immediately discarded just before the branch’s output. Furthermore,
different branches may have different lengths. However, one can arbitrarily
lengthen any branch, without affecting what it does, by inserting identity
channels just before the branch’s output. Since introducing the maximally
mixed state and the identity channel are both primitive CSS channels, we can,
without loss of generality, only consider sequences of primitive CSS channels
executed as binary trees where every branch has the same length and introduces
the same number of ancillary qubits.

######  Lemma 13.

A CSS circuit ${\cal E}$ on $n$ qubits is a statistical mixture of channels
${\cal E}_{i}$ representing sequences of primitive CSS channels, in which each
sequence ${\cal E}_{i}$ is a sum of (possibly trace-decreasing) operations
${\cal E}_{i,j}$ generating its distinguishable outputs. Thus one can write

$\displaystyle{\cal E}(\rho)$ $\displaystyle=\sum_{i}p_{i}{\cal E}_{i},\text{
where }{\cal E}_{i}=\sum_{j}{\cal E}_{i,j},$ $\displaystyle{\cal E}_{i,j}$
$\displaystyle=\mathrm{tr}_{{\cal
R}}\left[K_{i,j}(\rho\otimes\sigma_{i,j})K_{i,j}^{\dagger}\right],\text{ and
}$ $\displaystyle K_{i,j}$
$\displaystyle=\prod_{l=1}^{N}P(S_{(i,j),l})U_{(i,j),l},$ (116)

in which $\\{p_{i}\\}$ forms a probability distribution, $\sigma_{i,j}$ is a
CSS state on $m$ ancillary qubits, ${\cal R}$ is a subset of the $(n+m)$ input
and ancillary qubits, $U_{(i,j),l}$ is a completely CSS-preserving unitary and
$P(S_{(i,j),l})$ projects onto the $+1$ eigenspace of the CSS observable
$S_{(i,j),l}$. Moreover, $P(S_{(i,j),1}),\dots,P(S_{(i,j),N})$ gives the
sequence of measurement outcomes that operationally distinguish the $j$th
possible output of sequence ${\cal E}_{i}$.

###### Proof.

Without loss of generality, every branch of every sequence forming the mixture
of ${\cal E}$ introduces the same number of ancillary qubits $m$ and has same
length $N$. One can show that the $j$th branch of the $i$th sequence must
generate the channel ${\cal E}_{i,j}$ by induction over the steps of the
branch. ∎

Because each possible output from a sequence of primitive CSS channels results
from a unique sequence of measurement outcomes, it is operationally meaningful
to prepare a state conditioned upon obtaining the $j$th possible output in the
$i$th sequence from the statistical mixture forming ${\cal E}$. We therefore
have the following corollary:

######  Corollary 2.

We can record which operationally distinguishable output ${\cal E}_{i,j}$ from
a CSS circuit ${\cal E}$ was obtained using a classical register,

$\displaystyle{\cal E}^{\prime}(\rho)\coloneqq\sum_{i,j}p_{i}\ {\cal
E}_{i,j}(\rho)\otimes\outerproduct{r_{i,j}}{r_{i,j}},$ (117)

where $\ket{r_{i,j}}$ is a computational basis state on multiple qubits. We
note that, since $\ket{r_{i,j}}$ is a CSS state, ${\cal E}^{\prime}$ can be
carried out as a CSS circuit.

In the next subsection, we use this corollary to obtain the trace-preserving
CSS code projection studied throughout this paper.

We are finally in a position to prove Lemma 3, which is reproduced below. To
this end, it is convenient to define the unique 0-qubit state 1 as CSS.

######  Lemma 3.

Any CSS circuit is completely CSS-preserving.

###### Proof.

The decomposition of CSS circuits given in Lemma 13 implies that if (i)
performing completely CSS-preserving unitaries, (ii) conditioning on the $+1$
outcome in the projective measurement of a CSS observable, (iii) introducing a
CSS state and (iv) discarding any number qubits are completely CSS-preserving,
then all CSS circuits are completely CSS-preserving.

Now (i) is completely CSS-preserving by definition, we proved that (ii) is
completely CSS-preserving in Lemma 12, and since the tensor product of two CSS
states is always a CSS state, (iii) is completely CSS preserving.

Therefore, to prove that all CSS circuits are completely CSS-preserving, we
just have to prove that discarding any number of qubits is completely CSS-
preserving.

Consider discarding $l$ qubits from $n$, where $n\geq l\geq 1$. Since we can
freely relabel subsystems, we need only consider discarding the last $l$
qubits. Let $\ket{\psi}$ be a pure CSS state on $m+n$ qubits for any $m\geq
0$. Discarding the last $l$ qubits of $\ket{\psi}$ then produces the state
$\sigma\coloneqq\mathcal{I}_{m}\otimes\mathrm{tr}_{n-l+1,\dots,n}[\outerproduct{\psi}{\psi}]$.
Since tracing out is unaffected by first performing a computational basis
measurement on the last $l$ qubits, we have that

$\displaystyle\sigma=\sum_{{\bm{k}}\in\\{0,1\\}^{l}}$
$\displaystyle\mathrm{tr}_{m+n-l+1,\dots,m+n}\big{[}\mathbbm{1}^{\otimes(m+n-l)}\otimes\outerproduct{{\bm{k}}}{{\bm{k}}}$
$\displaystyle\hskip
5.0pt(\outerproduct{\psi}{\psi})\mathbbm{1}^{\otimes(m+n-l)}\otimes\outerproduct{{\bm{k}}}{{\bm{k}}}\big{]}.$
(118)

We then observe that

$\displaystyle\mathbbm{1}^{\otimes(m+n-l)}\otimes\outerproduct{{\bm{k}}}{{\bm{k}}}$
$\displaystyle=$ $\displaystyle P((-1)^{k_{1}}Z_{m+n-l+1})\circ\dots\circ
P((-1)^{k_{l}}Z_{m+n}),$ (119)

and so by Lemma 12, $\left(\mathbbm{1}^{\otimes
m+n-l}\otimes\outerproduct{{\bm{k}}}{{\bm{k}}}\right)\ket{\psi}$ is a possibly
subnormalised pure CSS state
${\sqrt{p_{\bm{k}}}\ket{\phi_{\bm{k}}}\otimes\ket{{\bm{k}}}}$, where
$p_{{\bm{k}}}$ is the probability of getting the $\ket{{\bm{k}}}$ outcome in
the computational basis measurement, and $\ket{\phi_{\bm{k}}}$ must be a
(normalised) CSS state to keep the full state CSS. We thus obtain

$\displaystyle\sigma$
$\displaystyle=\sum_{{\bm{k}}\in\\{0,1\\}^{l}}\mathrm{tr}_{m+n-l+1,\dots,m+n}\left(p_{\bm{k}}\outerproduct{\phi_{\bm{k}}}{\phi_{\bm{k}}}\otimes\outerproduct{{\bm{k}}}{{\bm{k}}}\right)$
$\displaystyle=\sum_{{\bm{k}}\in\\{0,1\\}^{l}}p_{\bm{k}}\outerproduct{\phi_{\bm{k}}}{\phi_{\bm{k}}},$
(120)

which is a CSS state on $(m+n-l)$ qubits. We conclude that, given any pure CSS
state on $m+n$ qubits, discarding any $l\leq n$ of its final $n$ qubits always
produces a CSS state. This is true if and only if discarding any number of
qubits is completely CSS-preserving. ∎

####  B.3.1 Omission of the collective Hadamard gate

The collective Hadamard gate promotes CSS circuits to a subset of stabilizer
circuits where CSS states play role of stabilizer states. One can reasonably
ask why we have excluded the collective Hadamard gate from the construction of
CSS circuits. Our justification is that one can conjugate the collective
Hadamard gate past any primitive CSS channel and leave another primitive CSS
channel behind. This follows from the conjugation relations given by Eq. (112)
and Eq. (113) for completely CSS-preserving unitaries and projective
measurements of CSS observables, from the cyclic property of the trace for
discarding qubits, and from

$\displaystyle H^{\otimes n}\otimes\mathbbm{1}^{\otimes
m}(\rho\otimes\sigma)H^{\otimes n}\otimes\mathbbm{1}^{\otimes m}$
$\displaystyle=$ $\displaystyle H^{\otimes(n+m)}(\rho\otimes(H^{\otimes
m}\sigma H^{\otimes m}))H^{\otimes(n+m)}$ (121)

for introducing a CSS state on $m$ ancillary qubits to an $n$-qubit system,
where we note that $H^{\otimes m}\sigma H^{\otimes m}$ is also a CSS state
because $H^{\otimes m}$ is CSS-preserving on $m$ qubits. Therefore, circuits
from this wider subset are operationally equivalent to CSS circuits followed
by the collective Hadamard gate conditioned upon obtaining certain outputs,
and are therefore not more powerful as magic distillation protocols.

###  B.4 CSS code projections

An $[[n,k]]$ CSS code, where $n\geq 1$ and $n>k\geq 0$, is a vector space
${\cal{C}}$ stabilized by a subgroup ${\cal S}$ of $n$-qubit Pauli observables
such that $-\mathbbm{1}^{\otimes n}\notin{\cal S}$ and ${\cal S}$ can be
generated from $n-k$ independent and commuting CSS observables
$S_{1},\dots,S_{n-k}$, of which none is the identity.

######  Lemma 14.

Let ${\cal S}\coloneqq\langle(-1)^{b_{i}}S_{i}\rangle_{i=1,\dots,n-k}$ be the
stabilizer group of an $[[n,k]]$ CSS code, where each $S_{i}$ is a positive
CSS observable and each $b_{i}$ is a binary digit. Then there exists a
completely CSS-preserving unitary $U$ such that

$\displaystyle U^{\dagger}[(-1)^{b_{i}}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}$
(122)

###### Proof.

Let $r$ be the number of $Z$-type generators for ${\cal S}$. We first
construct the completely CSS-preserving unitary $U$ for the case where all
$Z$-type generators of ${\cal S}$ appear before $X$-type ones, i.e.,

$\displaystyle S_{i}=\begin{cases}Z({\bm{u}}_{i})&\text{ for }1\leq i\leq r\\\
X({\bm{v}}_{i})&\text{ for }r<i\leq n-k\end{cases}$ (123)

where each ${\bm{u}}_{i},{\bm{v}}_{i}$ is a non-zero $n$-dimensional binary
vector.

Let us define ${\cal Z}$ as the set of $Z$-type generators for ${\cal S}$
without their signs, i.e., ${\cal
Z}\coloneqq\\{Z({\bm{u}}_{1}),\dots,Z({\bm{u}}_{r})\\}$. We now prove that
there exists a sequence of $\operatorname{CNOT}$ operations that transforms
$Z({\bm{u}}_{i})$ to $Z_{i}$ for all $1\leq i\leq r$.

We observe that ${\cal Z}$ is a subset of positive $Z$-type observables on $n$
qubits, which form an $n$-dimensional vector space $V$ over the field
$\mathbb{F}_{2}$. Choosing the basis $\\{Z_{1},\dots,Z_{n}\\}$ for $V$, we can
simply write $Z({\bm{u}}_{i})$ as ${\bm{u}}_{i}$, and we further have that
$\\{{\bm{u}}_{1},\dots,{\bm{u}}_{r}\\}$ are linearly independent. Therefore,
the matrix $M_{Z}$ formed by taking members of ${\cal Z}$ as columns has rank
$r$. Using Gauss-Jordan elimination, we can convert $M_{Z}$ into its unique
reduced row echelon form $R_{Z}$,

$\displaystyle M_{Z}\coloneqq\begin{bmatrix}|&\dots&|\\\
{\bm{u}}_{1}&\dots&{\bm{u}}_{r}\\\ |&\dots&|\end{bmatrix}\mapsto
R_{Z}\coloneqq\begin{bmatrix}I_{r,r}\\\ 0_{n-r,r}\end{bmatrix},$ (124)

where $I_{r,r}$ is an $r\times r$ identity matrix while $0_{n-r,r}$ is a
$(n-r)\times r$ null matrix.

On vector spaces over $\mathbb{F}_{2}$, Gauss-Jordan elimination consists of
row swaps and additions. We now show how both can be done on any matrix $M$
whose columns are elements of $V$ in the basis $\\{Z_{1},\dots,Z_{n}\\}$ using
$\operatorname{CNOT}$-gates:

  1. 1.

Swapping rows $j$ and $l$. This corresponds to swapping qubits $j$ and $l$,
which is carried out by performing
$\operatorname{CNOT}(l,j)\operatorname{CNOT}(j,l)\operatorname{CNOT}(a,b)$ on
each positive $Z$-type observable forming a column in $M$.

  2. 2.

Adding row $j$ to row $l$. The action of $CNOT(j,l)$ on $Z_{m}$ is

$\displaystyle\operatorname{CNOT}(l,j)Z_{m}\operatorname{CNOT}(l,j)=\begin{cases}Z_{j}Z_{l}&\text{
for }m=j,\\\ Z_{m}&\text{ otherwise.}\end{cases}$ (125)

Therefore, given any vector ${\bm{u}}$ in $V$, we have that

$\displaystyle\operatorname{CNOT}(l,j)Z({\bm{u}})\operatorname{CNOT}_{l,j}$
$\displaystyle=Z({\bm{u}}+u_{j}{\bm{e}}_{l})$ (126)

where arithmetic is modulo 2 and ${\bm{e}}_{l}$ gives co-ordinates for the
$l$th basis vector of $V$. In words, $\operatorname{CNOT}(j,l)$ adds the $j$th
component of ${\bm{u}}$ to the $l$th. Therefore, performing
$\operatorname{CNOT}(l,j)$ on each positive $Z$-type observable forming a
column in $M$ would add the $j$th row of $M$ to the $l$th row.

We conclude that there exists a sequence of $\operatorname{CNOT}$-gates that,
when performed on each element of ${\cal Z}$, accomplishes the Gauss-Jordan
elimination in Eq. (124). Denoting this sequence of
$\operatorname{CNOT}$-gates by the unitary $U_{Z}$, we have that
$U_{Z}(Z({\bm{u}}_{i}))U^{\dagger}_{Z}=Z_{i}$ for all $1\leq i\leq r$.

We next consider $X$-type generators for ${\cal S}$ without their signs. The
action of $\operatorname{CNOT}(j,l)$ on $X_{m}$ is

$\displaystyle\operatorname{CNOT}(j,l)X_{m}\operatorname{CNOT}(j,l)=\begin{cases}X_{j}X_{l}&\text{
for }m=j,\\\ X_{m}&\text{ otherwise,}\end{cases}$ (127)

so $U_{Z}$ only transforms positive $X$-type observables into other positive
$X$-type observables. In other words, we can find non-zero $n$-bit strings
$\\{{\bm{v}}^{\prime}_{r+1},\dots,{\bm{v}}^{\prime}_{n-k}\\}$ such that
$U_{Z}(X({\bm{v}}_{i}))U^{\dagger}_{Z}=X({\bm{v}}^{\prime}_{i})$ for all
$r<i\leq n-k$.

However, since the $Z$-type generators of ${\cal S}$ commute with the $X$-type
generators, $X({\bm{v}}^{\prime}_{i})$ must commute with $Z_{1},\dots,Z_{r}$.
Therefore, $X({\bm{v}}^{\prime}_{i})$ must act trivially on qubits 1 through
$r$, so the first $r$ bits of ${\bm{v}}^{\prime}_{i}$ must be 0. Therefore
$X({\bm{v}}^{\prime}_{i})=\mathbbm{1}^{\otimes r}\otimes
X({\bm{v}}^{\prime\prime}_{i})$ forall $r<i\leq n-k$, where
${\bm{v}}^{\prime\prime}_{i}$ are the last $(n-r)$ bits of
${\bm{v}}^{\prime}_{i}$.

Everything we have done for $\mathcal{Z}$ can now be repeated for
$\mathcal{X}\coloneqq\\{X({\bm{v}}^{\prime\prime}_{r+1}),\dots,X({\bm{v}}^{\prime\prime}_{n-k})\\}$
on qubits $r+1$ through $n$. The only thing that needs to be checked is that
row addition in any matrix whose columns are elements from the vector space of
positive $(n-r)$-qubit $X$-type observables can be performed by
$\operatorname{CNOT}$-gates. This can be confirmed using Eq. (127), which
implies

$\displaystyle\operatorname{CNOT}(j,l)X({\bm{v}})\operatorname{CNOT}(j,l)$
$\displaystyle=X({\bm{v}}+v_{j}{\bm{e}}_{l})$ (128)

where arithmetic is modulo 2 so $\operatorname{CNOT}(j,l)$ adds the $j$th
component of ${\bm{v}}$ to the $l$th.

We conclude that there also exists a sequence $U_{X}$ of
$\operatorname{CNOT}$-gates such that
$U_{X}(X({\bm{v}}^{\prime}_{i}))U^{\dagger}_{X}=X_{i}$ for all ${r<i\leq
n-k}$. Furthermore, $U_{X}$ acts trivially on qubits 1 through $r$, which
implies $U_{X}(Z_{i})U^{\dagger}_{X}=Z_{i}$ for all $1\leq i\leq r$. Defining
${\cal U}_{X}\coloneqq U_{X}(\cdot)U^{\dagger}_{X}$ and ${\cal U}_{Z}\coloneqq
U_{Z}(\cdot)U^{\dagger}_{Z}$, we therefore have

$\displaystyle({\cal U}_{Z}\circ{\cal U}_{X})[(-1)^{b_{i}}S_{i}]$
$\displaystyle=$ $\displaystyle\begin{cases}(-1)^{b_{i}}X_{i}&\text{ for
}1\leq i\leq r\\\ (-1)^{b_{i}}Z_{i}&\text{ for }r<i\leq n-k.\end{cases}$ (129)

We now define unitaries $U_{C}$ and $U_{\text{SWAP}}$, which respectively
remove the signs from the generators of ${\cal S}$ and moves qubits 1 through
$n-k$ to $k+1$ through $n$,

$\displaystyle U_{C}$
$\displaystyle\coloneqq\left[\prod_{i=r+1}^{n-k}X_{i}^{b_{i}}\right]\left[\prod_{i=1}^{r}Z_{i}^{b_{i}}\right],$
$\displaystyle U_{\text{SWAP}}$
$\displaystyle\coloneqq\prod_{i=0}^{n-k-1}\text{SWAP}(n-i,n-k-i),$ (130)

where
$\text{SWAP}(i,j)\coloneqq\operatorname{CNOT}(i,j)\operatorname{CNOT}(j,i)\operatorname{CNOT}(i,j)$
swaps qubits $i$ and $j$. Defining ${{\cal U}_{C}\coloneqq U_{C}(\cdot)U_{C}}$
and $U_{\text{SWAP}}\coloneqq U_{\text{SWAP}}(\cdot)U_{\text{SWAP}}$, we
obtain

$\displaystyle({\cal U}_{\text{SWAP}}\circ{\cal U}_{C}\circ{\cal
U}_{Z}\circ{\cal U}_{X})[(-1)^{b_{i}}S_{i}]$ $\displaystyle=$
$\displaystyle\begin{cases}X_{i}&\text{ for }1\leq i\leq r\\\ Z_{i}&\text{ for
}r+1\leq i\leq n-k.\end{cases}$ (131)

Since $U^{\dagger}\coloneqq U_{C}U_{Z}U_{X}$ is formed from
$\operatorname{CNOT}$-, single-qubit $X$\- and $Z$\- gates, it is a completely
CSS-preserving unitary that accomplishes the Lemma’s claim for the ordering of
$S_{i}$ given by Eq. (123).

By appropriate swaps among the last $n-k$ qubits, which we have seen is
completely CSS-preserving, we can construct a completely CSS-preserving
unitary accomplishing the Lemma’s claim for any ordering of $S_{i}$. ∎

As an immediate consequence of Lemma 14,

######  Corollary 3.

Every $[[n,k]]$ CSS code has a completely CSS-preserving encoding unitary.

###### Proof.

Let ${\cal{C}}$ be an $[[n,k]]$ CSS code whose stabilizer group is generated
by CSS observables $S_{1},\dots,S_{n-k}$, and let ${\bm{s}}$ be a $k$-bit
string (if $k=0$, then ${\bm{s}}$ is the empty string). By Lemma 14, there
exists a completely CSS-preserving unitary $U$ such that

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

In words, $U$ can encode any computational basis state $\ket{{\bm{s}}}$ on $k$
physical qubits (if $k=0$, then $\ket{{\bm{s}}}=1$) as a CSS logical basis
state $\ket{{\bm{s}}_{\cal{C}}}$ in ${\cal{C}}$. ∎

With Corollary 3 in hand, we can show that every trace-preserving CSS code
projection can be executed as a CSS circuit, which leads to the following
Lemma from the main text: See 6

###### Proof.

Let ${\cal{C}}$ be an $[[n,k]]$ CSS code generated by CSS observables
$S_{1},\dots,S_{n-k}$. We can then define a quantum channel ${\cal F}$ that
carries out the following sequence of primitive CSS channels:

  1. 1.

Projectively measure $S_{1},\dots,S_{n-k}$, which is equivalent to the
syndrome measurement of ${\cal{C}}$.

  2. 2.

If the no-error syndrome is obtained, decode onto the first $k$ qubit using a
completely CSS-preserving decoding unitary, which always exists in accordance
with Corollary 3, and discard the final $n-k$ qubits.

  3. 3.

Otherwise, discard all qubits and prepare a $k$-qubit CSS state $\sigma$.

Since ${\cal F}$ is a CSS circuit by construction, it is completely CSS-
preserving. By Corollary 2, we can convert ${\cal F}$ into a trace-preserving
code projection ${\cal E}$ for ${\cal{C}}$ by distinguishing the output of the
no-error syndrome from those of all other syndrome using a single-qubit
classical register, i.e. by preparing an ancillary qubit in the state
$\ket{0}$ if we obtain the no-error syndrome output, and in the state
$\ket{1}$ otherwise. Corollary 2 confirms that ${\cal E}$ can also be executed
as a CSS circuit and is therefore completely CSS-preserving. We conclude by
Lemma 3 that ${\cal E}$ is stochastically represented. ∎

##  APPENDIX C ENTROPIC CONSTRAINTS ON COMPLETELY CSS-PRESERVING PROTOCOLS

In this section we prove Theorem 5, which gives entropic constraints on
generic completely CSS-preserving protocols for qubits.

We first define the sets of positively-represented and real-represented
quantum states in any Wigner representation $W$ as

$\displaystyle W^{+}$
$\displaystyle\coloneqq\\{\rho:W_{\rho}({\bm{u}})>0,W_{\rho}({\bm{u}})\in\mathbb{R},\forall{\bm{u}}\in{\cal
P}\\},$ (133) $\displaystyle W^{\mathbb{R}}$
$\displaystyle\coloneqq\\{\rho:W_{\rho}({\bm{u}})\in\mathbb{R},\forall{\bm{u}}\in{\cal
P}\\},$ (134)

We then have the following Lemma, which is a generalisation of Theorem 11 of
Ref. [27].

######  Lemma 15.

Let $\rho$ and $\tau$ be states of a $d$-dimensional qudit such that $\rho\in
W^{\mathbb{R}}$ and $\tau\in W^{+}$ in some generalised Gross’s Wigner
representation $W$. Furthermore, let ${{\cal E}:{\cal B}({\cal
H}_{d})\mapsto{\cal B}({\cal H}_{d^{\prime}})}$ be a stochastically
represented channel. Then the $\alpha$-Rényi divergence
$D_{\alpha}(\cdot||\cdot)$ is well-defined and satisfies the following
properties for $\alpha\in{\cal A}$:

  1. 1.

$D_{\alpha}(W_{\rho}||W_{\tau})\geq 0$.

  2. 2.

$D_{\alpha}(W_{\rho}||W_{\tau})=0$ if and only if $\rho=\tau$.

  3. 3.

$D_{\alpha}(W_{\rho^{\otimes n}}||W_{\tau^{\otimes
n}})=nD_{\alpha}(W_{\rho}||W_{\tau})$ for all $n\in\mathbb{N}$.

  4. 4.

$D_{\alpha}(W_{\rho}||W_{\tau})\geq D_{\alpha}(W_{{\cal E}(\rho)}||W_{{\cal
E}(\tau)})$ for all stochastically represented ${\cal E}$ such that ${\cal
E}(\tau)\in{\cal W}^{+}$.

###### Proof.

In general, $W_{\rho}$ is a quasiprobability distribution, but for
$\alpha\in{\cal A}$ we see that $W_{\rho}({\bm{u}})^{\alpha}\geq 0$ for all
${\bm{u}}\in{\cal P}$. Therefore $D_{\alpha}(W_{\rho}||W_{\tau})$ is always
well-defined and real-valued. The proofs of 1-4 are then identical to the
proof given for Theorem 11 in Ref.[27]. ∎

Importantly for our purposes, this abstract but general result applies to
input and output systems of any (even or odd) finite dimension. With this in
hand, we can now give a proof of Theorem 5, which we restate for clarity:

See 5

###### Proof.

Since $\tau$ and $\tau^{\prime}$ are in the interior of ${\cal D}_{css}$, they
are positively represented. Moreover, we have established in Theorem 2 that
every trace-preserving and completely CSS-preserving operation is
stochasically represented. The results of Lemma 15 thus apply, from which
properties 3 and 4 combine to give the Lemma result. ∎

##  APPENDIX D ENTROPIC CONSTRAINTS ON CODE PROJECTION PROTOCOLS

###  D.1 Structure of the necessary conditions

We recall from Section V that if there exists an $n$-to-$k$ CSS code
projection that achieves the distillation ${\rho^{\otimes
n}\mapsto\rho^{\prime}}$ with acceptance probability $p$, then

$\displaystyle\Delta D_{\alpha}\geq 0$ (135)

for all $\alpha\in{\cal A}$, where

$\displaystyle\Delta
D_{\alpha}=nD_{\alpha}(W_{\rho}||W_{\frac{\mathbbm{1}}{2}})-D_{\alpha}\left(W_{\rho_{p}}\,||\,W_{\tau_{n,k}}\right).$
(136)

We recall the following output states from the system and reference processes,

$\displaystyle\rho_{p}$ $\displaystyle\coloneqq
p\rho^{\prime}\otimes\outerproduct{0}{0}+(1-p)\sigma\otimes\outerproduct{1}{1}\text{
and }$ (137) $\displaystyle\tau_{n,k}$ $\displaystyle\coloneqq
2^{k-n}\frac{\mathbbm{1}^{\otimes
k}}{2^{k}}\otimes\outerproduct{0}{0}+(1-2^{k-n})\sigma\otimes\outerproduct{1}{1},$
(138)

where $\sigma$ is the CSS state prepared after a failed run.

We now prove the following lemma, which enables us to simplify the expression
of our constraint functions $\Delta D_{\alpha}$. To this end, we will find it
useful to first introduce the general mean $Q_{\alpha}({\bm{w}}||{\bm{r}})$ on
a quasiprobabilty distribution ${{\bm{w}}\coloneqq(w_{1},\dots w_{N})^{T}}$
and probability distribution ${{\bm{r}}\coloneqq(r_{1},\dots r_{N})^{T}}$,

$\displaystyle Q_{\alpha}({\bm{w}}||{\bm{r}})\coloneqq
2^{(\alpha-1)D_{\alpha}({\bm{w}}||{\bm{r}})}=\sum_{i=1}^{N}w_{i}^{\alpha}r_{i}^{1-\alpha}.$
(139)

######  Lemma 16.

Consider the following pairs of $k$-rebit states $(\rho_{0},\rho_{1})$ and
$(\tau_{0},\tau_{1})\in\mathrm{Int}({\cal D}_{css})$. Moreover let $\psi_{0}$
and $\psi_{1}$ be two distinct computational basis states on $m$ rebits, and
let $\\{p_{i}\\}_{i=0}^{1}$, $\\{q_{i}\\}_{i=0}^{1}$ be valid probability
distributions. We then have the identity

$\displaystyle Q_{\alpha}(W_{\sum_{i}p_{i}\rho_{i}\otimes\psi_{i}}||$
$\displaystyle W_{\sum_{i}q_{i}\tau_{i}\otimes\psi_{i}})=$
$\displaystyle\sum_{i\in\\{0,1\\}}p_{i}^{\alpha}q_{i}^{1-\alpha}Q_{\alpha}(W_{\rho_{i}}||W_{\tau_{i}}),$
(140)

which in turn implies the inequality

$\displaystyle Q_{\alpha}(W_{\sum_{i}p_{i}\rho_{i}\otimes\psi_{i}}||$
$\displaystyle W_{\sum_{i}q_{i}\tau_{i}\otimes\psi_{i}})\geq$ $\displaystyle
p_{i}^{\alpha}q_{i}^{1-\alpha}Q_{\alpha}(W_{\rho_{i}}||W_{\tau_{i}}),$ (141)

for each $i\in\\{0,1\\}$.

###### Proof.

Since $\psi_{0}$ and $\psi_{1}$ are orthogonal, by Eq. (A.1) this implies

$\mathrm{tr}[\psi_{0}\psi_{1}]=2^{m}\sum_{{\bm{u}}\in{\cal
P}_{m}}W_{\psi_{0}}({\bm{u}})W_{\psi_{1}}({\bm{u}})=0.$ (142)

As $\psi_{i}\in{\cal D}_{css}$ for each $i\in\\{0,1\\}$, we must have
$W_{\psi_{i}}({\bm{u}})\geq 0$. We thus conclude from Eq. (142) that

$\displaystyle V_{0}$
$\displaystyle\coloneqq\operatorname{supp}(W_{\psi_{0}})\subseteq\ker(W_{\psi_{1}}),$
(143) $\displaystyle V_{1}$
$\displaystyle\coloneqq\operatorname{supp}(W_{\psi_{1}})\subseteq\ker(W_{\psi_{0}}).$
(144)

With this in hand, we can explicitly evaluate:

$\displaystyle
Q_{\alpha}(W_{\sum_{i}p_{i}\rho_{i}\otimes\psi_{i}}||W_{\sum_{i}q_{i}\tau_{i}\otimes\psi_{i}})=$
$\displaystyle\sum_{i\in\\{0,1\\}}\sum_{{\bm{u}}\in{\cal
P}_{k}}\sum_{{\bm{v}}\in
V_{i}}\left(p_{i}W_{\rho_{i}}({\bm{u}})W_{\psi_{i}}({\bm{v}})\right)^{\alpha}\left(q_{i}W_{\tau_{i}}({\bm{u}})W_{\psi_{i}}({\bm{v}})\right)^{1-\alpha}$
$\displaystyle=\sum_{i\in\\{0,1\\}}p_{i}^{\alpha}q_{i}^{1-\alpha}\sum_{{\bm{u}}\in{\cal
P}_{k}}W_{\rho_{i}}({\bm{u}})^{\alpha}W_{\tau_{i}}({\bm{u}})^{1-\alpha}$
$\displaystyle=\sum_{i\in\\{0,1\\}}p_{i}^{\alpha}q_{i}^{1-\alpha}Q_{\alpha}(W_{\rho_{i}}||W_{\tau_{i}}),$
(145)

where in the second equality we used the normalisation of our chosen
representation $W$. The inequality in the Lemma statement then follows from
the fact that both terms on the right hand side of Eq. (140) must be non-
negative for all $\alpha\in{\cal A}$.∎

With this property in hand, we obtain the following Lemma, which makes the
non-trivial $n$-dependence in $\Delta D_{\alpha}$ more explicit.

######  Lemma 17.

Let $\mu_{k}$ denote the maximally mixed state on $k$ qubits. The function
$\Delta D_{\alpha}$ can then be expressed as

$\displaystyle\Delta
D_{\alpha}=n\left(1-H_{\alpha}[W_{\rho}]\right)+k-\frac{1}{\alpha-1}\log\left[p^{\alpha}Q_{\alpha}\left(W_{\rho^{\prime}}||W_{\mu_{k}}\right)+(1-p)^{\alpha}\left(\frac{1}{2^{n-k}-1}\right)^{\alpha-1}\right],$
(146)

###### Proof.

By Lemma 16, we have the expansion

$\displaystyle Q_{\alpha}\left(W_{\rho_{p}}\,||\,W_{\tau_{n,k}}\right)$
$\displaystyle=p^{\alpha}\left(2^{k-n}\right)^{1-\alpha}Q_{\alpha}\left(W_{\rho^{\prime}}\,||\,W_{\mu_{k}}\right)+(1-p)^{\alpha}\left(1-2^{k-n}\right)^{1-\alpha}Q_{\alpha}\left(W_{\sigma}\,||\,W_{\sigma}\right)$
$\displaystyle=\left(2^{n-k}\right)^{\alpha-1}\left[p^{\alpha}Q_{\alpha}\left(W_{\rho^{\prime}}||W_{\mu_{k}}\right)+(1-p)^{\alpha}\left(\frac{1}{2^{n-k}-1}\right)^{\alpha-1}\right],$
(147)

where in the last equality we have used $Q_{\alpha}({\bm{p}}||{\bm{p}})=1$ for
all probability distributions ${\bm{p}}$. Therefore,

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

Substituting Eq. (148) and
$D_{\alpha}\left(W_{\rho}\Big{|}\Big{|}W_{\frac{\mathbbm{1}}{2}}\right)=2-H_{\alpha}[W_{\rho}]$
into Eq. (136) gives the result as claimed. ∎

###  D.2 Constraints are independent of the choice of CSS state $\sigma$
prepared on failed code projection

By inspection, the form for $\Delta D_{\alpha}$ given in Lemma 17 has no
$\sigma$-dependence, which implies

######  Corollary 4.

The entropic constraints $\Delta D_{\alpha}\geq 0$ on $n$-to-$k$ CSS code
projection protocols are independent of which CSS state $\sigma$ is prepared
following failed runs.

This result also follows from resource-theoretic arguments. Consider a CSS
circuit ${\cal E}$ on $k+1$ qubits that performs a $Z$-basis measurement on
the last qubit and re-prepares the first $k$ qubits in a CSS state $\omega$
conditioned upon the $-1$ outcome. Thus one can write

$\displaystyle{\cal E}_{\omega}(\cdot)\coloneqq\mathcal{I}\otimes
P_{0}(\cdot)+\omega\mathrm{tr}\otimes P_{1}(\cdot),$ (149)

where $P_{k}(\cdot)\coloneqq\outerproduct{k}{k}(\cdot)\outerproduct{k}{k}$,
from which one straightforwardly verifies that ${\cal E}_{\omega}(\rho_{p})$
and ${\cal E}_{\omega}(\tau_{n,k})$ simply replaces $\sigma$ in $\rho_{p}$ and
$\tau_{n,k}$ respectively by $\omega$. Since ${\cal E}$ is stochastically
represented, given any $\omega$ in the interior of ${\cal D}_{css}$, we have
by Property 4 in Lemma 15 that

$\displaystyle D_{\alpha}\left(W_{\rho_{p}}||W_{\tau_{n,k}}\right)$
$\displaystyle\geq D_{\alpha}\left(W_{{\cal E}_{\omega}[\rho_{p}]}||W_{{\cal
E}_{\omega}[\tau_{n,k}]}\right)$ $\displaystyle
D_{\alpha}\left(W_{\rho_{p}}||W_{\tau_{n,k}}\right)$ $\displaystyle\geq
D_{\alpha}\left(W_{{\cal E}_{\sigma}\circ{\cal
E}_{\omega}[\rho_{p}]}||W_{{\cal E}_{\sigma}\circ{\cal
E}_{\omega}[\tau_{n,k}]}\right)$
$\displaystyle=D_{\alpha}\left(W_{\rho_{p}}||W_{\tau_{n,k}}\right).$ (150)

We therefore conclude that

$\displaystyle D_{\alpha}\left({\cal E}_{\omega}(W_{\rho_{p}})||{\cal
E}_{\omega}(W_{\tau_{n,k}})\right)=D_{\alpha}\left(W_{\rho_{p}}||W_{\tau_{n,k}}\right),$
(151)

so the entropic constraints on CSS code projections are unaffected by varying
$\sigma$ in the interior of ${\cal D}_{css}$.

###  D.3 Proof of Lemma 7

We now prove the following properties of the constraint function $\Delta
D_{\alpha}$ from the main text: See 7

###### Proof.

Let us denote the maximally mixed state on $k$ qubits by $\mu_{k}$. We further
simplify notation by defining the constants $c_{1}\coloneqq
p^{\alpha}Q_{\alpha}(W_{\rho^{\prime}}||W_{\mu_{k}})$ and
${c_{2}\coloneqq(1-p)^{\alpha}}$.

Proof of (i): Let us define the following function

$\displaystyle
g(n)\coloneqq\left[c_{1}+c_{2}\left(\frac{1}{2^{n-k}-1}\right)^{\alpha-1}\right].$
(152)

This means that from Lemma 17 we can write

$\Delta
D_{\alpha}=n\left(1-H_{\alpha}[W_{\rho}]\right)+k-\frac{1}{\alpha-1}\log
g(n),$ (153)

and since the first term is linear we need only check the second derivative of
the second term to establish that $\Delta D_{\alpha}$ is concave. We have

$\displaystyle\partial_{n}^{2}\Delta
D_{\alpha}=-\frac{1}{\alpha-1}\partial_{n}^{2}\log g(n)=$ (154)
$\displaystyle-\frac{\ln
2\,c_{2}2^{k+n}\left(c_{1}\left(2^{k}+(\alpha-1)2^{n}\right)\left(2^{n-k}-1\right)^{\alpha}+c_{2}\left(2^{n}-2^{k}\right)\right)}{\left(2^{n}-2^{k}\right)\left(c_{1}2^{k}\left(2^{n-k}-1\right)^{\alpha}+c_{2}\left(2^{n}-2^{k}\right)\right)^{2}}.$

Since $c_{1},c_{2}\geq 0$ for all $\rho^{\prime}$ and $p$, the term in square
brackets is non-negative for all $n>k,\alpha>1,\rho^{\prime}$ and $p$
(strictly positive for $p<1$), which implies $\partial_{n}^{2}\Delta
D_{\alpha}$ is non-positive everywhere on our restricted domain. Therefore
$\Delta D_{\alpha}$ is concave, as claimed.

Proof of (ii): Recalling that $\alpha>1$, we have from Lemma 17 that

$\displaystyle\lim_{n\rightarrow k^{+}}\Delta D_{\alpha}$
$\displaystyle=-kH_{\alpha}[W_{\rho^{\prime}}]-$
$\displaystyle\frac{1}{\alpha-1}$ $\displaystyle\lim_{n\rightarrow
k^{+}}\left\\{\log\left[c_{1}+c_{2}\left(\frac{1}{2^{n-k}-1}\right)^{\alpha-1}\right]\right\\}$
$\displaystyle=-\infty<0,$ (155)

so long as $c_{2}>1$, which is true if and only if $p<1$.

Proof of (iii): We have:

$\displaystyle\lim_{n\rightarrow\infty}\Delta D_{\alpha}$
$\displaystyle=k-\frac{1}{\alpha-1}\log[c_{1}]+\lim_{n\rightarrow\infty}\left\\{n\left(1-H_{\alpha}[W_{\rho}]\right)\right\\}$
$\displaystyle=H_{\alpha}[W_{p\rho^{\prime}}]-k+\lim_{n\rightarrow\infty}\left\\{n\left(1-H_{\alpha}[W_{\rho}]\right)\right\\}$
$\displaystyle=\begin{cases}-\infty,&H_{\alpha}[W_{\rho}]>1,\\\
+\infty,&H_{\alpha}[W_{\rho}]<1,\\\
H_{\alpha}[W_{p\rho^{\prime}}]-k,&\mathrm{otherwise}.\end{cases}$ (156)

Therefore, if $H_{\alpha}[W_{\rho}]>1$ then $\lim_{n\rightarrow\infty}\Delta
D_{\alpha}<0$, as claimed.

This completes the proof.∎

###  D.4 Analytic bounds on code length in qudit code projection protocols

In this section, we consider $[[n,k]]$ stabilizer code projections for quantum
systems of arbitrary Hilbert space dimension $d$, which are stochastic under
some generalised Gross’s Wigner representation.

Following Eq. (37), we can define the following trace-preserving projection
${\cal E}$ on a $[[n,k]]$ stabilizer code ${\cal{C}}$ for $d$-dimensional
quantum systems,

$\displaystyle{\cal E}(\cdot)\coloneqq\mathrm{tr}_{k+1,\dots,n}\left[{\cal
U}\circ{\cal P}(\cdot)\right]\otimes$ $\displaystyle\outerproduct{0}{0}+$
$\displaystyle\mathrm{tr}[\overline{{\cal
P}}(\cdot)]\sigma\otimes\outerproduct{1}{1},$ (157)

where ${\cal U}$ and ${\cal P}$ are respectively the decoding channel and
codespace projection for ${\cal{C}}$, $\overline{{\cal P}}$ is the projection
onto the orthogonal complement of ${\cal{C}}$, and $\sigma$ is positively
represented under some generalised Gross’s Wigner representation of our
choice. This channel transforms $n$ copies of an input noisy magic state
$\rho$ as

$\displaystyle{\cal E}\left[\rho^{\otimes
n}\right]=p\rho^{\prime}\otimes\outerproduct{0}{0}+(1-p)\sigma\otimes\outerproduct{1}{1}\eqqcolon\rho_{p},$
(158)

where we assume the output state $\rho^{\prime}$ following successful code
projection is $\delta$-close to $k$ copies of our pure target magic state
$\psi$, as measured by the trace distance $\norm{\rho-\sigma}_{1}$ where
$\norm{X}_{1}\coloneqq\mathrm{tr}\absolutevalue{X}=\mathrm{tr}\sqrt{X^{\dagger}X}$
is the trace norm (also known as the Schatten-1 norm). Formally, we assume

$\norm{\rho^{\prime}-\psi^{\otimes k}}_{1}\leq\delta<\norm{\rho-\psi}_{1}.$
(159)

We also define the Frobenius norm (also known as the Schatten-2 norm) as

$\displaystyle\norm{X}_{2}\coloneqq\sqrt{\mathrm{tr}[X^{\dagger}X]}.$

We further define the $\ell_{1}$\- and $\ell_{2}$-norms, respectively, of a
vector ${\bm{w}}\in\mathbb{R}^{d}$ as

$\displaystyle\norm{{\bm{w}}}_{1}$
$\displaystyle\coloneqq\sum_{i=1}^{d}\absolutevalue{w_{i}},$ (160)
$\displaystyle\norm{{\bm{w}}}_{2}$
$\displaystyle\coloneqq\left[\sum_{i=1}^{d}\absolutevalue{w_{i}}^{2}\right]^{\frac{1}{2}}.$
(161)

We now make use of the following result from the literature on real vector
spaces (e.g. see [77]), which is a consequence of the Cauchy-Schwarz
inequality.

######  Lemma 18.

For all ${\bm{w}}\in\mathbb{R}^{d}$