# Polarization of quantum channels using Clifford-based channel combining

Frederic Dupuis, Ashutosh Goswami, Mehdi Mhalla, Valentin Savin

► To cite this version:

Frederic Dupuis, Ashutosh Goswami, Mehdi Mhalla, Valentin Savin. Polarization of quantum channels using Clifford-based channel combining. IEEE Transactions on Information Theory, 2021, 67 (5), pp.2857-2877. 10.1109/TIT.2021.3063093. cea-04940876

HAL Id: cea-04940876

https://cea.hal.science/cea-04940876v1

Submitted on 2 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Polarization of Quantum Channels using Clifford-based Channel Combining

Frédéric Dupuis, Ashutosh Goswami, Mehdi Mhalla, Valentin Savin

## Abstract

We provide a purely quantum version of polar codes, achieving the symmetric coherent information of any qubit-input quantum channel. Our scheme relies on a recursive channel combining and splitting construction, where a two-qubit gate randomly chosen from the Clifford group is used to combine two single-qubit channels. The inputs to the synthesized bad channels are frozen by preshared EPR pairs between the sender and the receiver, so our scheme is entanglement assisted. We further show that quantum polarization can be achieved by choosing the channel combining Clifford operator randomly, from a much smaller subset of only nine two-qubit Clifford gates. Subsequently, we show that a Pauli channel polarizes if and only if a specific classical channel over a four-symbol input set polarizes. We exploit this equivalence to prove fast polarization for Pauli channels, and to devise an efficient successive cancellation based decoding algorithm for such channels. Finally, we present a code construction based on chaining several quantum polar codes, which is shown to require a rate of preshared entanglement that vanishes asymptotically.

## 1 Introduction

Polar codes, proposed by Arikan [1], are the first explicit construction of a family of codes that provably achieve the channel capacity for any binary-input, symmetric, memoryless channel. His construction relies on a channel combining and splitting procedure, where a CNOT gate is used to combine two instances of the transmission channel. Applied recursively, this procedure allows synthesizing a set of so-called virtual channels from several instances of the transmission channel. When the code length goes to infinity, the synthesized channels tend to become either noiseless (good channels) or completely noisy (bad channels), a phenomenon which is known as "channel polarization". Channel polarization can effectively be exploited by transmitting messages via the good channels, while freezing the inputs to the bad channels to values known to both the encoder and decoder. This construction has been further generalized to classical channels with non-binary input alphabets in [19]. Moreover, polar codes have been generalized for the transmission of classical information over classical-quantum channels in [24], and for transmitting quantum information in [16, 25, 17]. It was shown in [16] that the recursive construction of polar codes using a CNOT polarizes in both amplitude and phase bases

<footnote>This work was supported in part by the "Investissements d'avenir" (ANR-15-IDEX-02) program of the French National Research Agency. Ashutosh Goswami acknowledges the European Union's Horizon 2020 research and innovation programme, under the Marie Skłodowska-Curie grant agreement No 754303.</footnote>

<footnote>Frédéric Dupuis was with Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France. He is currently with Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, Québec, Canada (dupuisf@iro.umontreal.ca).</footnote>

<footnote>Ashutosh Goswami is with Université Grenoble Alpes, Grenoble INP, LIG, F-38000 Grenoble, France (ashutosh-kumar.goswami@univ-grenoble-alpes.fr).</footnote>

<footnote>Mehdi Mhalla is with Université Grenoble Alpes, CNRS, Grenoble INP, LIG, F-38000 Grenoble, France (mehdi.mhalla@univ-grenoble-alpes.fr).</footnote>

<footnote>Valentin Savin is with Université Grenoble Alpes, CEA-LETI, F-38054 Grenoble, France (valentin.savin@cea.fr).</footnote>
for Pauli and erasure channels, and [17] extended this to general quantum channels. Then, a Calderbank-Shor-Steane (CSS)-like construction [6, 20] was used to generalize polar codes for transmitting quantum information. This construction requires a small number of EPR pairs to be shared between the sender and the receiver, in order to deal with virtual channels that are bad in both amplitude and phase bases, thus making the resulting code entanglement-assisted [4]. This construction was further refined in [21], where preshared entanglement is completely suppressed at the cost of a more complicated multilevel coding scheme, in which polar coding is employed separately at each level. However, all of these quantum channel coding schemes essentially exploit classical polarization, in either amplitude or phase basis.

In this paper, we give a purely quantum version of polar codes, i.e., a family of polar codes where the good channels are good as quantum channels, and not merely in one basis. Our construction uses a two-qubit gate chosen randomly from the Clifford group to combine two single-qubit channels, which bears similarities to the randomized channel combining/splitting operation proposed in [19], for the polarization of classical channels with non-binary input alphabets. We show that the synthesized quantum channels tend to become either noiseless or completely noisy as quantum channels, meaning that their symmetric coherent information<fnref n="1" /> tend to either +1 or -1. Similar to the classical case, information qubits are transmitted through good (almost noiseless) channels, while the inputs to the bad (noisy) channels are “frozen” by sharing EPR pairs between the sender and the receiver. Thus, our scheme is entanglement assisted, for which the capacity is established in [3]. We show that the proposed scheme achieves a quantum communication rate equal to half the symmetric mutual information of the quantum channel. The achieved net rate, defined as the quantum communication rate less the entanglement consumption rate, is equal to the symmetric coherent information of the quantum channel. Further, we show that polarization can be achieved while reducing the set of two-qubit Clifford gates, used to randomize the channel combining operation, to a subset of nine Clifford gates only. We also present an efficient decoding algorithm for the proposed quantum polar codes for the particular case of Pauli channels. To a Pauli channel, we associate a classical symmetric channel, with both input and output alphabets given by the quotient of the 1-qubit Pauli group by its centralizer, and show that the former polarizes quantumly if and only if the latter polarizes classically. This equivalence provides an alternative proof of the quantum polarization for a Pauli channel and, more importantly, an effective way to decode the quantum polar code for such channels, by decoding its classical counterpart. Fast polarization properties [19, 2] are also proven for Pauli channels, by using techniques similar to those in [19]. Finally, we present a code construction based on chaining several quantum polar codes [5], which is shown to require a rate of preshared entanglement that vanishes asymptotically. We conclude by discussing some perspectives opened by the proposed construction, which we believe may complement or extend the classical CSS-based viewpoint.

## 2 Preliminaries

Here are some basic definitions that we will need to prove the quantum polarization. First, we recall standard definitions of EPR pair and Clifford group.

**Definition 1** (Einstein-Podolsky-Rosen (EPR) pair). An EPR pair on two qubit systems A, A' is the quantum state, $\Phi_{AA'} = |\Phi_{AA'}\rangle\langle\Phi_{AA'}|$, where,

$$|\Phi_{AA'}\rangle = \frac{|0_A 0_{A'}\rangle + |1_A 1_{A'}\rangle}{\sqrt{2}}.$$

<footnote n="1">¹Symmetric coherent (respectively, mutual) information refers the coherent (respectively, mutual) information of the quantum channel for a uniformly distributed input, as defined in Section 2.</footnote>
**Definition 2 (Clifford group).** Let $P_n$ be Pauli group on $n$ qubits. The Clifford group $C_n$ on $n$ qubits is the group of unitary transformations that take $P_n$ to $P_n$ via conjugation. Precisely,

$$C_n := \{U \in U(2^n) \mid U\sigma U^\dagger \in P_n, \forall \sigma \in P_n\} / U(1),$$

where global phase factors are ignored, since $U$ and $e^{i\varphi}U$ act in the same way.

We will need the conditional sandwiched Rényi entropy of order 2, as defined by Renner [18], and the conditional Petz-Rényi entropy of order $\frac{1}{2}$.

**Definition 3 (Conditional sandwiched Rényi entropy of order 2).** Let $\rho_{AB}$ be a quantum state. Then,

$$\tilde{H}_2^\downarrow(A|B)_\rho := -\log \mathrm{Tr} \left[ \rho_B^{-\frac{1}{2}} \rho_{AB} \rho_B^{-\frac{1}{2}} \rho_{AB} \right],$$

where $\rho_B := \mathrm{Tr}_A(\rho_{AB})$ is the quantum state obtained by tracing out the $A$ system.

**Definition 4 (Petz-Rényi entropy of order $\frac{1}{2}$).** Let $\rho_{AB}$ be a quantum state. Then,

$$H_{\frac{1}{2}}^{\uparrow}(A|B)_{\rho} := 2 \log \sup_{\sigma_B} \mathrm{Tr} \left[ \rho_{AB}^{\frac{1}{2}} \sigma_B^{\frac{1}{2}} \right],$$

where the supremum is taken over all quantum states $\sigma_B$.

As shown in [23, Theorem 2], those two quantities satisfy a duality relation: given a pure tripartite state $\rho_{ABE}$, $\tilde{H}_2^\downarrow(A|B)_\rho = -H_{\frac{1}{2}}^\uparrow(A|E)_\rho$.

Throughout this work, we shall consider quantum channels $N_{A' \to B}$, with qubit input system $A'$ and output system $B$ of arbitrary dimension. When no confusion is possible, we shall discard the channel input and output systems from the notation. We will also need the symmetric coherent information of a quantum channel, and the concept of complementary channel.

**Definition 5 (Symmetric coherent information).** Let $N_{A' \to B}$ be a channel with qubit input $A'$ and output $B$ of arbitrary dimension. The symmetric coherent information of $N$ is defined as the coherent information of the channel for a uniformly distributed input, that is

$$I(\mathcal{N}) := -H(A|B)_{\mathcal{N}(\Phi_{A'A})} \in [-1, 1],$$

where $H(A|B)_{\rho_{AB}} := H(\rho_{AB}) - H(\rho_B)$, with $H(\sigma)$ being the Von Neumann entropy of a density matrix $\sigma$ and $\rho_B := \mathrm{Tr}_A(\rho_{AB})$, and $\mathcal{N}(\Phi_{A'A}) := (\mathcal{N} \otimes I_A)(\Phi_{A'A})$ is the quantum state on the AB system obtained by applying $\mathcal{N}$ on the $A'$-half of the EPR pair $\Phi_{A'A}$.

**Definition 6 (Complementary channel).** Let $N_{A' \to B}$ be a channel with qubit input $A'$ and output $B$ of arbitrary dimension, and let $U_{A' \to BE}$ be a Stinespring dilation of $\mathcal{N}$ (i.e. a partial isometry such that $\mathcal{N}(\cdot) = \mathrm{Tr}_E[U(\cdot)U^\dagger]$). The complementary channel of $\mathcal{N}$ is then $N_{A' \to E}^c$, which is given by $\mathcal{N}^c(\cdot) := \mathrm{Tr}_B[U(\cdot)U^\dagger]$.

Technically, Definition 6 depends on the choice of the Stinespring dilation, so the complementary channel is only unique up to an isometry on the output system. However, this will not matter for any of what we do here.

Finally, we need the following lemma, providing necessary conditions for the convergence of a stochastic process. The lemma below is a slightly modified version of [19, Lemma 2], so as to meet our specific needs. The proof is omitted, since it is essentially the same as the one in loc. cit. (see also [19, Remark 1]).
**Lemma 7** ([19, Lemma 2]). Suppose $B_i$, $i = 1, 2, \dots$ are independent and identically distributed (i.i.d.), $\{0, 1\}$-valued random variables with $P(B_1 = 0) = P(B_1 = 1) = 1/2$, defined on a probability space $(\Omega, \mathcal{F}, P)$. Set $\mathcal{F}_0 = \{\phi, \Omega\}$ as the trivial $\sigma$-algebra and set $\mathcal{F}_n$, $n \ge 1$, to be the $\sigma$-field generated by $(B_1, \dots, B_n)$. Suppose further that two stochastic processes $\{I_n : n \ge 0\}$ and $\{T_n : n \ge 0\}$ are defined on this probability space with the following properties:

(i.1) $I_n$ takes values in $[\iota_0, \iota_1]$ and is measurable with respect to $\mathcal{F}_n$. That is, $I_0$ is a constant, and $I_n$ is a function of $B_1, \dots, B_n$.

(i.2) $\{(I_n, \mathcal{F}_n) : n \ge 0\}$ is a martingale.

(t.1) $T_n$ takes values in the interval $[\theta_0, \theta_1]$ and is measurable with respect to $\mathcal{F}_n$.

(t.2) $T_{n+1} \le f(T_n)$ when $B_{n+1} = 1$, for some continuous function $f : [\theta_0, \theta_1] \to [\theta_0, \theta_1]$, such that $f(\theta) < \theta, \forall \theta \in (\theta_0, \theta_1)$.

(i&t.1) For any $\epsilon > 0$ there exists $\delta > 0$, such that $I_n \in (\iota_0 + \epsilon, \iota_1 - \epsilon)$ implies $T_n \in (\theta_0 + \delta, \theta_1 - \delta)$.

Then, $I_\infty := \lim_{n \to \infty} I_n$ exists with probability 1, $I_\infty$ takes values in $\{\iota_0, \iota_1\}$, and $\mathbb{E}(I_\infty) := \iota_0 P(I_\infty = \iota_0) + \iota_1 P(I_\infty = \iota_1) = I_0$.

## 3 Purely Quantum Polarization

In this section, we introduce our purely quantum version of polar codes, which is based on the channel combining and splitting operations depicted in Fig. 1. For the channel combining operation (Fig. 1(a)), we consider a randomly chosen two-qubit Clifford unitary, to combine two independent copies of a quantum channel $W$. The combined channel is then split, with the corresponding bad and good channels shown in Fig. 1(b) and Fig. 1(c), respectively. In other words, the bad channel $W \otimes_C W$ is a channel from $U_1$ to $Y_1Y_2$ that acts as

$$ (W \otimes_C W)(\rho) = W^{\otimes 2} \left( C(\rho \otimes \frac{1}{2})C^{\dagger} \right). $$

Likewise, the good channel $W \otimes_C W$ is a channel from $U_2$ to $R_1Y_1Y_2$ that acts as

$$ (W \otimes_C W)(\rho) = W^{\otimes 2} \left( C(\Phi_{R_1 U_1} \otimes \rho)C^{\dagger} \right), $$

where $\Phi_{R_1 U_1}$ is an EPR pair.

The polarization construction is obtained by recursively applying the above channel combining and splitting operations. Let us denote $W_C^{(0)} := W \otimes_C W$, $W_C^{(1)} := W \otimes_C W$, where index

<figure><img src="image_2.png" /><figcaption>Figure 1: Channel combining and splitting. (a) Combined channel: $C$ is a two-qubit Clifford unitary chosen at random. (b) Bad channel: we input a totally mixed state into the second input. (c) Good channel: we input half of an EPR pair into the first input, and the other half becomes the output $R_1$.</figcaption></figure>
C in the above notation indicates the Clifford unitary used for the channel combining operation. To accommodate a random choice of C, a classical description of C must be included as part of the output of the bad/good channels at each step of the transformation. To do so, for $i_1 = 0, 1$, we define

$$W^{(i_1)}(\rho) = \frac{1}{|C_2|} \sum_{C \in C_2} |C\rangle\langle C| \otimes W_C^{(i_1)}(\rho), \quad (1)$$

where $C_2$ denotes the Clifford group on two qubits, $|C_2| = 11520$ [14], and $\{|C\rangle\}_{C \in C_2}$ denotes an orthogonal basis of some auxiliary system. Put differently, $W^{(i_1)}$ is the classical equiprobable mixture of quantum channels $\{W_C^{(i_1)} | C \in C_2\}$. It has qubit input system (namely, $U_1$ if $i_1 = 0$, or $U_2$ if $i_1 = 1$), and composite output system consisting of the above auxiliary system and the output system of the $W_C^{(i_1)}$ channels (namely, $Y_1Y_2$ if $i_1 = 0$, or $R_1Y_1Y_2$ if $i_1 = 1$).

Now, applying twice the operation $W \mapsto (W^{(0)}, W^{(1)})$, we get channels $W^{(i_1 i_2)} := (W^{(i_1)})^{(i_2)}$, where $(i_1 i_2) \in \{00, 01, 10, 11\}$. In general, after $n$ levels of recursion, we obtain $2^n$ channels<fnref n="2" />:

$$W^{(i_1 \cdots i_n)} := (W^{(i_1 \cdots i_{n-1})})^{(i_n)}, \quad (i_1 \cdots i_n) \in \{0, 1\}^n. \qquad (2)$$

Since channels $W^{(i_1 \cdots i_n)}$ have qubit input system (and composite output system), it follows from Definition 5 that their symmetric coherent information $I(W^{(i_1 \cdots i_n)}) \in [-1, +1]$ (see also Lemma 8 below). Our main theorem below states that as $n$ goes to infinity, the symmetric coherent information of the synthesized channels $W^{(i_1 \cdots i_n)}$ polarizes, meaning that it goes to either $-1$ or $+1$, except possibly for a vanishing fraction of channels. To prove the polarization theorem, we will utilize Lemma 7. This basically requires us to find two quantities $I$ and $T$ that respectively play the roles of the symmetric mutual information of the channel and of the Bhattacharyya parameter from the classical case.

As mentioned above, for $I$ we shall consider the symmetric coherent information of the quantum channel. For $T$, we will need to be slightly more creative. Any choice (not necessarily unique) of $T$ would be convenient, as long as $I$ and $T$ satisfy the conditions in Lemma 7. For any channel $N_{A' \to B}$, let us define $R(N) \in [\frac{1}{2}, 2]$ as

$$R(N) := 2^{\frac{H_1}{2}(A|B)N(\Phi_{AA'})} = 2^{-\tilde{H}_2(A|E)N(\Phi_{AA'})}. \qquad (3)$$

This quantity will be our $T$ and we will call it the “Rényi-Bhattacharyya” parameter. We can see from the expression of $H_1$ that this indeed looks vaguely like the Bhattacharyya parameter; however we will work mostly with the second form involving the complementary channel as this will be more mathematically convenient for us.

Before stating the main theorem, we first provide the following lemma on the symmetric coherent information $I$ and the Rényi-Bhattacharyya parameter $R$ of a classical mixture of quantum channels. It will allow us to derive the main steps in the proof of the polarization theorem, by conveniently working with the $W_C^{(0)}(\rho)/W_C^{(1)}(\rho)$ construction, rather than the $W^{(0)}(\rho)/W^{(1)}(\rho)$ mixture (in which a classical description of $C$ is included in the output). The proof is omitted, since part (a) is trivial, and (b) follows easily from [13, Section B.2].

**Lemma 8.** Let $N(\rho) = \sum_{x \in X} \lambda_x |x\rangle\langle x| \otimes N_x(\rho)$, be a classical mixture of quantum channels $N_x$, where $\{|x\rangle\}_{x \in X}$ is some orthonormal basis of an auxiliary system, and $\lambda_x \ge 0, \forall x \in X$, with $\sum_{x \in X} \lambda_x = 1$. Then,

<footnote n="2">²Throughout this paper, we shall use a string-like notation for binary vectors, e.g., $(i_1 \cdots i_n) \in \{0, 1\}^n$. In Section 5, binary strings $(i_1 \cdots i_n) \in \{0, 1, \dots, N-1\}$, where $N = 2^n$. This will be explicitly stated in the text, so as to avoid any possible confusion that might arise.</footnote>
$$
(a) I(\mathcal{N}) = \mathbb{E}_X I(\mathcal{N}_X) := \sum_{x \in X} \lambda_x I(\mathcal{N}_x).
$$

$$
(b) R(\mathcal{N}) = \mathbb{E}_X R(\mathcal{N}_x) := \sum_{x \in X} \lambda_x R(\mathcal{N}_x).
$$

We can now state the polarization theorem.

**Theorem 9.** For any qubit-input quantum channel $\mathcal{W}$, let $I(\mathcal{W})$ be its symmetric coherent information, and $\{\mathcal{W}^{(i_1 \cdots i_n)} : (i_1 \cdots i_n) \in \{0,1\}^n\}$ be the set of virtual channels defined in (2). Then, for any $\delta > 0$,

$$
\lim_{n \to \infty} \frac{\#\{(i_1 \cdots i_n) \in \{0,1\}^n : I(\mathcal{W}^{(i_1 \cdots i_n)}) \in (-1+\delta, 1-\delta)\}}{2^n} = 0,
$$

and furthermore,

$$
\lim_{n \to \infty} \frac{\# \{(i_1 \cdots i_n) \in \{0,1\}^n : I(\mathcal{W}^{(i_1 \cdots i_n)}) \ge 1 - \delta\}}{2^n} = \frac{I(\mathcal{W}) + 1}{2}.
$$

Proof. Let {$B_n : n \ge 1$} be a sequence of i.i.d., {0, 1}-valued random variables with $P(B_n = 0) = P(B_n = 1) = 1/2$, as in Lemma 7. Let {$I_n : n \ge 0$} and {$R_n : n \ge 0$} be the stochastic processes defined by $I_n := I(W^{(B_1 \cdots B_n)})$ and $R_n := R(W^{(B_1 \cdots B_n)})$. By convention, $W^{(\mathcal{Z})} := \mathcal{W}$, thus $I_0 = I(\mathcal{W})$ and $R_0 = R(\mathcal{W})$. We prove that all the conditions of Lemma 7 hold for $I_n$ and $T_n := R_n$.

(i.1) Straightforward (with $[\iota_0, \iota_1] = [-1, 1]$).

(i.2) We must show that $I_n$ forms a martingale. In other words, that the channel combining and splitting transformation does not change the total coherent information, i.e., $I(W^{(0)}) + I(W^{(1)}) = 2I(W)$. This follows from Lemma 10 below, and Lemma 8 (a).

(t.1) Straightforward (with $[\theta_0, \theta_1] = [\frac{1}{2}, 2]$).

(t.2) Here, we will show that $R_{n+1} = \frac{2}{5} + \frac{2}{5}R_n^2$, when $B_{n+1} = 1$. It is enough to prove it for $n=0$ (i.e., the first step of recursion), since in the general case the proof is obtained simply by replacing $\mathcal{W}$ with $\mathcal{W}^{(B_1 \cdots B_n)}$. First, by using Lemma 8 (b), and assuming $B_1 = 1$, we get $R_1 := R(\mathcal{W}^{(1)}) = \mathbb{E}_C R(\mathcal{W}_C^{(1)}) = \mathbb{E}_C R(\mathcal{W} \otimes_C \mathcal{W})$, where the last equality is simply a reminder of our notation $\mathcal{W}_C^{(1)} := \mathcal{W} \otimes_C \mathcal{W}$. We then prove that $\mathbb{E}_C R(\mathcal{W} \otimes_C \mathcal{W}) = \frac{2}{5} + \frac{2}{5}R(\mathcal{W})^2$. This is where most of the action happens, and the proof is in Lemma 11.

(i&t.1) For any $\varepsilon > 0$, there exists a $\delta > 0$ such that $I_n \in (-1 + \varepsilon, 1 - \varepsilon)$ implies that $R_n \in (\frac{1}{2} + \delta, 2 - \delta)$. In other words, we need to show that if $R$ polarizes, then so does $I$. This holds for any choice of the Clifford unitary in the channel combining operation, and is proven in Lemma 12.

By using Lemma 7, we conclude that $I_\infty := \lim_{n \to \infty} I_n$ exists with probability 1 and takes values in $\{-1, +1\}$, which implies the first limit, and $\mathbb{E}(I_\infty) := P(I_\infty = +1) - P(I_\infty = -1) = I(\mathcal{W})$, which implies the second limit (since also, $P(I_\infty = +1) + P(I_\infty = -1) = 1$). $\square$

We now proceed with the lemmas. The following lemmas are stated in slightly more gen-
eral settings, with the channel combining and splitting construction applied to two quantum
channels $\mathcal{N}$ and $\mathcal{M}$, rather than to two copies of the same quantum channel $\mathcal{W}$. More precisely,
the channels $\mathcal{N} \oplus_C \mathcal{M}$ and $\mathcal{N} \otimes_C \mathcal{M}$ are defined by using a similar construction to the one in
Fig. 1, while applying $\mathcal{N}$ on the first input (top), and $\mathcal{M}$ on the second input (bottom). Thus,
$(\mathcal{N} \oplus_C \mathcal{M})(\rho) = (\mathcal{N} \otimes \mathcal{M})(C(\rho \otimes \frac{1}{2})C^\dagger)$ and $(\mathcal{N} \otimes_C \mathcal{M})(\rho) = (\mathcal{N} \otimes \mathcal{M})(C(\Phi_{R_1 U_1} \otimes \rho)C^\dagger)$,
where $\Phi_{R_1 U_1}$ is an EPR pair.
**Lemma 10.** Given two channels $\mathcal{N}_{A'_1 \to B_1}$ and $\mathcal{M}_{A'_2 \to B_2}$ with qubit inputs, then

$$I(\mathcal{N} \otimes_C \mathcal{M}) + I(\mathcal{N} \oplus_C \mathcal{M}) = I(\mathcal{N}) + I(\mathcal{M}),$$

and this holds for all choices of $C$.

*Proof.* Consider the state $\rho = (\mathcal{N} \otimes \mathcal{M})(C(\Phi_{A_1 A'_1} \otimes \Phi_{A_2 A'_2})C^\dagger)$ on systems $A_1 A_2 B_1 B_2$. We have that $I(\mathcal{N} \oplus_C \mathcal{M}) = -H(A_1|B_1 B_2)_\rho$ and $I(\mathcal{N} \otimes_C \mathcal{M}) = -H(A_2|A_1 B_1 B_2)_\rho$. Therefore, by the chain rule,

$$I(\mathcal{N} \oplus_C \mathcal{M}) + I(\mathcal{N} \otimes_C \mathcal{M}) = -H(A_1|B_1 B_2)_\rho - H(A_2|A_1 B_1 B_2)_\rho \\ = -H(A_1 A_2|B_1 B_2)_\rho.$$

Now, recall that the EPR pair has the property that $(Z \otimes 1)|\Phi\rangle = (1 \otimes Z^\dagger)|\Phi\rangle$ for any matrix $Z$, where $Z^\dagger$ is the transpose of $Z$. Using this, we can move $C$ from the input systems $A'_1$ and $A'_2$ to the purifying systems $A_1 A_2$: $\rho = C^\dagger(\mathcal{N} \otimes \mathcal{M})(\Phi_{A_1 A'_1} \otimes \Phi_{A_2 A'_2})\bar{C}$, where $\bar{C}$ is the complex conjugate of $C$. Hence, we have

$$-H(A_1 A_2|B_1 B_2)_\rho = -H(A_1 A_2|B_1 B_2)_{(\mathcal{N} \otimes \mathcal{M})(\Phi)} \\ = -H(A_1|B_1)_{\mathcal{N}(\Phi)} - H(A_2|B_2)_{\mathcal{M}(\Phi)} \\ = I(\mathcal{N}) + I(\mathcal{M}),$$

which completes the proof.

<figure><img src="image_3.png" /></figure>

**Lemma 11.** Given two channels $\mathcal{N}_{A'_1 \to B_1}$ and $\mathcal{M}_{A'_2 \to B_2}$ with qubit inputs, then

$$\mathbb{E}_C R(\mathcal{N} \oplus_C \mathcal{M}) = \frac{2}{5} + \frac{2}{5} R(\mathcal{N}) R(\mathcal{M}),$$

where $C$ is the channel combining Clifford operator and is chosen uniformly at random over the Clifford group.

*Proof.* Let $\mathcal{N}_{A'_1 \to E_1}^c$ and $\mathcal{M}_{A'_2 \to E_2}^c$ be the complementary channels of $\mathcal{N}$ and $\mathcal{M}$ respectively. It can be shown that (see Lemma 28 in Appendix A)

$$(\mathcal{N} \oplus_C \mathcal{M})^c(\rho) = (\mathcal{N}^c \otimes \mathcal{M}^c) \left( C \left( \frac{1}{2} \otimes \rho \right) C^\dagger \right),$$

and therefore $R(\mathcal{N} \oplus_C \mathcal{M}) = 2^{-\tilde{H}_2^\dagger(A_2|E_1 E_2)_\rho}$, where $\rho_{A_2 E_1 E_2} = (\mathcal{N} \otimes \mathcal{M})^c(\Phi_{A_2 A'_2})$. Note that $\rho_{E_1 E_2} = \mathcal{N}^c(\frac{1}{2})_{E_1} \otimes \mathcal{M}^c(\frac{1}{2})_{E_2}$, which is independent of $C$. Now, to compute the expected value of this for a random choice of $C$, we proceed as follows:

$$\mathbb{E}_C 2^{-\tilde{H}_2^\dagger(A_2|E_1 E_2)_\rho} = \mathbb{E}_C \mathrm{Tr} \left[ \left( \rho_{E_1 E_2}^{-\frac{1}{4}} \rho_{A_2 E_1 E_2} \rho_{E_1 E_2}^{-\frac{1}{4}} \right)^2 \right] \\ = \mathbb{E}_C \mathrm{Tr} \left[ \left( \rho_{E_1 E_2}^{-\frac{1}{4}} (\mathcal{N}^c \otimes \mathcal{M}^c) \left( C \left( \frac{1}{2} \otimes \Phi_{A_2 A'_2} \right) C^\dagger \right) \rho_{E_1 E_2}^{-\frac{1}{4}} \right)^2 \right]$$

Now, note that this is basically the same calculation as in [7], at Equation (3.32) (there, $U$ is chosen according to the Haar measure over the full unitary group, but all that is required is a 2-design, and hence choosing a random Clifford yields the same result). However, since here we are dealing with small systems, we will not make the simplifications after (3.44) and (3.45) in [7] but will instead keep all the terms. We therefore get $\mathbb{E}_C 2^{-\tilde{H}_2^\dagger(A_2|E_1 E_2)_\rho} = \alpha \mathrm{Tr}[\pi_{A_2}^2] +$
$\beta \operatorname{Tr}[\pi_{A_1}^2 \otimes \Phi_{A_2 A_2'}] = \frac{1}{2}\alpha + \frac{1}{2}\beta$, where $\alpha = \frac{16}{15} - \frac{4}{15}2^{-\tilde{H}_2^\dagger(A_1 A_2 | E_1 E_2)\omega}$, $\beta = \frac{16}{15}2^{-\tilde{H}_2^\dagger(A_1 A_2 | E_1 E_2)\omega} - \frac{4}{15}$, and $\omega_{A_1 A_2 E_1 E_2} := (\mathcal{N}^c \otimes \mathcal{M}^c)(\Phi_{A_1 A_1'} \otimes \Phi_{A_2 A_2'})$. Hence,

$$
\begin{align*}
\mathbb{E}_C 2^{-\tilde{H}_2^\dagger(A_2 | E_1 E_2)\rho} &= \frac{6}{15} + \frac{6}{15} 2^{-\tilde{H}_2^\dagger(A_1 A_2 | E_1 E_2)\omega} \\
&= \frac{6}{15} + \frac{6}{15} 2^{-\tilde{H}_2^\dagger(A_1 | E_1)_{\mathcal{N}^c}(\Phi_{A_1 A_1'}) 2^{-\tilde{H}_2^\dagger(A_2 | E_2)_{\mathcal{M}^c}(\Phi_{A_2 A_2'})} \\
&= \frac{2}{5} + \frac{2}{5} R(\mathcal{N}) R(\mathcal{M}).
\end{align*}
$$

where we have used that the conditional sandwiched Rényi entropy of order 2 is additive with respect to tensor-product states, which follows easily from Definition 3. $\square$

**Lemma 12.** Let $\mathcal{N}_{A' \to B}$ be a channel with qubit input. Then,

$$1. R(\mathcal{N}) \le \frac{1}{2} + \delta \Rightarrow I(\mathcal{N}) \ge 1 - \log(1 + 2\delta).$$

$$2. R(\mathcal{N}) \ge 2 - \delta \Rightarrow I(\mathcal{N}) \le -1 + \sqrt{2\delta} + \left(1 + \sqrt{\delta/2}\right) h\left(\frac{\sqrt{\delta/2}}{1+\sqrt{\delta/2}}\right),$$

where $h(\cdot)$ denotes the binary entropy function.

*Proof.* We first prove point 1). Observe that for any state $\sigma_{AB}$, the inequality $H(A|B)_\sigma \le H_2^\dagger(A|B)_\sigma$ holds. Now, for $\rho_{AB} = \mathcal{N}(\Phi_{AA'})$, we have that

$$\frac{1}{2} + \delta \ge R(\mathcal{N}) = 2^{\frac{H_2^\dagger(A|B)_\rho}2} \ge 2^{H(A|B)_\rho} = 2^{-I(\mathcal{N})},$$

where we have used $H_2^\dagger(A|B)_\rho \ge H(A|B)_\rho$, which follows from the monotonically decreasing property of the conditional Petz-Rényi entropy with respect to its order [13, Theorem 7]. It follows that $I(\mathcal{N}) \ge 1 - \log(1 + 2\delta)$.

We now turn to the second point. We have that

$$
\begin{align*}
2 - \delta \le R(\mathcal{N}) &= \max_{\sigma_B} \operatorname{Tr} \left[ \rho_{AB}^{\frac{1}{2}} \sigma_B^{\frac{1}{2}} \right]^2 \\
&= 2 \max_{\sigma_B} \operatorname{Tr} \left[ \sqrt{\rho_{AB}} \sqrt{\frac{1_A}{2} \otimes \sigma_B} \right]^2 \\
&\le 2 \max_{\sigma_B} \left\| \sqrt{\rho_{AB}} \sqrt{\frac{1_A}{2} \otimes \sigma_B} \right\|_1^2 \\
&= 2 \max_{\sigma_B} F \left( \rho_{AB}, \frac{1_A}{2} \otimes \sigma_B \right)^2.
\end{align*}
$$

Now, using the Fuchs-van de Graaf inequalities [8], we get that there exists a $\sigma_B$ such that

$$\left\| \rho_{AB} - \frac{1_A}{2} \otimes \sigma_B \right\|_1 \le \sqrt{2\delta}.$$

We are now in a position to use the Alicki-Fannes-Winter [26, Lemma 2] inequality, which states that

$$|H(A|B)_\rho - 1| \le \sqrt{2\delta} + \left(1 + \sqrt{\delta/2}\right) h\left(\frac{\sqrt{\delta/2}}{1+\sqrt{\delta/2}}\right).$$

This concludes the proof of the lemma. $\square$
# 4 Quantum Polarization Using Only Nine Clifford Gates

In this section, we prove that quantum polarization can be achieved while reducing the set of two-qubit Clifford gates used to randomize the channel combining operation, to a subset of nine Clifford gates only. To do so, we need to find a subset of Clifford gates such that the condition (t.2) from Lemma 7 is still fulfilled.

Let $C_n$ be the Clifford group on $n$ qubits. Clearly $C_1 \otimes C_1$ is a subgroup of $C_2$, and we may define an equivalence relation on $C_2$, whose equivalence classes are the left cosets of $C_1 \otimes C_1$.

**Definition 13.** We say that $C'$ and $C'' \in C_2$ are equivalent, and denote it by $C' \sim C''$, if there exist $C_1, C_2 \in C_1$ such that $C'' = C'(C_1 \otimes C_2)$ (see also Fig. 2).

<figure><img src="image_4.png" /><figcaption>Figure 2: Equivalent two-qubit Clifford gates $C' \sim C''$</figcaption></figure>

Now, the main observation is that two equivalent Clifford gates used to combine any two quantum channels with qubit inputs, yield the same Rényi-Bhattacharyya parameter of the bad/good channels. This is stated in the following lemma, whose proof is provided in Appendix A.

**Lemma 14.** Let $C', C'' \in C_2$. If $C' \sim C''$, then for any two quantum channels $M$ and $N$ with qubit inputs, we have:

$$R(M \otimes_{C'} N) = R(M \otimes_{C''} N) \quad \text{and} \quad R(M \otimes_{C''} N) = R(M \otimes_{C'} N).$$

As a consequence, one may ensure polarization while restricting the set of Clifford gates to any set of representatives of the equivalence classes of the above equivalence relation (since such a restriction will not affect the $E_C R(N \otimes_C M)$ value, for any two quantum channels $M$ and $N$ with qubit inputs). Since $|C_1| = 24$ and $|C_2| = 11520$, it follows that there are exactly $11520/(24 \times 24) = 20$ equivalence classes. A set of representatives of these 20 equivalence classes can be chosen as follows<fnref n="3" />:

* For two of these equivalence classes, one may choose the identity gate $I$ and swap gate $S$, as representatives.

* For nine out of the remaining 18 equivalence classes, one may find representatives of the form $(C_1 \otimes C_2)\text{CNOT}_{21}$, where $\text{CNOT}_{21}$ denotes the controlled-NOT gate with control on the second qubit and target on the first qubit, $C_1 \in \{I, \sqrt{Z}, \sqrt{Y}\}$, $C_2 \in \{I, \sqrt{X}, \sqrt{Y}\}$, and $\sqrt{P} = \frac{(1-i)(1+iP)}{2}$, for any Pauli matrix $P \in \{X, Y, Z\}$. We denote this set by $\mathcal{L}$, which is further depicted in Fig. 3.

$$\mathcal{L} := \{ (C_1 \otimes C_2)\text{CNOT}_{21} \mid C_1 \in \{I, \sqrt{Z}, \sqrt{Y}\}, C_2 \in \{I, \sqrt{X}, \sqrt{Y}\} \}.$$

* For the remaining nine equivalence classes, one may find representatives of the form $SL$, where $S$ is the swap gate and $L \in \mathcal{L}$. We denote this set by $\mathcal{R}$,

$$\mathcal{R} := \{SL \mid L \in \mathcal{L}\}.$$

<footnote n="3">³We used a computer program to determine such a set of representatives.</footnote>
<figure><img src="image_5.png" /><figcaption>Figure 3: The set $\mathcal{L} := \{L_{i,j} | 1 \le i, j \le 3\}$ containing nine Cliffords.</figcaption></figure>

Now, we prove that two Clifford gates $C'$ and $C''$, such that $C'' = SC'$, used to combine two copies of a quantum channel $W$ with qubit input, yield the same Rényi-Bhattacharyya parameter of the bad/good channels. Although this property is weaker than the one in Lemma 14, which holds for any two quantum channels $M$ and $N$, it is sufficient for whatever we need here.

**Lemma 15.** Let $C', C'' \in C_2$, such that $C'' = SC'$, where $S$ is the swap gate. Then, for two copies of a quantum channel $W$ with qubit input,

$$R(W \otimes_{C'} W) = R(W \otimes_{C''} W) \quad \text{and} \quad R(W \otimes_{C'} W) = R(W \otimes_{C''} W).$$

*Proof.* First, we note that by applying a unitary on the output of any quantum channel does not change the Rényi-Bhattacharyya parameter. Precisely, let $N_{A \to B}$ be any quantum channel, and $UN_{A \to B}U^\dagger$ be the quantum channel$^4$ obtained by applying the unitary $U$ on the output system $B$, that is, $(UN_{A \to B}U^\dagger)(\rho_A) := UN_{A \to B}(\rho_A)U^\dagger$. Then,

$$R(UN_{A \to B}U^\dagger) = R(N_{A \to B}). \qquad (4)$$

Going back to the proof of our Lemma, by the definition of $W \otimes_C W$ and using that $S^\dagger = S$, we may write:

$$ \begin{aligned} (W \otimes_{C''} W)(\rho) &= (W \otimes W) \left(C''(\rho \otimes \frac{1}{2})C''^\dagger\right) \\ &= (W \otimes W) \left(SC'(\rho \otimes \frac{1}{2})C'^\dagger S\right). \end{aligned} $$

Now, it is easily seen that the $W \otimes W$ channel is covariant with respect to the swap gate, i.e., the swap gate commutes with the action of the channel. Hence we may further write:

$$ \begin{aligned} (W \otimes_{C''} W)(\rho) &= S(W \otimes W) \left(C'(\rho \otimes \frac{1}{2})C'^\dagger\right) S \\ &= S(W \otimes_{C'} W)(\rho)S \\ &= (S(W \otimes_{C'} W)S)(\rho). \end{aligned} $$

<footnote>$^4$To see that $UN_{A \to B}U^\dagger$ is a quantum channel, it is enough to notice that if $N_{A \to B}$ is defined by Kraus operators $\{E_k\}$, then $UN_{A \to B}U^\dagger$ is defined by Kraus operators $\{UE_kU^\dagger\}$.</footnote>
Hence, $W \otimes_{C''} W = S(W \otimes_{C'} W)S$, and using (4), with $\mathcal{N} := W \otimes_{C'} W$ and $U := S$, we get

$$R(W \otimes_{C'} W) = R(W \otimes_{C''} W),$$

as desired. The equality $R(W \otimes_{C'} W) = R(W \otimes_{C''} W)$ may be proven in a similar way. $\square$

The following lemma implies that polarization can be achieved by choosing the channel combining Clifford operator randomly from either $\mathcal{L}$ or $\mathcal{R}$. It is the analogue of the Lemma 11 used to check the (t.2) condition in the proof of the polarization Theorem 9.

**Lemma 16.** Given two copies of a quantum channel $W_{A'_1 \to B_1}$ with qubit input, we have

$$\mathbb{E}_{C \in \mathcal{L}} R(W \otimes_C W) = \mathbb{E}_{C \in \mathcal{R}} R(W \otimes_C W) = \frac{4}{9} - \frac{1}{9} R(W) + \frac{4}{9} R(W)^2,$$

where $C$ is the channel combining Clifford operator and is chosen uniformly either from the set $\mathcal{L}$ or from the set $\mathcal{R}$, each containing nine Clifford gates.

*Proof.* Since $S := \{I, S\} \cup \mathcal{L} \cup \mathcal{R}$ is a set of representatives of the 20 equivalence classes partitioning the Clifford group $C_2$, we have:

$$\mathbb{E}_{C \in S} R(W \otimes_C W) = \mathbb{E}_{C \in C_2} R(W \otimes_C W) = \frac{2}{5} + \frac{2}{5} R(W)^2,$$

where the first equality follows from Lemma 14, and the second from Lemma 11. Now, using Lemma 15, we have $R(W \otimes_S W) = R(W \otimes_I W) = R(W)$ and $\mathbb{E}_{C \in \mathcal{L}} R(W \otimes_C W) = \mathbb{E}_{C \in \mathcal{R}} R(W \otimes_C W)$. Hence,

$$\mathbb{E}_{C \in S} R(W \otimes_C W) = \frac{2R(W) + 9\mathbb{E}_{C \in \mathcal{L}} R(W \otimes_C W) + 9\mathbb{E}_{C \in \mathcal{R}} R(W \otimes_C W)}{20},$$

and therefore

$$\mathbb{E}_{C \in \mathcal{L}} R(W \otimes_C W) = \mathbb{E}_{C \in \mathcal{R}} R(W \otimes_C W) = \frac{4}{9} - \frac{1}{9} R(W) + \frac{4}{9} R(W)^2.$$

Finally, we also note that the above expected value is less than the one in Lemma 11, namely $\mathbb{E}_{C \in C_2} R(W \otimes_C W) = \frac{2}{5} + \frac{2}{5} R(W)^2$, since the expected value can only decrease by taking out the identity and swap gate from the set of representatives. $\square$

# 5 Quantum Polar Coding

## 5.1 Quantum Polar Codes

Polar coding is a coding method that takes advantage of the channel polarization phenomenon [1]. To construct a quantum polar code of length $N = 2^n, n > 0$, we start with $N$ copies of the quantum channel $W$, pair them in $N/2$ pairs, and apply the channel combining and splitting operation on each pair. The same channel combining Clifford gate is used for each of the $N/2$ pairs, which will be denoted by $C$. By doing so, we generate $N/2$ copies of the channel $W^{(0)} := W \otimes_C W$ and $N/2$ copies of the channel $W^{(1)} := W \otimes_C W$. Hence, for each $i_1 = 0, 1$, we group together the $N/2$ copies of the $W^{(i_1)}$ channel, pair them in $N/4$ pairs, and apply the channel combining and splitting operation on each pair, by using some channel combining Clifford gate denoted by $C_{i_1}$. By performing $n$ polarization steps (that is, applying the above construction recursively $n$ times), we generate quantum channels $W^{(i_1 \cdots i_n)}$, which can be recursively defined for $n > 0$, as follows:

$$W^{(i_1 \cdots i_n)} := \begin{cases} W^{(i_1 \cdots i_{n-1})} \otimes_{C_{i_1 \cdots i_{n-1}}} W^{(i_1 \cdots i_{n-1})}, & \text{if } i_n = 0 \\ W^{(i_1 \cdots i_{n-1})} \otimes_{C_{i_1 \cdots i_{n-1}}} W^{(i_1 \cdots i_{n-1})}, & \text{if } i_n = 1 \end{cases} \quad (5)$$
<figure><img src="image_6.png" /><figcaption>Figure 4: Quantum polar code of length $N = 8$</figcaption></figure>

where, for $n = 1$, in the right hand side term of the above equality, we set by convention $W^{(\emptyset)} := W$ and $C_{\emptyset} := C$. Note that, for the sake of simplicity, we have dropped the channel combining Clifford gate from the $W^{(i_1 \cdots i_n)}$ notation. The construction is illustrated in Fig. 4, for $N = 8$. Horizontal "wires" represent qubits, and for each polarization step, we have indicated on each wire the virtual channel $W^{(i_1 i_2 \cdots)}$ "seen" by the corresponding qubit state.

The above construction synthesizes a set of $N$ channels and, for any $i = 0, \dots, N-1$, we shall further denote $W^{(i)} := W^{(i_1 \cdots i_n)}$, where $i_1 \cdots i_n$ is the binary decomposition of $i$. Let $\mathcal{I} \subseteq \{0, 1, \dots, N-1\}$ denote the set of good channels (i.e., with coherent information close to 1, or equivalently, Rényi-Bhattacharyya parameter close to $1/2$), and let $\mathcal{J} := \{0, 1, \dots, N-1\} \setminus \mathcal{I}$. With a slight abuse of notation, we shall also denote by $\mathcal{I}$ and $\mathcal{J}$ two qudit systems, of dimension $2^{|\mathcal{I}|}$ and $2^{|\mathcal{J}|}$, respectively (it will be clear from the context whether the notation is meant to indicate a set of indices or a quantum system).

A quantum state $\rho_{\mathcal{I}}$ on system $\mathcal{I}$ is encoded by supplying it as input to channels $i \in \mathcal{I}$, while supplying each channel $j \in \mathcal{J}$ with half of an EPR pair, shared between the sender and the receiver. Precisely, let $\Phi_{\mathcal{J}\mathcal{J}'}$ be a maximally entangled state, defined by

$$ \Phi_{\mathcal{J}\mathcal{J}'} = \otimes_{j \in \mathcal{J}} \Phi_{jj'}, \qquad (6) $$

where indices $j$ and $j'$ indicate the $j$-th qubits of $\mathcal{J}$ and $\mathcal{J}'$ systems, respectively, and $\Phi_{jj'}$ is an EPR pair. Let also $G_q$ denote the quantum polar transform, that is the unitary operator defined by applying Clifford gates corresponding to the $n$ polarization steps. The encoded state, denoted $\varphi_{\mathcal{I}\mathcal{J}\mathcal{J}'}$, is obtained by applying the $G_q \otimes I_{\mathcal{J}'}$ unitary on the $\mathcal{I}\mathcal{J}\mathcal{J}'$ system, hence:

$$ \varphi_{\mathcal{I}\mathcal{J}\mathcal{J}'} := (G_q \otimes I_{\mathcal{J}'}) (\rho_{\mathcal{I}} \otimes \Phi_{\mathcal{I}\mathcal{J}\mathcal{J}'}) (G_q^\dagger \otimes I_{\mathcal{J}'}). \qquad (7) $$

Since no errors occur on the $\mathcal{J}'$ system, the channel output state is given by:

$$ \psi_{\mathcal{I}\mathcal{J}\mathcal{J}'} := (W^{\otimes N} \otimes I_{\mathcal{J}'}) (\varphi_{\mathcal{I}\mathcal{J}\mathcal{J}'}). \qquad (8) $$

It is worth noticing that randomness is used only at the code construction stage (since Clifford gates used in the $n$ polarization steps are randomly chosen from some predetermined set of gates), but not at the encoding stage. The constructed polar code allows communicating quantum information over a quantum channel $W$ at a rate $|\mathcal{I}|/N$, which approaches $(1 + I(W))/2$ (that is, half the symmetric mutual information of the channel), as $N$ goes to infinity. The net communication rate, which we define as the quantum communication rate less the entanglement consumption rate, is given by $((|\mathcal{I}| - |\mathcal{J}|)/N)$, and approaches $I(W)$, as $N$ goes to infinity.
## 5.2 Quantum Polar Codes as Entanglement-Assisted Stabilizer Codes

Including all information qubits ($\mathcal{I}$ system) and both systems of the preshared EPR pairs ($\mathcal{J}$ and $\mathcal{J}'$ systems), the quantum polar code from the above section can be described as an entanglement assisted stabilizer code, in the sense of [4]. Precisely, using the notation from the previous section, the quantum state $\rho_{\mathcal{I}} \otimes \Phi_{\mathcal{J}\mathcal{J}'}$ is stabilized by the set of Pauli operators

$$S_{\mathcal{I}\mathcal{J}\mathcal{J}'} := \{I_{\mathcal{I}} \otimes X_j X_{j'}, I_{\mathcal{I}} \otimes Z_j Z_{j'} \mid j \in \mathcal{J}\}, \quad (9)$$

where $I_{\mathcal{I}}$ denotes the identity on the $\mathcal{I}$ system, and $X_j X_{j'}$ (respectively, $Z_j Z_{j'}$) denotes the tensor product of the Pauli-$X$ (respectively, Pauli-$Z$) operators of the $j$-th qubits of systems $\mathcal{J}$ and $\mathcal{J}'$$^5$. Conversely, any quantum state on the tripartite $\mathcal{I}\mathcal{J}\mathcal{J}'$ system, which is stabilized by Pauli operators in $S_{\mathcal{I}\mathcal{J}\mathcal{J}'}$, is necessarily of the form $\rho_{\mathcal{I}} \otimes \Phi_{\mathcal{J}\mathcal{J}'}$ (by a dimension argument). Hence, encoded states ($\varphi_{\mathcal{I}\mathcal{J}\mathcal{J}'}$ defined in (7)) are stabilized by the set of Pauli operators obtained by passing the elements of $S_{\mathcal{I}\mathcal{J}\mathcal{J}'}$ through the polar transform $G_q$, that is,

$$\bar{S}_{\mathcal{I}\mathcal{J}\mathcal{J}'} := (G_q \otimes I_{\mathcal{J}'}) S_{\mathcal{I}\mathcal{J}\mathcal{J}'} (G_q^\dagger \otimes I_{\mathcal{J}'}). \quad (10)$$

For stabilizer codes, the decoding problem for general quantum channels reduces to decoding Pauli errors only, after performing syndrome measurement, i.e., measuring all the generators of the stabilizer group (in our case, the elements of $\bar{S}_{\mathcal{I}\mathcal{J}\mathcal{J}'}$). Here, the implicit assumption is that syndrome measurement induces appropriate projections, such that it results in the standard Pauli error model.

For Pauli channels, we provide an efficient decoding algorithm (Section 6.4), achieving the symmetric coherent information of the channel. For general quantum channels, syndrome measurement coupled with the above decoding on the induced Pauli error model may yield a practical solution to the decoding problem. However, such a solution is not optimal, due to the loss of information incurred during syndrome measurement. Besides, the polar code should be fitted to (and thus exploit the polarization of) the induced Pauli error model, rather than the quantum channel itself. Devising an efficient decoding algorithm capable of achieving the symmetric coherent information of general quantum channels is an open problem.

# 6 Polarization of Pauli Channels

This section further investigates the quantum polarization of Pauli channels. First, to a Pauli channel $\mathcal{N}$ we associate a classical symmetric channel $\mathcal{N}^\#$, with both input and output alphabets given by the quotient of the 1-qubit Pauli group by its centralizer. We then show that the former polarizes quantumly if and only if the latter polarizes classically. We use this equivalence to provide an alternative proof of the quantum polarization for a Pauli channel, as well as fast polarization properties. We then devise an effective way to decode a quantum polar code on a Pauli channel, by decoding its classical counterpart.

Let $P_n$ denote the Pauli group on $n$ qubits, and $\bar{P}_n = P_n/\{\pm 1, \pm i\}$ the Abelian group obtained by taking the quotient of $P_n$ by its centralizer. We write $\bar{P}_1 = \{\sigma_i \mid i = 0, \dots, 3\}$, with $\sigma_0 = I$, $\sigma_1 = X$, $\sigma_2 = Y$, $\sigma_3 = Z$, and $\bar{P}_2 = \{\sigma_{i,j} := \sigma_i \otimes \sigma_j \mid i, j = 0, \dots, 3\} \simeq \bar{P}_1 \times \bar{P}_1$. For any two-qubit Clifford unitary $C$, we denote by $\Gamma(C)$, or simply $\Gamma$ when no confusion is possible, the conjugate action of $C$ on $\bar{P}_2$. Hence, $\Gamma$ is the automorphism of $\bar{P}_2$ (or equivalently $\bar{P}_1 \times \bar{P}_1$), defined by $\Gamma(\sigma_{i,j}) = C\sigma_{i,j}C^\dagger$.

<footnote>$^5$Note that the definition of $S_{\mathcal{I}\mathcal{J}\mathcal{J}'}$ in (9) depends only on index $j \in \mathcal{J}$, since $j' \in \mathcal{J}'$ is the counterpart of $j$ (thus, uniquely determined by the latter).</footnote>
Let $\mathcal{N}$ be a Pauli channel defined by$^6$ $\mathcal{N}(\rho) = \sum_{i=0}^3 p_i \sigma_i \rho \sigma_i^\dagger$, with $\sum_{i=0}^3 p_i = 1$. Its coherent information for a uniformly distributed input is given by $I(\mathcal{N}) = 1 - h(\mathbf{p})$, where $h(\mathbf{p}) = -\sum_{i=0}^3 p_i \log(p_i)$ denotes the entropy of the probability vector $\mathbf{p} = (p_0, p_1, p_2, p_3)$.

**Definition 17 (Classical counterpart of a Pauli channel).** Let $\mathcal{N}$ be a Pauli channel. The classical counterpart of $\mathcal{N}$, denoted by $\mathcal{N}^{\#}$, is the classical channel with input and output alphabet $\bar{P}_1$, and transition probabilities $\mathcal{N}^{\#}(\sigma_i | \sigma_j) = p_k$, where $k$ is such that $\sigma_i \sigma_j = \sigma_k$$^7$.

Hence, $\mathcal{N}^{\#}$ is a memoryless symmetric channel, whose capacity is given by the mutual information for uniformly distributed input $I(\mathcal{N}^{\#}) = \frac{1}{2}(2 - h(\mathbf{p})) \in [0, 1]$. It follows that

$$I(\mathcal{N}^{\#}) = \frac{1 + I(\mathcal{N})}{2}.$$

Note that the right hand side term in the above equation is half the mutual information of the Pauli channel $\mathcal{N}$, for a uniformly distributed input.

It is worth noticing that the quantum channels synthesized during the quantum polarization of a Pauli channel are identifiable (see below) to classical mixtures of Pauli channels (this will be proved in Proposition 20). A Classical Mixture of Pauli (CMP) channels is a quantum channel $\mathcal{N}(\rho) = \sum_{x \in X} \lambda_x |x\rangle\langle x| \otimes \mathcal{N}_x(\rho)$, where $\{|x\rangle\rangle_{x \in X}$ is some orthonormal basis of an auxiliary system, $\mathcal{N}_x$ are Pauli channels, and $\sum_{x \in X} \lambda_x = 1$. We further extend Definition 17 to the case of CMP channels, by defining the classical channel $\mathcal{N}^{\#}$ as the mixture of the channels $\mathcal{N}_x^{\#}$, where channel $\mathcal{N}_x^{\#}$ is used with probability $\lambda_x$. Hence, input and output alphabets of $\mathcal{N}^{\#}$ are $\bar{P}_1$ and $X \times \bar{P}_1$, respectively, with channel transition probabilities defined by $\mathcal{N}^{\#}(x, \sigma_i | \sigma_j) = \lambda_x \mathcal{N}_x(\sigma_i | \sigma_j)$. It also follows that:

$$I(\mathcal{N}^{\#}) = \sum_{x} \lambda_x I(\mathcal{N}_x^{\#}) = \sum_{x} \lambda_x \frac{1 + I(\mathcal{N}_x)}{2} = \frac{1 + I(\mathcal{N})}{2}.$$

Given two classical channels $\mathcal{U}$ and $\mathcal{V}$, we say they are equivalent, and denote it by $\mathcal{U} \equiv \mathcal{V}$, if they are defined by the same transition probability matrix, modulo a permutation of rows and columns. The following lemma states that the classical channel associated with a CMP channel does not depend on the basis.

**Lemma 18.** Let $\mathcal{N}(\rho) = \sum_{x \in X} \lambda_x |x\rangle\langle x| \otimes \mathcal{N}_x(\rho)$ and $\mathcal{M}(\rho) = \sum_{y \in Y} \tau_y |y\rangle\langle y| \otimes \mathcal{M}_y(\rho)$ be two CMP channels, where $\{|x\rangle\rangle_{x \in X}$ and $\{|y\rangle\rangle_{y \in Y}$ are orthonormal bases of the same auxiliary system. If $\mathcal{N} = \mathcal{M}$, then there exists a bijective mapping $\pi: X \to Y$, such that $\lambda_x = \tau_{\pi(x)}$ and $\mathcal{N}_x = \mathcal{M}_{\pi(x)}$. In particular, $\mathcal{N}^{\#} \equiv \mathcal{M}^{\#}$.

Finally, we say that a quantum channel $\mathcal{N}_{U \to AX}$ is identifiable to a channel $\mathcal{N}'_{U \to A}$ if, for some unitary operator $C$ on the $AX$ system, we have that $\mathcal{N}(\rho) = C(\mathcal{N}'(\rho) \otimes \frac{I_X}{|X|}) C^\dagger$, where $|X|$ denotes the dimension of the $X$ system. In other words, $\mathcal{N}$ and $\mathcal{N}'$ are equal modulo the conjugate action of an unitary operator $C$, and possibly after discarding a "useless" output system $X$. If $\mathcal{N}_{U \to AX}$ is identifiable to a CMP channel $\mathcal{N}'_{U \to A}$, we shall define $\mathcal{N}^{\#} := (\mathcal{N}')^{\#}$. It can be seen that $\mathcal{N}^{\#}$ is well defined up to equivalence of classical channels, that is, if $\mathcal{N}_{U \to AX}$ is identifiable to another CMP channel $\mathcal{N}''_{U \to A}$, then $(\mathcal{N}')^{\#} \equiv (\mathcal{N}'')^{\#}$. This follows from the following lemma, proven in Appendix B.

**Lemma 19.** Let $\mathcal{N}'$ and $\mathcal{N}''$ be two CMP channels, such that $\mathcal{N}'(\rho) \otimes \frac{I_X}{|X|} = C(\mathcal{N}''(\rho) \otimes \frac{I_X}{|X|}) C^\dagger$, for some unitary $C$. Then $(\mathcal{N}')^{\#} \equiv (\mathcal{N}'')^{\#}$.

<footnote>$^6$We use $\sigma_i^\dagger$ in the definition of the Pauli channel, to explicitly indicate that the definition does not depend on the representative of the equivalence class.</footnote>

<footnote>$^7$Here, equality is understood as equivalence classes in $\bar{P}_1$.</footnote>
## 6.1 Classical Channel Combining and Splitting Operations

**Simplified notation:** To simplify notation, we shall identify $(\bar{P}_1, \times) \cong (\{0, 1, 2, 3\}, \oplus)$, by identifying $\sigma_u \cong u, \forall u = 0, \dots, 3$, where the additive group operation $u \oplus v$ is given by the bitwise exclusive OR (XOR) between the binary representations of integers $u, v$. The classical counterpart $\mathcal{N}^\#$ of a Pauli channel $\mathcal{N}(\rho) = \sum_{u=0}^3 p_u \sigma_u \rho \sigma_u^\dagger$ (Definition 17), is therefore identified to a channel with input and output alphabet $\bar{P}_1 \cong \{0, 1, 2, 3\}$, and transition probabilities $\mathcal{N}^\#(u | v) = p_{u \oplus v}$.

Let $N$ and $M$ be two classical channels, both with input alphabet $\bar{P}_1 \cong \{0, 1, 2, 3\}$, and output alphabets $A$ and $B$, respectively. Channel transition probabilities are denoted by $N(a | u)$ and $M(b | v)$, for $u, v \in \bar{P}_1$, $a \in A$, and $b \in B$. Let $\Gamma : \bar{P}_1 \times \bar{P}_1 \to \bar{P}_1 \times \bar{P}_1$ be any permutation, and write $\Gamma = (\Gamma_1, \Gamma_2)$, with $\Gamma_i : \bar{P}_1 \times \bar{P}_1 \to \bar{P}_1$, $i = 1, 2$. The combined channel $N \bowtie_\Gamma M$ is defined by:

$$ (N \bowtie_\Gamma M)(a, b | u, v) = N(a | \Gamma_1(u, v)) M(b | \Gamma_2(u, v)) \quad (11) $$

It is further split into two channels $N \oplus_\Gamma M$ and $N \ominus_\Gamma M$, defined by:

$$ (N \oplus_\Gamma M)(a, b | u) = \frac{1}{4} \sum_v (N \bowtie_\Gamma M)(a, b | u, v), \quad (12) $$

$$ (N \ominus_\Gamma M)(a, b, u | v) = \frac{1}{4} (N \bowtie_\Gamma M)(a, b | u, v). \quad (13) $$

Applying the above construction to classical counterparts of CMP channels, we have the following proposition, proven in Appendix C.

**Proposition 20.** Let $N_{U \to A}$ and $M_{V \to B}$ be two CMP channels, and $C$ be any two-qubit Clifford unitary, acting on the two qubit system $UV$. Let $\mathcal{N}^\#$ and $\mathcal{M}^\#$ denote the two classical counterparts of the above CMP channels, and $\Gamma := \Gamma(C)$ be the permutation induced by the conjugate action of $C$ on $\bar{P}_1 \times \bar{P}_1$. Then $N \oplus_\Gamma M$ and $N \ominus_\Gamma M$ are identifiable to CMP channels, thus $(N \oplus_\Gamma M)^\#$ and $(N \ominus_\Gamma M)^\#$ are well defined, and the following properties hold:

$$ (i) \quad (N \oplus_\Gamma M)^\# \equiv \mathcal{N}^\# \oplus_\Gamma M^\# $$

$$ (ii) \quad (N \ominus_\Gamma M)^\# \equiv \mathcal{N}^\# \ominus_\Gamma M^\# $$

A consequence of the above proposition is that a CMP channel polarizes under the recursive application of the channel combining and splitting rules, if and only if its classical counterpart does so. Moreover, processes of both quantum and classical polarization yield the same set of indices for the good/bad channels. More precisely, we have the following:

**Corollary 21.** Let $W$ be a CMP channel, and $W^{(i_1 \cdots i_n)}$ be defined recursively as in (5), $\forall n > 0$, $\forall i_1 \cdots i_n \in \{0, 1\}^n$. Let $W^\#$ be the classical counterpart of $W$, and $(W^\#)^{(i_1 \cdots i_n)}$ be defined recursively, similar to (5), while replacing $W$ by $W^\#$, and Clifford unitaries $C_{i_1 \cdots i_n}$ by the corresponding permutations $\Gamma_{i_1 \cdots i_n} := \Gamma(C_{i_1 \cdots i_n})$. Then $(W^{(i_1 \cdots i_n)})^\# \equiv (W^\#)^{(i_1 \cdots i_n)}$, $\forall n, \forall i_1 \cdots i_n \in \{0, 1\}^n$. In particular:

$$ I \left( (W^\#)^{(i_1 \cdots i_n)} \right) = \frac{1 + I(W^{(i_1 \cdots i_n)})}{2}. $$

As we already know that the quantum transform polarizes, it follows that the classical transform does also polarize. Moreover, a direct proof of the classical polarization can be derived by verifying the conditions from Lemma 7, with stochastic process $\{T_n : n \ge 0\}$ given by Bhattacharyya parameter $Z$ of the classical channels synthesized during the recursive construction. We recall below the definition of the Bhattacharyya parameter for a classical channel $W$, as defined in [19]. We shall restrict our attention to classical channels with input alphabet $\bar{P}_1$.
**Definition 22** ([19]). Let W be a classical channel, with input alphabet $\bar{P}_1 \cong (\{0, 1, 2, 3\}, \oplus)$ and output alphabet Y. For $u, u', d \in \bar{P}_1$, we define

$$Z(W_{u,u'}) := \sum_{y \in Y} \sqrt{W(y|u)W(y|u')}. $$

$$Z_d(W) := \frac{1}{4} \sum_{u \in \bar{P}_1} Z(W_{u,u \oplus d}). $$

In particular, note that $Z(W_{u,u}) = 1, \forall u \in \bar{P}_1$, and $Z_0(W) = 1$. The Bhattacharyya parameter of W, denoted $Z(W)$, is then defined as

$$Z(W) := \frac{1}{3} \sum_{d \neq 0} Z_d(W) = \frac{1}{12} \sum_{u \neq u'} Z(W_{u,u'}). $$

Polarization of the classical channel $W^#$ follows then from the lemma below, whose proof is provided in Appendix D.

**Lemma 23.** Let W be a CMP channel and $W^#$ its classical counterpart. Given two instances of the channel $W^#$, we have that

$$\mathbb{E}_{\Gamma \in \Gamma(\mathcal{L})} Z(W^# \otimes_{\Gamma} W^#) = \mathbb{E}_{\Gamma \in \Gamma(\mathcal{R})} Z(W^# \otimes_{\Gamma} W^#) = \frac{1}{3} Z(W^#) + \frac{2}{3} Z(W^#)^2, \quad (14)$$

where $\Gamma(\mathcal{L})$ and $\Gamma(\mathcal{R})$ denote the set of permutations generated on $\bar{P}_2$ by the conjugate action of Cliffords in $\mathcal{L}$ and $\mathcal{R}$, respectively.

## 6.2 Polarization Using Only Three Clifford Gates

In this section, we show that for Pauli channels the set of channel combining Clifford gates can be reduced to three gates only, while still ensuring polarization. Let $\mathcal{S}$ denote the set containing the Clifford gates $L_{1,3}$, $L_{2,2}$, and $L_{3,1}$ from Fig. 3, and $\Gamma(\mathcal{S})$ denote the corresponding set of permutations, namely $\Gamma(L_{1,3})$, $\Gamma(L_{2,2})$ and $\Gamma(L_{3,1})$, generated by the conjugate actions of $L_{1,3}$, $L_{2,2}$, and $L_{3,1}$ on $\bar{P}_1 \times \bar{P}_1$.

**Lemma 24.** Let W be a CMP channel and $W^#$ its classical counterpart. Given two instances of the channel $W^#$, then

$$\mathbb{E}_{\Gamma \in \Gamma(\mathcal{S})} Z(W^# \otimes_{\Gamma} W^#) \le \frac{1}{3} Z(W^#) + \frac{2}{3} Z(W^#)^2. \quad (15)$$

The proof is given in Appendix E.

## 6.3 Speed of Polarization

Before discussing decoding of quantum polar codes over Pauli channels (Section 6.4), it is worth noticing that classical polar codes come equipped with a decoding algorithm, known as successive cancellation (SC) [1]. However, the effectiveness of the classical SC decoding, i.e., its capability of successfully decoding at rates close to the capacity, depends on the speed of polarization. The Bhattacharyya parameter of the synthesized channels plays an important role in determining the speed at which polarization takes place. First, we note that for a classical channel W, the Bhattacharyya parameter upper bounds the error probability of uncoded transmission. Precisely, given a classical channel W with input alphabet X, the error probability of the maximum-likelihood decoder for a single channel use, denoted $P_e$, is upper-bounded as follows ([19, Proposition 2]):

$$P_e \le (|X| - 1)Z(W). $$
Now, consider a polar code defined by the recursive application of n polarization steps to the classical channel $W := W^\#$(the input alphabet is $X := \bar{P}_1$, of size $|\bar{P}_1| = 4$). The construction is the same as the one in Section 5, while replacing the quantum channel $W$ by its classical counterpart $W$, and channel combining Clifford gates $C_{i_1 i_2 \dots}$ by the corresponding permutations $\Gamma_{i_1 i_2 \dots} := \Gamma(C_{i_1 i_2 \dots})$. For any $i = 0, \dots, N-1$, let $W^{(i)} := (W^\#)^{(i_1 \cdots i_n)}$, where $i_1 \cdots i_n$ is the binary decomposition of $i$. For the sake of simplicity, we drop the channel combining permutations $\Gamma$'s from the above notation. Let $\mathcal{I} \subset \{0, 1, \dots, N-1\}$ denote the set of good channels (i.e., channels used to transmit information symbols, as opposed to bad channels, which are frozen to symbol values known to both the encoder and decoder). Since the SC decoding proceeds by decoding successively the synthesized good channels$^8$, it can be easily seen that the block error probability of the SC decoder, denoted by $P_e(N, \mathcal{I})$, is upper-bounded by (see also [1, Proposition 2]):

$$P_e(N, \mathcal{I}) \le 3 \sum_{i \in \mathcal{I}} Z(W^{(i)}). \qquad (16)$$

If the Bhattacharyya parameters of the $W^{(i)}$ channels, with $i \in \mathcal{I}$, converge sufficiently fast to zero, one can use (16) to ensure that $P_e(N, \mathcal{I})$ goes to zero. Since the number of terms in the right hand side of (16) is linear in $N$, it is actually enough to prove that $Z(W^{(i)}) \le O(N^{-(1+\theta)})$, $\forall i \in \mathcal{I}$, for some $\theta > 0$.

The proof of fast polarization properties in [19, Lemma 3], for channels with non-binary input alphabets, exploits two main ingredients:

(1) The quadratic improvement of the Bhattacharyya parameter, when taking the good channel, i.e., $Z(W^{(i_1 \cdots i_{n-1} i_n)}) \le Z(W^{(i_1 \cdots i_{n-1})})^2$, $\forall i_1 \cdots i_{n-1} i_n \in \{0, 1\}^n$, such that $i_n = 1$.

(2) The linearly upper-bounded degradation of the Bhattacharyya parameter, when taking the bad channel, i.e., $Z(W^{(i_1 \cdots i_{n-1} i_n)}) \le \kappa Z(W^{(i_1 \cdots i_{n-1})})$, $\forall i_1 \cdots i_{n-1} i_n \in \{0, 1\}^n$, such that $i_n = 0$, for some constant $\kappa > 0$.

Regarding the second condition, in our case we have the following lemma, where for a classical channel $W$ with input alphabet $\bar{P}_1 \cong \{0, 1, 2, 3\}$, we define

$$\bar{Z}(W) := \max_{d=1,2,3} Z_d(W). \qquad (17)$$

**Lemma 25.** For any classical channel $W$ with input alphabet $\bar{P}_1$, and any linear permutation $\Gamma : \bar{P}_1 \times \bar{P}_1 \to \bar{P}_1 \times \bar{P}_1$, the following inequalities hold:

$$\bar{Z}(W \oplus_{\Gamma} W) \le 4\bar{Z}(W).$$

$$Z(W \oplus_{\Gamma} W) \le 12Z(W).$$

The proof is given in Appendix F.

Condition (1) above – quadratic improvement of the Bhattacharyya parameter, when taking the good channel – is more problematic, due to the linear term in the right hand side of (14) and (15). In particular, we can not apply [19, Lemma 3] to derive fast polarization properties in our case. Instead, we will prove fast polarization properties by drawing upon arguments similar to those in the proof of [1, Theorem 2]. First, we need the following definition.

**Definition 26.** Let $W$ be a classical channel with input alphabet $\bar{P}_1$, and $\Gamma = \{\Gamma, \Gamma_{i_1 \cdots i_n} | n > 0, i_1 \cdots i_n \in \{0, 1\}^n\}$ be an infinite sequence of permutations. For $n > 0$, let

$$W^{(i_1 \cdots i_n)} := \begin{cases} W^{(i_1 \cdots i_{n-1})} \oplus_{\Gamma_{i_1 \cdots i_{n-1}}} W^{(i_1 \cdots i_{n-1})}, & \text{if } i_n = 0 \\ W^{(i_1 \cdots i_{n-1})} \oplus_{\Gamma_{i_1 \cdots i_{n-1}}} W^{(i_1 \cdots i_{n-1})}, & \text{if } i_n = 1 \end{cases} \qquad (18)$$

<footnote>$^8$Each good channel is decoded by taking a maximum-likelihood decision, according to the observed channel output and the previously decoded channels.</footnote>
where, for $n = 1$, in the right hand side term of the above equality, we set by convention $W^{(\varnothing)} := W$ and $\Gamma_{\varnothing} := \Gamma$. We say that $\Gamma$ is a polarizing sequence (or that polarization happens for $\Gamma$), if for any $\delta > 0$,

$$ \lim_{n \to \infty} \frac{\#\{(i_1 \cdots i_n) \in \{0, 1\}^n : \mathbf{I}(W^{(i_1 \cdots i_n)}) \in (\delta, 1 - \delta)\}}{2^n} = 0. $$

Note that different from (the classical counterpart of) Theorem 9, we consider here a given sequence of permutations, instead of averaging over some set of sequences. If $W = W^\#$ is the classical counterpart of a CMP channel $W$, by Lemma 24, we know that polarization happens when averaging over all the sequences $\Gamma \in \Gamma(S)^\infty$. As a consequence, there exists a subset $\Gamma(S)^\infty_{pol} \subset \Gamma(S)^\infty$ of positive probability$^9$, such that polarization happens for any $\Gamma \in \Gamma(S)^\infty_{pol}$. We are now ready to state the following fast polarization result, whose proof is given in Appendix G.

**Proposition 27.** Let $W$ be a CMP channel, $W := W^\#$ its classical counterpart, and $S$ the set of three Clifford gates from Section 6.2. Then the following fast polarization property holds for almost all $\Gamma$ sequences in $\Gamma(S)^\infty_{pol}$:

For any $\theta > 0$ and $R < \mathbf{I}(W)$, there exists a sequence of sets $\mathcal{I}_N \subset \{0, \dots, N-1\}$, $N \in \{1, 2, \dots, 2^n, \dots\}$, such that $|\mathcal{I}_N| \ge NR$ and $Z(W^{(i)}) \le O(N^{-(1+\theta)})$, $\forall i \in \mathcal{I}_N$. In particular, the block error probability of polar coding under SC decoding satisfies

$$ P_e(N, \mathcal{I}_N) \le O(N^{-\theta}). $$

## 6.4 Decoding the Quantum Polar Code by Using its Classical Counterpart

Let $W$ be a CMP channel and $W^\#$ its classical counterpart. Let $G_q$ denote the unitary operator corresponding to the quantum polar code (defined by the recursive application of $n$ polarization steps, see Section 5), and $G_c$ denote the linear transformation corresponding to the classical polar code. Let $\mathcal{I}$ and $\mathcal{J}$ be the set of indices corresponding to the good and bad channels, respectively, with $|\mathcal{I}| + |\mathcal{J}| = N := 2^n$. We shall use the following notation from Section 5:

* $\rho_\mathcal{I}$ denotes the original state of system $\mathcal{I}$,

* $\varphi_{\mathcal{I}\mathcal{J}\mathcal{J}'} := (G_q \otimes I_{\mathcal{J}'}) (\rho_\mathcal{I} \otimes \Phi_{\mathcal{J}\mathcal{J}'}) (G_q^\dagger \otimes I_{\mathcal{J}'})$ denotes the encoded state, where $\Phi_{\mathcal{J}\mathcal{J}'}$ is a maximally entangled state, as defined in (6).

* $\psi_{\mathcal{I}\mathcal{J}\mathcal{J}'} := (W^{\otimes N} \otimes I_{\mathcal{J}'}) (\varphi_{\mathcal{I}\mathcal{J}\mathcal{J}'})$ denotes the channel output state.

Since $W$ is a CMP channel, it follows that:

$$ \psi_{\mathcal{I}\mathcal{J}\mathcal{J}'} = (E_{\mathcal{I}\mathcal{J}} G_q \otimes I_{\mathcal{J}'}) (\rho_{\mathcal{I}} \otimes \Phi_{\mathcal{J}\mathcal{J}'}) (G_q^\dagger E_{\mathcal{I}\mathcal{J}}^\dagger \otimes I_{\mathcal{J}'}). $$

for some error $E_{\mathcal{I}\mathcal{J}} \in P_N$. Hence, quantum polar code decoding can be performed in the 4 steps described below.

**Step 1: Apply the inverse quantum polar transform on the channel output state.** Applying $G_q^\dagger$ on the output state $\psi_{\mathcal{I}\mathcal{J}\mathcal{J}'}$, leaves the $\mathcal{I}\mathcal{J}\mathcal{J}'$ system in the following state:

$$ \psi'_{\mathcal{I}\mathcal{J}\mathcal{J}'} = (G_q^\dagger E_{\mathcal{I}\mathcal{J}} G_q \otimes I_{\mathcal{J}'}) (\rho_\mathcal{I} \otimes \Phi_{\mathcal{J}\mathcal{J}'}) (G_q^\dagger E_{\mathcal{I}\mathcal{J}}^\dagger G_q \otimes I_{\mathcal{J}'}) $$

<footnote>$^9$Note that $\Gamma(S)^\infty$ is the infinite product space of countable many copies of $\Gamma(S)$, and it is endowed with the infinite product probability measure, taking the uniform probability measure on each copy of $\Gamma(S)$. See [10] for infinite product probability measures.</footnote>
$$ = (E'_{IJ} \otimes I_{J'}) (\rho_I \otimes \Phi_{IJ'})(E'_{IJ}^{\dagger} \otimes I_{J'}). $$

where $E'_{IJ} := G_q^\dagger E_{IJ} G_q$. Since we only need to correct up to a global phase, we may assume that $E'_{IJ}, E_{IJ} \in P_N / \{\pm 1, \pm i\} \simeq \bar{P}_1^N$, and thus write $E'_{IJ} = G_c^{-1} E_{IJ}$, or equivalently:

$$ E_{IJ} = G_c E'_{IJ}. $$

Put differently, $E_{IJ}$ is the classical polar encoded version of $E'_{IJ}$.

**Step 2: Quantum measurement.**$^{10}$ Let $E'_{IJ} = \bigotimes_{i \in \mathcal{I}} E'_i \otimes \bigotimes_{j \in \mathcal{J}} E'_j$, with $E'_i, E'_j \in \bar{P}_1$. Measuring $X_j X_{j'}$ and $Z_j Z_{j'}$ observables$^{11}$, allows determining the value of $E'_j$, for any $j \in \mathcal{J}$, since no errors occurred on the $\mathcal{J}'$ system.

**Step 3: Decode the classical polar code counterpart.** We note that the error $E_{IJ}$ can be seen as the output of the classical vector channel $(W^\#)^N$, when the "all-identity vector" $\sigma_0^N \in \bar{P}_1^N$ is applied at the channel input. However, by the definition of the classical channel $W^\#$, we have $(W^\#)^N(E_{IJ} | \sigma_0^N) = (W^\#)^N(\sigma_0^N | E_{IJ})$, meaning that we can equivalently consider $\sigma_0^N$ as being the observed channel output, and $E_{IJ}$ the (unknown) channel input. Hence, we have given (i) the value of $E'_{IJ} := \otimes_{j \in \mathcal{J}} E'_j$, and (ii) a noisy observation (namely $\sigma_0^N$) of $E_{IJ} = G_c E'_{IJ}$. We can then use classical polar code decoding to recover the value of $E'_{IJ} := \otimes_{i \in \mathcal{I}} E'_i$.

**Step 4: Error correction.** Once we have recovered the $E'_{\mathcal{J}}$ (step 2) and $E'_{\mathcal{I}}$ (step 3) values, we can apply the $E'_{IJ} \otimes I_{J'}$ operator on $\psi'_{IJ\mathcal{J}'}$, thus leaving the $\mathcal{I}\mathcal{J}\mathcal{J}'$ system in the state $\rho_I \otimes \Phi_{\mathcal{J}\mathcal{J}'}$.

# 7 Polarization with Vanishing Rate of Preshared Entanglement

In this section we present a code construction using an asymptotically vanishing rate or pre-shared entanglement, while achieving a transmission rate equal to the coherent information of the channel. In particular, we shall assume that the coherent information of the channel is positive, $I(W) > 0$. The proposed construction bears similarities to the universal polar code construction in [9, Section V], capable of achieving the compound capacity of a finite set of classical channels.

Let $P_q(N, \mathcal{J}, \mathcal{I})$ denote a quantum polar code of length $N = 2^n$, for some $n > 0$, where $\mathcal{I}$ and $\mathcal{J}$ denote the sets of good and bad channels respectively. By Theorem 9, as $n$ goes to infinity, $|\mathcal{I}|$ approaches $\frac{1+I(W)}{2}N$, and thus $|\mathcal{J}|$ approaches $\frac{1-I(W)}{2}N$. Since $I(W) > 0$, it follows that $|\mathcal{J}| < |\mathcal{I}|$, provided that $n$ is large enough. Therefore, we may find a subset of good channels $\mathcal{I}' \subset \mathcal{I}$, such that $|\mathcal{I}'| = |\mathcal{J}|$. In the sequel, we shall extend the definition of a polar code to include such a subset $\mathcal{I}'$, and denote it by $P_q(N, \mathcal{J}, \mathcal{I}, \mathcal{I}')$.

Let us now consider $k$ copies of a quantum polar code $P_q(N, \mathcal{J}, \mathcal{I}, \mathcal{I}')$, denoted by $P_q^l(N, \mathcal{J}, \mathcal{I}, \mathcal{I}')$ or simply by $P_q^l$, for any $l \in \{0, 1, \dots, k-1\}$. We define a quantum code $C_q^k$ of codelength $|C_q^k| = kN$, by chaining them in the following way (see also Fig. 5):

(i) For system $\mathcal{J}_0$, the input quantum state before encoding is half of a maximally entangled state $\Phi_{\mathcal{J}_0\mathcal{J}_0'}$, where system $\mathcal{J}_0'$ is part of channel output. This is the only preshared entanglement between the sender and the receiver.

(ii) For systems $\mathcal{I}_{l-1}'$ and $\mathcal{J}_l$, with $l \neq 0$, the input quantum state before encoding is a maximally entangled state $\Phi_{\mathcal{I}_{l-1}'\mathcal{J}_l}$.

<footnote>$^{10}$Steps (1) and (2) together perform a set of measurements that are equivalent to measuring the elements of the stabilizer set $\tilde{S}_{\mathcal{I}\mathcal{J}\mathcal{J}'}$ defined in (10).</footnote>

<footnote>$^{11}$Here, indices $j$ and $j'$ indicate the $j$-th qubits of $\mathcal{J}$ and $\mathcal{J}'$ systems.</footnote>
<figure><img src="image_7.png" /><figcaption>Figure 5: $C_q^3$: Chaining construction with $k = 3$ copies of a quantum polar codes $P_q$</figcaption></figure>

(iii) Systems $\mathcal{I}_l \setminus \mathcal{I}'_l$, for $l \neq k-1$, and $\mathcal{I}_{k-1}$ are information systems, meaning that the corresponding quantum state is the one that needs to be transmitted from the sender to the receiver.

It can be easily seen that the transmission (coding) rate of the proposed scheme is given by

$$R := \frac{\sum_{l=0}^{k-2} |\mathcal{I}_l \setminus \mathcal{I}'_l| + |\mathcal{I}_{k-1}|}{kN} \underset{n \to \infty}{\longrightarrow} \frac{(k-1)I(\mathcal{W}) + \frac{1+I(\mathcal{W})}{2}}{k} \underset{k \to \infty}{\longrightarrow} I(\mathcal{W}),$$

while the rate of preshared entanglement is given by

$$E := \frac{|\mathcal{J}_0|}{kN} \underset{n \to \infty}{\longrightarrow} \frac{1 - I(\mathcal{W})}{2k} \underset{k \to \infty}{\longrightarrow} 0.$$

**Decoding $C_q^k$:** We shall assume that we are given an effective decoding algorithm of the quantum polar code $P_q$, capable of achieving the symmetric coherent information of the channel. We note that this is indeed the case for Pauli channels (Section 6.4), but it is an open problem for general quantum channels. In this case, $C_q^k$ can be decoded sequentially, by decoding first $P_q^0$, then $P_q^1$, $P_q^2$, and so on. Indeed, after decoding $P_q^0$, thus in particular correcting the state of the $\mathcal{I}'_0$ system, the EPR pairs $\Phi_{\mathcal{I}'_0 \mathcal{J}_1}$ will play the role of the preshared entanglement required to decode $P_q^1$. Therefore, $P_q^1$ can be decoded once $P_q^0$ has been decoded, and similarly, $P_q^l$ can be decoded after $P_q^{l-1}$ has been decoded, for any $l \in \{2, \dots, k-1\}$.

**Entanglement as a catalyst:** Finally, the above coding scheme can be slightly modified, such that preshared entanglement between the sender and the receiver is not consumed. In the above construction, we have considered that for the last $P_q^{k-1}$ polar code, the $\mathcal{I}'_{k-1}$ system is an information system, i.e., used to transmit quantum information from the sender to the receiver (system $\mathcal{I}'_2$ in Fig. 5). Let us now assume that the input quantum state to the $\mathcal{I}'_{k-1}$ system is half of a maximally entangled state $\Phi_{\mathcal{I}'_{k-1} \mathcal{J}_k}$, where quantum system $\mathcal{J}_k$ is held by the sender. When the receiver completes decoding of the $C_q^k$ code, it restores the initial state of the $\mathcal{I}'_{k-1}$, thus resulting in a maximally entangled state $\Phi_{\mathcal{I}'_{k-1} \mathcal{J}_k}$ shared between the sender ($\mathcal{J}_k$ system) and the receiver ($\mathcal{I}'_{k-1}$ system). Hence, the initial preshared entanglement $\Phi_{\mathcal{J}_0 \mathcal{J}'_0}$ acts as a catalyst, in that it produces a new state $\Phi_{\mathcal{I}'_{k-1} \mathcal{J}_k}$ shared between the sender and the receiver, which can be used for the next transmission.

# 8 Conclusion and Perspectives

In this paper, we demonstrated an entanglement assisted polarization phenomenon that happens at the quantum level, and which relies on a channel combining construction using randomized two-qubit Clifford gates instead of the CNOT gate. In the case of Pauli channels, we
have proven that the quantum polarization is equivalent to a classical polarization for an associ-
ated non-binary channel which allows us to have an efficient decoding scheme. We also proved
a fast polarization property in this case. Finally, we presented a quantum polar code chaining
construction, for which the required entanglement assistance is negligible with respect to the
code length.

The quantum polar code construction proposed in this paper makes an efficient use of pre-
shared entanglement, achieving a quantum communication rate equal to half the symmetric
mutual information of the quantum channel. This differentiates our construction from the CSS-
based one. In terms of net communication rate, both constructions exhibit the same asymptotic
performance, achieving the symmetric coherent information of the quantum channel. How-
ever, for finite code-lengths, we expect that our scheme may have some benefits, due to more
degrees of freedom in the construction of the polar code. We expect that an appropriate choice
of the Clifford unitaries in the channel combining step may increase not only the polarization
speed, but also the minimum distance of the code. Increasing the minimum distance is rele-
vant in case that list decoding [22] is used, which may significantly improve the error correc-
tion capability for finite code-lengths. Finite-length specific issues (e.g., devising optimization
algorithms for code construction, or considering decoding algorithms other than successive-
cancellation) may be the subject of future research.

Besides, the quantum polarization phenomenon presented here opens new perspectives
that complement or extend the classical CSS-based viewpoint, and which are discussed below.

1) One of the main characteristics of our approach is to yield a family of quantum codes, whose construction does not rely exclusively on the stabilizer formalism. This invites the study of quantum decoding algorithms that might achieve the symmetric coherent information for non Pauli channels (as explained in Section 5.2, stabilizer decoding is not optimal for non-Pauli channels). Explicit capacity-achieving decoders for non Pauli channels have been recently proposed in [15], based on a belief-propagation algorithm that passes quantum messages and is capable of decoding the classical-quantum channel with pure state outputs. Since the successive-cancellation decoding of polar codes is essentially a belief-propagation algorithm, it would be interesting to devise similar approaches for the family of quantum polar codes proposed here.

2) Another question with potentially wide-reaching implications is related to the use of quantum polar codes in the context of fault-tolerant computing. The preshared entanglement requirement amounts to having a reliable quantum memory to store one half of each EPR pair. In this context, it would be interesting to study the impact of a "noisy" channel combining step on the quantum polarization.

3) Finally, while this paper focused on the polarization of qubit-input channels, our con-
struction admits a simple and natural generalization to the case of qudit-input channels. In-
deed, the definitions of symmetric coherent information and Rényi-Bhattacharyya parameter
are valid for qudit channels. Therefore, to prove quantum polarization for qudit channels, we
again need to show that all the constraints in Lemma 7 are satisfied. The most challenging
constraint in Lemma 7 is point (t.2), which in the qubit case follows from Lemma 11. It is not
too difficult to see that Lemma 11 can be generalized to the qudit case with a few adjustments
depending on the system dimension, reusing again the computations in [7], and given that the
channel combining operation is randomly chosen from a unitary 2-design.
A Proof of Lemma 14

Throughout this section, $\mathcal{N} := \mathcal{N}_{A'_1 \to B_1}$ and $\mathcal{M} := \mathcal{M}_{A'_2 \to B_2}$ denote two quantum channels with input qubit systems $A'_1$ and $A'_2$. We denote by $\mathcal{N}^{c}_{A'_1 \to E_1}$ and $\mathcal{M}^{c}_{A'_2 \to E_2}$ their complementary channels, and by $\Phi_{A_1 A'_1}$ and $\Phi_{A'_2 A_2}$ two EPR pairs on 2-qubit systems $A_1 A'_1$ and $A'_2 A_2$. First, we will need the following lemma, which basically states that taking the complementary of the bad/good channels inverts the bad and good channel constructions, as well as the input system on which we input the half of the EPR pair.

**Lemma 28.** Let $C := C_{A'_1 A'_2}$ be a 2-qubit Clifford unitary acting on the $A'_1 A'_2$ system. Then the bad channel's complementary $(\mathcal{N} \otimes_C \mathcal{M})^c$ is a channel from $A'_1$ to $E_1 E_2 A_2$, the good channel's complementary $(\mathcal{N} \otimes_C \mathcal{M})^c$ is a channel from $A'_2$ to $E_1 E_2$, and the following equalities hold:

$$ (a) \quad (\mathcal{N} \otimes_C \mathcal{M})^{c}_{A'_1 \to E_1 E_2 A_2}(\rho_{A'_1}) = \mathcal{N}^{c}_{A'_1 \to E_1} \otimes \mathcal{M}^{c}_{A'_2 \to E_2} \left( C \left( \rho_{A'_1} \otimes \Phi_{A'_2 A_2} \right) C^{\dagger} \right), $$

$$ (b) \quad (\mathcal{N} \otimes_C \mathcal{M})^{c}_{A'_2 \to E_1 E_2}(\rho_{A'_2}) = \mathcal{N}^{c}_{A'_1 \to E_1} \otimes \mathcal{M}^{c}_{A'_2 \to E_2} \left( C \left( \frac{1}{2} \otimes \rho_{A'_2} \right) C^{\dagger} \right). $$

*Proof.* Let $U_{A'_1 \to B_1 E_1}$ and $V_{A'_2 \to B_2 E_2}$ be Stinespring dilations of $\mathcal{N}_{A'_1 \to B_1}$ and $\mathcal{M}_{A'_2 \to B_2}$, respectively. Define isometries $W_{A'_1 \to B_1 B_2 E_1 E_2 A_2}$ and $W'_{A'_2 \to B_1 B_2 E_1 E_2 A_1}$, such that

$$ W(\rho_{A'_1})W^{\dagger} := U \otimes V \left( C \left( \rho_{A'_1} \otimes \Phi_{A'_2 A_2} \right) C^{\dagger} \right) U^{\dagger} \otimes V^{\dagger}, $$

$$ W'(\rho_{A'_2})W'^{\dagger} := U \otimes V \left( C \left( \Phi_{A_1 A'_1} \otimes \rho_{A'_2} \right) C^{\dagger} \right) U^{\dagger} \otimes V^{\dagger}. $$

It is easy to see that

$$ \mathrm{Tr}_{E_1 E_2 A_2} (W(\rho_{A'_1}) W^{\dagger}) = \mathcal{N} \otimes \mathcal{M} \left( C \left( \rho_{A_1} \otimes \frac{1}{2} \otimes \Phi_{A'_2 A_2} \right) C^{\dagger} \right) = (\mathcal{N} \otimes_C \mathcal{M})(\rho_{A'_1}), $$

$$ \mathrm{Tr}_{E_1 E_2} (W'(\rho_{A'_2}) W'^{\dagger}) = \mathcal{N} \otimes \mathcal{M} \left( C \left( \Phi_{A_1 A'_1} \otimes \rho_{A'_2} \right) C^{\dagger} \right) = (\mathcal{N} \otimes_C \mathcal{M})(\rho_{A'_2}). $$

Thus, isometries $W_{A'_1 \to B_1 B_2 E_1 E_2 A_2}$ and $W'_{A'_2 \to B_1 B_2 E_1 E_2 A_1}$ are Stinespring dilations of $(\mathcal{N} \otimes_C \mathcal{M})$ and $(\mathcal{N} \otimes_C \mathcal{M})$, respectively (see also [12, Theorem 1]). Therefore, by tracing out the channel outputs of $(\mathcal{N} \otimes_C \mathcal{M})$ and $(\mathcal{N} \otimes_C \mathcal{M})$, we get their respective complementary channels:

$$ (\mathcal{N} \otimes_C \mathcal{M})^c(\rho_{A'_1}) = \mathrm{Tr}_{B_1 B_2} (W(\rho_{A'_1}) W^{\dagger}) = \mathcal{N}^c \otimes \mathcal{M}^c \left( C \left( \rho_{A'_1} \otimes \Phi_{A'_2 A_2} \right) C^{\dagger} \right), $$

$$ (\mathcal{N} \otimes_C \mathcal{M})^c(\rho_{A'_2}) = \mathrm{Tr}_{A_1 B_1 B_2} (W'(\rho_{A'_2}) W'^{\dagger}) = \mathcal{N}^c \otimes \mathcal{M}^c \left( C \left( \frac{1}{2} \otimes \rho_{A'_2} \right) C^{\dagger} \right). $$

This concludes the proof of the lemma. $\square$

To prove Lemma 14, we need to show that two equivalent Clifford unitaries $C' \sim C'' \in C_2$ yield bad/good quantum channels with identical Rényi-Bhattacharyya parameter, when used for combining (then splitting) two quantum channels $\mathcal{N}$ and $\mathcal{M}$. Here, we first show this for the bad channel, and then for the good channel.

A.1 Bad Channel

We prove first the following lemma.

**Lemma 29.** Given $C''_{A'_1 A'_2} = C'_{A'_1 A'_2} (C^1_{A'_1} \otimes C^2_{A'_2})$, let

$$ \rho' := (\mathcal{N} \otimes_C \mathcal{M})^{c}_{A'_1 \to E_1 E_2 A_2} (\Phi_{A_1 A'_1}) \quad \text{and} \quad \rho'' := (\mathcal{N} \otimes_C \mathcal{M})^{c}_{A'_1 \to E_1 E_2 A_2} (\Phi_{A_1 A'_1}). $$

Then,

$$ \rho'' = C^1_{A_1} \otimes C^2_{A_2} (\rho') \bar{C}^1_{A_1} \otimes \bar{C}^2_{A_2}. $$
Proof. We have:

$$
\begin{align*}
\rho'' &= \mathcal{N}_{A'_1 \to E_1}^c \otimes \mathcal{M}_{A'_2 \to E_2}^c \left( C'_{A'_1 A'_2} (C_{A'_1}^1 \otimes C_{A'_2}^2) (\Phi_{A_1 A'_1} \otimes \Phi_{A'_2 A_2}) (C_{A'_1}^1 {}^\dagger \otimes C_{A'_2}^2 {}^\dagger) C'_{A'_1 A'_2} {}^\dagger \right) \\
&= \mathcal{N}_{A'_1 \to E_1}^c \otimes \mathcal{M}_{A'_2 \to E_2}^c \left( C'_{A'_1 A'_2} (C_{A'_1}^{1\top} \otimes C_{A'_2}^{2\top}) (\Phi_{A_1 A'_1} \otimes \Phi_{A'_2 A_2}) (\bar{C}_{A_1}^1 \otimes \bar{C}_{A_2}^2) C'_{A'_1 A'_2} {}^\dagger \right) \\
&= C_{A'_1}^{1\top} \otimes C_{A'_2}^{2\top} \left( \mathcal{N}_{A'_1 \to E_1}^c \otimes \mathcal{M}_{A'_2 \to E_2}^c \left( C'_{A'_1 A'_2} (\Phi_{A_1 A'_1} \otimes \Phi_{A'_2 A_2}) C'_{A'_1 A'_2} {}^\dagger \right) \right) \bar{C}_{A_1}^1 \otimes \bar{C}_{A_2}^2 \\
&= C_{A'_1}^{1\top} \otimes C_{A'_2}^{2\top} (\rho') \bar{C}_{A_1}^1 \otimes \bar{C}_{A_2}^2,
\end{align*}
$$

where the first equality follows from part (a) of Lemma 28 and second equality follows from
the relation $(\mathbb{1} \otimes Z)|\Phi\rangle = (Z^\top \otimes \mathbb{1})|\Phi\rangle$, for any matrix $Z$. $\square$

**Proof of** $R(\mathcal{N} \oplus_{C''} \mathcal{M}) = R(\mathcal{N} \oplus_{C'} \mathcal{M})$. By the definition of the Rényi-Bhattacharyya parameter, see (3), we have that

$$
R(\mathcal{N} \oplus_{C''} \mathcal{M}) = 2^{-\tilde{H}_2^{\downarrow}(A_1|E_1 E_2 A_2)_{\rho''}},
$$

where $\tilde{H}_2^{\downarrow}(A|B)_{\rho} = -\tilde{D}_2(\rho_{AB}||I \otimes \rho_B)$, with $\tilde{D}_2(\rho||\sigma) = \log \text{Tr}[(\sigma^{-\frac{1}{4}}\rho\sigma^{-\frac{1}{4}})^2]$ [13, 23]. We have the following unitary equivalence for $\tilde{D}_2(\rho||\sigma)$,

$$
\tilde{D}_2(\rho || \sigma) = \tilde{D}_2(U \rho U^{\dagger} || U \sigma U^{\dagger}). \qquad (19)
$$

Hence,

$$
\begin{align*}
\tilde{H}_2^{\downarrow}(A_1|E_1 E_2 A_2)_{\rho''} &= -\tilde{D}_2(\rho'' || \mathbb{1} \otimes \text{Tr}_{A_1}(\rho'')) \\
&= -\tilde{D}_2(C_{A_1}^{1\top} \otimes C_{A_2}^{2\top}(\rho') \bar{C}_{A_1}^1 \otimes \bar{C}_{A_2}^2 || \mathbb{1} \otimes (C_{A_2}^{2\top} \text{Tr}_{A_1}(\rho') \bar{C}_{A_2}^2)) \\
&= -\tilde{D}_2(\rho' || \mathbb{1} \otimes \text{Tr}_{A_1}(\rho')) \\
&= \tilde{H}_2^{\downarrow}(A_1|E_1 E_2 A_2)_{\rho'},
\end{align*}
$$

where the second equality follows from Lemma 29 and $\text{Tr}_{A_1}(\rho'') = C_{A_2}^{2\top} \text{Tr}_{A_1}(\rho') \bar{C}_{A_2}^2$, and the
third equality follows from the unitary equivalence above. Therefore, we get $R(\mathcal{N} \oplus_{C''} \mathcal{M}) =$
$R(\mathcal{N} \oplus_{C'} \mathcal{M})$, as desired. $\blacksquare$

A.2 Good Channel

**Lemma 30.** Given $C''_{A'_1 A'_2} = C'_{A'_1 A'_2} (C_{A'_1}^1 \otimes C_{A'_2}^2)$, let

$$
\rho' := (\mathcal{N} \oplus_{C'} \mathcal{M})_{A'_2 \to E_1 E_2}^c (\Phi_{A_2 A'_2}) \quad \text{and} \quad \rho'' := (\mathcal{N} \oplus_{C''} \mathcal{M})_{A'_2 \to E_1 E_2}^c (\Phi_{A_2 A'_2}).
$$

Then

$$
\rho'' = C_{A_2}^{2\top} \rho' \bar{C}_{A_2}^2.
$$

Proof. Similar to the proof of Lemma 29.

<figure><img src="image_8.png" /></figure>

**Proof of** $R(\mathcal{N} \oplus_{C''} \mathcal{M}) = R(\mathcal{N} \oplus_{C'} \mathcal{M})$. Using Lemma 30, it can be proved similar to the proof for bad channel in Subsection A.1 that $R(\mathcal{N} \oplus_{C''} \mathcal{M}) = R(\mathcal{N} \oplus_{C'} \mathcal{M})$. $\blacksquare$
# B Proof of Lemma 19

We have to prove that if $\mathcal{N}'$ and $\mathcal{N}''$ are CMP channels, such that

$$ \mathcal{N}'(\rho) \otimes \frac{I_X}{|X|} = C \left( \mathcal{N}''(\rho) \otimes \frac{I_X}{|X|} \right) C^{\dagger}, \qquad (20) $$

for some unitary $C$, then $(\mathcal{N}')^{\#} = (\mathcal{N}'')^{\#}$. We restrict ourselves to the case when $\mathcal{N}'$ and $\mathcal{N}''$ are Pauli channels, since the case of CMP channels follows in a similar manner, by introducing an auxiliary system providing a classical description of the Pauli channel being used. Hence, we may write $\mathcal{N}'(\rho) = \sum_{i=0}^3 p'_i \sigma_i \rho \sigma_i^{\dagger}$ and $\mathcal{N}''(\rho) = \sum_{i=0}^3 p''_i \sigma_i \rho \sigma_i^{\dagger}$, with $\sum_{i=0}^3 p'_i = \sum_{i=0}^3 p''_i = 1$. It follows that $\mathcal{N}'(\sigma_k) = \alpha'_k \sigma_k$ and $\mathcal{N}''(\sigma_k) = \alpha''_k \sigma_k$, where $\alpha'_0 = \alpha''_0 = 1$, and for $k = 1, 2, 3$, $\alpha'_k = p'_0 + p'_k - p'_k - p''_k$, $\alpha''_k = p''_0 + p''_k - p''_k - p''_k$, with $\{k_1, k_2\} = \{1, 2, 3\} \setminus \{k\}$. Using bold notation for vectors $\mathbf{p}' := (p'_0, p'_1, p'_2, p'_3)$, and similarly $\mathbf{p}''$, $\alpha'$, $\alpha''$, the above equalities rewrite as

$$ \alpha' = A\mathbf{p}' \text{ and } \alpha'' = A\mathbf{p}'' \qquad (21) $$

$$ \text{where } A := \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix} $$

Now, replacing $\rho$ by $\sigma_k$ in (20), we have that

$$ \alpha'_k \sigma_k \otimes I_X = C (\alpha''_k \sigma_k \otimes I_X) C^{\dagger}. \qquad (22) $$

Since the conjugate action of the unitary $C$ preserves the Hilbert-Schmidt norm of an operator, it follows that $\|\alpha'_k \sigma_k \otimes I_X\|_{HS} = \|\alpha''_k \sigma_k \otimes I_X\|_{HS}$, and therefore $|\alpha'_k| = |\alpha''_k|$.

**Case 1:** We first assume that $\alpha'_k = \alpha''_k, \forall k = 1, 2, 3$. In this case, using (21), it follows that $\mathbf{p}' = \mathbf{p}''$, and therefore $(\mathcal{N}')^{\#} = (\mathcal{N}'')^{\#}$.

**Case 2:** We consider now the case when $\alpha'_k \neq \alpha''_k$, for some $k = 1, 2, 3$. To address this case, we start by writing $C = \sum_{i=0}^3 \sigma_i \otimes C_i$, where $C_i$ are linear operators on the system $X$. Hence, (20) rewrites as

$$ \mathcal{N}'(\rho) \otimes \frac{I_X}{|X|} = \sum_{i,j} \left( \sigma_i \mathcal{N}''(\rho) \sigma_j^{\dagger} \right) \otimes \frac{C_i C_j^{\dagger}}{|X|}. \qquad (23) $$

Tracing out the $X$ system, we have

$$ \mathcal{N}'(\rho) = \sum_{i,j} \gamma_{i,j} \sigma_i \mathcal{N}''(\rho) \sigma_j^{\dagger}, \quad \text{where } \gamma_{i,j} = \frac{\mathrm{Tr}(C_i C_j^{\dagger})}{|X|}. \qquad (24) $$

We define $\gamma_i := \gamma_{i,i}$, and from (24) it follows that $\gamma_i := \gamma_{i,i} \in \mathbb{R}_+$. Replacing $\rho = \sigma_k$ in (24), we have that for all $k = 0, \dots, 3$,

$$ \alpha'_k \sigma_k = \alpha''_k \sum_i \gamma_i \sigma_i \sigma_k \sigma_i^{\dagger} + \alpha''_k \sum_{i,j, i \neq j} \gamma_{i,j} \sigma_i \sigma_k \sigma_j^{\dagger}. \qquad (25) $$

The left hand side of the above equation has only $\sigma_k$ term, so only $\sigma_k$ on the right hand side should survive as Pauli matrices form an orthogonal basis. It follows that either $\alpha'_k = \alpha''_k = 0$, or the terms of the second sum in the right hand side of the above equation necessarily cancel each other. In both cases, we have that

$$ \alpha'_k \sigma_k = \alpha''_k \sum_i \gamma_i \sigma_i \sigma_k \sigma_i^{\dagger} = \alpha''_k \lambda_k \sigma_k, \qquad (26) $$
$$ \text{and thus,} \qquad \alpha'_{k} = \lambda_{k} \alpha''_{k}, \qquad (27) $$

$$ \text{where,} \qquad \lambda_0 := \gamma_0 + \gamma_1 + \gamma_2 + \gamma_3 \qquad (28) $$

$$ \lambda_1 := \gamma_0 + \gamma_1 - \gamma_2 - \gamma_3 \qquad (29) $$

$$ \lambda_2 := \gamma_0 - \gamma_1 + \gamma_2 - \gamma_3 \qquad (30) $$

$$ \lambda_3 := \gamma_0 - \gamma_1 - \gamma_2 + \gamma_3 \qquad (31) $$

We also note that $\lambda_0 = 1$, since $\alpha'_0 = \alpha''_0 = 1$. We further rewrite (27) as

$$ \alpha' = \Lambda\alpha''. \qquad (32) $$

where $\Lambda = \text{diag}(\lambda_0, \lambda_1, \lambda_2, \lambda_3)$ is the square diagonal matrix with $\lambda_i$'s on the main diagonal. Plugging (21) into (32), and using $A^2 = 4I$, we get

$$ \mathbf{p}' = \frac{1}{4} A \Lambda A \mathbf{p}'' = \Gamma \mathbf{p}'' \qquad (33) $$

$$ \text{where } \Gamma := \frac{1}{4} A \Lambda A = \begin{pmatrix} \gamma_0 & \gamma_1 & \gamma_2 & \gamma_3 \\ \gamma_1 & \gamma_0 & \gamma_3 & \gamma_2 \\ \gamma_2 & \gamma_3 & \gamma_0 & \gamma_1 \\ \gamma_3 & \gamma_2 & \gamma_1 & \gamma_0 \end{pmatrix} $$

We now come back to our assumption, namely $\alpha'_k \neq \alpha''_k$, for some $k = 1, 2, 3$. Without loss of generality, we may assume that $\alpha'_1 \neq \alpha''_1$. Since $|\alpha'_1| = |\alpha''_1|$ and $\alpha'_1 = \lambda_1 \alpha''_1$, it follows that $\lambda_1 = -1$. Then, using (28) and (29), we have that $2(\gamma_0 + \gamma_1) = \lambda_0 + \lambda_1 = 0$, which implies

$$ \gamma_0 = \gamma_1 = 0, \qquad (34) $$

since they are non-negative. We proceed now with several sub-cases:

*Case 2.1:* either $\alpha'_2 \neq \alpha''_2$ or $\alpha'_3 \neq \alpha''_3$. Similarly to the derivation of (34), we get either $\gamma_2 = 0$ (in which case $\gamma_3 = 1$) or $\gamma_3 = 0$ (in which case $\gamma_2 = 1$). In either case $\Lambda$ is a permutation matrix, which implies that $(\mathcal{N}')^{\#} = (\mathcal{N}'')^{\#}$, as desired.

*Case 2.2:* $\alpha'_2 = \alpha''_2$ and $\alpha'_3 = \alpha''_3$, and either $\alpha'_2 = \alpha''_2 \neq 0$ or $\alpha'_3 = \alpha''_3 \neq 0$. Let us assume that $\alpha'_2 = \alpha''_2 \neq 0$. In this case, using (27), we have that $\lambda_2 = 1$, and from (30) it follows that $\gamma_2 - \gamma_3 = 1$. This implies $\gamma_2 = 1$ and $\gamma_3 = 0$, therefore $\Lambda$ is a permutation matrix, and thus $(\mathcal{N}')^{\#} = (\mathcal{N}'')^{\#}$, as desired.

*Case 2.3:* $\alpha'_2 = \alpha''_2 = 0$ and $\alpha'_3 = \alpha''_3 = 0$. Using $\alpha'_k = 2(p'_0 + p'_k) - 1, \forall k \neq 0$, we get $p'_2 = p'_3 = \frac{1}{2} - p'_0$, and similarly $p''_2 = p''_3 = \frac{1}{2} - p''_0$. Moreover, using (33) and the fact that $\gamma_2 + \gamma_3 = 1$, we get $p'_0 = p'_1 = p''_2 = p''_3$ and $p'_2 = p'_3 = p''_0 = p''_1$. This implies that $(\mathcal{N}')^{\#} = (\mathcal{N}'')^{\#}$, as desired.

This concludes the second case, and finishes the proof. $\square$

## C Proof of Proposition 20

Using the notation from Section 6.1, we shall identify $(\bar{P}_1, \times) \cong (\{0, 1, 2, 3\}, \oplus)$, where $\sigma_i \cong i$, $\forall i = 0, \dots, 3$, and thus assume that the classical channel $\mathcal{N}^{\#}$ – associated with a Pauli channel $\mathcal{N}(\rho) = \sum_{i=0}^{3} p_i \sigma_i \rho \sigma_i^{\dagger}$ – has input and output alphabet $\{0, 1, 2, 3\}$, with transition probabilities defined by $\mathcal{N}^{\#}(i | j) = p_{i \oplus j}$. Moreover, the automorphism $\Gamma = \Gamma(C)$ induced by the conjugate action of a two-qubit Clifford unitary $C$ on $\bar{P}_1 \times \bar{P}_1$, is identified to a linear permutation $\Gamma: \{0, 1, 2, 3\}^2 \to \{0, 1, 2, 3\}^2$, such that $C\sigma_{i,j}C^{\dagger} = \sigma_{\Gamma(i,j)}$. We shall also write $\Gamma = (\Gamma_1, \Gamma_2)$, with $\Gamma_i: \{0, 1, 2, 3\}^2 \to \{0, 1, 2, 3\}, i = 1, 2$.

It can be easily seen that it is enough to prove the statement of Proposition 20 for the case when $\mathcal{N}$ and $\mathcal{M}$ are Pauli channels. Let $\mathcal{N}(\rho) = \sum_{i=0}^{3} p_i \sigma_i \rho \sigma_i^{\dagger}$ and $\mathcal{M}(\rho) = \sum_{j=0}^{3} q_j \sigma_j \rho \sigma_j^{\dagger}$.
We start by proving (i).

$$
\begin{align*}
(\mathcal{N} \oplus \mathcal{M})(\rho_U) &= (\mathcal{N} \otimes \mathcal{M}) \left( C \left( \rho_U \otimes \frac{I_V}{2} \right) C^\dagger \right) \\
&= \sum_{i,j} p_i q_j \sigma_{i,j} C \left( \rho_U \otimes \frac{I_V}{2} \right) C^\dagger \sigma_{i,j}^\dagger \\
&= \sum_{i,j} r_{i,j} C \sigma_{\Gamma^{-1}(i,j)} \left( \rho_U \otimes \frac{I_V}{2} \right) \sigma_{\Gamma^{-1}(i,j)}^\dagger C^\dagger, \quad \text{where } r_{i,j} := p_i q_j \\
&= C \left( \sum_{i,j} r_{\Gamma(i,j)} \sigma_{i,j} \left( \rho_U \otimes \frac{I_V}{2} \right) \sigma_{i,j}^\dagger \right) C^\dagger \\
&= C \left( \sum_{i,j} r_{\Gamma(i,j)} \sigma_{i,j} \left( \rho_U \otimes \frac{I_V}{2} \right) \sigma_{i,j}^\dagger \right) C^\dagger \\
&= C \left( \sum_{i,j} r_{\Gamma(i,j)} \sigma_i \rho_U \sigma_i^\dagger \otimes \frac{I_V}{2} \right) C^\dagger \\
&= C \left( \sum_i s_i \sigma_i \rho_U \sigma_i^\dagger \otimes \frac{I_V}{2} \right) C^\dagger, \quad \text{where } s_i := \sum_j r_{\Gamma(i,j)}
\end{align*}
$$

where the fourth equality follows from the variable change (i, j) ↦→ Γ(i, j). Omitting the conjugate action of the unitary C and discarding the V system, we may further identify:

$$
(\mathcal{N} \oplus \mathcal{M})(\rho_U) = \sum_i s_i \sigma_i \rho_U \sigma_i^\dagger.
$$

Hence, the associated classical channel ($\mathcal{N} \oplus \mathcal{M})^{\#}$ is defined by the probability vector $\mathbf{s} =$
$(s_0, s_1, s_2, s_3)$, meaning that

$$
(\mathcal{N} \oplus \mathcal{M})^{\#}(i | j) = s_{i \oplus j}. \tag{35}
$$

On the other hand, we have:

$$
\begin{align*}
(\mathcal{N}^{\#} \oplus \mathcal{M}^{\#})(a, b | u) &= \frac{1}{4} \sum_{v} \mathcal{N}^{\#}(a | \Gamma_1(u, v)) \mathcal{M}^{\#}(b | \Gamma_2(u, v)) \\
&= \frac{1}{4} \sum_{v} p_{a \oplus \Gamma_1(u, v)} q_{b \oplus \Gamma_2(u, v)}.
\end{align*}
$$

Applying $\Gamma^{-1}$ on the channel output, we may identify $\mathcal{N}^{\#} \oplus \mathcal{M}^{\#}$ to a channel with output $(a', b') = \Gamma^{-1}(a, b)$, and transition probabilities given by:

$$
\begin{align*}
(\mathcal{N}^{\#} \oplus \mathcal{M}^{\#})(a', b' | u) &= \frac{1}{4} \sum_{v} p_{\Gamma_1(a', b') \oplus \Gamma_1(u, v)} q_{\Gamma_2(a', b') \oplus \Gamma_2(u, v)} \\
&= \frac{1}{4} \sum_{v} p_{\Gamma_1((a', b') \oplus (u, v))} q_{\Gamma_2((a', b') \oplus (u, v))} \\
&= \frac{1}{4} \sum_{v} p_{\Gamma_1(a' \oplus u, b' \oplus v)} q_{\Gamma_2(a' \oplus u, b' \oplus v)} \\
&= \frac{1}{4} \sum_{v} p_{\Gamma_1(a' \oplus u, v)} q_{\Gamma_2(a' \oplus u, v)} \\
&= \frac{1}{4} \sum_{v} r_{\Gamma(a' \oplus u, v)} \\
&= \frac{1}{4} s_{a' \oplus u}.
\end{align*}
$$
We can then discard the $b'$ output, since the channel transition probabilities do not depend on it, which gives a channel defined by transition probabilities:

$$ (\mathcal{N}^{\#} \oplus \mathcal{M}^{\#})(a' | u) = s_{a' \oplus u}. \qquad (36) $$

Finally, using (35) and (36), and noticing that omitting the conjugate action of the unitary $C$ and discarding the $V$ system in the derivation of (35) is equivalent to applying $\Gamma^{-1}$ on the channel output and discarding the $b'$ output in the derivation of (36), we conclude that $(\mathcal{N} \oplus \mathcal{M})^{\#} \equiv \mathcal{N}^{\#} \oplus \mathcal{M}^{\#}$

We prove now the (ii) statement. Similar to the derivations used for (i), we get:

$$ \begin{aligned} (\mathcal{N} \otimes \mathcal{M})(\rho_V) &= C \left( \sum_{i,j} r_{\Gamma(i,j)} \sigma_{i,j} (\Phi_{U'U} \otimes \rho_V) \sigma_{i,j}^{\dagger} \right) C^{\dagger} \\ &= C \left( \sum_{i,j} r_{\Gamma(i,j)} \left( (I_{U'} \otimes \sigma_i)(\Phi_{U'U}) (I_{U'} \otimes \sigma_i^{\dagger}) \right) \otimes (\sigma_j \rho_V \sigma_j^{\dagger}) \right) C^{\dagger} \end{aligned} \qquad (37) $$

Omitting the conjugate action of the unitary $C$, and expressing $(I_{U'} \otimes \sigma_i)(\Phi_{U'U}) (I_{U'} \otimes \sigma_i^{\dagger})$ in the Bell basis, $\{|i\rangle\}_{i=0,...,3} := \{\frac{|00\rangle+|11\rangle}{\sqrt{2}}, \frac{|01\rangle+|10\rangle}{\sqrt{2}}, \frac{|01\rangle-|10\rangle}{\sqrt{2}}, \frac{|00\rangle-|11\rangle}{\sqrt{2}}\}$, we get:

$$ (\mathcal{N} \oplus \mathcal{M})(\rho_V) = \sum_{i,j} r_{\Gamma(i,j)} |i\rangle\langle i| \otimes (\sigma_j \rho_V \sigma_j^{\dagger}). $$

Let $\lambda_i := \sum_j r_{\Gamma(i,j)}$ and $s_{i,j} := r_{\Gamma(i,j)} / \lambda_i$ (with $s_{i,j} := 0$ if $\lambda_i = 0$). Denoting by $S_i$ the Pauli channel defined by $S(\rho)_i = \sum_j s_{i,j} \sigma_j \rho_V \sigma_j^{\dagger}$, we may rewrite:

$$ (\mathcal{N} \oplus \mathcal{M})(\rho_V) = \sum_i \lambda_i |i\rangle\langle i| \otimes S_i(\rho_V). $$

Hence, $(\mathcal{N} \oplus \mathcal{M})^{\#}$ is the mixture of the channels $S_i^{\#}$, with $S_i^{\#}$ being used with probability $\lambda_i$, whose transition probabilities are given by:

$$ (\mathcal{N} \oplus \mathcal{M})^{\#}(i, j | k) = \lambda_i s_{i,j \oplus k} = r_{\Gamma(i,j \oplus k)}. \qquad (38) $$

On the other hand, we have:

$$ \begin{aligned} (\mathcal{N}^{\#} \oplus \mathcal{M}^{\#})(a, b, u | v) &= \frac{1}{4} \mathcal{N}^{\#}(a | \Gamma_1(u, v)) \mathcal{M}^{\#}(b | \Gamma_2(u, v)) \\ &= \frac{1}{4} p_{a \oplus \Gamma_1(u, v)} q_{b \oplus \Gamma_2(u, v)}. \end{aligned} $$

We apply $\Gamma^{-1}$ on the $(a, b)$ output of the channel, which is equivalent to omitting the conjugate action of the unitary $C$ in (37), and then identify $\mathcal{N}^{\#} \oplus \mathcal{M}^{\#}$ to a channel with output $(a', b', u)$, where $(a', b') = \Gamma^{-1}(a, b)$, and transition probabilities:

$$ \begin{aligned} (\mathcal{N}^{\#} \oplus \mathcal{M}^{\#})(a', b', u | v) &= \frac{1}{4} p_{\Gamma_1(a', b') \oplus \Gamma_1(u, v)} q_{\Gamma_2(a', b') \oplus \Gamma_2(u, v)} \\ &= \frac{1}{4} p_{\Gamma_1(a' \oplus u, b' \oplus v)} q_{\Gamma_2(a' \oplus u, b' \oplus v)} \\ &= \frac{1}{4} r_{\Gamma(a' \oplus u, b' \oplus v)}. \end{aligned} $$

We further perform a change of variable, replacing $(a', u)$ by $(a' \oplus u, u)$, which makes the above transition probability independent of $u$. We may then discard the $u$ output, and thus identify $\mathcal{N}^{\#} \oplus \mathcal{M}^{\#}$ to a channel with output $(a', b')$ and transition probabilities:

$$ (\mathcal{N}^{\#} \oplus \mathcal{M}^{\#})(a', b' | v) = r_{\Gamma(a', b' \oplus v)}. \qquad (39) $$

Finally, using (38) and (39), we conclude that $(\mathcal{N} \oplus \mathcal{M})^{\#} \equiv \mathcal{N}^{\#} \oplus \mathcal{M}^{\#}$. $\square$
D Proof of Lemma 23

We prove first the following lemma.

**Lemma 31.** For any classical channels $N, M$, with input alphabet $\bar{P}_1 \cong (\{0, 1, 2, 3\}, \oplus)$, and any linear permutation $\Gamma = (A, B) : \bar{P}_1 \times \bar{P}_1 \to \bar{P}_1 \times \bar{P}_1$, the following equality holds for any $d \in \bar{P}_1$:

$$Z_d(N \otimes_{\Gamma} M) = Z_{A(0,d)}(N)Z_{B(0,d)}(M).$$

*Proof.* According to Definition 22, for the channel $N \otimes_{\Gamma} M$, we have:

$$
\begin{align*}
Z((N \otimes_{\Gamma} M)_{v, v'}) &= \sum_{u, y_1, y_2} \sqrt{(N \otimes_{\Gamma} M)(y_1, y_2, u | v) (N \otimes_{\Gamma} M)(y_1, y_2, u | v')} \\
&= \frac{1}{4} \sum_{u, y_1, y_2} \sqrt{N(y_1 | A(u, v)) M(y_2 | B(u, v)) N(y_1 | A(u, v')) M(y_2 | B(u, v'))} \\
&= \frac{1}{4} \sum_{u, y_1, y_2} \sqrt{N(y_1 | A(u, v)) N(y_1 | A(u, v')) M(y_2 | B(u, v)) M(y_2 | B(u, v'))} \\
&= \frac{1}{4} \sum_u Z(N_{A(u,v), A(u,v')}) Z(M_{B(u,v), B(u,v')}).
\end{align*}
$$

Therefore,

$$
\begin{align*}
Z_d (N \otimes_{\Gamma} M) &= \frac{1}{4} \sum_v Z ((N \otimes_{\Gamma} M)_{v, v \oplus d}) \\
&= \frac{1}{16} \sum_{u,v} Z (N_{A(u,v), A(u,v \oplus d)}) Z (M_{B(u,v), B(u,v \oplus d)}) \\
&= \frac{1}{16} \sum_{u,v} Z (N_{A(u,v), A(u,v) \oplus A(0,d)}) Z (M_{B(u,v), B(u,v) \oplus B(0,d)}) \\
&= \frac{1}{16} \sum_a Z (N_{a, a \oplus A(0,d)}) \sum_b Z (M_{b, b \oplus B(0,d)}) \\
&= Z_{A(0,d)}(N)Z_{B(0,d)}(M),
\end{align*}
$$

where the third equality follows from the linearity of the permutation $\Gamma = (A, B)$, and the fourth equality follows from the change of basis for the summation from $(u, v)$ to $(a, b) := (A(u, v), B(u, v))$. $\square$

Throughout the remaining of this section, we shall denote by $u := [u_1, u_2]$ the binary representation of a given $u \in \bar{P}_1 \cong \{0, 1, 2, 3\}$, where $u_1, u_2 \in \{0, 1\}$ and $u_2$ is the least significant bit.

**Lemma 32.** Let $\Gamma_{i,j} := \Gamma(L_{i,j}) : \bar{P}_1 \times \bar{P}_1 \to \bar{P}_1 \times \bar{P}_1$ be the permutation defined by the conjugate action of $L_{i,j} \in \mathcal{L}$, where $\mathcal{L}$ is the set of two-qubit Clifford gates defined in Section 4 (Fig. 3). Then $\Gamma_{i,j} = (A_i, B_j), \forall 1 \le i, j \le 3$, with $A_i, B_j : \bar{P}_1 \times \bar{P}_1 \to \bar{P}_1$ given by:

$$
\begin{align*}
A_1(u, v) &= [u_1, u_2 \oplus v_1 \oplus v_2], & B_1(u, v) &= [u_1 \oplus v_1, u_1 \oplus v_2] \\
A_2(u, v) &= [u_2 \oplus v_1 \oplus v_2, u_1], & B_2(u, v) &= [u_1 \oplus v_1, v_1 \oplus v_2] \\
A_3(u, v) &= [u_1 \oplus u_2 \oplus v_1 \oplus v_2, u_2 \oplus v_1 \oplus v_2] & B_3(u, v) &= [v_1 \oplus v_2, u_1 \oplus v_2]
\end{align*}
$$

where $u$ and $v$ inputs are represented in binary form, $u := [u_1, u_2]$ and $v := [v_1, v_2]$, with $u_1, u_2, v_1, v_2 \in \{0, 1\}$ ($\Gamma_{i,j}$ permutations are also depicted in Fig. 6).
<figure><img src="image_9.png" /><figcaption>Figure 6: Elements of the set $\Gamma(\mathcal{L})$</figcaption></figure>

*Proof.* Recall from Section 4, that $L_{i,j} = (C' \otimes C'')_{\text{CNOT}_{21}}$, where $C' \in \{I, \sqrt{Z}, \sqrt{Y}\}$, and $C'' \in \{I, \sqrt{X}, \sqrt{Y}\}$. Recall also that by identifying $\bar{P}_1 \cong \{0, 1, 2, 3\}$, we have $I = \sigma_0 \cong 0$, $X = \sigma_1 \cong 1$, $Y = \sigma_2 \cong 2$, $Z = \sigma_3 \cong 3$. The conjugate action of $\sqrt{X}$ on $\bar{P}_1$, fixes $I$ and $X$, and permutes $Y$ and $Z$. Hence, the corresponding permutation on $\bar{P}_1 \cong \{0, 1, 2, 3\}$, can be written as $(0, 1, 3, 2)$. Similarly, the conjugate action of $\sqrt{Y}$ and $\sqrt{Z}$ induces the permutations $(0, 3, 2, 1)$ and $(0, 2, 1, 3)$, respectively. Replacing $u \in \{0, 1, 2, 3\}$ by its binary representation $[u_1, u_2]$, we may write:

$$ 
\begin{align} 
\sqrt{X} & : [u_1, u_2] \mapsto [u_1, u_1 \oplus u_2] \notag \\ 
\sqrt{Y} & : [u_1, u_2] \mapsto [u_1 \oplus u_2, u_2] \tag{40} \\ 
\sqrt{Z} & : [u_1, u_2] \mapsto [u_2, u_1] \notag 
\end{align} 
$$

Moreover, the permutation induced by the conjugate action of the CNOT$_{21}$ gate is the linear permutation on $\bar{P}_1 \times \bar{P}_1$ such that:

$$ 
\begin{align} 
\text{CNOT}_{21} & : (X, I) \mapsto (X, I), \quad (I, X) \mapsto (X, X) \notag \\ 
& (Z, I) \mapsto (Z, Z), \quad (I, Z) \mapsto (I, Z) \notag \\ 
\Rightarrow \text{CNOT}_{21} & : ([u_1, u_2], [v_1, v_2]) \mapsto ([u_1, u_2 \oplus v_1 \oplus v_2], [u_1 \oplus v_1, u_1 \oplus v_2]). \tag{41} 
\end{align} 
$$

Finally, using (40) and (41), it can be easily verified that $\Gamma_{i,j} = (A_i, B_j)$, $\forall 1 \le i, j \le 3$, with $A_i$ and $B_j$ as given in the lemma. $\square$

**Proof of Lemma 23.** To simplify notation, let $W := W^\#$ be the classical counterpart of the CMP channel $W$ from Lemma 23. Applying Lemma 31 and Lemma 32, we may express $Z_d(W \otimes \Gamma_{i,j} W)$ as a function of $(Z_1(W), Z_2(W), Z_3(W))$, for any $\Gamma_{i,j} \in \Gamma(\mathcal{L})$ and any $d = 1, 2, 3$ (recall that $Z_0(W) = 1$). The corresponding expressions are given in Table 1.
<table><caption>Table 1: $Z_d(W \otimes_{\Gamma_{i,j}} W)$ as a function of $(Z_1(W), Z_2(W), Z_3(W))$</caption><thead><tr><th>(i, j)</th><th>Z<sub>1</sub>(W) ⊗<sub>Γ<sub>i,j</sub></sub> W)</th><th>Z<sub>2</sub>(W) ⊗<sub>Γ<sub>i,j</sub></sub> W)</th><th>Z<sub>3</sub>(W) ⊗<sub>Γ<sub>i,j</sub></sub> W)</th></tr></thead><tbody><tr><td>(1, 1)</td><td>Z<sub>1</sub>(W)<sup>2</sup></td><td>Z<sub>1</sub>(W)Z<sub>2</sub>(W)</td><td>Z<sub>3</sub>(W)</td></tr><tr><td>(1, 2)</td><td>Z<sub>1</sub>(W)<sup>2</sup></td><td>Z<sub>1</sub>(W)Z<sub>3</sub>(W)</td><td>Z<sub>2</sub>(W)</td></tr><tr><td>(1, 3)</td><td>Z<sub>1</sub>(W)Z<sub>3</sub>(W)</td><td>Z<sub>1</sub>(W)Z<sub>2</sub>(W)</td><td>Z<sub>1</sub>(W)</td></tr><tr><td>(2, 1)</td><td>Z<sub>1</sub>(W)Z<sub>2</sub>(W)</td><td>Z<sub>2</sub>(W)<sup>2</sup></td><td>Z<sub>3</sub>(W)</td></tr><tr><td>(2, 2)</td><td>Z<sub>1</sub>(W)Z<sub>2</sub>(W)</td><td>Z<sub>2</sub>(W)Z<sub>3</sub>(W)</td><td>Z<sub>2</sub>(W)</td></tr><tr><td>(2, 3)</td><td>Z<sub>2</sub>(W)Z<sub>3</sub>(W)</td><td>Z<sub>2</sub>(W)<sup>2</sup></td><td>Z<sub>1</sub>(W)</td></tr><tr><td>(3, 1)</td><td>Z<sub>1</sub>(W)Z<sub>3</sub>(W)</td><td>Z<sub>2</sub>(W)Z<sub>3</sub>(W)</td><td>Z<sub>3</sub>(W)</td></tr><tr><td>(3, 2)</td><td>Z<sub>1</sub>(W)Z<sub>3</sub>(W)</td><td>Z<sub>3</sub>(W)<sup>2</sup></td><td>Z<sub>2</sub>(W)</td></tr><tr><td>(3, 3)</td><td>Z<sub>3</sub>(W)<sup>2</sup></td><td>Z<sub>2</sub>(W)Z<sub>3</sub>(W)</td><td>Z<sub>1</sub>(W)</td></tr></tbody></table>

Hence,

$$ 
\begin{aligned}
\sum_{\Gamma \in \Gamma(\mathcal{L})} Z(W \otimes_{\Gamma} W) &= \frac{1}{3} \sum_{\Gamma \in \Gamma(\mathcal{L})} \sum_{d=1}^{3} Z_d(W \otimes_{\Gamma} W) \\
&= \sum_{d=1}^{3} Z_1(W) + \frac{2}{3} \left( \sum_{d=1}^{3} Z_1(W) \right)^2 \\
&= 3Z(W) + 6Z(W)^2,
\end{aligned}
$$

and therefore,

$$ \mathbb{E}_{\Gamma \in \Gamma(\mathcal{L})} Z(W \otimes_{\Gamma} W) = \frac{1}{9} \sum_{\Gamma \in \Gamma(\mathcal{L})} Z(W \otimes_{\Gamma} W) = \frac{1}{3} Z(W) + \frac{2}{3} Z(W)^2. $$

The case $\Gamma \in \mathcal{R}$ can be derived in a similar way. Alternatively, one can directly verify that $\mathbb{E}_{\Gamma \in \Gamma(\mathcal{L})} Z(W \otimes_{\Gamma} W) = \mathbb{E}_{\Gamma \in \Gamma(\mathcal{R})} Z(W \otimes_{\Gamma} W)$, similarly to the proof of Lemma 15 in the quantum case. $\square$

## E Proof of Lemma 24

Using Table 1 from Appendix D, for $\Gamma \in \Gamma(S) = \{\Gamma_{1,3}, \Gamma_{2,2}, \Gamma_{3,1}\}$, we get

$$ 
\begin{aligned}
\mathbb{E}_{\Gamma \in \Gamma(S)} Z(W \otimes_{\Gamma} W) &= \frac{1}{3} \sum_{\Gamma \in \Gamma(S)} Z(W \otimes_{\Gamma} W) \\
&= \frac{1}{9} \sum_{\Gamma \in \Gamma(S)} \sum_{1 \le d \le 3} Z_d(W \otimes_{\Gamma} W) \\
&= \frac{1}{9} \sum_{1 \le d \le 3} Z_d(W) + \frac{2}{9} \sum_{1 \le d' \ne d'' \le 3} Z_{d'}(W) Z_{d''}(W) \\
&\le \frac{1}{3} Z(W) + \frac{2}{3} Z(W)^2,
\end{aligned}
$$

where, using $Z(W) = (Z_1(W) + Z_2(W) + Z_3(W))/3$, it is easily seen that the last inequality is equivalent to $Z_1(W)Z_2(W) + Z_1(W)Z_3(W) + Z_2(W)Z_3(W) \le Z_1(W)^2 + Z_2(W)^2 + Z_3(W)^2$, which follows from $Z_i(W)Z_j(W) \le (Z_i(W)^2 + Z_j(W)^2)/2$. $\square$

## F Proof of Lemma 25

We prove first the following lemma.
**Lemma 33.** For any classical channels $N, M$, with input alphabet $\bar{P}_1 \cong (\{0, 1, 2, 3\}, \oplus)$, and any linear permutation $\Gamma = (A, B) : \bar{P}_1 \times \bar{P}_1 \to \bar{P}_1 \times \bar{P}_1$, the following inequality holds for any $d \in \bar{P}_1$:

$$Z_d(N \oplus_{\Gamma} M) \leq \sum_{d' \in \bar{P}_1} Z_{A(d,d')}(N) Z_{B(d,d')}(M).$$

*Proof.* According to Definition 22, for the channel $N \oplus_{\Gamma} M$, we have:

$$
\begin{align*}
Z((N \oplus_{\Gamma} M)_{u, u'}) &= \sum_{y_1, y_2} \sqrt{(N \oplus_{\Gamma} M)(y_1, y_2 | u) (N \oplus_{\Gamma} M)(y_1, y_2 | u')} \\
&= \frac{1}{4} \sum_{y_1, y_2} \sqrt{\sum_v N(y_1 | A(u, v)) M(y_2 | B(u, v)) \sum_{v'} N(y_1 | A(u', v')) M(y_2 | B(u', v'))} \\
&\le \frac{1}{4} \sum_{v, v'} \sum_{y_1, y_2} \sqrt{N(y_1 | A(u, v)) M(y_2 | B(u, v)) N(y_1 | A(u', v')) M(y_2 | B(u', v'))} \\
&= \frac{1}{4} \sum_{v, v'} \sum_{y_1, y_2} \sqrt{N(y_1 | A(u, v)) N(y_1 | A(u', v')) M(y_2 | B(u, v)) M(y_2 | B(u', v'))} \\
&= \frac{1}{4} \sum_{v, v'} Z(N_{A(u,v), A(u',v')}) Z(M_{B(u,v), B(u',v')}),
\end{align*}
$$

where the inequality above follows from $\sqrt{\sum_v x_v} \le \sum_v \sqrt{x_v}$. Therefore,

$$
\begin{align*}
Z_d (N \oplus_{\Gamma} M) &= \frac{1}{4} \sum_u Z ((N \oplus_{\Gamma} M)_{u, u \oplus d}) \\
&\le \frac{1}{16} \sum_{u, v, v'} Z (N_{A(u,v), A(u \oplus d, v')}) Z (M_{B(u,v), B(u \oplus d, v')}) \\
&= \frac{1}{16} \sum_{u, v, d'} Z (N_{A(u,v), A(u \oplus d, v \oplus d')}) Z (M_{B(u,v), B(u \oplus d, v \oplus d')}) \\
&= \frac{1}{16} \sum_{u, v, d'} Z (N_{A(u,v), A(u,v) \oplus A(d,d')}) Z (M_{B(u,v), B(u,v) \oplus B(d,d')}) \\
&= \frac{1}{16} \sum_{d'} \sum_a Z (N_{a, a \oplus A(d,d')}) \sum_b Z (M_{b, b \oplus B(d,d')}) \\
&= \sum_{d'} Z_{A(d,d')}(N) Z_{B(d,d')}(M),
\end{align*}
$$

where the third to last equality follows from the linearity of the permutation $\Gamma = (A, B)$, and the second to last follows from the change of basis for the summation from $(u, v)$ to $(a, b) := (A(u, v), B(u, v))$. $\square$

**Proof of Lemma 25.** To simplify notation, let $W := W^\#)$ be the classical counterpart of the CMP channel $W$ from Lemma 25. Using Lemma 33, we have

$$Z_d(W \oplus_{\Gamma} W) \leq \sum_{d' \in \bar{P}_1} Z_{A(d,d')}(W) Z_{B(d,d')}(W).$$

For $d \neq 0$, $A(d, d')$ and $B(d, d')$ cannot be simultaneously zero (recall that $Z_0(W) = 1$), and therefore we get $Z_{A(d,d')}(W)Z_{B(d,d')}(W) \le \bar{Z}(W)$. Hence, $Z_d(W \oplus_{\Gamma} W) \le 4\bar{Z}(W)$, $\forall d = 1, 2, 3$, which implies $\bar{Z}(W \oplus_{\Gamma} W) \le 4\bar{Z}(W)$, as desired. Finally, we have

$$Z(W \oplus_{\Gamma} W) \le \bar{Z}(W \oplus_{\Gamma} W) \le 4\bar{Z}(W) \le 12Z(W),$$

which proves the second inequality of the lemma. $\square$
G Proof of Proposition 27

We proceed first with several lemmas. In the following, the notation $x = x(\cdot)$ means that the value of $x$ depends only on the list of variables $(\cdot)$ enclosed between parentheses.

**Lemma 34.** (i) For any permutation $\Gamma \in \Gamma(S)$, there exist $\delta_1 = \delta_1(\Gamma)$, $\delta_2 = \delta_2(\Gamma)$, $\delta_3 = \delta_3(\Gamma)$, such that $\{\delta_1, \delta_2, \delta_3\} = \{1, 2, 3\}$, and

$$
\begin{align*}
Z_3(W \otimes_{\Gamma} W) &= Z_{\delta_3}(W) \\
Z_2(W \otimes_{\Gamma} W) &= Z_{\delta_3}(W)Z_{\delta_2}(W) \\
Z_1(W \otimes_{\Gamma} W) &= Z_{\delta_3}(W)Z_{\delta_1}(W),
\end{align*}
$$

and the above equalities hold for any channel $W$.

(ii) For any $d \in \{1, 2, 3\}$, there exists exactly one permutation $\Gamma \in \Gamma(S)$, such that $\delta_3(\Gamma) = d$.

Proof. Follows from Table 1 in Appendix D, wherein $\Gamma(S) = \{\Gamma_{1,3}, \Gamma_{2,2}, \Gamma_{3,1}\}$. Precisely, we have $\delta_3(\Gamma_{1,3}) = 1$, $\delta_3(\Gamma_{2,2}) = 2$, $\delta_3(\Gamma_{3,1}) = 3$. $\square$

**Lemma 35.** There exist a constant $\kappa > 1$ and $\delta = \delta(W) \in \{1, 2, 3\}$, such that for any $\Gamma \in \Gamma(S)$ and any $d \in \{1, 2, 3\}$, the following equality holds

$$
Z_d(W \otimes_{\Gamma} W) \le \kappa Z_{\delta}(W).
$$

Proof. Follows from Lemma 25, for $\kappa = 4$ and $\delta = \delta(W) := \argmax_{d=1,2,3} Z_d(W)$. $\square$

We shall also use the following lemma (known as Hoeffding's inequality) providing an upper bound for the probability that the mean of $n$ independent random variables falls below its expected value mean by a positive number.

**Lemma 36 ([11, Theorem 1]).** Let $X_1, X_2, \dots, X_n$ be independent random variables such that $0 \le X_i \le 1$, for any $i = 1, \dots, n$. Let $\bar{X} := \frac{1}{n} \sum_{i=1}^n X_i$, and $\mu = \mathbb{E}(\bar{X})$. Then, for any $0 < t < \mu$,

$$
\Pr\{\bar{X} \le \mu - t\} \le e^{-2nt^2}.
$$

Now, let $\Gamma(S)^\infty$ be the infinite Cartesian product of countable many copies of $\Gamma(S)$. It is endowed with an infinite product probability measure [10], denoted by $P$, where the uniform probability measure is taken on each copy of $\Gamma(S)$. For our purposes, an infinite sequence $\Gamma \in \Gamma(S)^\infty$ should be written as $\Gamma := \{\Gamma, \Gamma_{i_1 \cdots i_n} \mid n > 0, i_1 \cdots i_n \in \{0, 1\}^n\}$ (this is always possible, since the set of indices is countable). We further define a sequence of independent and identically distributed (i.i.d) Bernoulli random variables on $\Gamma(S)^\infty$, denoted $\Delta^{i_1 \cdots i_n}$, $n \ge 0$, $i_1 \cdots i_n \in \{0, 1\}^n$,

$$
\Delta^{i_1 \cdots i_n}(\mathbf{\Gamma}) := \mathbf{1}_{\{\delta_3(\Gamma_{i_1 \cdots i_n}) \in \{1,2\}\}},
$$

that is, $\Delta^{i_1 \cdots i_n}(\Gamma)$ is equal to 1, if $\delta_3(\Gamma_{i_1 \cdots i_n}) \in \{1, 2\}$, and equal to 0, if $\delta_3(\Gamma_{i_1 \cdots i_n}) = 3$. Note that $\Delta^{i_1 \cdots i_n}(\Gamma)$ does actually only depend on the $\Gamma_{i_1 \cdots i_n}$ element of $\Gamma$ (here, $n$ and $i_1 \cdots i_n$ are fixed). From Lemma 34 (ii), it follows that $\mathbb{E}(\Delta^{i_1 \cdots i_n}) = 2/3, \forall n \ge 0, \forall i_1 \cdots i_n \in \{0, 1\}^n$.

For $0 < \gamma < 2/3$ and $m > 0$, we define

$$
\Pi_m(\gamma) := \left\{ \Gamma \in \Gamma(S)^\infty \mid \sum_{i_1 \cdots i_{m-1}} \Delta^{i_1 \cdots i_{m-1}}(\Gamma) \ge \left(\frac{2}{3} - \gamma\right) 2^{m-1} \right\} \quad (42)
$$

$$
\bar{\Pi}_m(\gamma) := \bigcap_{n \ge m} \Pi_n(\gamma) \qquad (43)
$$

The sum in (42) comprises all the terms $\Delta^{i_1 \cdots i_{m-1} i_m}(\Gamma)$, with $i_1 \cdots i_{m-1} \in \{0, 1\}^{m-1}$ and $i_m = 1$ (here, $m$ is fixed). Thus, $\Pi_m(\gamma)$ is defined by requiring that at least a fraction of $(2/3 - \gamma)$ of $\Delta^{i_1 \cdots i_{m-1} i_m}$ variables are equal to 1, where $i_m = 1$. In (43), the above condition must hold for any $n \ge m$.
**Lemma 37.** For any $0 < \gamma < 2/3$ and $m > 0$,

$$P(\bar{\Pi}_m(\gamma)) \geq 2 - \frac{1}{1 - e^{-\gamma^2 2^m}}. \quad (44)$$

*Proof.* By Lemma 36, $P(\Pi_m(\gamma)) \geq 1 - e^{-\gamma^2 2^m}$. Therefore, we have

$$\begin{aligned}
P(\bar{\Pi}_m(\gamma)) &\geq 1 - \sum_{n \geq m} e^{-\gamma^2 2^n} \\
&= 1 - \sum_{n \geq 0} (e^{-\gamma^2 2^m})^{2^n} \\
&\geq 1 - \sum_{n \geq 1} (e^{-\gamma^2 2^m})^n \\
&= 1 - \left( \frac{1}{1 - e^{-\gamma^2 2^m}} - 1 \right) \\
&= 2 - \frac{1}{1 - e^{-\gamma^2 2^m}}.
\end{aligned}$$

□

Note that the right hand side term in (44) converges to 1 as $m$ goes to infinity. Hence, for $\varepsilon > 0$, we denote by $m(\gamma, \varepsilon)$ the smallest $m$ value, such that $2 - \frac{1}{1 - e^{-\gamma^2 2^m}} \geq 1 - \varepsilon$. It follows that $P(\bar{\Pi}_{m(\gamma, \varepsilon)}(\gamma)) \geq 1 - \varepsilon$.

In the following, we fix once for all some $\gamma$ value, such that $0 < \gamma < 2/3$. The value of $\gamma$ will not matter for any of what we do here, we only need $(2/3 - \gamma)$ to be positive. We proceed now with the proof of Proposition 27.

**Proof of Proposition 27.** Let $\Omega := \{0, 1\}^\infty$ denote the set of infinite binary sequences $\omega := (\omega_1\omega_2\cdots) \in \{0, 1\}^\infty$. Hence, $\Omega$ can be endowed with an infinite product probability measure, by taking the uniform probability measure on each $\omega_n$ component. We denote this probability measure by $P$ (the notation is the same as for the probability measure on $\Gamma(S)^\infty$, but no confusion should arise, since the sample spaces are different).

Let $\varepsilon > 0$ and fix any $\Gamma \in \Gamma(S)^\infty_{\text{pol}} \cap \bar{\Pi}_{m(\gamma, \varepsilon)}(\gamma)$. Given $\Gamma$, the polarization process can be formally described as a random process on the probability space $\Omega$ [1]. Precisely, for any $\omega = (\omega_1\omega_2\cdots) \in \Omega$ and $n > 0$, we define

$$\begin{aligned}
Z^{[n]}(\omega) &:= Z(W^{(\omega_1 \cdots \omega_n)}) \\
Z_d^{[n]}(\omega) &:= Z_d(W^{(\omega_1 \cdots \omega_n)}), \quad \forall d \in \{1, 2, 3\}
\end{aligned}$$

Note that $W^{(\omega_1 \cdots \omega_n)}$ is recursively defined as in (18), through the implicit assumption of using the channel combining permutations in the given sequence $\Gamma$. For $n = 0$, we set $Z^{[0]}(\omega) := Z(W)$ and $Z_d^{[0]}(\omega) := Z_d(W)$.

For $\zeta > 0$ and $m \geq 0$, we define

$$T_m(\zeta) := \{\omega \in \Omega \mid Z_d^{[n]}(\omega) \leq \zeta, \forall d = 1, 2, 3, \forall n \geq m\}.$$

Hence, for $\omega \in T_m(\zeta)$, $d \in \{1, 2, 3\}$, and $n > m$, we may write

$$Z_d^{[n]}(\omega) = \frac{Z_{d_n}^{[n]}(\omega)}{Z_{d_{n-1}}^{[n-1]}(\omega)} \frac{Z_{d_{n-1}}^{[n-1]}(\omega)}{Z_{d_{n-2}}^{[n-2]}(\omega)} \cdots \frac{Z_{d_{m+1}}^{[m+1]}(\omega)}{Z_{d_m}^{[m]}(\omega)} Z_{d_m}^{[m]}(\omega), \quad (45)$$
where $d_n := d$, and $d_{n-1}, \dots, d_m$ are defined as explained below. Recall that $Z_d^{[k]}(\omega) := Z_d(W^{(\omega_1 \cdots \omega_k)})$, and for $k \in \{n, n-1, \dots, m+1\}$, we have

$$W^{(\omega_1 \cdots \omega_k)} = \begin{cases} W^{(\omega_1 \cdots \omega_{k-1})} \oplus \Gamma_{\omega_1 \cdots \omega_{k-1}} W^{(\omega_1 \cdots \omega_{k-1})}, & \text{if } \omega_k = 0 \\ W^{(\omega_1 \cdots \omega_{k-1})} \otimes \Gamma_{\omega_1 \cdots \omega_{k-1}} W^{(\omega_1 \cdots \omega_{k-1})}, & \text{if } \omega_k = 1 \end{cases}$$

Hence, if $\omega_k = 0$, we set $d_{k-1} := \delta(W^{(\omega_1 \cdots \omega_{k-1})})$ from Lemma 35, such that we have

$$\frac{Z_{d_k}^{[k]}(\omega)}{Z_{d_{k-1}}^{[k-1]}(\omega)} \le \kappa, \text{ if } \omega_k = 0. \quad (46)$$

If $\omega_k = 1$, we set $d_{k-1} := \delta_3(\Gamma_{\omega_1 \cdots \omega_{k-1}})$ from Lemma 34, such that we have

$$\frac{Z_{d_k}^{[k]}(\omega)}{Z_{d_{k-1}}^{[k-1]}(\omega)} = 1, \quad \text{if } \omega_k = 1 \text{ and } d_k = 3. \quad (47)$$

$$\frac{Z_{d_k}^{[k]}(\omega)}{Z_{d_{k-1}}^{[k-1]}(\omega)} \le \zeta, \quad \text{if } \omega_k = 1 \text{ and } d_k \in \{1, 2\}. \quad (48)$$

Let $A_{m,n}(\omega) := \{k \in \{m+1, \dots, n\} \mid \omega_k = 1\}$, and $B_{m,n}(\omega) := \{k \in \{m+1, \dots, n\} \mid \omega_k = 1\}$ and $d_k \in \{1, 2\}$. Using (45), (46)–(48), for $\omega \in T_m(\zeta)$ and $n > m$, we get:

$$Z_d^{[n]}(\omega) \le \kappa^{(n-m)-|A_{m,n}(\omega)|\zeta|B_{m,n}(\omega)|\zeta}. \quad (49)$$

Now, we want to upper-bound the right hand side term of the above inequality, by providing lower-bounds for the $|A_{m,n}(\omega)|$ and $|B_{m,n}(\omega)|$ values.

**lower-bound:** Let $A^{[k]}(\omega) := \omega_k$, hence $|A_{m,n}(\omega)| = \sum_{k=m+1}^n A^{[k]}(\omega)$. Fix any $\alpha \in (0, 1/2)$, and let

$$A_{m,n}(\alpha) := \left\{ \omega \in \Omega \mid \sum_{k=m+1}^{n} A^{[k]}(\omega) \ge \left(\frac{1}{2} - \alpha\right)(n-m) \right\}.$$

Hence, for any $\omega \in A_{m,n}(\alpha)$,

$$|A_{m,n}(\omega)| \ge (1/2 - \alpha)(n - m). \quad (50)$$

Moreover, by Lemma 36, $P(A_{m,n}(\alpha)) \ge 1 - e^{-2\alpha^2(n-m)}$.

**lower-bound:** First, note that $d_k$ is defined depending on $\omega_{k+1}$ value. Hence, we may write

$$\begin{aligned} B_{m,n}(\omega) &= \{k \in \{m+1, \dots, n\} \mid \omega_k = 1 \text{ and } d_k \in \{1, 2\}\} \\ &\supset \{k \in \{m+1, \dots, n-1\} \mid \omega_k = 1, \omega_{k+1} = 1, \text{ and } d_k \in \{1, 2\}\} \\ &= \{k \in \{m+1, \dots, n-1\} \mid \omega_k = 1, \omega_{k+1} = 1, \text{ and } \delta_3(\Gamma_{\omega_1 \cdots \omega_k}) \in \{1, 2\}\}. \end{aligned}$$

Let $B^{[k]}$ be the Bernoulli random variable on $\Omega$, defined by

$$B^{[k]}(\omega) := \mathbf{1}_{\{\omega_{k+1}=1\}} \mathbf{1}_{\{\omega_k=1\}} \mathbf{1}_{\{\delta_3(\Gamma_{\omega_1 \cdots \omega_k}) \in \{1,2\}\}}.$$

The expected value of $B^{[k]}$ is given by

$$\mathbb{E}B^{[k]} = \frac{1}{2^{k+1}} \sum_{i_1 \cdots i_k i_{k+1}} \mathbf{1}_{\{i_{k+1}=1\}} \mathbf{1}_{\{i_k=1\}} \mathbf{1}_{\{\delta_3(\Gamma_{i_1 \cdots i_k}) \in \{1,2\}\}}$$
$$
\begin{align*}
&= \frac{1}{2^{k+1}} \sum_{i_1 \cdots i_{k-1}} \mathbf{1}_{\{\delta_3(\Gamma_{i_1 \cdots i_{k-1}}) \in \{1,2\}\}} \\
&= \frac{1}{2^{k+1}} \sum_{i_1 \cdots i_{k-1}} \Delta^{i_1 \cdots i_{k-1} 1}(\Gamma).
\end{align*}
$$

Since $\Gamma \in \bar{\Pi}_{m(\gamma, \epsilon)}(\gamma)$, for $k > m \ge m(\gamma, \epsilon)$, we get

$$
\mathbb{E}B^{[k]} \geq \gamma_0 := \frac{1}{4} \left( \frac{2}{3} - \gamma \right).
$$

Let $\mathcal{K}(m, n) := \{k \in m + 1, \dots, n - 1 \mid k = m + 1 \bmod 2\}$, the set of integers $m + 1, m + 3, \dots$
comprised between $m + 1$ and $n - 1$. Random variables $B^{[k]}, k \in \mathcal{K}(m, n)$, are independent, and
the expected value of their mean, denoted $\mathbb{E}B_{\mathcal{K}(m,n)} := \frac{1}{|\mathcal{K}(m,n)|} \mathbb{E}B^{[k]}$, satisfies $\mathbb{E}B_{\mathcal{K}(m,n)} \ge \gamma_0$.
Fix any $\beta \in (0, \gamma_0)$, and let

$$
\mathcal{B}_{m,n}(\beta) := \left\{ \omega \in \Omega \mid \sum_{k \in \mathcal{K}(m,n)} B^{[k]}(\omega) \ge (\gamma_0 - \beta) |\mathcal{K}(m,n)| \right\}.
$$

Hence, for $m \ge m(\gamma, \epsilon)$ and $\omega \in \mathcal{B}_{m,n}(\beta)$, we have<fnref n="12" />

$$
|B_{m,n}(\omega)| \ge \sum_{k=m+1}^{n-1} B^{[k]}(\omega) \ge \sum_{k \in \mathcal{K}(m,n)} B^{[k]}(\omega) \ge (\gamma_0 - \beta) |\mathcal{K}(m,n)| \ge (\gamma_0 - \beta) \frac{n-m}{3}. \quad (51)
$$

Moreover, by applying Lemma 36, we have

$$
\begin{align*}
P(\mathcal{B}_{m,n}(\beta)) &\ge P\left(\sum_{k \in \mathcal{K}(m,n)} B^{[k]}(\omega) \ge (\mathbb{E}B_{\mathcal{K}(m,n)} - \beta) |\mathcal{K}(m,n)|\right) \\
&\ge 1 - e^{-2\beta^2 |\mathcal{K}(m,n)|} \\
&\ge 1 - e^{-2\beta^2 \frac{n-m}{3}}.
\end{align*}
$$

We define $\mathcal{U}_{m,n}(\zeta, \alpha, \beta) := T_m(\zeta) \cap \mathcal{A}_{m,n}(\alpha) \cap \mathcal{B}_{m,n}(\beta)$. Using (49), (50), and (51), for $n > m \ge m(\gamma, \epsilon)$ and $\omega \in \mathcal{U}_{m,n}(\zeta, \alpha, \beta)$, we have

$$
Z_d^{[n]}(\omega) \le \kappa^{(\alpha + \frac{1}{2})(n-m)} \zeta^{\frac{\gamma_0 - \beta}{3}(n-m)} \zeta = \left( \kappa^{\alpha + \frac{1}{2}} \zeta^{\frac{\gamma_0 - \beta}{3}} \right)^{n-m} \zeta.
$$

Note that $\alpha, \beta$, and $\gamma$ (thus, $\gamma_0$) are some fixed constants. Hence, for any $\theta > 0$ (as in the fast
polarization property), we may choose $\zeta > 0$, such that $\kappa^{\alpha+\frac{1}{2}}\zeta^{\frac{\gamma_0-\beta}{3}} \le 2^{-(1+\theta)}$. Using $Z^{[n]}(\omega) \le$
$\max_{d=1,2,3} Z_d^{[n]}(\omega)$, we get the following inequality, that holds for any $n > m \ge m(\gamma, \epsilon)$ and any
$\omega \in \mathcal{U}_{m,n}(\zeta, \alpha, \beta)$:

$$
Z^{[n]}(\omega) \le c 2^{-n(1+\theta)} = cN^{-(1+\theta)}.
$$

where $c = c(m, \alpha, \beta, \gamma, \zeta) := (\kappa^{\alpha+\frac{1}{2}} \zeta^{\frac{\gamma_0-\beta}{3}})^{-m} \zeta$, and $N = 2^n$. Note that $\alpha, \beta, \gamma$, and $\zeta$ have been
fixed at this point, and only the value of $m$ can still be varied.

To complete the proof, we need to show that $\mathcal{U}_{m,n}(\zeta, \alpha, \beta)$ is sufficiently large (for some $m$,
and large enough $n > m$), so that we may find information sets $\mathcal{I}_N$ of size $|\mathcal{I}_N| \ge RN$, for
$R < \mathbb{I}(W)$. For this, we need the following lemma, which is essentially the same as Lemma 1
in [1], and the proof follows using exactly the same arguments as in loc. cit. (and also using the
fact that $\Gamma$ is a polarizing sequence).

<footnote n="12">¹²The last inequality could be tighten, but we only need a non-zero fraction of $n-m$.</footnote>
**Lemma 38.** For any fixed $\zeta > 0$ and any $0 \le \delta < \mathbf{I}(W)$, there exists an integer $m_0(\zeta, \delta)$, such that

$$P(T_{m_0}(\zeta)) \ge \mathbf{I}(W) - \delta.$$

Therefore, $P(T_m(\zeta))$ can be made arbitrarily close to $\mathbf{I}(W)$, by taking $m$ large enough, and once we have made $P(T_m(\zeta))$ as close as desired to $\mathbf{I}(W)$, we can make $P(A_{m,n}(\alpha))$ and $P(B_{m,n}(\beta))$ arbitrarily close to 1, by taking $n > m$ large enough. Hence, for any $R < \mathbf{I}(W)$, we may find $m_0 = m_0(\zeta, R)$ and $n_0 = n_0(m_0, \alpha, \beta, \gamma) > m_0$, such that

$$P(\mathcal{U}_{m_0,n}(\zeta, \alpha, \beta)) > R, \quad \forall n \ge n_0,$$

and since we may assume that $m_0 \ge m(\gamma, \varepsilon)$, we also have

$$Z^{[n]}(\omega) \le c_0 N^{-(1+\theta)}, \quad \forall n \ge n_0, \forall \omega \in \mathcal{U}_{m_0,n}(\zeta, \alpha, \beta) \quad (52)$$

where $c_0 := c_0(m_0, \alpha, \beta, \gamma, \zeta)$.

Now, for $n > 0$, let $\mathcal{V}_n := \{\omega \in \Omega \mid Z^{[n]}(\omega) \le c_0 N^{-(1+\theta)}\}$. Using (52), we have that $\mathcal{U}_{m_0,n}(\zeta, \alpha, \beta) \subseteq \mathcal{V}_n$, for any $n \ge n_0$, and therefore $P[\mathcal{V}_n] \ge R$. On the other hand,

$$P[\mathcal{V}_n] = \sum_{i_1 \cdots i_n \in \{0,1\}^n} \frac{1}{2^n} \mathbf{1} \left\{ Z(W^{(i_1 \cdots i_n)}) \le c_0 N^{-(1+\theta)} \right\} \\ = \frac{1}{N} |\mathcal{I}_N|,$$

where $\mathcal{I}_N := \{i \in \{0, \dots, N-1\} \mid Z(W^{(i)}) \le cN^{-(1+\theta)}\}$. It follows that $|\mathcal{I}_N| \ge RN$, for $n \ge n_0$.

We have shown that, given $\varepsilon > 0$, the fast polarization property holds for any $\Gamma \in \Gamma(S)_{\text{pol}}^{\infty} \cap \bar{\Pi}_{m(\gamma,\varepsilon)}(\gamma)$, with $P(\bar{\Pi}_{m(\gamma,\varepsilon)}(\gamma)) \ge 1 - \varepsilon$. We then conclude that it holds for any $\Gamma \in \Gamma(S)_{\text{pol}}^{\infty} \cap (\bigcup_{\varepsilon>0} \bar{\Pi}_{m(\gamma,\varepsilon)}(\gamma))$, which is a measurable subset of $\Gamma(S)_{\text{pol}}^{\infty}$, of same probability. $\square$

## References

[1] Erdal Arıkan. “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels”. In: *IEEE Transactions on Information Theory* 55.7 (July 2009), pp. 3051–3073. DOI: 10.1109/TIT.2009.2021379. arXiv: 0807.3917.

[2] Erdal Arıkan and Emre Telatar. “On the rate of channel polarization”. In: *IEEE International Symposium on Information Theory*. 2009, pp. 1493–1495. DOI: 10.1109/ISIT.2009.5205856. arXiv: 0807.3806.

[3] Charles H. Bennett, Peter W. Shor, John A. Smolin, and Ashish V. Thapliyal. “Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem”. In: *IEEE Transactions on Information Theory* 48.10 (2002), pp. 2637–2655. DOI: 10.1109/TIT.2002.802612. arXiv: quant-ph/0106052.

[4] Todd Brun, Igor Devetak, and Min-Hsiu Hsieh. “Correcting quantum errors with entanglement”. In: *Science* 314.5798 (2006), pp. 436–439. DOI: 10.1126/science.1131563. arXiv: quant-ph/0610092.

[5] Todd A. Brun, Igor Devetak, and Min-Hsiu Hsieh. “Catalytic quantum error correction”. In: *IEEE Transactions on Information Theory* 60.06 (2014), pp. 3073–3089. DOI: 10.1109/TIT.2014.2313559. arXiv: quant-ph/0608027.
[6] A. R. Calderbank and Peter W. Shor. "Good quantum error-correcting codes exist". In: *Physical Review A* 54.2 (1996), p. 1098. DOI: 10.1103/PhysRevA.54.1098. arXiv: quant-ph/9512032.

[7] Frédéric Dupuis. "The decoupling approach to quantum information theory". PhD thesis. Université de Montréal, 2009. arXiv: 1004.1641.

[8] Christopher A. Fuchs and Jeroen van de Graaf. "Cryptographic distinguishability measures for quantum-mechanical states." In: *IEEE Transactions on Information Theory* 45.4 (1999), pp. 1216-1227. DOI: 10.1109/18.761271. arXiv: quant-ph/9712042.

[9] S Hamed Hassani and Rüdiger Urbanke. "Universal polar codes". In: *IEEE International Symposium on Information Theory*. 2014, pp. 1451-1455. DOI: 10.1109/ISIT.2014.6875073. arXiv: 1307.7223.

[10] Edwin Hewitt and Karl Stromberg. *Real and abstract analysis: a modern treatment of the theory of functions of a real variable*. Springer-Verlag, 2013.

[11] Wassily Hoeffding. "Probability inequalities for sums of bounded random variables". In: *Journal of the American Statistical Association* 58.301 (1963), pp. 13-30. DOI: 10.1080/01621459.1963.10500830.

[12] A. S. Holevo. "Complementary channels and the additivity problem". In: *Theory of Probability and Its Applications* 51.1 (2007), pp. 92-100. DOI: 10.1137/S0040585X97982244. arXiv: quant-ph/0509101.

[13] Martin Müller-Lennert, Frédéric Dupuis, Oleg Szehr, Serge Fehr, and Marco Tomamichel. "On quantum Rényi entropies: a new generalization and some properties". In: *Journal of Mathematical Physics* 54.12, 122203 (2013). DOI: 10.1063/1.4838856. arXiv: 1306.3142.

[14] Maris Ozols. *Clifford group*. home.lu.lv/~sd20008/papers/essays/Clifford%20group%20[paper].pdf. 2008.

[15] Joseph M Renes. "Belief propagation decoding of quantum channels by passing quantum messages". In: *New Journal of Physics* 19.7 (2017), p. 072001. DOI: 10.1088/1367-2630/aa7c78.

[16] Joseph M. Renes, Frédéric Dupuis, and Renato Renner. "Efficient Polar Coding of Quantum Information". In: *Physical Review Letters* 109.5 (Aug. 2012), p. 050504. DOI: 10.1103/PhysRevLett.109.050504. arXiv: 1109.3195.

[17] Joseph M. Renes and Mark M. Wilde. "Polar Codes for Private and Quantum Communication Over Arbitrary Channels". In: *IEEE Transactions on Information Theory* 60.6 (June 2014), pp. 3090-3103. DOI: 10.1109/TIT.2014.2314463. arXiv: 1212.2537.

[18] Renato Renner. "Security of quantum key distribution". PhD thesis. ETH Zürich, 2005. DOI: 10.3929/ethz-a-005115027. arXiv: quant-ph/0512258.

[19] Eren Şasoğlu, Emre Telatar, and Erdal Arikan. "Polarization for arbitrary discrete memoryless channels". In: *IEEE Information Theory Workshop (ITW)*. 2009, pp. 144-148. arXiv: 0908.0302.

[20] Andrew Steane. "Multiple-particle interference and quantum error correction". In: *Proceedings of the Royal Society A* 452.1954 (1996), pp. 2551-2577. DOI: 10.1098/rspa.1996.0136. arXiv: quant-ph/9601029.

[21] David Sutter, Joseph M. Renes, Frédéric Dupuis, and Renato Renner. "Efficient quantum channel coding scheme requiring no preshared entanglement". In: *Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on*. July 2013, pp. 354-358. DOI: 10.1109/ISIT.2013.6620247. arXiv: 1307.1136.
[22] Ido Tal and Alexander Vardy. "List decoding of polar codes". In: *IEEE Transactions on Information Theory* 61.5 (2015), pp. 2213–2226. DOI: 10.1109/tit.2015.2410251. arXiv: 1206.0050.

[23] Marco Tomamichel, Mario Berta, and Masahito Hayashi. "Relating different quantum generalizations of the conditional Rényi entropy". In: *Journal of Mathematical Physics* 55.8, 082206 (2014). DOI: 10.1063/1.4892761. arXiv: 1311.3887.

[24] Mark M. Wilde and Saikat Guha. "Polar Codes for Classical-Quantum Channels". In: *Information Theory, IEEE Transactions on* 59.2 (Feb. 2013), pp. 1175–1187. DOI: 10.1109/TIT.2012.2218792. arXiv: 1109.2591.

[25] Mark M. Wilde and Saikat Guha. "Polar Codes for Degradable Quantum Channels". In: *Information Theory, IEEE Transactions on* 59.7 (July 2013), pp. 4718–4729. DOI: 10.1109/TIT.2013.2250575. arXiv: 1109.5346.

[26] Andreas Winter. "Tight uniform continuity bounds for quantum entropies: conditional entropy, relative entropy distance and energy constraints". In: *Communications in Mathematical Physics* 347.1 (2016), pp. 291–313. DOI: 10.1007/s00220-016-2609-8. arXiv: 1507.07775.