# Fault-tolerant preparation of quantum polar codes encoding one logical qubit

Ashutosh-Kumar Goswami, Mehdi Mhalla, Valentin Savin

► To cite this version:

Ashutosh-Kumar Goswami, Mehdi Mhalla, Valentin Savin. Fault-tolerant preparation of quantum polar codes encoding one logical qubit. Physical Review A, 2023, 108, pp.042605. 10.1103/Phys-RevA.108.042605. cea-04372547

HAL Id: cea-04372547

https://cea.hal.science/cea-04372547

Submitted on 4 Jan 2024

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
# Fault-tolerant preparation of quantum polar codes encoding one logical qubit

Ashutosh-Kumar Goswami, Mehdi Mhalla, Valentin Savin

► To cite this version:

Ashutosh-Kumar Goswami, Mehdi Mhalla, Valentin Savin. Fault-tolerant preparation of quantum polar codes encoding one logical qubit. Physical Review A, 2023, 108, pp.042605. 10.1103/Phys-RevA.108.042605. cea-04372547

HAL Id: cea-04372547

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

Submitted on 4 Jan 2024

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
# Fault-Tolerant Preparation of Quantum Polar Codes Encoding One Logical Qubit

Ashutosh Goswami¹, Mehdi Mhalla², Valentin Savin¹

¹ Univ. Grenoble Alpes, CEA-Léti, F-38054 Grenoble, France

² Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG, F-38000 Grenoble, France

ashutosh-kumar.goswami@cea.fr, mehdi.mhalla@univ-grenoble-alpes.fr, valentin.savin@cea.fr

(Dated:)

This paper explores a new approach to fault-tolerant quantum computing (FTQC), relying on quantum polar codes. We consider quantum polar codes of Calderbank-Shor-Steane type, encoding one logical qubit, which we refer to as $Q_1$ codes. First, we show that a subfamily of $Q_1$ codes is equivalent to the well-known family of Shor codes. Moreover, we show that $Q_1$ codes significantly outperform Shor codes, of the same length and minimum distance. Second, we consider the fault-tolerant preparation of $Q_1$ code states. We give a recursive procedure to prepare a $Q_1$ code state, based on two-qubit Pauli measurements only. The procedure is not by itself fault-tolerant, however, the measurement operations therein provide redundant classical bits, which can be advantageously used for error detection. Fault-tolerance is then achieved by combining the proposed recursive procedure with an error detection method. Finally, we consider the fault-tolerant error correction of $Q_1$ codes. We use Steane error correction, which incorporates the proposed fault-tolerant code state preparation procedure. We provide numerical estimates of the logical error rates for $Q_1$ and Shor codes of length 16 and 64 qubits, assuming a circuit-level depolarizing noise model. Remarkably, the $Q_1$ code of length 64 qubits achieves a logical error rate very close to $10^{-6}$ for the physical error rate $p = 10^{-3}$, therefore, demonstrating the potential of the proposed polar codes based approach to FTQC.

## I. Introduction

Large-scale quantum computers are expected to use quantum error correcting (QEC) codes to provide resilience against noise [1]. A QEC code encodes one or more logical qubits into many noisy physical qubits, so that the logical qubits are more robust against noise than the physical qubits. However, a QEC code alone does not provide the ability to do fault-tolerant quantum computation (FTQC). To avoid the uncontrolled propagation of errors, it must be complemented with several *fault-tolerant* procedures [2], aimed at (i) preparing logical code states, (ii) operating on the logical subspace, and (iii) performing error correction.

In this paper, we explore a new approach to FTQC, relying on quantum polar codes. Introduced first in 2009 for classical systems [3], and then generalized to the quantum case [4–7], polar codes arguably represent one of the most important advances of the past decade in the coding theory. In the classical setting, polar codes are the first family of explicit codes that provably achieve the capacity of any symmetric, binary-input, discrete, memoryless classical channel, and come equipped with an efficient decoding algorithm, known as *successive cancellation (SC)*, whose complexity scales log-linearly with the code-length [3]. In the quantum setting, they achieve the coherent information (one-shot capacity) of any quantum channel [4, 6, 7], and further, the efficient classical polar

decoder can be adapted for Pauli channels by considering a syndrome decoding approach [4, 7]. Quantum polar codes are thus of both theoretical and practical importance, due to their theoretically proven optimal error correction capacity and their practical, low-complexity successive-cancellation-based decoding.

It is important to note that a fast decoder is key to performing fault-tolerant error correction. Indeed, the QEC decoder needs to be fast enough to fight against the qubit decoherence, energy efficient to meet possibly stringent power-consumption requirements, and highly scalable to meet the needs of fault-tolerance [8]. Moreover, as noticed in [8], the decoding must be faster than the syndrome extraction rate, since otherwise the latency overhead becomes exponential in the number of non-Clifford gates, hindering any quantum advantage. Achieving all these constraints is extremely challenging, and might not be possible by existing solutions.

Hence, it is worth investigating polar codes in the context of FTQC, where they may potentially provide a viable alternative to present solutions based on topological [9–11], or more generally quantum low-density parity-check (LDPC) codes [12–15].

Yet, despite their excellent error correction properties, polar codes have been hardly explored for quantum computing, except the work in [16] on magic state distillation. Here, we focus on two closely related ingredients of FTQC, namely fault-tolerant code state prepara-
Fault-Tolerant Preparation of Quantum Polar Codes Encoding One Logical Qubit

Ashutosh Goswami¹, Mehdi Mhalla², Valentin Savin¹

¹ Univ. Grenoble Alpes, CEA-Léti, F-38054 Grenoble, France

² Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG, F-38000 Grenoble, France

ashutosh-kumar.goswami@cea.fr, mehdi.mhalla@univ-grenoble-alpes.fr, valentin.savin@cea.fr

(Dated:)

This paper explores a new approach to fault-tolerant quantum computing (FTQC), relying on quantum polar codes. We consider quantum polar codes of Calderbank-Shor-Steane type, encoding one logical qubit, which we refer to as $Q_1$ codes. First, we show that a subfamily of $Q_1$ codes is equivalent to the well-known family of Shor codes. Moreover, we show that $Q_1$ codes significantly outperform Shor codes, of the same length and minimum distance. Second, we consider the fault-tolerant preparation of $Q_1$ code states. We give a recursive procedure to prepare a $Q_1$ code state, based on two-qubit Pauli measurements only. The procedure is not by itself fault-tolerant, however, the measurement operations therein provide redundant classical bits, which can be advantageously used for error detection. Fault-tolerance is then achieved by combining the proposed recursive procedure with an error detection method. Finally, we consider the fault-tolerant error correction of $Q_1$ codes. We use Steane error correction, which incorporates the proposed fault-tolerant code state preparation procedure. We provide numerical estimates of the logical error rates for $Q_1$ and Shor codes of length 16 and 64 qubits, assuming a circuit-level depolarizing noise model. Remarkably, the $Q_1$ code of length 64 qubits achieves a logical error rate very close to $10^{-6}$ for the physical error rate $p = 10^{-3}$, therefore, demonstrating the potential of the proposed polar codes based approach to FTQC.

# I. Introduction

Large-scale quantum computers are expected to use quantum error correcting (QEC) codes to provide resilience against noise [1]. A QEC code encodes one or more logical qubits into many noisy physical qubits, so that the logical qubits are more robust against noise than the physical qubits. However, a QEC code alone does not provide the ability to do fault-tolerant quantum computation (FTQC). To avoid the uncontrolled propagation of errors, it must be complemented with several *fault-tolerant* procedures [2], aimed at (i) preparing logical code states, (ii) operating on the logical subspace, and (iii) performing error correction.

In this paper, we explore a new approach to FTQC, relying on quantum polar codes. Introduced first in 2009 for classical systems [3], and then generalized to the quantum case [4–7], polar codes arguably represent one of the most important advances of the past decade in the coding theory. In the classical setting, polar codes are the first family of explicit codes that provably achieve the capacity of any symmetric, binary-input, discrete, memoryless classical channel, and come equipped with an efficient decoding algorithm, known as *successive cancellation (SC)*, whose complexity scales log-linearly with the code-length [3]. In the quantum setting, they achieve the coherent information (one-shot capacity) of any quantum channel [4, 6, 7], and further, the efficient classical polar

decoder can be adapted for Pauli channels by considering a syndrome decoding approach [4, 7]. Quantum polar codes are thus of both theoretical and practical importance, due to their theoretically proven optimal error correction capacity and their practical, low-complexity successive-cancellation-based decoding.

It is important to note that a fast decoder is key to performing fault-tolerant error correction. Indeed, the QEC decoder needs to be fast enough to fight against the qubit decoherence, energy efficient to meet possibly stringent power-consumption requirements, and highly scalable to meet the needs of fault-tolerance [8]. Moreover, as noticed in [8], the decoding must be faster than the syndrome extraction rate, since otherwise the latency overhead becomes exponential in the number of non-Clifford gates, hindering any quantum advantage. Achieving all these constraints is extremely challenging, and might not be possible by existing solutions.

Hence, it is worth investigating polar codes in the context of FTQC, where they may potentially provide a viable alternative to present solutions based on topological [9–11], or more generally quantum low-density parity-check (LDPC) codes [12–15].

Yet, despite their excellent error correction properties, polar codes have been hardly explored for quantum computing, except the work in [16] on magic state distillation. Here, we focus on two closely related ingredients of FTQC, namely fault-tolerant code state prepara-
tion and fault-tolerant error correction. Note that, unlike quantum LDPC codes, quantum polar codes have high-weight stabilizer generators, which prevent fault-tolerant state preparation and error correction from being implemented by repeated syndrome measurements. Indeed, quantum LDPC code states can be prepared and error corrected by repeated syndrome measurements, where stabilizer generators are measured by using the standard “phase kickback trick” [2]. Errors are detected by the difference between syndromes, and since the syndrome values can also contain errors, several measurement rounds have to be decoded simultaneously to achieve fault-tolerance [17]. Since this approach is no longer fault-tolerant for codes with high-weight stabilizer generators, alternative solutions have to be devised for quantum polar codes. The main contributions of this paper are as follows.

We consider quantum polar codes of Calderbank-Shor-Steane (CSS) type that encode one logical qubit, which we refer to as $Q_1$ codes. We show that $Q_1$ codes are a natural generalization of the well-known family of Shor codes, providing improved error correction performance.

We then consider the fault-tolerant preparation of $Q_1$ code states. By taking advantage of the quantum polar code structure, we propose a procedure to prepare $Q_1$ code states, by recursively performing Pauli $Z \otimes Z$ or Pauli $X \otimes X$ measurements. This procedure is not by itself fault-tolerant, however, the measurement operations therein provide redundant classical bits, which can be advantageously used for error detection. Hence, to achieve fault-tolerance, the proposed procedure is complemented by an error detection method [18].

Indeed, unlike the LDPC case, where the syndrome extraction can be repeated to deal with errors in generator measurements, in our case, the measurements cannot be repeated, as they may correspond to anti-commuting Pauli operators. Therefore, to ensure the fault tolerance, we have introduced an error detection gadget, which takes advantage of the redundancy in the measurement outcome.

Finally, we consider the fault-tolerant error correction of $Q_1$ codes, using Steane error correction [19, 20]. We provide numerical estimates of the logical error rate (LER), assuming a circuit-level depolarizing noise model, for $Q_1$ and Shor-$Q_1$ codes of length $N = 16$ and $N = 64$. Remarkably, the $Q_1$ code of length 64 qubits achieves an LER very close to $10^{-6}$ for the physical error rate $p = 10^{-3}$, therefore, demonstrating the potential of the proposed polar codes based approach to FTQC.

<figure><img src="image_2.png" /><figcaption>Fig. 1: The quantum polar code, with $N = 2^3$, frozen sets $\mathcal{Z} = \{1, 2, 3\}$, $\mathcal{X} = \{6, 7, 8\}$ (chosen only for the simplicity of illustration), and frozen states $|u\rangle_\mathcal{Z} = |0, 0, 0\rangle$, and $|\bar{v}\rangle_\mathcal{X} = |+, +, +\rangle$.</figcaption></figure>

## II. CSS Quantum Polar Codes

We refer to Appendix A and Appendix B for the relevant background on classical and quantum polar codes. Here, we introduce the notation and summarize the definitions needed to understand the main results of the paper.

The quantum polar transform $Q_N$, where $N = 2^n$, with $n > 0$, is the unitary operation on $N$ qubits that operates in the computational basis as the classical polar transform $P_N$. Precisely, for any $\mathbf{u} = (u_1, \dots, u_N) \in \{0, 1\}^N$, we define $Q_N|\mathbf{u}\rangle = |P_N\mathbf{u}\rangle$, where $P_N = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}^{\otimes n}$. Hence, $Q_N$ can be realized by recursively applying the quantum CNOT gate, transversely, on subblocks of $2^k$ qubits, for $k = 0, \dots, n-1$ (see Fig. 1).

Let $S = \{1, \dots, N\}$ denote an $N$-qubit quantum system. For a CSS quantum polar code [4], the system $S$ is partitioned into $S = \mathcal{Z} \cup \mathcal{I} \cup \mathcal{X}$, and the input quantum state of the polar transform is taken as follows.

For $\mathcal{Z} \subseteq S$, the quantum state is frozen to a known Pauli $Z$ basis state $|u\rangle_\mathcal{Z}$, where $u := (u_1, \dots, u_n) \in \{0, 1\}^{|\mathcal{Z}|}$. For $\mathcal{X} \subseteq S$, with $\mathcal{Z} \cap \mathcal{X} = \emptyset$, it is frozen to a known Pauli $X$ basis state $|\bar{v}\rangle_\mathcal{X}$, where $\bar{v} \in \{0, 1\}^{|\mathcal{X}|}$ and we use the notation $|\bar{0}\rangle := |+\rangle$, and $|\bar{1}\rangle := |-\rangle$. The remaining subset $\mathcal{I} := S \setminus (\mathcal{X} \cup \mathcal{Z})$ is used to encode quantum information $|\phi\rangle_\mathcal{I}$.

Therefore, the logical code state, denoted by $|\tilde{\phi}\rangle_S$, is given by $|\tilde{\phi}\rangle_S = Q_N(|u\rangle_\mathcal{Z} \otimes |\phi\rangle_\mathcal{I} \otimes |\bar{v}\rangle_\mathcal{X})$.

## III. $Q_1$ codes: Quantum Polar Codes with One Logical Qubit

As $Q_1$ codes encode only one qubit, the information set $\mathcal{I} = \{i\}$, for some $i \in S = \{1, \dots, N\}$. Given the index $i$, the frozen sets $\mathcal{Z}$ consists of the set of indices preceding $i$, i.e., $\mathcal{Z} := \{1, \dots, i-1\}$, and the frozen set $\mathcal{X}$ consists of the set of indices succeeding $i$, i.e., $\mathcal{X} := \{i+1, \dots, N\}$.
tion and fault-tolerant error correction. Note that, unlike quantum LDPC codes, quantum polar codes have high-weight stabilizer generators, which prevent fault-tolerant state preparation and error correction from being implemented by repeated syndrome measurements. Indeed, quantum LDPC code states can be prepared and error corrected by repeated syndrome measurements, where stabilizer generators are measured by using the standard “phase kickback trick” [2]. Errors are detected by the difference between syndromes, and since the syndrome values can also contain errors, several measurement rounds have to be decoded simultaneously to achieve fault-tolerance [17]. Since this approach is no longer fault-tolerant for codes with high-weight stabilizer generators, alternative solutions have to be devised for quantum polar codes. The main contributions of this paper are as follows.

We consider quantum polar codes of Calderbank-Shor-Steane (CSS) type that encode one logical qubit, which we refer to as $Q_1$ codes. We show that $Q_1$ codes are a natural generalization of the well-known family of Shor codes, providing improved error correction performance.

We then consider the fault-tolerant preparation of $Q_1$ code states. By taking advantage of the quantum polar code structure, we propose a procedure to prepare $Q_1$ code states, by recursively performing Pauli $Z \otimes Z$ or Pauli $X \otimes X$ measurements. This procedure is not by itself fault-tolerant, however, the measurement operations therein provide redundant classical bits, which can be advantageously used for error detection. Hence, to achieve fault-tolerance, the proposed procedure is complemented by an error detection method [18].

Indeed, unlike the LDPC case, where the syndrome extraction can be repeated to deal with errors in generator measurements, in our case, the measurements cannot be repeated, as they may correspond to anti-commuting Pauli operators. Therefore, to ensure the fault tolerance, we have introduced an error detection gadget, which takes advantage of the redundancy in the measurement outcome.

Finally, we consider the fault-tolerant error correction of $Q_1$ codes, using Steane error correction [19, 20]. We provide numerical estimates of the logical error rate (LER), assuming a circuit-level depolarizing noise model, for $Q_1$ and Shor-$Q_1$ codes of length $N = 16$ and $N = 64$. Remarkably, the $Q_1$ code of length 64 qubits achieves an LER very close to $10^{-6}$ for the physical error rate $p = 10^{-3}$, therefore, demonstrating the potential of the proposed polar codes based approach to FTQC.

<figure><img src="image_2.png" /><figcaption>Fig. 1: The quantum polar code, with $N = 2^3$, frozen sets $\mathcal{Z} = \{1, 2, 3\}$, $\mathcal{X} = \{6, 7, 8\}$ (chosen only for the simplicity of illustration), and frozen states $|u\rangle_\mathcal{Z} = |0, 0, 0\rangle$, and $|\bar{v}\rangle_\mathcal{X} = |+, +, +\rangle$.</figcaption></figure>

## II. CSS Quantum Polar Codes

We refer to Appendix A and Appendix B for the relevant background on classical and quantum polar codes. Here, we introduce the notation and summarize the definitions needed to understand the main results of the paper.

The quantum polar transform $Q_N$, where $N = 2^n$, with $n > 0$, is the unitary operation on $N$ qubits that operates in the computational basis as the classical polar transform $P_N$. Precisely, for any $\mathbf{u} = (u_1, \dots, u_N) \in \{0, 1\}^N$, we define $Q_N|\mathbf{u}\rangle = |P_N\mathbf{u}\rangle$, where $P_N = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}^{\otimes n}$. Hence, $Q_N$ can be realized by recursively applying the quantum CNOT gate, transversely, on subblocks of $2^k$ qubits, for $k = 0, \dots, n-1$ (see Fig. 1).

Let $S = \{1, \dots, N\}$ denote an $N$-qubit quantum system. For a CSS quantum polar code [4], the system $S$ is partitioned into $S = \mathcal{Z} \cup \mathcal{I} \cup \mathcal{X}$, and the input quantum state of the polar transform is taken as follows.

For $\mathcal{Z} \subseteq S$, the quantum state is frozen to a known Pauli $Z$ basis state $|u\rangle_\mathcal{Z}$, where $u := (u_1, \dots, u_n) \in \{0, 1\}^{|\mathcal{Z}|}$. For $\mathcal{X} \subseteq S$, with $\mathcal{Z} \cap \mathcal{X} = \emptyset$, it is frozen to a known Pauli $X$ basis state $|\bar{v}\rangle_\mathcal{X}$, where $\bar{v} \in \{0, 1\}^{|\mathcal{X}|}$ and we use the notation $|\bar{0}\rangle := |+\rangle$, and $|\bar{1}\rangle := |-\rangle$. The remaining subset $\mathcal{I} := S \setminus (\mathcal{X} \cup \mathcal{Z})$ is used to encode quantum information $|\phi\rangle_\mathcal{I}$.

Therefore, the logical code state, denoted by $|\tilde{\phi}\rangle_S$, is given by $|\tilde{\phi}\rangle_S = Q_N(|u\rangle_\mathcal{Z} \otimes |\phi\rangle_\mathcal{I} \otimes |\bar{v}\rangle_\mathcal{X})$.

## III. $Q_1$ codes: Quantum Polar Codes with One Logical Qubit

As $Q_1$ codes encode only one qubit, the information set $\mathcal{I} = \{i\}$, for some $i \in S = \{1, \dots, N\}$. Given the index $i$, the frozen sets $\mathcal{Z}$ consists of the set of indices preceding $i$, i.e., $\mathcal{Z} := \{1, \dots, i-1\}$, and the frozen set $\mathcal{X}$ consists of the set of indices succeeding $i$, i.e., $\mathcal{X} := \{i+1, \dots, N\}$.
The choice of the frozen sets $\mathcal{Z}$ and $\mathcal{X}$, given the information qubit position $i$, is simply explained by the sequential nature of the SC decoding, and the fact that only errors on the information position $i$ need to be decoded. To correct $X$ errors, virtual channels [21] are decoded in order, from 1 to $N$. Freezing a virtual channel $j > i$ in $\mathcal{Z}$ basis would be of no help in decoding the virtual channel $i$, while freezing it in $X$ basis amounts to ignoring $X$ errors that happen on it. A similar observation holds for $\mathcal{Z}$ errors, by noticing that in this case virtual channels are decoded in reversed (decreasing) order, from $N$ to 1 (see also Appendix B.2, Fig. 6).

In case the information position is a power of two, that is, $i = 2^k, 0 \le k \le n$, the corresponding $Q_1$ code is a Shor code [22, 23]. This follows from Theorem 1 below, which is proven in Appendix C.1. We refer to these codes as Shor-$Q_1$ codes, or simply Shor codes, when no confusion is possible.

**Theorem 1.** For a given $i = 2^k, 0 \le k \le n$, the logical states $|0\rangle_S$ and $|1\rangle_S$ of the $Q_1(N, i)$ code are as follows (up to a normalization factor),

$$|0\rangle_S = \otimes_{r=1}^{2^k} \left( \otimes_{c=1}^{2^{n-k}} |+\rangle_{r,c} + \otimes_{c=1}^{2^{n-k}} |-\rangle_{r,c} \right), \quad (1)$$

$$|1\rangle_S = \otimes_{r=1}^{2^k} \left( \otimes_{c=1}^{2^{n-k}} |+\rangle_{r,c} - \otimes_{c=1}^{2^{n-k}} |-\rangle_{r,c} \right), \quad (2)$$

where $r$ and $c$ are row and column indexes, with $S$ being reshaped as a $2^k \times 2^{n-k}$ matrix of qubits.

The construction of a $Q_1$ code refers to the choice of the information position $i$, which determines how well the code protects the encoded quantum information. Hence, the position $i \in S$ should be chosen in a way to optimize the LER performance, depending on the specific noisy quantum channel. For the subfamily of Shor-$Q_1$ codes, the choice is restricted to positions $i = 2^k, 0 \le k \le n$ (We refer to Appendix B.2 for the construction of CSS quantum polar codes, and to Appendix C.2 for more details on the construction of $Q_1$ and Shor-$Q_1$ codes).

For depolarizing quantum channels, we use the density evolution technique [3, 24] to numerically estimate the LER of $Q_1$ and Shor-$Q_1$ codes. The numerical results are shown in Fig. 2 for both $Q_1$ and Shor codes, for even recursion levels $n = 4$ to 12, where the corresponding best index $i$ is given in the legend. It can be observed that the $Q_1$ code in general outperforms the Shor code, for a given $n$. From the corresponding values of $i$ given in Fig. 2, one may further note that the $Q_1$ and Shor codes have the same quantum minimum distance, for a given $n$. The superior performance of $Q_1$ codes owes to the SC decoding, which is able to decode beyond the minimum distance of the code, by effectively exploiting the channel polarization property of polar codes.

<figure><img src="image_3.png" /><figcaption>Fig. 2: LER of $Q_1$ and Shor codes, for the depolarizing channel.</figcaption></figure>

For the odd recursion levels, our numerical results indicate performance gains, depending on $n$ and the physical error rate value (Further numerical results for the depolarizing and the quantum erasure channels, as well as the details of the numerical methods, are provided in Appendix C.3.).

## IV. measurement-based Preparation of $Q_1$ Code States

The conventional encoding of quantum polar codes in Fig. 1 is not fault-tolerant, as errors propagate through the CNOT gates. Further, measuring the stabilizer generators using the standard “phase kickback trick” [2], similar to the case of quantum LDPC codes [13], is also not fault-tolerant, due to the high weights of generators.

Hence, we propose a new procedure to prepare $Q_1$ code states, based on two-qubit Pauli measurements only. We describe our procedure in two steps. First, we assume that all the operations are error free, and show that the proposed procedure does indeed prepare a $Q_1$ code state. Then, we consider our procedure under the effect of errors (i.e., noisy gates and measurements), and show that it can be made fault-tolerant by incorporating an error detection gadget, exploiting the redundancy in the measurement outcomes.

We consider the preparation of logical $|0\rangle$ and $|+\rangle$ states, for which all the input qubits are frozen in either $\mathcal{Z}$ or $X$ basis. Consequently, we consider the preparation of general $Q_1$ code states, with frozen sets $\mathcal{Z} = \{1, \dots, i\}$ and $\mathcal{X} = \{i+1, \dots, N\}$, for some arbitrary $1 \le i \le N$, where $N = 2^n, n \ge 1$. Further, since our preparation procedure is recursive, to clearly indicate the length of the prepared $Q_1$ state, we will use the notation $i(n) := i$,
The choice of the frozen sets $\mathcal{Z}$ and $\mathcal{X}$, given the information qubit position $i$, is simply explained by the sequential nature of the SC decoding, and the fact that only errors on the information position $i$ need to be decoded. To correct $X$ errors, virtual channels [21] are decoded in order, from 1 to $N$. Freezing a virtual channel $j > i$ in $\mathcal{Z}$ basis would be of no help in decoding the virtual channel $i$, while freezing it in $X$ basis amounts to ignoring $X$ errors that happen on it. A similar observation holds for $\mathcal{Z}$ errors, by noticing that in this case virtual channels are decoded in reversed (decreasing) order, from $N$ to 1 (see also Appendix B.2, Fig. 6).

In case the information position is a power of two, that is, $i = 2^k, 0 \le k \le n$, the corresponding $Q_1$ code is a Shor code [22, 23]. This follows from Theorem 1 below, which is proven in Appendix C.1. We refer to these codes as Shor-$Q_1$ codes, or simply Shor codes, when no confusion is possible.

**Theorem 1.** For a given $i = 2^k, 0 \le k \le n$, the logical states $|0\rangle_S$ and $|1\rangle_S$ of the $Q_1(N, i)$ code are as follows (up to a normalization factor),

$$|0\rangle_S = \otimes_{r=1}^{2^k} \left( \otimes_{c=1}^{2^{n-k}} |+\rangle_{r,c} + \otimes_{c=1}^{2^{n-k}} |-\rangle_{r,c} \right), \quad (1)$$

$$|1\rangle_S = \otimes_{r=1}^{2^k} \left( \otimes_{c=1}^{2^{n-k}} |+\rangle_{r,c} - \otimes_{c=1}^{2^{n-k}} |-\rangle_{r,c} \right), \quad (2)$$

where $r$ and $c$ are row and column indexes, with $S$ being reshaped as a $2^k \times 2^{n-k}$ matrix of qubits.

The construction of a $Q_1$ code refers to the choice of the information position $i$, which determines how well the code protects the encoded quantum information. Hence, the position $i \in S$ should be chosen in a way to optimize the LER performance, depending on the specific noisy quantum channel. For the subfamily of Shor-$Q_1$ codes, the choice is restricted to positions $i = 2^k, 0 \le k \le n$ (We refer to Appendix B.2 for the construction of CSS quantum polar codes, and to Appendix C.2 for more details on the construction of $Q_1$ and Shor-$Q_1$ codes).

For depolarizing quantum channels, we use the density evolution technique [3, 24] to numerically estimate the LER of $Q_1$ and Shor-$Q_1$ codes. The numerical results are shown in Fig. 2 for both $Q_1$ and Shor codes, for even recursion levels $n = 4$ to 12, where the corresponding best index $i$ is given in the legend. It can be observed that the $Q_1$ code in general outperforms the Shor code, for a given $n$. From the corresponding values of $i$ given in Fig. 2, one may further note that the $Q_1$ and Shor codes have the same quantum minimum distance, for a given $n$. The superior performance of $Q_1$ codes owes to the SC decoding, which is able to decode beyond the minimum distance of the code, by effectively exploiting the channel polarization property of polar codes.

<figure><img src="image_3.png" /><figcaption>Fig. 2: LER of $Q_1$ and Shor codes, for the depolarizing channel.</figcaption></figure>

For the odd recursion levels, our numerical results indicate performance gains, depending on $n$ and the physical error rate value (Further numerical results for the depolarizing and the quantum erasure channels, as well as the details of the numerical methods, are provided in Appendix C.3.).

## IV. measurement-based Preparation of $Q_1$ Code States

The conventional encoding of quantum polar codes in Fig. 1 is not fault-tolerant, as errors propagate through the CNOT gates. Further, measuring the stabilizer generators using the standard “phase kickback trick” [2], similar to the case of quantum LDPC codes [13], is also not fault-tolerant, due to the high weights of generators.

Hence, we propose a new procedure to prepare $Q_1$ code states, based on two-qubit Pauli measurements only. We describe our procedure in two steps. First, we assume that all the operations are error free, and show that the proposed procedure does indeed prepare a $Q_1$ code state. Then, we consider our procedure under the effect of errors (i.e., noisy gates and measurements), and show that it can be made fault-tolerant by incorporating an error detection gadget, exploiting the redundancy in the measurement outcomes.

We consider the preparation of logical $|0\rangle$ and $|+\rangle$ states, for which all the input qubits are frozen in either $\mathcal{Z}$ or $X$ basis. Consequently, we consider the preparation of general $Q_1$ code states, with frozen sets $\mathcal{Z} = \{1, \dots, i\}$ and $\mathcal{X} = \{i+1, \dots, N\}$, for some arbitrary $1 \le i \le N$, where $N = 2^n, n \ge 1$. Further, since our preparation procedure is recursive, to clearly indicate the length of the prepared $Q_1$ state, we will use the notation $i(n) := i$,
$\mathcal{Z}(n) := \mathcal{Z}$, and $\mathcal{X}(n) := \mathcal{X}$. Therefore, we want to prepare the following $N$-qubit $Q_1$ state on the system $S = \{1, \dots, N\}$,

$$|q_N\rangle_S := Q_N(|\mathbf{u}, \bar{\mathbf{v}}\rangle_S) = Q_N(|\mathbf{u}\rangle_{\mathcal{Z}(n)} \otimes |\bar{\mathbf{v}}\rangle_{\mathcal{X}(n)}), \quad (3)$$

where $\mathbf{u} \in \{0, 1\}^{i(n)}$ and $\mathbf{v} \in \{0, 1\}^{N-i(n)}$. When no confusion is possible, we may simply write $|q_N\rangle$ instead of $|q_N\rangle_S$. Here, we consider $Q_1$ states defined by the same value of $i(n)$ as equivalent, regardless of the corresponding frozen values $\mathbf{u}, \mathbf{v}$. Put differently, equivalent $Q_1$ states are defined by the same stabilizer generators, up to sign factors.

To prepare $|q_N\rangle_S$ from (3), we will use the following measurement-based procedure.

**Procedure 1 (measurement-based Preparation).** Given a $n$-bit sequence $b_1 \cdots b_n \in \{0, 1\}$, our measurement-based procedure on $N = 2^n$ qubit system $S = \{1, \dots, N\}$ is as follows.

(1) First, $S$ is initialized in a Pauli Z basis state $|\mathbf{u}\rangle_S, \mathbf{u} \in \{0, 1\}^N$.

(2) Then, two-qubit Pauli measurements are recursively applied for $n$ levels. The recursion is the same as the recursion of the quantum polar transform (see Fig. 1), except the CNOT gate is replaced by either Pauli $X \otimes X$ or $Z \otimes Z$ measurement. Precisely, if $b_k = 0$ (or, $b_k = 1$), we apply Pauli $X \otimes X$ (or, $Z \otimes Z$) measurements at the $k^{th}$, $k = 1, \dots, n$ recursion level.

**Theorem 2.** Consider the $Q_1$ state $|q_N\rangle_S$ from (3), with $1 \le i(n) \le N$. Let $b_1 \cdots b_n$ be the binary representation of $i(n) - 1$, with $b_n$ being the most significant bit, i.e, $i(n) - 1 = \sum_{k=1}^n b_k 2^{k-1}$. Then, $|q_N\rangle_S$ can be prepared, using the measurement-based procedure in Procedure 1, corresponding to the $n$ bit sequence $b_1 \cdots b_n$.

The measurement-based preparation for $N = 8, i(n) = 3$ is illustrated in Fig. 3.

We first show in Lemma 1 that given two equivalent $Q_1$ states of length $K/2, K = 2^k$, we can prepare a $Q_1$ state of length $K$ by performing $Z \otimes Z$ or $X \otimes X$ measurements transversely on them. Further, when we apply Pauli $Z \otimes Z$ measurements, we have $i(k) = i(k-1) + K/2 > K/2$ and when we apply Pauli $X \otimes X$ measurements, we have $i(k) = i(k-1) \le K/2$. The proof of Theorem 2 then simply follows from Lemma 1, by noting that $b_k = 1 \Leftrightarrow i(k) > K/2$ (hence, $b_k = 0 \Leftrightarrow i(k) \le K/2$).

**Lemma 1.** Consider two equivalent $Q_1$ states on $K/2$-qubit systems $S_1 := \{1, \dots, K/2\}$ and $S_2 := \{K/2 + 1, \dots, K\}$ as follows, $|q_{\frac{K}{2}}\rangle_{S_1} := Q_{\frac{K}{2}}|\mathbf{u}_1, \bar{\mathbf{v}}_1\rangle_{S_1}$

<figure><img src="image_4.png" /><figcaption>Fig. 3: Measurement-based preparation of $|q_N\rangle_S$ in (3), with $N = 8, i(n) = 3$, where slightly flattened circles connected by a vertical wire denote either a $X \otimes X$ or a $Z \otimes Z$ measurement on the corresponding qubits, and $|q_{2^k}\rangle$ are equivalent $Q_1$ states of length $2^k$ ($|q_{2^0}\rangle$ is a Pauli Z basis state).</figcaption></figure>

and $|q_{\frac{K}{2}}^2\rangle_{S_2} := Q_{\frac{K}{2}}|\mathbf{u}_2, \bar{\mathbf{v}}_2\rangle_{S_2}$, where $\mathbf{u}_1, \mathbf{u}_2 \in \{0, 1\}^{i(k-1)}$ and $\mathbf{v}_1, \mathbf{v}_2 \in \{0, 1\}^{\frac{K}{2}-i(k-1)}$, with $1 \le i(k-1) \le K/2$. Let $S := S_1 \cup S_2$ be the joint system, then we have the following two cases.

**Case 1:** If we apply transversal Pauli $Z \otimes Z$ measurements on the corresponding qubits of $S_1$ and $S_2$, we get the $K/2$ bit measurement outcome as follows,

$$\mathbf{m} = P_{\frac{K}{2}}(\mathbf{u}', \mathbf{x}) \in \{0, 1\}^{\frac{K}{2}}, \quad (4)$$

where $\mathbf{u}' = \mathbf{u}_1 \oplus \mathbf{u}_2 \in \{0, 1\}^{i(k-1)}$ and $\mathbf{x} \in \{0, 1\}^{\frac{K}{2}-i(k-1)}$ is a random vector, and $P_{\frac{K}{2}}$ is the classical polar transform. After measurements, the state of $S$ is a $Q_1$ state, $|q_K\rangle_S = Q_K|(\mathbf{u}', \mathbf{x}, \mathbf{u}_2), \bar{\mathbf{v}}_1 \oplus \mathbf{v}_2\rangle_S$, with $i(k) = i(k-1) + K/2 > K/2$, and where $\mathbf{x}$ is determined from the measurement outcome $\mathbf{m}$ in (4) by, $\mathbf{x} = P_{\frac{K}{2}}(\mathbf{m})|\mathcal{X}(k-1)\rangle$, i.e., the subvector of $P_{\frac{K}{2}}(\mathbf{m}) \in \{0, 1\}^{K/2}$ corresponding to indices in the set $\mathcal{X}(k-1)$.

**Case 2:** If we apply transversal Pauli $X \otimes X$ measurements on the corresponding qubits of $S_1$ and $S_2$, we get the $K/2$ bit measurement outcome as follows,

$$\mathbf{m} = P_{\frac{K}{2}}^{\top}(\mathbf{z}, \mathbf{v}') \in \{0, 1\}^{\frac{K}{2}}, \quad (5)$$

where $\mathbf{z} \in \{0, 1\}^{i(k-1)}$ is a random vector, and $\mathbf{v}' = \mathbf{v}_1 \oplus \mathbf{v}_2 \in \{0, 1\}^{\frac{K}{2}-i(k-1)}$. After measurements, the state on $S$ is a $Q_1$ state $|q_K\rangle_S = Q_K|\mathbf{u}_1 \oplus \mathbf{u}_2, (\mathbf{v}_1, \mathbf{z}, \mathbf{v}')\rangle_S$, with $i(k) = i(k-1) \le K/2$ and from (5), $\mathbf{z} = P_{\frac{K}{2}}^{\top}(\mathbf{m})|\mathcal{Z}(k-1)\rangle$.

The proof of Lemma 1 is given in Appendix D.1. The Case 1 and Case 2 from Lemma 1 are also illustrated in Fig. 11 and Fig. 12, respectively, in Appendix D.1.
$\mathcal{Z}(n) := \mathcal{Z}$, and $\mathcal{X}(n) := \mathcal{X}$. Therefore, we want to prepare the following $N$-qubit $Q_1$ state on the system $S = \{1, \dots, N\}$,

$$|q_N\rangle_S := Q_N(|\mathbf{u}, \bar{\mathbf{v}}\rangle_S) = Q_N(|\mathbf{u}\rangle_{\mathcal{Z}(n)} \otimes |\bar{\mathbf{v}}\rangle_{\mathcal{X}(n)}), \quad (3)$$

where $\mathbf{u} \in \{0, 1\}^{i(n)}$ and $\mathbf{v} \in \{0, 1\}^{N-i(n)}$. When no confusion is possible, we may simply write $|q_N\rangle$ instead of $|q_N\rangle_S$. Here, we consider $Q_1$ states defined by the same value of $i(n)$ as equivalent, regardless of the corresponding frozen values $\mathbf{u}, \mathbf{v}$. Put differently, equivalent $Q_1$ states are defined by the same stabilizer generators, up to sign factors.

To prepare $|q_N\rangle_S$ from (3), we will use the following measurement-based procedure.

**Procedure 1 (measurement-based Preparation).** Given a $n$-bit sequence $b_1 \cdots b_n \in \{0, 1\}$, our measurement-based procedure on $N = 2^n$ qubit system $S = \{1, \dots, N\}$ is as follows.

(1) First, $S$ is initialized in a Pauli Z basis state $|\mathbf{u}\rangle_S, \mathbf{u} \in \{0, 1\}^N$.

(2) Then, two-qubit Pauli measurements are recursively applied for $n$ levels. The recursion is the same as the recursion of the quantum polar transform (see Fig. 1), except the CNOT gate is replaced by either Pauli $X \otimes X$ or $Z \otimes Z$ measurement. Precisely, if $b_k = 0$ (or, $b_k = 1$), we apply Pauli $X \otimes X$ (or, $Z \otimes Z$) measurements at the $k^{th}$, $k = 1, \dots, n$ recursion level.

**Theorem 2.** Consider the $Q_1$ state $|q_N\rangle_S$ from (3), with $1 \le i(n) \le N$. Let $b_1 \cdots b_n$ be the binary representation of $i(n) - 1$, with $b_n$ being the most significant bit, i.e, $i(n) - 1 = \sum_{k=1}^n b_k 2^{k-1}$. Then, $|q_N\rangle_S$ can be prepared, using the measurement-based procedure in Procedure 1, corresponding to the $n$ bit sequence $b_1 \cdots b_n$.

The measurement-based preparation for $N = 8, i(n) = 3$ is illustrated in Fig. 3.

We first show in Lemma 1 that given two equivalent $Q_1$ states of length $K/2, K = 2^k$, we can prepare a $Q_1$ state of length $K$ by performing $Z \otimes Z$ or $X \otimes X$ measurements transversely on them. Further, when we apply Pauli $Z \otimes Z$ measurements, we have $i(k) = i(k - 1) + K/2 > K/2$ and when we apply Pauli $X \otimes X$ measurements, we have $i(k) = i(k - 1) \le K/2$. The proof of Theorem 2 then simply follows from Lemma 1, by noting that $b_k = 1 \Leftrightarrow i(k) > K/2$ (hence, $b_k = 0 \Leftrightarrow i(k) \le K/2$).

**Lemma 1.** Consider two equivalent $Q_1$ states on $K/2$-qubit systems $S_1 := \{1, \dots, K/2\}$ and $S_2 := \{K/2 + 1, \dots, K\}$ as follows, $|q_{\frac{K}{2}}\rangle_{S_1} := Q_{\frac{K}{2}}|\mathbf{u}_1, \bar{\mathbf{v}}_1\rangle_{S_1}$

<figure><img src="image_4.png" /><figcaption>Fig. 3: Measurement-based preparation of $|q_N\rangle_S$ in (3), with $N = 8, i(n) = 3$, where slightly flattened circles connected by a vertical wire denote either a $X \otimes X$ or a $Z \otimes Z$ measurement on the corresponding qubits, and $|q_{2^k}\rangle$ are equivalent $Q_1$ states of length $2^k$ ($|q_{2^0}\rangle$ is a Pauli Z basis state).</figcaption></figure>

and $|q_{\frac{K}{2}}^2\rangle_{S_2} := Q_{\frac{K}{2}}|\mathbf{u}_2, \bar{\mathbf{v}}_2\rangle_{S_2}$, where $\mathbf{u}_1, \mathbf{u}_2 \in \{0, 1\}^{i(k-1)}$ and $\mathbf{v}_1, \mathbf{v}_2 \in \{0, 1\}^{\frac{K}{2}-i(k-1)}$, with $1 \le i(k-1) \le K/2$. Let $S := S_1 \cup S_2$ be the joint system, then we have the following two cases.

**Case 1:** If we apply transversal Pauli $Z \otimes Z$ measurements on the corresponding qubits of $S_1$ and $S_2$, we get the $K/2$ bit measurement outcome as follows,

$$\mathbf{m} = P_{\frac{K}{2}}(\mathbf{u}', \mathbf{x}) \in \{0, 1\}^{\frac{K}{2}}, \quad (4)$$

where $\mathbf{u}' = \mathbf{u}_1 \oplus \mathbf{u}_2 \in \{0, 1\}^{i(k-1)}$ and $\mathbf{x} \in \{0, 1\}^{\frac{K}{2}-i(k-1)}$ is a random vector, and $P_{\frac{K}{2}}$ is the classical polar transform. After measurements, the state of $S$ is a $Q_1$ state, $|q_K\rangle_S = Q_K|(\mathbf{u}', \mathbf{x}, \mathbf{u}_2), \bar{\mathbf{v}}_1 \oplus \mathbf{v}_2\rangle_S$, with $i(k) = i(k-1) + K/2 > K/2$, and where $\mathbf{x}$ is determined from the measurement outcome $\mathbf{m}$ in (4) by, $\mathbf{x} = P_{\frac{K}{2}}(\mathbf{m})|\mathcal{X}(k-1)\rangle$, i.e., the subvector of $P_{\frac{K}{2}}(\mathbf{m}) \in \{0, 1\}^{K/2}$ corresponding to indices in the set $\mathcal{X}(k-1)$.

**Case 2:** If we apply transversal Pauli $X \otimes X$ measurements on the corresponding qubits of $S_1$ and $S_2$, we get the $K/2$ bit measurement outcome as follows,

$$\mathbf{m} = P_{\frac{K}{2}}^{\top}(\mathbf{z}, \mathbf{v}') \in \{0, 1\}^{\frac{K}{2}}, \quad (5)$$

where $\mathbf{z} \in \{0, 1\}^{i(k-1)}$ is a random vector, and $\mathbf{v}' = \mathbf{v}_1 \oplus \mathbf{v}_2 \in \{0, 1\}^{\frac{K}{2}-i(k-1)}$. After measurements, the state on $S$ is a $Q_1$ state $|q_K\rangle_S = Q_K|\mathbf{u}_1 \oplus \mathbf{u}_2, (\mathbf{v}_1, \mathbf{z}, \mathbf{v}')\rangle_S$, with $i(k) = i(k-1) \le K/2$ and from (5), $\mathbf{z} = P_{\frac{K}{2}}^{\top}(\mathbf{m})|\mathcal{Z}(k-1)\rangle$.

The proof of Lemma 1 is given in Appendix D.1. The Case 1 and Case 2 from Lemma 1 are also illustrated in Fig. 11 and Fig. 12, respectively, in Appendix D.1.
## V. Fault-tolerant measurement-based procedure

We now consider our measurement-based procedure under the effect of Pauli noise. We assume the standard implementation of Pauli $Z \otimes Z$ and $X \otimes X$ measurements, where a bare ancilla qubit is initialized in either Pauli $Z$ or Pauli $X$ basis state, then two CNOT gates are applied between data and ancilla qubits, and finally the ancilla qubit is measured in Pauli $Z$ or $X$ basis. Therefore, any two-qubit Pauli measurement decomposes into four basic components, namely one single-qubit initialization, two CNOT-gates, and one single-qubit measurement (See Fig. 10 in Appendix D.1).

As the preparation of $|q_N\rangle_S$ consists of $N$ single-qubit initializations, followed by $N/2 \log N$ two-qubit Pauli measurements, the total number of components in the preparation is equal to $N(1 + 2 \log N)$.

We assume that each component fails independently with some probability $p$, according to a circuit level Pauli noise model as follows.

A failure in a CNOT gate corresponds to applying the perfect CNOT gate, followed by a two-qubit Pauli error on the output qubits of the CNOT gate. A failure in initialization in Pauli $Z$ (or $X$) basis corresponds to the perfect initialization, followed by an $X$ (or $Z$) error on the initialized qubit. A failure in Pauli $Z$ (or $X$) measurement corresponds to first applying a Pauli $X$ (or $Z$) error on the qubit to be measured, and then doing the perfect Pauli $Z$ (or $X$) measurement.

We note that the preparation in Procedure 1 is not fault-tolerant by itself. Due to failures in the components, the measurement outcomes of transversal Pauli $Z \otimes Z$ or $X \otimes X$ measurements are noisy. Precisely, we have $\mathbf{m} = P_K(\mathbf{u}', \mathbf{x}) \oplus e_X$ instead of (4), and $\mathbf{m} = P_K^\top(\mathbf{z}, \mathbf{v}') \oplus e_Z$ instead of (5), where $e_X, e_Z \in \{0, 1\}^{K/2}$ are unknown error terms. Recall from Lemma 1 that vectors $\mathbf{x}$ and $\mathbf{z}$ are determined from $\mathbf{m}$, and they are necessary to know the prepared state $|q_K\rangle_S$ after Pauli $Z \otimes Z$ and $X \otimes X$ measurements, respectively. However, due to unknown error terms, the methods in Lemma 1 may not correctly determine $\mathbf{x}$ and $\mathbf{z}$. Accepting a wrong estimate $\hat{\mathbf{x}} \neq \mathbf{x}$ and $\hat{\mathbf{z}} \neq \mathbf{z}$ amounts to extra $X$ and $Z$ errors on the respective prepared states, given by the vectors $P_K(0, \hat{\mathbf{x}} \oplus \mathbf{x}, 0, 0)$, and $P_K^\top(0, 0, \hat{\mathbf{z}} \oplus \mathbf{z}, 0)$, respectively.

To make the measurement-based preparation fault-tolerant, we consider the following error detection procedure.

**Procedure 2 (Measurement-based Preparation with Error Detection).** Consider the preparation of a $Q_1$ state of length

$N$ from Procedure 1. We further incorporate an error detection gadget within each level of recursion, $k = 1, \dots, n$, consisting of the following two steps.

(1) For all $2^{n-k}$ instances of prepared $|q_K\rangle$ states at the $k^{th}$ level of recursion, we first determine the syndrome of the error in the measurement outcome $\mathbf{m}$ as follows. When Pauli $Z \otimes Z$ measurements are performed (i.e, Case 1 of Lemma 1), we determine the syndrome of the error term $e_X$ in the measurement outcome $\mathbf{m}$ as, $P_K^\top(\mathbf{e}_X)|_{Z(k-1)} = P_K(\mathbf{m})|_{Z(k-1)} \oplus \mathbf{u}'$. Similarly, when Pauli $X \otimes X$ measurements are performed (i.e, Case 2 of Lemma 1), we determine the syndrome of the error term $e_Z$ as, $P_K(\mathbf{e}_Z)|_{\chi_{(k-1)}} = P_K^\top(\mathbf{m})|_{\chi_{(k-1)}} \oplus \mathbf{v}'$.

(2) If the syndrome is the zero vector for all the $2^{n-k}$ instances of $|q_K\rangle$, we determine the value of $\mathbf{x}$ or $\mathbf{z}$ for all prepared states as in Lemma 1, and proceed to the next level of recursion. Otherwise, we declare a preparation failure.

In case Procedure 2 fails, we may restart the procedure from the beginning, by initializing $N$ qubits in a Pauli $Z$ basis state.

The fault-tolerance of the successfully prepared state (i.e., when errors are not detected at any recursion level $k=1$ to $n$), follows from Theorem 3, which is proven in Appendix D.2.

**Theorem 3.** Consider the measurement-based preparation with error detection from Procedure 2. Suppose a successful preparation of $|q_N\rangle$, where $T_n$ component failures occur during the preparation. Let $e_X^f, e_Z^f \in \{0, 1\}^N$ be the final Pauli $X$ and $Z$ errors in the noisy prepared state $|q'_N\rangle$, due to the component failures. Then, there exist equivalent errors $e_X'^f \equiv e_X^f$ and $e_Z'^f \equiv e_Z^f$, so that $\text{wt}(e_X'^f) \le T_n$ and $\text{wt}(e_Z'^f) \le T_n$, where $\text{wt}(\mathbf{u})$ denotes the Hamming weight of $\mathbf{u}$.

Theorem 3 implies that the weight of $X$ and $Z$ errors on a successfully prepared state remains small given a sufficiently low component failure probability $p$. In particular, it upper bounds the average weight of the final error by $N(1 + 2 \log N)p$. Our numerical simulation suggests that the average error weight is much lower than $N(1 + 2 \log N)p$, which is expected as we discard the preparations where errors are detected.

## VI. Fault-tolerant error correction

For fault-tolerant error correction of $Q_1$ codes, we consider Steane error correction (See Appendix B.3 for the details of Steane error correction applied to CSS quantum polar codes). The $Q_1$ states, needed in the Steane error
## V. Fault-tolerant measurement-based procedure

We now consider our measurement-based procedure under the effect of Pauli noise. We assume the standard implementation of Pauli $Z \otimes Z$ and $X \otimes X$ measurements, where a bare ancilla qubit is initialized in either Pauli $Z$ or Pauli $X$ basis state, then two CNOT gates are applied between data and ancilla qubits, and finally the ancilla qubit is measured in Pauli $Z$ or $X$ basis. Therefore, any two-qubit Pauli measurement decomposes into four basic components, namely one single-qubit initialization, two CNOT-gates, and one single-qubit measurement (See Fig. 10 in Appendix D.1).

As the preparation of $|q_N\rangle_S$ consists of $N$ single-qubit initializations, followed by $N/2 \log N$ two-qubit Pauli measurements, the total number of components in the preparation is equal to $N(1 + 2 \log N)$.

We assume that each component fails independently with some probability $p$, according to a circuit level Pauli noise model as follows.

A failure in a CNOT gate corresponds to applying the perfect CNOT gate, followed by a two-qubit Pauli error on the output qubits of the CNOT gate. A failure in initialization in Pauli $Z$ (or $X$) basis corresponds to the perfect initialization, followed by an $X$ (or $Z$) error on the initialized qubit. A failure in Pauli $Z$ (or $X$) measurement corresponds to first applying a Pauli $X$ (or $Z$) error on the qubit to be measured, and then doing the perfect Pauli $Z$ (or $X$) measurement.

We note that the preparation in Procedure 1 is not fault-tolerant by itself. Due to failures in the components, the measurement outcomes of transversal Pauli $Z \otimes Z$ or $X \otimes X$ measurements are noisy. Precisely, we have $\mathbf{m} = P_K(\mathbf{u}', \mathbf{x}) \oplus e_X$ instead of (4), and $\mathbf{m} = P_K^\top(\mathbf{z}, \mathbf{v}') \oplus e_Z$ instead of (5), where $e_X, e_Z \in \{0, 1\}^{K/2}$ are unknown error terms. Recall from Lemma 1 that vectors $\mathbf{x}$ and $\mathbf{z}$ are determined from $\mathbf{m}$, and they are necessary to know the prepared state $|q_K\rangle_S$ after Pauli $Z \otimes Z$ and $X \otimes X$ measurements, respectively. However, due to unknown error terms, the methods in Lemma 1 may not correctly determine $\mathbf{x}$ and $\mathbf{z}$. Accepting a wrong estimate $\hat{\mathbf{x}} \neq \mathbf{x}$ and $\hat{\mathbf{z}} \neq \mathbf{z}$ amounts to extra $X$ and $Z$ errors on the respective prepared states, given by the vectors $P_K(0, \hat{\mathbf{x}} \oplus \mathbf{x}, 0, 0)$, and $P_K^\top(0, 0, \hat{\mathbf{z}} \oplus \mathbf{z}, 0)$, respectively.

To make the measurement-based preparation fault-tolerant, we consider the following error detection procedure.

**Procedure 2 (Measurement-based Preparation with Error Detection).** Consider the preparation of a $Q_1$ state of length

$N$ from Procedure 1. We further incorporate an error detection gadget within each level of recursion, $k = 1, \dots, n$, consisting of the following two steps.

(1) For all $2^{n-k}$ instances of prepared $|q_K\rangle$ states at the $k^{th}$ level of recursion, we first determine the syndrome of the error in the measurement outcome $\mathbf{m}$ as follows. When Pauli $Z \otimes Z$ measurements are performed (i.e, Case 1 of Lemma 1), we determine the syndrome of the error term $e_X$ in the measurement outcome $\mathbf{m}$ as, $P_K^\top(\mathbf{e}_X)|_{Z(k-1)} = P_K(\mathbf{m})|_{Z(k-1)} \oplus \mathbf{u}'$. Similarly, when Pauli $X \otimes X$ measurements are performed (i.e, Case 2 of Lemma 1), we determine the syndrome of the error term $e_Z$ as, $P_K(\mathbf{e}_Z)|_{\chi_{(k-1)}} = P_K^\top(\mathbf{m})|_{\chi_{(k-1)}} \oplus \mathbf{v}'$.

(2) If the syndrome is the zero vector for all the $2^{n-k}$ instances of $|q_K\rangle$, we determine the value of $\mathbf{x}$ or $\mathbf{z}$ for all prepared states as in Lemma 1, and proceed to the next level of recursion. Otherwise, we declare a preparation failure.

In case Procedure 2 fails, we may restart the procedure from the beginning, by initializing $N$ qubits in a Pauli $Z$ basis state.

The fault-tolerance of the successfully prepared state (i.e., when errors are not detected at any recursion level $k=1$ to $n$), follows from Theorem 3, which is proven in Appendix D.2.

**Theorem 3.** Consider the measurement-based preparation with error detection from Procedure 2. Suppose a successful preparation of $|q_N\rangle$, where $T_n$ component failures occur during the preparation. Let $e_X^f, e_Z^f \in \{0, 1\}^N$ be the final Pauli $X$ and $Z$ errors in the noisy prepared state $|q'_N\rangle$, due to the component failures. Then, there exist equivalent errors $e_X'^f \equiv e_X^f$ and $e_Z'^f \equiv e_Z^f$, so that $\text{wt}(e_X'^f) \le T_n$ and $\text{wt}(e_Z'^f) \le T_n$, where $\text{wt}(\mathbf{u})$ denotes the Hamming weight of $\mathbf{u}$.

Theorem 3 implies that the weight of $X$ and $Z$ errors on a successfully prepared state remains small given a sufficiently low component failure probability $p$. In particular, it upper bounds the average weight of the final error by $N(1 + 2 \log N)p$. Our numerical simulation suggests that the average error weight is much lower than $N(1 + 2 \log N)p$, which is expected as we discard the preparations where errors are detected.

## VI. Fault-tolerant error correction

For fault-tolerant error correction of $Q_1$ codes, we consider Steane error correction (See Appendix B.3 for the details of Steane error correction applied to CSS quantum polar codes). The $Q_1$ states, needed in the Steane error
<figure><img src="image_5.png" /><figcaption>Fig. 4: Monte-Carlo (MC) and Density-evolution (DE) based evaluation of the LER, for $Q_1$ and Shor codes of length $N = 16$ and $N = 64$.</figcaption></figure>

correction, are prepared using Procedure 2, assuming a circuit-level depolarizing noise model. Further, as Procedure 2 consists of error detection, we consider $Q_1$ code states of small lengths $N = 16, 64$.

Let $p_{\text{prep}} = \lim_{R \to \infty} \frac{t}{R}$ be the preparation rate, where $t$ is the number of successful preparations out of $R$ preparation attempts. For a component failure probability $p = 10^{-3}$, our numerical simulation gives $p_{\text{prep}} \approx 0.88$ and $p_{\text{prep}} \approx 0.47$, respectively, for $Q_1(N = 16, i = 7)$ and $Q_1(N = 64, i = 23)$ codes (See Fig. 16 in Appendix E.2).

The numerical estimate of the LER for $Q_1$ and Shor codes of length $N = 16$ and $N = 64$ qubits are given in Fig. 4. The LER has been estimated by Monte-Carlo (MC) simulation of the Steane error correction procedure, until a number of $f$ logical errors are reported, where $f$ is taken to be between 50 and 200. We also provide a theoretical upper-bound of the LER based on density evolution (DE), providing a trustworthy extrapolation of the LER for smaller values of $p$. It can be also observed that the pseudothreshold (crossing point between the LER curve and the diagonal line [25, 26]) of the $Q_1(N = 16, i = 7)$ code is $p_{\text{th}} \approx 0.001$, while for the $Q_1(N = 64, i = 23)$ code, we get $p_{\text{th}} \approx 0.01$.

We have provided more details about the numerical simulation of fault tolerant error correction in Appendix E.

In Table I, we compare the error correction performance of the $Q_1$ code of length $N = 64$, with previous simulations on surface and color codes of similar lengths from the literature, under circuit level depolarizing noise [10, 27]. We can see that the $Q_1$ code has a better pseudo-threshold value than the considered sur-

face and color codes. In terms of logical error rates, the performance of the $Q_1$ code is between that of the two surface codes, while being significantly better than that of the color code. This establishes that polar codes are of independent interest and may provide a potential alternative for FTQC.

However, we emphasize that the above comparison must be interpreted carefully. For example, even though we have considered similar code-lengths, the overhead in terms of qubits may be quite different for each scheme. As we use Steane error correction, we need two codestates for each round of correction. Hence, the number of ancilla qubits per round of error correction is twice the code-length. Offline preparation of these ancilla qubits may further incur qubit overheads due to error-detection, especially at high physical error rates. Surface and color codes are based on error syndrome extraction by measuring stabilizer generators. For surface code, each generator measurement requires one ancilla, hence, requiring approximately the same number of ancilla qubits as the code-length. For color codes, the number of ancilla qubits depends, whether the syndrome extraction is done using Shor's extraction technique or using flag qubits [27, 28].

Further, time overheads required or the gates applied during each error correction step may also be quite different. For example, $Q_1$ codes correct errors after each round of syndrome extraction. However, Surface and color codes require $d$ (minimum distance) rounds of syndrome extraction to account for the errors in syndrome, hence incurring an extra time-overhead and requiring more CNOT gates [10, 26, 27].

## VII. Discussion

Polar encoded quantum computation may be seen as an error correction centric approach to FTQC. It exploits a family of codes that have met with remarkable success, fueled by their excellent error correction performance, under practical, low complexity decoding. In this paper, we focused on two closely related ingredients of FTQC, namely fault-tolerant code state preparation and fault-tolerant error correction. We considered polar codes encoding one logical qubit, referred to as $Q_1$ codes, constituting a case of practical interest to FTQC (they support transversal logical CNOT gate), and which we showed to be a meaningful generalization of the well-known Shor codes. We may also notice that the preparation procedure presented here naturally extends to the case of quantum polar codes encoding several logical qubits, provided they are encoded in consecutive information positions.
<figure><img src="image_5.png" /><figcaption>Fig. 4: Monte-Carlo (MC) and Density-evolution (DE) based evaluation of the LER, for $Q_1$ and Shor codes of length $N = 16$ and $N = 64$.</figcaption></figure>

correction, are prepared using Procedure 2, assuming a circuit-level depolarizing noise model. Further, as Procedure 2 consists of error detection, we consider $Q_1$ code states of small lengths $N = 16, 64$.

Let $p_{\text{prep}} = \lim_{R \to \infty} \frac{t}{R}$ be the preparation rate, where $t$ is the number of successful preparations out of $R$ preparation attempts. For a component failure probability $p = 10^{-3}$, our numerical simulation gives $p_{\text{prep}} \approx 0.88$ and $p_{\text{prep}} \approx 0.47$, respectively, for $Q_1(N = 16, i = 7)$ and $Q_1(N = 64, i = 23)$ codes (See Fig. 16 in Appendix E.2).

The numerical estimate of the LER for $Q_1$ and Shor codes of length $N = 16$ and $N = 64$ qubits are given in Fig. 4. The LER has been estimated by Monte-Carlo (MC) simulation of the Steane error correction procedure, until a number of $f$ logical errors are reported, where $f$ is taken to be between 50 and 200. We also provide a theoretical upper-bound of the LER based on density evolution (DE), providing a trustworthy extrapolation of the LER for smaller values of $p$. It can be also observed that the pseudothreshold (crossing point between the LER curve and the diagonal line [25, 26]) of the $Q_1(N = 16, i = 7)$ code is $p_{\text{th}} \approx 0.001$, while for the $Q_1(N = 64, i = 23)$ code, we get $p_{\text{th}} \approx 0.01$.

We have provided more details about the numerical simulation of fault tolerant error correction in Appendix E.

In Table I, we compare the error correction performance of the $Q_1$ code of length $N = 64$, with previous simulations on surface and color codes of similar lengths from the literature, under circuit level depolarizing noise [10, 27]. We can see that the $Q_1$ code has a better pseudo-threshold value than the considered

surface and color codes. In terms of logical error rates, the performance of the $Q_1$ code is between that of the two surface codes, while being significantly better than that of the color code. This establishes that polar codes are of independent interest and may provide a potential alternative for FTQC.

However, we emphasize that the above comparison must be interpreted carefully. For example, even though we have considered similar code-lengths, the overhead in terms of qubits may be quite different for each scheme. As we use Steane error correction, we need two codestates for each round of correction. Hence, the number of ancilla qubits per round of error correction is twice the code-length. Offline preparation of these ancilla qubits may further incur qubit overheads due to error-detection, especially at high physical error rates. Surface and color codes are based on error syndrome extraction by measuring stabilizer generators. For surface code, each generator measurement requires one ancilla, hence, requiring approximately the same number of ancilla qubits as the code-length. For color codes, the number of ancilla qubits depends, whether the syndrome extraction is done using Shor's extraction technique or using flag qubits [27, 28].

Further, time overheads required or the gates applied during each error correction step may also be quite different. For example, $Q_1$ codes correct errors after each round of syndrome extraction. However, Surface and color codes require $d$ (minimum distance) rounds of syndrome extraction to account for the errors in syndrome, hence incurring an extra time-overhead and requiring more CNOT gates [10, 26, 27].

## VII. Discussion

Polar encoded quantum computation may be seen as an error correction centric approach to FTQC. It exploits a family of codes that have met with remarkable success, fueled by their excellent error correction performance, under practical, low complexity decoding. In this paper, we focused on two closely related ingredients of FTQC, namely fault-tolerant code state preparation and fault-tolerant error correction. We considered polar codes encoding one logical qubit, referred to as $Q_1$ codes, constituting a case of practical interest to FTQC (they support transversal logical CNOT gate), and which we showed to be a meaningful generalization of the well-known Shor codes. We may also notice that the preparation procedure presented here naturally extends to the case of quantum polar codes encoding several logical qubits, provided they are encoded in consecutive information positions.
<table><caption>TABLE I: Comparison of $Q_1$ codes with surface and color codes.</caption><thead><tr><th rowspan="2">Codes</th><th rowspan="2">Code length (N), Min. distance (d)</th><th rowspan="2">pseudo-threshold</th><th colspan="3">Logical error rate</th></tr><tr><th>p = 5 × 10<sup>-3</sup></th><th>p = 10<sup>-3</sup></th><th>p = 10<sup>-4</sup></th></tr></thead><tbody><tr><td rowspan="2">Surface codes<sup>(*)</sup> [10, Fig.4a]</td><td>N = 49, d = 7</td><td>3.5 × 10<sup>-3</sup></td><td>9 × 10<sup>-3</sup></td><td>9 × 10<sup>-6</sup></td><td>9 × 10<sup>-10</sup><br>(extrapolated)</td></tr><tr><td>N = 81, d = 9</td><td>4.2 × 10<sup>-3</sup></td><td>7 × 10<sup>-3</sup></td><td>8 × 10<sup>-7</sup><br>(extrapolated)</td><td>2 × 10<sup>-12</sup><br>(extrapolated)</td></tr><tr><td>Hexagonal color codes<sup>(*)</sup> [27, Fig.3]</td><td>N = 61, d = 9</td><td>3 × 10<sup>-4</sup></td><td>5 × 10<sup>-1</sup></td><td>3 × 10<sup>-2</sup></td><td>10<sup>-6</sup></td></tr><tr><td>$Q_1$ codes</td><td>N = 64, d = 8</td><td>10<sup>-2</sup></td><td>8 × 10<sup>-4</sup></td><td>2 × 10<sup>-6</sup></td><td>3 × 10<sup>-10</sup></td></tr></tbody></table>

Our numerical results suggest that for a circuit-level de-polarizing noise model, there exists a pseudo-threshold below which the logical error rate is smaller than physical error rate. In particular, the pseudo-thresholds for $Q_1$ codes of length $N = 16, 64$ are around $10^{-3}$ and $10^{-2}$, respectively. Moreover, for $N = 64$, the logical error rate is around $10^{-6}$ for a practically interesting physical error rate $10^{-3}$, showing the promise of the proposed fault tolerant error correction.

One can prepare asymptotically large states, by incorporating concatenation [29, 30] in our preparation. Precisely, we replace each physical qubit by a logical qubit and then do recursive logical Pauli $Z \otimes Z$ and Pauli $X \otimes X$ measurements. As failure probabilities of the logical measurements is smaller than the physical measurements, we will have a better preparation rate after each level of concatenation. The concatenated codes, however, are not $Q_1$ codes themselves and would require a greater qubit overhead with respect to the family of $Q_1$ codes, hence may not be an ideal choice in practice. As explained below, one might avoid using concatenation in practice, with the help of some improvement on our preparation procedure.

First, let us note that the current estimates of the logical error rate needed to run large scale quantum algorithms are around $10^{-15}$ [10, 31], which could be achieved by preparing $Q_1$ code states of length 256 and 1024, for physical error rates in the range $10^{-3} - 10^{-4}$. We discuss below two possible improvements, which may allow to prepare larger $Q_1$ code states, with reasonably high probability, therefore avoiding concatenation in a practical scenario.

The first such improvement would be to consider a factory preparation, where several code-states are prepared in parallel. In this scenario, due to the recursive nature of the preparation, one may not have to disregard completely a preparation, every time an error is detected. Therefore, a factory preparation might improve

the preparation rate (similar to the magic state distillation case [32, 33]).

The second improvement would be to consider error correction in place of error detection. This may work for specific $Q_1$ codes only, as the classical code defined by the measurement outcomes needs to be a good code, with large enough minimum distance (to ensure good error correction capabilities).

The detailed analysis of the above proposals is left for future works.

Finally, we note that our preparation procedure requires distant interactions between qubits, which may be possible on some quantum technologies only such as ion traps [34, 35]. Yet, for quantum systems with local interaction constraints, it may be possible to reduce the number of distant operations required to prepare small $Q_1$ codes, by arranging the qubits in an appropriate manner (taking advantage of the polar code structure). Distant operations may then be implemented through the use of swap gates [36, 37], or by physically moving the qubits around [38–40]. For longer codes, solutions have to be sought that may heavily depend on the specific quantum technology.

*Acknowledgment:* The authors would like to thank Davide Orsucci for useful discussions. This work was supported by the QuantERA grant EQUIP, by the French Agence Nationale de la Recherche, ANR-22-QUA2-0005-01.

## A. Classical Polar Codes

### A.1. Encoding

The encoding of classical polar codes is done by applying the reversible XOR gate recursively on an $N$ bit input

<footnote>(*) For a fair comparison with $Q_1$ codes, reported logical error rates for surface and color codes should be multiplied by two, since they only account for one type of errors. Moreover, following [27], the corresponding pseudo-thresholds are defined as the physical error rate $p$ in which the logical error rate curve $P^L(p)$ intersects with the line $P^L = 2p/3$. We also note that the surface codes in [10] are actually of length $N = 2d^2 - 2d + 1$; the code length reported here $N = d^2$ corresponds to the rotated surface code variant (minimizing the number of qubits for a given minimum distance).</footnote>
<table><caption>TABLE I: Comparison of $Q_1$ codes with surface and color codes.</caption><thead><tr><th rowspan="2">Codes</th><th rowspan="2">Code length (N), Min. distance (d)</th><th rowspan="2">pseudo-threshold</th><th colspan="3">Logical error rate</th></tr><tr><th>p = 5 × 10<sup>-3</sup></th><th>p = 10<sup>-3</sup></th><th>p = 10<sup>-4</sup></th></tr></thead><tbody><tr><td rowspan="2">Surface codes<sup>(*)</sup> [10, Fig.4a]</td><td>N = 49, d = 7</td><td>3.5 × 10<sup>-3</sup></td><td>9 × 10<sup>-3</sup></td><td>9 × 10<sup>-6</sup></td><td>9 × 10<sup>-10</sup><br>(extrapolated)</td></tr><tr><td>N = 81, d = 9</td><td>4.2 × 10<sup>-3</sup></td><td>7 × 10<sup>-3</sup></td><td>8 × 10<sup>-7</sup><br>(extrapolated)</td><td>2 × 10<sup>-12</sup><br>(extrapolated)</td></tr><tr><td>Hexagonal color codes<sup>(*)</sup> [27, Fig.3]</td><td>N = 61, d = 9</td><td>3 × 10<sup>-4</sup></td><td>5 × 10<sup>-1</sup></td><td>3 × 10<sup>-2</sup></td><td>10<sup>-6</sup></td></tr><tr><td>$Q_1$ codes</td><td>N = 64, d = 8</td><td>10<sup>-2</sup></td><td>8 × 10<sup>-4</sup></td><td>2 × 10<sup>-6</sup></td><td>3 × 10<sup>-10</sup></td></tr></tbody></table>

Our numerical results suggest that for a circuit-level de-polarizing noise model, there exists a pseudo-threshold below which the logical error rate is smaller than physical error rate. In particular, the pseudo-thresholds for $Q_1$ codes of length $N = 16, 64$ are around $10^{-3}$ and $10^{-2}$, respectively. Moreover, for $N = 64$, the logical error rate is around $10^{-6}$ for a practically interesting physical error rate $10^{-3}$, showing the promise of the proposed fault tolerant error correction.

One can prepare asymptotically large states, by incorporating concatenation [29, 30] in our preparation. Precisely, we replace each physical qubit by a logical qubit and then do recursive logical Pauli $Z \otimes Z$ and Pauli $X \otimes X$ measurements. As failure probabilities of the logical measurements is smaller than the physical measurements, we will have a better preparation rate after each level of concatenation. The concatenated codes, however, are not $Q_1$ codes themselves and would require a greater qubit overhead with respect to the family of $Q_1$ codes, hence may not be an ideal choice in practice. As explained below, one might avoid using concatenation in practice, with the help of some improvement on our preparation procedure.

First, let us note that the current estimates of the logical error rate needed to run large scale quantum algorithms are around $10^{-15}$ [10, 31], which could be achieved by preparing $Q_1$ code states of length 256 and 1024, for physical error rates in the range $10^{-3} - 10^{-4}$. We discuss below two possible improvements, which may allow to prepare larger $Q_1$ code states, with reasonably high probability, therefore avoiding concatenation in a practical scenario.

The first such improvement would be to consider a factory preparation, where several code-states are prepared in parallel. In this scenario, due to the recursive nature of the preparation, one may not have to disregard completely a preparation, every time an error is detected. Therefore, a factory preparation might improve

the preparation rate (similar to the magic state distillation case [32, 33]).

The second improvement would be to consider error correction in place of error detection. This may work for specific $Q_1$ codes only, as the classical code defined by the measurement outcomes needs to be a good code, with large enough minimum distance (to ensure good error correction capabilities).

The detailed analysis of the above proposals is left for future works.

Finally, we note that our preparation procedure requires distant interactions between qubits, which may be possible on some quantum technologies only such as ion traps [34, 35]. Yet, for quantum systems with local interaction constraints, it may be possible to reduce the number of distant operations required to prepare small $Q_1$ codes, by arranging the qubits in an appropriate manner (taking advantage of the polar code structure). Distant operations may then be implemented through the use of swap gates [36, 37], or by physically moving the qubits around [38–40]. For longer codes, solutions have to be sought that may heavily depend on the specific quantum technology.

*Acknowledgment:* The authors would like to thank Davide Orsucci for useful discussions. This work was supported by the QuantERA grant EQUIP, by the French Agence Nationale de la Recherche, ANR-22-QUA2-0005-01.

## A. Classical Polar Codes

### A.1. Encoding

The encoding of classical polar codes is done by applying the reversible XOR gate recursively on an $N$ bit input

<footnote>(*) For a fair comparison with $Q_1$ codes, reported logical error rates for surface and color codes should be multiplied by two, since they only account for one type of errors. Moreover, following [27], the corresponding pseudo-thresholds are defined as the physical error rate $p$ in which the logical error rate curve $P^L(p)$ intersects with the line $P^L = 2p/3$. We also note that the surface codes in [10] are actually of length $N = 2d^2 - 2d + 1$; the code length reported here $N = d^2$ corresponds to the rotated surface code variant (minimizing the number of qubits for a given minimum distance).</footnote>
$u = (u_1, \dots, u_N) \in \{0, 1\}^N$, where $N = 2^n$, with $n > 0$ (see Fig. 5). For a set of positions $\mathcal{F} \subseteq \{1, \dots, N\}$, the corresponding component $u|_{\mathcal{F}} \in \{0, 1\}^{|\mathcal{F}|}$ of the input vector $u$ is frozen. We may take $u|_{\mathcal{F}}$ to be any vector in $\{0, 1\}^{|\mathcal{F}|}$, but it should be known to both the encoder and the decoder. The set $\mathcal{F}$ is called the frozen set. The remaining positions $\mathcal{I} := \{1, \dots, N\} \setminus \mathcal{F}$ are used to encode information bits. The set $\mathcal{I}$ is called the information set.

In the following, we denote by $\mathcal{P}(N, \mathcal{F}, u|_{\mathcal{F}})$, the classical polar code of length $N$, frozen positions $\mathcal{F}$, and frozen vector $u|_{\mathcal{F}} \in \{0, 1\}^{|\mathcal{F}|}$.

The action of the XOR$_{2 \to 1}$ gate on input $u = (u_1, u_2) \in \{0, 1\}^2$ gives $x = (u_1 \oplus u_2, u_2)$. In matrix form, we may write $x = P_2 u$, where

$$P_2 = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \qquad (A1)$$

The classical polar transform, that is, the recursive application of XOR$_{2 \to 1}$ on $N = 2^n$ qubits, is thus given by the matrix

$$P_N = P_2^{\otimes n}. \qquad (A2)$$

For any value of the information bits $u_{\mathcal{I}} \in \{0, 1\}^{|\mathcal{I}|}$, $x = P_N(u|_{\mathcal{F}}, u|_{\mathcal{I}}) \in \{0, 1\}^N$ is a codeword of the polar code $\mathcal{P}(N, F, u|_{\mathcal{F}})$. If $u|_{\mathcal{F}}$ is the all zero vector, the polar code $\mathcal{P}(N, \mathcal{F}, u|_{\mathcal{F}})$ is generated by the columns of $P_N$ corresponding to the information set $\mathcal{I}$.

## A.2. Construction

The construction of a classical polar code refers to the choice of the information set $\mathcal{I}$ (or, equivalently, the frozen set $\mathcal{F}$). This is done in a channel specific way as follows.

Consider a discrete, memoryless, classical channel $W(y|x)$, with binary input $x \in \{0, 1\}$, and output $y \in \mathcal{Y}$. For $u \in \{0, 1\}^N$, let $x = P_N(u) \in \{0, 1\}^N$ (note that here $\mathcal{F}$ and $\mathcal{I}$ need not be defined) and $y \in \mathcal{Y}^N$ be the output corresponding to $N$ uses of the $W$ channel, with inputs $x_1, \dots, x_N$. For $i = 1, \dots, N$, let $W^{(i)}(y, u_{1:i-1} | u_i)$ denote the so-called virtual channel, with input $u_i \in \{0, 1\}$ and output $(y, u_{1:i-1}) \in \mathcal{Y} \times \{0, 1\}^{i-1}$, where $u_{1:i-1} := (u_1, \dots, u_{i-1})$.

Informally, the channel polarization theorem [3] states that, for sufficiently large $N$, almost all the virtual channels become arbitrarily close to either the noiseless (perfect) channel or to the completely noisy (useless) channel. The closeness to the either perfect or useless channel can be expressed in terms of different parameters, such as the

mutual information $I(W^{(i)})$, the Bhattacharyya parameter $Z(W^{(i)})$, or the error probability $P_e(W^{(i)})$, which can be computed analytically for some channels (e.g., binary erasure channels), or estimated numerically through density evolution, for more general channels [24]. Once one of these parameters is computed for all the virtual channels, they are sorted from the most reliable (closest to the perfect channel) to the least reliable (closest to the useless channel) one.

For a polar code encoding $K$ information bits, the information set $\mathcal{I}$ consists of the indexes corresponding to the $K$ most reliable virtual channels (equivalently, the $N-K$ least reliable virtual channels are frozen). The usefulness of this construction will become apparent in relation to the successive cancellation decoding, discussed in the next section.

## A.3. Decoding

Classical polar codes come equipped with an efficient successive cancellation (SC) decoding algorithm. SC decoding takes advantage of the polar code construction, by estimating inputs $u_1, \dots, u_N$ sequentially. For $i = 1, \dots, N$, SC decoding outputs the maximum a posteriori estimate.

<figure><img src="image_6.png" /><figcaption>(a) $P_N = P_{N/2} \otimes P_2$</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Classical polar code $\mathcal{P}(N = 8, \mathcal{F} = \{1, 2, 3\}, 0|_{\mathcal{F}})$</figcaption></figure>

<caption>Fig. 5: (a) Polar transform recursion: $P_N$ in terms of $P_{N/2}$. (b) Example of a classical polar code encoding $|\mathcal{I}| = 5$ bits into $N = 2^3$ bits, with frozen set $\mathcal{F} = \{1, 2, 3\}$, and frozen vector $u_{\mathcal{F}} = (0, 0, 0)$. Here, the set $\mathcal{F}$ (thus, $\mathcal{I}$) is chosen only for the purpose and the simplicity of the illustration. In general, it needs not consist of consecutive positions.</caption>
$u = (u_1, \dots, u_N) \in \{0, 1\}^N$, where $N = 2^n$, with $n > 0$ (see Fig. 5). For a set of positions $\mathcal{F} \subseteq \{1, \dots, N\}$, the corresponding component $u|_{\mathcal{F}} \in \{0, 1\}^{|\mathcal{F}|}$ of the input vector $u$ is frozen. We may take $u|_{\mathcal{F}}$ to be any vector in $\{0, 1\}^{|\mathcal{F}|}$, but it should be known to both the encoder and the decoder. The set $\mathcal{F}$ is called the frozen set. The remaining positions $\mathcal{I} := \{1, \dots, N\} \setminus \mathcal{F}$ are used to encode information bits. The set $\mathcal{I}$ is called the information set.

In the following, we denote by $\mathcal{P}(N, \mathcal{F}, u|_{\mathcal{F}})$, the classical polar code of length $N$, frozen positions $\mathcal{F}$, and frozen vector $u|_{\mathcal{F}} \in \{0, 1\}^{|\mathcal{F}|}$.

The action of the XOR$_{2 \to 1}$ gate on input $u = (u_1, u_2) \in \{0, 1\}^2$ gives $x = (u_1 \oplus u_2, u_2)$. In matrix form, we may write $x = P_2 u$, where

$$P_2 = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \qquad (A1)$$

The classical polar transform, that is, the recursive application of XOR$_{2 \to 1}$ on $N = 2^n$ qubits, is thus given by the matrix

$$P_N = P_2^{\otimes n}. \qquad (A2)$$

For any value of the information bits $u_{\mathcal{I}} \in \{0, 1\}^{|\mathcal{I}|}$, $x = P_N(u|_{\mathcal{F}}, u|_{\mathcal{I}}) \in \{0, 1\}^N$ is a codeword of the polar code $\mathcal{P}(N, F, u|_{\mathcal{F}})$. If $u|_{\mathcal{F}}$ is the all zero vector, the polar code $\mathcal{P}(N, \mathcal{F}, u|_{\mathcal{F}})$ is generated by the columns of $P_N$ corresponding to the information set $\mathcal{I}$.

## A.2. Construction

The construction of a classical polar code refers to the choice of the information set $\mathcal{I}$ (or, equivalently, the frozen set $\mathcal{F}$). This is done in a channel specific way as follows.

Consider a discrete, memoryless, classical channel $W(y|x)$, with binary input $x \in \{0, 1\}$, and output $y \in \mathcal{Y}$. For $u \in \{0, 1\}^N$, let $x = P_N(u) \in \{0, 1\}^N$ (note that here $\mathcal{F}$ and $\mathcal{I}$ need not be defined) and $y \in \mathcal{Y}^N$ be the output corresponding to $N$ uses of the $W$ channel, with inputs $x_1, \dots, x_N$. For $i = 1, \dots, N$, let $W^{(i)}(y, u_{1:i-1} | u_i)$ denote the so-called virtual channel, with input $u_i \in \{0, 1\}$ and output $(y, u_{1:i-1}) \in \mathcal{Y} \times \{0, 1\}^{i-1}$, where $u_{1:i-1} := (u_1, \dots, u_{i-1})$.

Informally, the channel polarization theorem [3] states that, for sufficiently large $N$, almost all the virtual channels become arbitrarily close to either the noiseless (perfect) channel or to the completely noisy (useless) channel. The closeness to the either perfect or useless channel can be expressed in terms of different parameters, such as the

mutual information $I(W^{(i)})$, the Bhattacharyya parameter $Z(W^{(i)})$, or the error probability $P_e(W^{(i)})$, which can be computed analytically for some channels (e.g., binary erasure channels), or estimated numerically through density evolution, for more general channels [24]. Once one of these parameters is computed for all the virtual channels, they are sorted from the most reliable (closest to the perfect channel) to the least reliable (closest to the useless channel) one.

For a polar code encoding $K$ information bits, the information set $\mathcal{I}$ consists of the indexes corresponding to the $K$ most reliable virtual channels (equivalently, the $N-K$ least reliable virtual channels are frozen). The usefulness of this construction will become apparent in relation to the successive cancellation decoding, discussed in the next section.

## A.3. Decoding

Classical polar codes come equipped with an efficient successive cancellation (SC) decoding algorithm. SC decoding takes advantage of the polar code construction, by estimating inputs $u_1, \dots, u_N$ sequentially. For $i = 1, \dots, N$, SC decoding outputs the maximum a posteriori estimate.

<figure><img src="image_6.png" /><figcaption>(a) $P_N = P_{N/2} \otimes P_2$</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Classical polar code $\mathcal{P}(N = 8, \mathcal{F} = \{1, 2, 3\}, \mathbf{0}|_{\mathcal{F}})$</figcaption></figure>

<caption>Fig. 5: (a) Polar transform recursion: $P_N$ in terms of $P_{N/2}$. (b) Example of a classical polar code encoding $|\mathcal{I}| = 5$ bits into $N = 2^3$ bits, with frozen set $\mathcal{F} = \{1, 2, 3\}$, and frozen vector $u_{\mathcal{F}} = (0, 0, 0)$. Here, the set $\mathcal{F}$ (thus, $\mathcal{I}$) is chosen only for the purpose and the simplicity of the illustration. In general, it needs not consist of consecutive positions.</caption>
timate $\hat{u}_i$ of $u_i$, conditional on the observed output $\mathbf{y}$ and previous estimates $\hat{u}_{1:i-1} = (\hat{u}_1, \dots, \hat{u}_{i-1})$. Precisely, we have

$$ \hat{u}_i := \begin{cases} u_i, & \text{if } i \in \mathcal{F} \\ \arg\max_{u \in \{0,1\}} W^{(i)}(\mathbf{y}, \hat{u}_{1:i-1} | u), & \text{if } i \in \mathcal{I} \end{cases} \quad (A3) $$

If the information set contains indexes of good virtual channels (close to the perfect channel), the maximum a posteriori estimate $\hat{u}_i$ is equal to the input $u_i$ with high probability. This does not happen for bad virtual channels (close to the useless channel), which must then be frozen, so that the corresponding inputs are known to both the encoder and decoder. It is worth noticing that the maximum a posteriori decoding of the virtual channels can be performed in an efficient way, by using a message passing algorithm that takes advantage of the recursive structure of the polar code [3]. Overall, the complexity of the SC decoding scales as $O(N \log(N))$.

Finally, we note that Polar codes under SC decoding are known to achieve the channel capacity [3]. This means that for sufficiently large $N$, it is possible to choose an information set of size $|\mathcal{I}|$ arbitrary close of $NI(W)$, where $I(W)$ is the channel's mutual information, while ensuring an arbitrary small error probability under SC decoding.

## B. Quantum Polar Codes

### B.1. Encoding

The encoding of quantum information for CSS quantum polar codes is briefly given in Section II. In this section, we provide more details.

Recall from Section II that the quantum polar transform $Q_N$ corresponds to the recursive action of the quantum CNOT gate on an $N$-qubit quantum state. The quantum CNOT gate induces the reversible XOR gate in the Pauli $Z$ and Pauli $X$ bases. Precisely, $CNOT_{2 \to 1}$ acts as XOR$_{2 \to 1}$ in the Pauli $Z$ basis, while it acts as XOR$_{1 \to 2}$ in the Pauli $X$ basis. Hence, it follows that $Q_N$ acts as the classical polar transform $P_N$ in the Pauli $Z$ basis, while it acts as the reverse classical polar transform (i.e., with inverted target and control bits) in the Pauli $X$ basis.

It can be seen that the reversed classical polar transform is described by $P_N^\top$, where $P_N^\top$ is the transpose of $P_N$ [4]. Therefore, we have the following, for $\mathbf{u} \in \{0, 1\}^N$,

$$ Q_N |\mathbf{u}\rangle = |P_N \mathbf{u}\rangle, \quad (B1) $$

$$ Q_N |\bar{\mathbf{u}}\rangle = |\bar{P}_N^\top \mathbf{u}\rangle. \quad (B2) $$

In the following, we denote by $\mathcal{Q}(N, \mathcal{Z}, \mathcal{X}, |\mathbf{u}\rangle_\mathcal{Z}, |\bar{\mathbf{v}}\rangle_\mathcal{X})$, the quantum polar code on $N$ qubits, with frozen sets $\mathcal{Z}$ and $\mathcal{X}$, corresponding to the Pauli $Z$ and Pauli $X$ bases, respectively, and with corresponding frozen quantum states $|\mathbf{u}\rangle_\mathcal{Z}$ and $|\bar{\mathbf{v}}\rangle_\mathcal{X}$. It induces two classical polar codes, one in $\mathcal{Z}$ basis, with frozen set $\mathcal{Z}$, and one in $\mathcal{X}$ basis, with frozen set $\mathcal{X}$, where the latter is defined by a reversed polar transform, as illustrated in Fig. 6.

Let $\pi$ denote the reverse order permutation of $S = \{1, \dots, N\}$, defined by $\pi(i) = N + 1 - i$. Then, the classical polar code induced in the $\mathcal{Z}$ basis is $\mathcal{P}(N, \mathcal{Z}, \mathbf{u})$, while the classical polar code induced in the $\mathcal{X}$ basis is $\mathcal{P}(N, \pi(\mathcal{X}), \pi(\mathbf{v}))$, where the vector $\pi(\mathbf{v})$ is defined by permuting the entries of $\mathbf{v}$ according to $\pi$, that is, $\pi(\mathbf{v})_i := v_{\pi(i)}$, $\forall i \in \mathcal{X}$.

The $\mathcal{X}$ and $\mathcal{Z}$ type stabilizer generators of $\mathcal{Q}(N, \mathcal{Z}, \mathcal{X}, |\mathbf{u}\rangle_\mathcal{Z}, |\bar{\mathbf{v}}\rangle_\mathcal{X})$ are given by the lemma below.

**Lemma 2.** Let $\mathcal{C}_i \in \{0, 1\}^N$ be the binary vector, with 0 everywhere except 1 at the $i$-th position. Then, the stabilizer group of $\mathcal{Q}(N, \mathcal{Z}, \mathcal{X}, |\mathbf{u}\rangle_\mathcal{Z}, |\bar{\mathbf{v}}\rangle_\mathcal{X})$ is generated by the following $\mathcal{X}$ and $\mathcal{Z}$ type operators

$$ (-1)^{v_i} X^{P_N \mathcal{C}_i}, \forall i \in \mathcal{X}. \quad (B3) $$

$$ (-1)^{\mathbf{u}_i} Z^{P_N^\top \mathcal{C}_i}, \forall i \in \mathcal{Z}. \quad (B4) $$

*Proof.* Note that the input of the polar transform, that is,

<figure><img src="image_8.png" /><figcaption>Fig. 6: Classical polar codes in (a) $\mathcal{Z}$ basis, and (b) $\mathcal{X}$ basis, induced by the CSS quantum polar code $\mathcal{Q}(N, \mathcal{Z}, \mathcal{X}, |\mathbf{u}\rangle_\mathcal{Z}, |\bar{\mathbf{v}}\rangle_\mathcal{X})$. The permutation $\pi$ in (b) is the reverse order permutation. (Note that in this example the two codes are actually the same.)</figcaption></figure>
timate $\hat{u}_i$ of $u_i$, conditional on the observed output $\mathbf{y}$ and previous estimates $\hat{u}_{1:i-1} = (\hat{u}_1, \dots, \hat{u}_{i-1})$. Precisely, we have

$$ \hat{u}_i := \begin{cases} u_i, & \text{if } i \in \mathcal{F} \\ \arg\max_{u \in \{0,1\}} W^{(i)}(\mathbf{y}, \hat{u}_{1:i-1} | u), & \text{if } i \in \mathcal{I} \end{cases} \quad (A3) $$

If the information set contains indexes of good virtual channels (close to the perfect channel), the maximum a posteriori estimate $\hat{u}_i$ is equal to the input $u_i$ with high probability. This does not happen for bad virtual channels (close to the useless channel), which must then be frozen, so that the corresponding inputs are known to both the encoder and decoder. It is worth noticing that the maximum a posteriori decoding of the virtual channels can be performed in an efficient way, by using a message passing algorithm that takes advantage of the recursive structure of the polar code [3]. Overall, the complexity of the SC decoding scales as $O(N \log(N))$.

Finally, we note that Polar codes under SC decoding are known to achieve the channel capacity [3]. This means that for sufficiently large $N$, it is possible to choose an information set of size $|\mathcal{I}|$ arbitrary close of $NI(W)$, where $I(W)$ is the channel's mutual information, while ensuring an arbitrary small error probability under SC decoding.

## B. Quantum Polar Codes

### B.1. Encoding

The encoding of quantum information for CSS quantum polar codes is briefly given in Section II. In this section, we provide more details.

Recall from Section II that the quantum polar transform $Q_N$ corresponds to the recursive action of the quantum CNOT gate on an $N$-qubit quantum state. The quantum CNOT gate induces the reversible XOR gate in the Pauli $Z$ and Pauli $X$ bases. Precisely, $CNOT_{2 \to 1}$ acts as XOR$_{2 \to 1}$ in the Pauli $Z$ basis, while it acts as XOR$_{1 \to 2}$ in the Pauli $X$ basis. Hence, it follows that $Q_N$ acts as the classical polar transform $P_N$ in the Pauli $Z$ basis, while it acts as the reverse classical polar transform (i.e., with inverted target and control bits) in the Pauli $X$ basis.

It can be seen that the reversed classical polar transform is described by $P_N^\top$, where $P_N^\top$ is the transpose of $P_N$ [4]. Therefore, we have the following, for $\mathbf{u} \in \{0, 1\}^N$,

$$ Q_N |\mathbf{u}\rangle = |P_N \mathbf{u}\rangle, \quad (B1) $$

$$ Q_N |\bar{\mathbf{u}}\rangle = |\bar{P}_N^\top \mathbf{u}\rangle. \quad (B2) $$

In the following, we denote by $\mathcal{Q}(N, \mathcal{Z}, \mathcal{X}, |\mathbf{u}\rangle_\mathcal{Z}, |\bar{\mathbf{v}}\rangle_\mathcal{X})$, the quantum polar code on $N$ qubits, with frozen sets $\mathcal{Z}$ and $\mathcal{X}$, corresponding to the Pauli $Z$ and Pauli $X$ bases, respectively, and with corresponding frozen quantum states $|\mathbf{u}\rangle_\mathcal{Z}$ and $|\bar{\mathbf{v}}\rangle_\mathcal{X}$. It induces two classical polar codes, one in $\mathcal{Z}$ basis, with frozen set $\mathcal{Z}$, and one in $\mathcal{X}$ basis, with frozen set $\mathcal{X}$, where the latter is defined by a reversed polar transform, as illustrated in Fig. 6.

Let $\pi$ denote the reverse order permutation of $S = \{1, \dots, N\}$, defined by $\pi(i) = N + 1 - i$. Then, the classical polar code induced in the $\mathcal{Z}$ basis is $\mathcal{P}(N, \mathcal{Z}, \mathbf{u})$, while the classical polar code induced in the $\mathcal{X}$ basis is $\mathcal{P}(N, \pi(\mathcal{X}), \pi(\mathbf{v}))$, where the vector $\pi(\mathbf{v})$ is defined by permuting the entries of $\mathbf{v}$ according to $\pi$, that is, $\pi(\mathbf{v})_i := v_{\pi(i)}$, $\forall i \in \mathcal{X}$.

The $\mathcal{X}$ and $\mathcal{Z}$ type stabilizer generators of $\mathcal{Q}(N, \mathcal{Z}, \mathcal{X}, |\mathbf{u}\rangle_\mathcal{Z}, |\bar{\mathbf{v}}\rangle_\mathcal{X})$ are given by the lemma below.

**Lemma 2.** Let $\mathcal{C}_i \in \{0, 1\}^N$ be the binary vector, with 0 everywhere except 1 at the $i$-th position. Then, the stabilizer group of $\mathcal{Q}(N, \mathcal{Z}, \mathcal{X}, |\mathbf{u}\rangle_\mathcal{Z}, |\bar{\mathbf{v}}\rangle_\mathcal{X})$ is generated by the following $\mathcal{X}$ and $\mathcal{Z}$ type operators

$$ (-1)^{v_i} X^{P_N \mathcal{C}_i}, \forall i \in \mathcal{X}. \quad (B3) $$

$$ (-1)^{\mathbf{u}_i} Z^{P_N^\top \mathcal{C}_i}, \forall i \in \mathcal{Z}. \quad (B4) $$

*Proof.* Note that the input of the polar transform, that is,

<figure><img src="image_8.png" /><figcaption>Fig. 6: Classical polar codes in (a) $\mathcal{Z}$ basis, and (b) $\mathcal{X}$ basis, induced by the CSS quantum polar code $\mathcal{Q}(N, \mathcal{Z}, \mathcal{X}, |\mathbf{u}\rangle_\mathcal{Z}, |\bar{\mathbf{v}}\rangle_\mathcal{X})$. The permutation $\pi$ in (b) is the reverse order permutation. (Note that in this example the two codes are actually the same.)</figcaption></figure>
the quantum state $|u\rangle_Z \otimes |\phi\rangle_I \otimes |\bar{v}\rangle_X$, is stabilized by the following Pauli operators

$$(-1)^{v_i} X^{\mathcal{E}_i}, \forall i \in \mathcal{X}, \qquad (B5)$$

$$(-1)^{u_i} Z^{\mathcal{E}_i}, \forall i \in \mathcal{Z}. \qquad (B6)$$

Therefore, the encoded quantum state $|\tilde{\phi}\rangle_S = Q_N(|u\rangle_Z \otimes |\phi\rangle_I \otimes |\bar{v}\rangle_X)$ is stabilized by the following Pauli operators,

$$(-1)^{v_i} Q_N X^{\mathcal{E}_i} Q_N, \forall i \in \mathcal{X}, \qquad (B7)$$

$$(-1)^{u_i} Q_N Z^{\mathcal{E}_i} Q_N, \forall i \in \mathcal{Z}. \qquad (B8)$$

The operators in (B7)-(B8) are a generating set of the stabilizer group of $Q(N, \mathcal{Z}, \mathcal{X}, |u\rangle_Z, |\bar{v}\rangle_X)$. These generators can be written in terms of classical polar transforms $P_N$ and $P_N^\top$ as follows.

We first consider the case of two qubits, and observe that the sandwiching actions of the CNOT gate on Pauli operators gives, for $u \in \{0, 1\}^2$,

$$\text{CNOT}_{2 \to 1} X^u \text{CNOT}_{2 \to 1} = X^{P_2 u}, \qquad (B9)$$

$$\text{CNOT}_{2 \to 1} Z^u \text{CNOT}_{2 \to 1} = Z^{P_2^\top u}. \qquad (B10)$$

Using (B9)-(B10) and (A2), the sandwiching action of $Q_N$ is described by the classical polar transforms $P_N$ and $P_N^\top$, respectively, on $X$ and $Z$ type operators. Hence, the stabilizer generators from (B7)-(B8) can be written as given in (B3)-(B4) $\square$

Note, from (B3), that the indicator vector of $X$-type generators are given by the columns of $P_N$, corresponding to the set $\mathcal{X}$. Further, from (B4), the indicator vectors of the $Z$-type generators are given by the columns of $P_N^\top$ (i.e, the rows of $P_N$), corresponding to the set $\mathcal{Z}$.

Similarly to Lemma 2, logical Pauli operators can be determined by passing $X$ and $Z$ operators through the polar transform, as shown in the lemma below.

**Lemma 3.** Let $\tilde{X}_i$ and $\tilde{Z}_i$ be the logical $X$ and $Z$ operators, corresponding to the encoded qubit at the position $i \in \mathcal{I}$. Then,

$$\tilde{X}_i = X^{P_N \mathcal{E}_i}, \qquad (B11)$$

$$\tilde{Z}_i = Z^{P_N^\top \mathcal{E}_i}. \qquad (B12)$$

## B.2. Construction

The construction of a CSS quantum polar code refers to determining the frozen sets $\mathcal{Z}$ and $\mathcal{X}$ (thus, the information set $\mathcal{I}$), which exploits the classical polarization in $Z$ and $X$ bases, respectively [4]. We shall assume a Pauli channel $\mathcal{W}$, with qubit input, given by

$$\mathcal{W}(\rho) = p_I \rho + p_X X \rho X + p_Y Y \rho Y + p_Z Z \rho Z, \qquad (B13)$$

where $\rho$ denotes the density matrix of the qubit (mixed) state, and $p_I, p_X, p_Y, p_Z \in [0, 1]$ are probability values, summing to 1.

In $Z$ basis, only $X$ errors matter. Thus, the $Z$-basis induced channel, denoted $W_Z$, captures the effect of $X$-type errors on the quantum state, and is given by

$$W_Z(|u\rangle\langle u|) = (p_I + p_Z)|u\rangle\langle u| + (p_X + p_Y)X|u\rangle\langle u|X, \qquad (B14)$$

where $u \in \{0, 1\}$. Hence, $W_Z$ is a classical binary symmetric channel (BSC), with error probability $p_X + p_Y$. Similarly, the $X$-basis induced channel, denoted $W_X$, captures the effect of $Z$-type errors on the quantum state, and is given by

$$W_X(|\bar{u}\rangle\langle\bar{u}|) = (p_I + p_X)|\bar{u}\rangle\langle\bar{u}| + (p_Z + p_Y)Z|\bar{u}\rangle\langle\bar{u}|Z, \qquad (B15)$$

where $u \in \{0, 1\}$. Hence, $W_X$ is a classical BSC, with error probability $p_X + p_Y$.

To construct the CSS quantum polar code, we exploit the classical polarization of $W_Z$ and $W_X$ channels (See Section A.3). Note that this construction ignores the correlations between $X$ and $Z$ (we will explain how these correlations can be captured a little later, below). The frozen set $\mathcal{Z}$ is determined by the classical polarization of the $W_Z$ channel, under the classical polar transform $P_N$, while the frozen set $\mathcal{X}$ is determined by the classical polarization of the $W_X$, under the reversed classical polar transform $P_N^\top$. The remaining information set $\mathcal{I}$ corresponds to virtual channels that are good in both $Z$ and $X$ bases. The frozen set $\mathcal{Z}$ corresponds to virtual channels that are bad in $Z$ basis. These channels may be either bad or good in $X$ basis, it does not matter, since we need not decode $Z$ errors on corresponding inputs (such errors correspond to $Z$-type generators, thus they act trivially on the code space). Similarly, the frozen set $\mathcal{X}$ corresponds to virtual channels that are bad in $X$ basis, and which may be either bad or good in $Z$ basis. Precisely, positions in $\mathcal{X}$ that do not impact the decoding of subsequent positions in $\mathcal{I}$ (if any) may correspond to bad virtual channels in $Z$ basis. For instance, this may be the case for some positions in $\mathcal{X}$ that come after the last position in $\mathcal{I}$, i.e., some $j \in \mathcal{X}$, such that $i < j, \forall i \in \mathcal{I}$. See also Fig. 6a.

To capture the correlations between $X$ and $Z$ errors, one of the two channels, say $W_X$, has to be extended [4]. The extended channel, denoted by $W_{X'}$, is thus defined by the conditional probability of a $Z$ error, given the $X$ er-
the quantum state $|u\rangle_Z \otimes |\phi\rangle_I \otimes |\bar{v}\rangle_X$, is stabilized by the following Pauli operators

$$(-1)^{v_i} X^{\mathcal{L}_i}, \forall i \in \mathcal{X}, \qquad (B5)$$

$$(-1)^{u_i} Z^{\mathcal{L}_i}, \forall i \in \mathcal{Z}. \qquad (B6)$$

Therefore, the encoded quantum state $|\tilde{\phi}\rangle_S = Q_N(|u\rangle_Z \otimes |\phi\rangle_I \otimes |\bar{v}\rangle_X)$ is stabilized by the following Pauli operators,

$$(-1)^{v_i} Q_N X^{\mathcal{L}_i} Q_N, \forall i \in \mathcal{X}, \qquad (B7)$$

$$(-1)^{u_i} Q_N Z^{\mathcal{L}_i} Q_N, \forall i \in \mathcal{Z}. \qquad (B8)$$

The operators in (B7)-(B8) are a generating set of the stabilizer group of $Q(N, \mathcal{Z}, \mathcal{X}, |u\rangle_Z, |\bar{v}\rangle_X)$. These generators can be written in terms of classical polar transforms $P_N$ and $P_N^\top$ as follows.

We first consider the case of two qubits, and observe that the sandwiching actions of the CNOT gate on Pauli operators gives, for $u \in \{0, 1\}^2$,

$$\text{CNOT}_{2 \to 1} X^u \text{CNOT}_{2 \to 1} = X^{P_2 u}, \qquad (B9)$$

$$\text{CNOT}_{2 \to 1} Z^u \text{CNOT}_{2 \to 1} = Z^{P_2^\top u}. \qquad (B10)$$

Using (B9)-(B10) and (A2), the sandwiching action of $Q_N$ is described by the classical polar transforms $P_N$ and $P_N^\top$, respectively, on $X$ and $Z$ type operators. Hence, the stabilizer generators from (B7)-(B8) can be written as given in (B3)-(B4) $\square$

Note, from (B3), that the indicator vector of $X$-type generators are given by the columns of $P_N$, corresponding to the set $\mathcal{X}$. Further, from (B4), the indicator vectors of the $Z$-type generators are given by the columns of $P_N^\top$ (i.e, the rows of $P_N$), corresponding to the set $\mathcal{Z}$.

Similarly to Lemma 2, logical Pauli operators can be determined by passing $X$ and $Z$ operators through the polar transform, as shown in the lemma below.

**Lemma 3.** Let $\tilde{X}_i$ and $\tilde{Z}_i$ be the logical $X$ and $Z$ operators, corresponding to the encoded qubit at the position $i \in \mathcal{I}$. Then,

$$\tilde{X}_i = X^{P_N \mathcal{L}_i}, \qquad (B11)$$

$$\tilde{Z}_i = Z^{P_N^\top \mathcal{L}_i}. \qquad (B12)$$

## B.2. Construction

The construction of a CSS quantum polar code refers to determining the frozen sets $\mathcal{Z}$ and $\mathcal{X}$ (thus, the information set $\mathcal{I}$), which exploits the classical polarization in $Z$ and $X$ bases, respectively [4]. We shall assume a Pauli channel $W$, with qubit input, given by

$$W(\rho) = p_I \rho + p_X X \rho X + p_Y Y \rho Y + p_Z Z \rho Z, \qquad (B13)$$

where $\rho$ denotes the density matrix of the qubit (mixed) state, and $p_I, p_X, p_Y, p_Z \in [0, 1]$ are probability values, summing to 1.

In $Z$ basis, only $X$ errors matter. Thus, the $Z$-basis induced channel, denoted $W_Z$, captures the effect of $X$-type errors on the quantum state, and is given by

$$W_Z(|u\rangle\langle u|) = (p_I + p_Z)|u\rangle\langle u| + (p_X + p_Y)X|u\rangle\langle u|X, \qquad (B14)$$

where $u \in \{0, 1\}$. Hence, $W_Z$ is a classical binary symmetric channel (BSC), with error probability $p_X + p_Y$. Similarly, the $X$-basis induced channel, denoted $W_X$, captures the effect of $Z$-type errors on the quantum state, and is given by

$$W_X(|\bar{u}\rangle\langle\bar{u}|) = (p_I + p_X)|\bar{u}\rangle\langle\bar{u}| + (p_Z + p_Y)Z|\bar{u}\rangle\langle\bar{u}|Z, \qquad (B15)$$

where $u \in \{0, 1\}$. Hence, $W_X$ is a classical BSC, with error probability $p_X + p_Y$.

To construct the CSS quantum polar code, we exploit the classical polarization of $W_Z$ and $W_X$ channels (See Section A.3). Note that this construction ignores the correlations between $X$ and $Z$ (we will explain how these correlations can be captured a little later, below). The frozen set $\mathcal{Z}$ is determined by the classical polarization of the $W_Z$ channel, under the classical polar transform $P_N$, while the frozen set $\mathcal{X}$ is determined by the classical polarization of the $W_X$, under the reversed classical polar transform $P_N^\top$. The remaining information set $\mathcal{I}$ corresponds to virtual channels that are good in both $Z$ and $X$ bases. The frozen set $\mathcal{Z}$ corresponds to virtual channels that are bad in $Z$ basis. These channels may be either bad or good in $X$ basis, it does not matter, since we need not decode $Z$ errors on corresponding inputs (such errors correspond to $Z$-type generators, thus they act trivially on the code space). Similarly, the frozen set $\mathcal{X}$ corresponds to virtual channels that are bad in $X$ basis, and which may be either bad or good in $Z$ basis. Precisely, positions in $\mathcal{X}$ that do not impact the decoding of subsequent positions in $\mathcal{I}$ (if any) may correspond to bad virtual channels in $Z$ basis. For instance, this may be the case for some positions in $\mathcal{X}$ that come after the last position in $\mathcal{I}$, i.e., some $j \in \mathcal{X}$, such that $i < j, \forall i \in \mathcal{I}$. See also Fig. 6a.

To capture the correlations between $X$ and $Z$ errors, one of the two channels, say $W_X$, has to be extended [4]. The extended channel, denoted by $W_{X'}$, is thus defined by the conditional probability of a $Z$ error, given the $X$ er-
ror. Precisely,

$$
W_{X'}(|\bar{u}\rangle\langle\bar{u}|) = (p_I + p_Z)|0\rangle\langle0|_X \otimes \\
\left( \frac{p_I}{p_I + p_Z} |\bar{u}\rangle\langle\bar{u}| + \frac{p_Z}{p_I + p_Z} Z|\bar{u}\rangle\langle\bar{u}|Z \right) \\
+ (p_X + p_Y)|1\rangle\langle1|_X \otimes \\
\left( \frac{p_X}{p_X + p_Y} |\bar{u}\rangle\langle\bar{u}| + \frac{p_Y}{p_X + p_Y} Z|\bar{u}\rangle\langle\bar{u}|Z \right), \quad (B16)
$$

where {|0⟩<sub>X</sub>, |1⟩<sub>X</sub>} is an orthogonal basis of an auxiliary
system, indicating whether an *X* error happened or not.
Put differently, *W*<sub>X'</sub> is a classical mixture of two BSCs,
the first with error probability *p*<sub>Z</sub>/*(p*<sub>I</sub> + *p*<sub>Z</sub>)* (when no *X*
error happened), and the second with error probability
*p*<sub>Y</sub>/*(p*<sub>X</sub> + *p*<sub>Y</sub>)* (when an *X* error happened).

The construction of the CSS quantum polar code, tak-
ing into account the correlations between X and Z errors,
is done in the same way as above, while replacing the W<sub>X</sub>
channel by its extended version W<sub>X'</sub>.

B.3. Steane Error Correction

We describe here the Steane error correction proce-
dure [19, 20] (see also [2, Section 4.4]), applied to CSS
quantum polar codes. Throughout this section, we con-
sider an encoded state | ̂$\phi$ 〉<sub>S</sub> = $Q_N (|u\rangle_Z \otimes |\phi\rangle_I \otimes |\bar{v}\rangle_\chi)$ of
the quantum polar code $Q(N, Z, \mathcal{X}, |u\rangle_Z, |\bar{v}\rangle_\chi)$, that we
want to protect against Pauli errors.

Steane's error correction procedure consists of the fol-
lowing steps.

(1) An ancilla system $S'$ is prepared in either the logical all-`|+⟩` state or the logical all-`|0⟩` state of $Q(N, \mathcal{Z}, \mathcal{X}, |u\rangle_{\mathcal{Z}}, |\bar{v}\rangle_{\mathcal{X}})$. The former state is prepared for X-error correction, while the latter of Z-error correction.

(2) A transverse CNOT gate is applied between $S$ (original) and $S'$ (ancilla) systems, in such a way that either the $X$ or the $Z$ errors on $S$ are copied to $S'$, while the two systems remain separated.

(3) The ancilla system is measured, outputting a ran-
dom codeword of a classical polar code (in either
$Z$ or $X$ basis), corrupted by the error that has been
copied to $S'$.

(4) A classical SC decoding is applied to determine the error (possibly, the corresponding corrective opera- tion is applied on the S system).

It is easily seen that steps (2) and (3) are fault-tolerant,
as they consist only of transverse gates and single qubit
measurements.

By a slight abuse of language, we shall refer to steps
(1)-(3) above as syndrome extraction [41]. In case of ideal
syndrome extraction, steps (1)-(3) are assumed to be error
free, and the error corrected at step (4) is the one preex-
isting on system S, before the syndrome is extracted. In
case of noisy syndrome extraction, steps (1)-(3) may gener-
ate additional errors on systems S and S'. We will analyze
the impact of these errors, together with providing the de-
tails of Steane's error correction applied to either X or Z
errors, on the two subsections below.

We will consider an ancilla system $S' = \{1', \dots, N'\}$ and subsets $Z', \mathcal{I}', \mathcal{X}' \subseteq S'$. They are the counterparts of the subsets $Z, \mathcal{I}, \mathcal{X} \subseteq S$, in the sense that $i' \in Z' \Leftrightarrow i \in Z$, and similarly for $\mathcal{I}'$ and $\mathcal{X}'$.

a. X-Error Correction. To extract the syndrome for $X$ errors, the ancilla system $S' = Z' \cup \mathcal{I}' \cup \mathcal{X}'$ must be prepared in a logical $X$ basis state. Usually, the ancilla state is taken to be the logical all-`|+⟩` state, obtained by encoding the all-`|+⟩` state on system $\mathcal{I}'$. Here, we consider a slightly more general logical $X$ basis state, as follows,

$$
\overline{\langle w' \rangle}_{S'} = Q_N (|u'\rangle_{Z'} \otimes |\overline{w'}\rangle_{\mathcal{I}''} \otimes |\overline{v'}\rangle_{\mathcal{X}'}) \quad (B17)
$$

where **u'**, **w'**, **v'** are known. Note that frozen values **u'** and **v'** may be different from frozen values **u** and **v**.
The reason we consider the above logical state is that our preparation procedure for logical polar code states is measurement-based, for which **u'**, **w'**, **v'** are determined based on random outcomes of measurements therein.

Steane's X-error syndrome extraction procedure is de-
picted in Fig. 7a. After preparing the state $|\widetilde{w'}\rangle_{S'}$ on sys-
tem $S'$, the transversal CNOT$_{S \to S'}$ gate is applied on cor-
responding qubits of systems $S$ and $S'$. Then, each qubit
in the ancilla system $S'$ is measured in the Pauli $Z$ basis.
We denote by $m = (m_1, \dots, m_N)$ the classical outputs of
these measurements.

The following lemma gives the state of the *S* system,
as well as the measurement result *m*, after the syndrome
extraction procedure. We consider errors *e*<sub>*X*</sub> and *e*'<sub>*X*</sub>
that have happened on systems *S* and *S*', respectively.
We assume that errors *e*<sub>*X*</sub> and *e*'<sub>*X*</sub> have happened be-
fore the transversal CNOT<sub>*S*→*S*'</sub> gate is applied, while
the transversal CNOT<sub>*S*→*S*'</sub> gate, as well as the measure-
ment operations, are error free. We refer to these errors
as preparation errors. This assumption is made for sim-
plicity only. Indeed, it is not too difficult to see that er-
rors generated on the *S*' system, by either the transver-
sal CNOT<sub>*S*→*S*'</sub> gate or the measurement operations, can
ror. Precisely,

$$
W_{X'}(|\bar{u}\rangle\langle\bar{u}|) = (p_I + p_Z)|0\rangle\langle0|_X \otimes \\
\left( \frac{p_I}{p_I + p_Z} |\bar{u}\rangle\langle\bar{u}| + \frac{p_Z}{p_I + p_Z} Z|\bar{u}\rangle\langle\bar{u}|Z \right) \\
+ (p_X + p_Y)|1\rangle\langle1|_X \otimes \\
\left( \frac{p_X}{p_X + p_Y} |\bar{u}\rangle\langle\bar{u}| + \frac{p_Y}{p_X + p_Y} Z|\bar{u}\rangle\langle\bar{u}|Z \right), \quad (B16)
$$

where {|0⟩<sub>X</sub>, |1⟩<sub>X</sub>} is an orthogonal basis of an auxiliary
system, indicating whether an *X* error happened or not.
Put differently, *W*<sub>X'</sub> is a classical mixture of two BSCs,
the first with error probability *p*<sub>Z</sub>/*(p*<sub>I</sub> + *p*<sub>Z</sub>)* (when no *X*
error happened), and the second with error probability
*p*<sub>Y</sub>/*(p*<sub>X</sub> + *p*<sub>Y</sub>)* (when an *X* error happened).

The construction of the CSS quantum polar code, tak-
ing into account the correlations between X and Z errors,
is done in the same way as above, while replacing the W<sub>X</sub>
channel by its extended version W<sub>X'</sub>.

B.3. Steane Error Correction

We describe here the Steane error correction proce-
dure [19, 20] (see also [2, Section 4.4]), applied to CSS
quantum polar codes. Throughout this section, we con-
sider an encoded state | ̂$\phi$ 〉<sub>S</sub> = Q<sub>N</sub> (|**u**〉<sub>Z</sub> ⊗ |**$\phi$**〉<sub>I</sub> ⊗ |**v**〉<sub>X</sub>) of
the quantum polar code Q(N, Z, X, |**u**〉<sub>Z</sub>, |**v**〉<sub>X</sub>), that we
want to protect against Pauli errors.

Steane's error correction procedure consists of the fol-
lowing steps.

(1) An ancilla system $S'$ is prepared in either the logical all-|+⟩ state or the logical all-|0⟩ state of $Q(N, \mathbb{Z}, \mathcal{X}, |\mathbf{u}\rangle_{\mathbb{Z}}, |\bar{\mathbf{v}}\rangle_{\mathcal{X}})$. The former state is prepared for X-error correction, while the latter of Z-error correction.

(2) A transverse CNOT gate is applied between $S$ (original) and $S'$ (ancilla) systems, in such a way that either the $X$ or the $Z$ errors on $S$ are copied to $S'$, while the two systems remain separated.

(3) The ancilla system is measured, outputting a ran-
dom codeword of a classical polar code (in either
$Z$ or $X$ basis), corrupted by the error that has been
copied to $S'$.

(4) A classical SC decoding is applied to determine the error (possibly, the corresponding corrective operation is applied on the S system).

It is easily seen that steps (2) and (3) are fault-tolerant,
as they consist only of transverse gates and single qubit
measurements.

By a slight abuse of language, we shall refer to steps
(1)-(3) above as syndrome extraction [41]. In case of ideal
syndrome extraction, steps (1)-(3) are assumed to be error
free, and the error corrected at step (4) is the one preex-
isting on system S, before the syndrome is extracted. In
case of noisy syndrome extraction, steps (1)-(3) may gener-
ate additional errors on systems S and S'. We will analyze
the impact of these errors, together with providing the de-
tails of Steane's error correction applied to either X or Z
errors, on the two subsections below.

We will consider an ancilla system $S' = \{1', \dots, N'\}$ and subsets $Z', \mathcal{I}', \mathcal{X}' \subseteq S'$. They are the counterparts of the subsets $Z, \mathcal{I}, \mathcal{X} \subseteq S$, in the sense that $i' \in Z' \Leftrightarrow i \in Z$, and similarly for $\mathcal{I}'$ and $\mathcal{X}'$.

a. X-Error Correction. To extract the syndrome for X errors, the ancilla system $S' = Z' \cup \mathcal{I}' \cup \mathcal{X}'$ must be prepared in a logical X basis state. Usually, the ancilla state is taken to be the logical all-|+⟩ state, obtained by encoding the all-|+⟩ state on system $\mathcal{I}'$. Here, we consider a slightly more general logical X basis state, as follows,

$$
\widetilde{|w'|}_{S'} = Q_N(|u'\rangle_{Z'} \otimes |\overline{w'}\rangle_{\mathcal{I}''} \otimes |\overline{v'}\rangle_{\mathcal{X}'}), \quad (B17)
$$

where **u'**, **w'**, **v'** are known. Note that frozen values **u'** and **v'** may be different from frozen values **u** and **v**. The reason we consider the above logical state is that our preparation procedure for logical polar code states is measurement-based, for which **u'**, **w'**, **v'** are determined based on random outcomes of measurements therein.

Steane's X-error syndrome extraction procedure is de-
picted in Fig. 7a. After preparing the state $|\widetilde{w'}\rangle_{S'}$ on sys-
tem $S'$, the transversal CNOT$_{S\to S'}$ gate is applied on cor-
responding qubits of systems $S$ and $S'$. Then, each qubit
in the ancilla system $S'$ is measured in the Pauli $Z$ basis.
We denote by $\mathbf{m} = (m_1, \dots, m_N)$ the classical outputs of
these measurements.

The following lemma gives the state of the *S* system,
as well as the measurement result *m*, after the syndrome
extraction procedure. We consider errors *e*<sub>*X*</sub> and *e*'<sub>*X*</sub>
that have happened on systems *S* and *S*', respectively.
We assume that errors *e*<sub>*X*</sub> and *e*'<sub>*X*</sub> have happened be-
fore the transversal CNOT<sub>*S*→*S*'</sub> gate is applied, while
the transversal CNOT<sub>*S*→*S*'</sub> gate, as well as the measure-
ment operations, are error free. We refer to these errors
as preparation errors. This assumption is made for sim-
plicity only. Indeed, it is not too difficult to see that er-
rors generated on the *S*' system, by either the transver-
sal CNOT<sub>*S*→*S*'</sub> gate or the measurement operations, can
<figure><img src="image_9.png" /><figcaption>(a) X-error correction: X errors are copied from the original (top) to the ancilla (bottom) system, which is measured in Z basis.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(b) Z-error correction: Z errors are copied from the original (top) to the ancilla (bottom) system, which is measured in X basis.</figcaption></figure>

<caption>Fig. 7: Steane’s error correction procedure.</caption>

actually be incorporated to the error $e'_X$. Errors generated by the transversal CNOT$_{S→S'}$ gate on the S system go undetected, but they may be corrected during the next round of error correction.

**Lemma 4.** Let $e_X$ and $e'_X$ be preparation errors that have happened on systems S and S', respectively. Then, after the Steane's X-error syndrome extraction, the state of the system S is given by

$$X^{e_X} |\tilde{Zw'}\phi\rangle_S = X^{e_X} Q_N(|u\rangle_Z \otimes Z^{w'} |\phi\rangle_I \otimes |\overline{v \oplus v'}\rangle_\chi). \quad (B18)$$

Further, the measurement outcome is a noisy codeword of the classical polar code $\mathcal{P}(N, Z, u \oplus u')$, with frozen set $Z$ and frozen vector $u \oplus u'$, as follows,

$$m = P_N(u \oplus u', a', x') \oplus e_X \oplus e'_X \in \{0, 1\}^N, \quad (B19)$$

where $a' \in \{0, 1\}^{|\mathcal{I}|}$ and $x' \in \{0, 1\}^{|\chi|}$ are random vectors.

*Proof.* Let $|\phi\rangle_I = \sum_{a \in \{0, 1\}^{|\mathcal{I}|}} \phi_a |a\rangle_I$. Note also that $|\overline{v}\rangle_\chi = \sum_{x \in \{0, 1\}^{|\chi|}} (-1)^{v \cdot x} |x\rangle_\chi$ (up to a normalization factor, which will be omitted in the sequel). Then, the noisy logical state $X^{e_X} |\tilde{\phi}\rangle_S$ can be written as

$$X^{e_X} |\tilde{\phi}\rangle_S = X^{e_X} Q_N (|u\rangle_Z \otimes |\phi\rangle_I \otimes |\overline{v}\rangle_\chi) \quad (B20)$$

$$= \sum_{a,x} \phi_a (-1)^{v \cdot x} |P_N(u, a, x) \oplus e_X\rangle. \quad (B21)$$

Similarly, the noisy ancilla state can be written as

$$\begin{aligned} X^{e'_X} |\tilde{w'}\rangle_{S'} &= X^{e'_X} Q_N(|u'\rangle_{Z'} \otimes |\overline{w'}\rangle_{I'} \otimes |\overline{v'}\rangle_{\chi'}) \\ &= \sum_{a', x'} (-1)^{w' \cdot a' + v' \cdot x'} |P_N(u', a', x') \oplus e'_{X}\rangle. \end{aligned} \quad (B22)$$

After the transverse CNOT$_{S→S'}$ gate is applied, we get the following state on the bipartite $S_S'$ system,

$$\begin{aligned} |\theta\rangle_{SS'} &= \text{CNOT}_{S→S'} \left( X^{e_X} |\tilde{\phi}\rangle_S \otimes X^{e'_{X}} |\tilde{w'}\rangle_{S'} \right) \\ &= \sum_{a,x} \phi_a (-1)^{v \cdot x} |P_N(u, a, x) \oplus e_X\rangle \otimes \sum_{a',x'} (-1)^{w' \cdot a' + v' \cdot x'} \\ &\qquad |P_N(u \oplus u', a \oplus a', x \oplus x') \oplus e_X \oplus e'_{X}\rangle \\ &= \sum_{a,x} \phi_a (-1)^{w' \cdot a + (v \oplus v') \cdot x} |P_N(u, a, x) \oplus e_X\rangle \\ &\qquad \otimes \sum_{a',x'} (-1)^{w' \cdot a' + v' \cdot x'} |P_N(u \oplus u', a', x') \oplus e_X \oplus e'_{X}\rangle. \end{aligned} \quad (B23)$$

where for the last equality, we use variable changes $a' \leftarrow a' \oplus a$, and $x' \leftarrow x' \oplus x$. It can be seen that the error on the system S has propagated to the system S', and $|\theta\rangle_{SS'}$ is a product state that can be rewritten as

$$\begin{aligned} |\theta\rangle_{SS'} &= X^{e_X} Q_N(|u\rangle_Z \otimes Z^{w'} |\phi\rangle_I \otimes |\overline{v \oplus v'}\rangle_\chi) \\ &\quad \otimes X^{e_X \oplus e'_{X}} Q_N(|u' \oplus u\rangle_{Z'} \otimes |\overline{w'}\rangle_{I'} \otimes |\overline{v'}\rangle_{\chi'}). \end{aligned} \quad (B24)$$

Hence, the partial state of the system S is the same as in (B18). Further, measuring the qubits of the ancilla system in the Pauli Z basis, we get $m = P_N(u \oplus u', a', x') \oplus e_X \oplus e'_X \in \{0, 1\}^N$, for some random vectors $a' \in \{0, 1\}^{|\mathcal{I}|}$ and $x' \in \{0, 1\}^{|\chi|}$. $\square$

Two observations are in place here.

First, from (B18), it follows that the frozen vector corresponding to $\mathcal{X} \subset S$ (original system) has changed to $v \oplus v'$, after the Steane's procedure. Further, the logical Z
<figure><img src="image_9.png" /><figcaption>(a) X-error correction: X errors are copied from the original (top) to the ancilla (bottom) system, which is measured in Z basis.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(b) Z-error correction: Z errors are copied from the original (top) to the ancilla (bottom) system, which is measured in X basis.</figcaption></figure>

<caption>Fig. 7: Steane’s error correction procedure.</caption>

actually be incorporated to the error $e'_X$. Errors generated by the transversal CNOT$_{S→S'}$ gate on the S system go undetected, but they may be corrected during the next round of error correction.

**Lemma 4.** Let $e_X$ and $e'_X$ be preparation errors that have happened on systems S and S', respectively. Then, after the Steane's X-error syndrome extraction, the state of the system S is given by

$$X^{e_X} |\tilde{Zw'}\phi\rangle_S = X^{e_X} Q_N(|u\rangle_Z \otimes Z^{w'} |\phi\rangle_I \otimes |\overline{v \oplus v'}\rangle_\chi). \quad (B18)$$

Further, the measurement outcome is a noisy codeword of the classical polar code $\mathcal{P}(N, Z, u \oplus u')$, with frozen set $Z$ and frozen vector $u \oplus u'$, as follows,

$$m = P_N(u \oplus u', a', x') \oplus e_X \oplus e'_X \in \{0, 1\}^N, \quad (B19)$$

where $a' \in \{0, 1\}^{|I|}$ and $x' \in \{0, 1\}^{|X|}$ are random vectors.

*Proof.* Let $|\phi\rangle_I = \sum_{a \in \{0, 1\}^{|I|}} \phi_a |a\rangle_I$. Note also that $|\overline{v}\rangle_\chi = \sum_{x \in \{0, 1\}^{|X|}} (-1)^{v \cdot x} |x\rangle_\chi$ (up to a normalization factor, which will be omitted in the sequel). Then, the noisy logical state $X^{e_X} |\tilde{\phi}\rangle_S$ can be written as

$$X^{e_X} |\tilde{\phi}\rangle_S = X^{e_X} Q_N (|u\rangle_Z \otimes |\phi\rangle_I \otimes |\overline{v}\rangle_\chi) \quad (B20)$$

$$= \sum_{a,x} \phi_a (-1)^{v \cdot x} |P_N(u, a, x) \oplus e_X\rangle. \quad (B21)$$

Similarly, the noisy ancilla state can be written as

$$\begin{aligned} X^{e'_X} |\tilde{w'}\rangle_{S'} &= X^{e'_X} Q_N(|u'\rangle_{Z'} \otimes |\overline{w'}\rangle_{I'} \otimes |\overline{v'}\rangle_{\chi'}) \\ &= \sum_{a', x'} (-1)^{w' \cdot a' + v' \cdot x'} |P_N(u', a', x') \oplus e'_X\rangle. \end{aligned} \quad (B22)$$

After the transverse CNOT$_{S→S'}$ gate is applied, we get the following state on the bipartite $SS'$ system,

$$\begin{aligned} |\theta\rangle_{SS'} &= \text{CNOT}_{S→S'} \left( X^{e_X} |\tilde{\phi}\rangle_S \otimes X^{e'_X} |\overline{w'}\rangle_{S'} \right) \\ &= \sum_{a,x} \phi_a (-1)^{v \cdot x} |P_N(u, a, x) \oplus e_X\rangle \otimes \sum_{a',x'} (-1)^{w' \cdot a' + v' \cdot x'} \\ & \qquad |P_N(u \oplus u', a \oplus a', x \oplus x') \oplus e_X \oplus e'_X\rangle \\ &= \sum_{a,x} \phi_a (-1)^{w' \cdot a + (v \oplus v') \cdot x} |P_N(u, a, x) \oplus e_X\rangle \\ & \qquad \otimes \sum_{a',x'} (-1)^{w' \cdot a' + v' \cdot x'} |P_N(u \oplus u', a', x') \oplus e_X \oplus e'_X\rangle. \end{aligned} \quad (B23)$$

where for the last equality, we use variable changes $a' \leftarrow a' \oplus a$, and $x' \leftarrow x' \oplus x$. It can be seen that the error on the system S has propagated to the system S', and $|\theta\rangle_{SS'}$ is a product state that can be rewritten as

$$\begin{aligned} |\theta\rangle_{SS'} &= X^{e_X} Q_N(|u\rangle_Z \otimes Z^{w'} |\phi\rangle_I \otimes |\overline{v \oplus v'}\rangle_\chi) \\ & \quad \otimes X^{e_X \oplus e'_X} Q_N(|u' \oplus u\rangle_{Z'} \otimes |\overline{w'}\rangle_{I'} \otimes |\overline{v'}\rangle_{\chi'}). \end{aligned} \quad (B24)$$

Hence, the partial state of the system S is the same as in (B18). Further, measuring the qubits of the ancilla system in the Pauli Z basis, we get $m = P_N(u \oplus u', a', x') \oplus e_X \oplus e'_X \in \{0, 1\}^N$, for some random vectors $a' \in \{0, 1\}^{|I|}$ and $x' \in \{0, 1\}^{|X|}$. $\square$

Two observations are in place here.

First, from (B18), it follows that the frozen vector corresponding to $\mathcal{X} \subset S$ (original system) has changed to $v \oplus v'$, after the Steane's procedure. Further, the logical Z
operator corresponding to $Z^{w'}$ gets applied on $S$. However, since we know $w'$, we can reverse this logical operation using (B12). Hence, the logical information encoded in $S$ has not been altered, due to the syndrome extraction.

The second observation concerns the SC decoding, which takes as input the measurement outcome $m = P_N(\mathbf{u} \oplus \mathbf{u}', \mathbf{a}', \mathbf{x}') \oplus e_X \oplus e'_X$, and the frozen vector $\mathbf{u} \oplus \mathbf{u}'$. It produces an estimate of the information vector $(\mathbf{a}', \mathbf{x}')$, from which we can produce an estimate of the total error $e_X \oplus e'_X$. The vector $\mathbf{a}'$ may be correctly estimated, owning to the fact that it corresponds to good virtual channels. Some of the $\mathbf{x}'$ positions may be incorrectly estimated, but this does not matter, as the induced logical error corresponds to an $X$-type stabilizer operator, acting trivially on the code space.

Hence, assuming the vector $\mathbf{a}'$ is decoded correctly, we also get the correct value of the total error $e_X \oplus e'_X$ (up to an $X$-type stabilizer operator). We then correct the $S$ system by applying $X^{e_X \oplus e'_X}$, which will leave the error $X^{e'_X}$ (original error on $S'$) on $S$ after correction. This left-over error, may hopefully be corrected in the next round of correction, where we may similarly add another error from the ancilla system. However, note that the advantage of error correction is that it does not allow errors to accumulate and the only left error on the encoded state is due to the last round of error correction (which may be corrected, when the encoded logical state is eventually measured). Hence, we may stabilize logical qubits against noise, by doing error correction repeatedly.

It is worth noticing that for topological (or some families of quantum LDPC codes), fault tolerant error correction needs the decoding operation to be applied on a time window, composed of several consecutive syndrome extractions, e.g., [10]. For Steane's fault tolerant error correction, decoding is simply applied on each extracted "syndrome" (recall the "syndrome" in this case is actually a noisy codeword).

**b. Z-Error Correction.** The decoding of $Z$ errors can be done similarly to the case of $X$ errors as follows. To extract the syndrome for $Z$ errors (see Fig. 7b), one needs an ancilla system $S'$ prepared in a logical $Z$ basis state,

$$|\tilde{\mathbf{w}}'\rangle_S = Q_N(|\mathbf{u}'\rangle_{Z'} \otimes |\mathbf{w}'\rangle_{\mathcal{I}'} \otimes |\overline{\mathbf{v}}'\rangle_{\mathcal{X}'}), \quad (B25)$$

After preparing the state $|\tilde{\mathbf{w}}'\rangle_S'$ on ancilla system $S'$, the transversal CNOT$_{S' \to S}$ gate is applied on corresponding qubits of systems $S$ and $S'$. Then, each qubit in the ancilla system $S'$ is measured in the Pauli $X$ basis. The measurement output $m$ is a noisy codeword of the classical polar code $\mathcal{P}(N, \pi(\mathcal{X}), \pi(\mathbf{v}))$, induced in $X$ basis (Fig. 6b).

**Lemma 5.** Let $e_Z$ and $e'_Z$ be preparation errors that has happened on systems $S$ and $S'$, respectively. Then, after the Steane's Z-error syndrome extraction, the state of the system $S$ is given by

$$Z^{e_Z} |\tilde{X} \mathbf{w}' \phi\rangle_S = Z^{e_Z} Q_N(|\mathbf{u} \oplus \mathbf{u}'\rangle_Z \otimes X^{\mathbf{w}'} |\phi\rangle_I \otimes |\overline{\mathbf{v}}\rangle_\mathcal{X}). \quad (B26)$$

Further, the measurement outcome is a noisy codeword of the classical polar code $\mathcal{P}(N, \pi(\mathcal{X}), \pi(\mathbf{v}))$, with frozen set $\mathcal{X}$ and frozen vector $\pi(\mathbf{v} \oplus \mathbf{v}')$, as follows,

$$\mathbf{m} = P_N^\top(\mathbf{z}', \mathbf{a}', \mathbf{v} \oplus \mathbf{v}') \oplus e_Z \oplus e'_Z, \quad (B27)$$

where $\mathbf{a}' \in \{0, 1\}^{|\mathcal{I}|}$ and $\mathbf{x}' \in \{0, 1\}^{|\mathcal{X}|}$ are random vectors.

The proof of Lemma 5 is similar to that of Lemma 4, by expanding quantum states of systems $S$ and $S'$ in the Pauli $X$ basis. Finally, based on the frozen vector $\mathbf{v} \oplus \mathbf{v}'$ and the noisy codeword $\mathbf{m}$ in (B27), the SC decoder generates an estimate of $\mathbf{a}'$, and in turn we can obtain an estimate of the error $e_Z \oplus e'_Z$ (up to a $Z$-type stabilizer operator).

### C. $Q_1$ Codes: Quantum Polar Codes Encoding One Qubit

#### C.1. Shor $Q_1$ Codes (Proof of Theorem 1)

To prove Theorem 1, we will use the decomposition $Q_N = (I_{2^k} \otimes Q_{2^{n-k}})(Q_{2^k} \otimes I_{2^{n-k}})$, for $0 \le k \le n$. This decomposition is illustrated in Fig. 8, where we have $2^{n-k}$ parallel $Q_{2^k}$ blocks, followed by $2^k$ parallel $Q_{2^{n-k}}$ blocks. If one considers the quantum system $S$ as a vector of $N$ qubits, the decomposition illustrated in Fig. 8 is equivalent to reshaping $S$ as a $2^k \times 2^{n-k}$ matrix of qubits, with columns filled in by consecutive qubits from the original vector, then applying $Q_{2^k}$ on each column, and $Q_{2^{n-k}}$ on each row.

For the logical state $|\tilde{0}\rangle_S$, the first $i = 2^k$ inputs of the quantum polar transform $Q_N$ are equal to $|0\rangle$, while the remaining $2^n - 2^k$ inputs are equal to $|+\rangle$ (see Fig. 8). Hence, each of the $2^{n-k}$ parallel $Q_{2^k}$ unitaries in Fig. 8 acts trivially on its input state. Therefore, the input of the $r$-th $Q_{2^{n-k}}$ unitary, where $1 \le r \le 2^k$, is the quantum state $|0\rangle_{r,1} \otimes 2^{2^{n-k}} |+\rangle_{r,c}$. It follows that (omitting normalization factors),

$$ \begin{align} |\tilde{0}\rangle_S &= \otimes_{r=1}^{2^k} Q_{2^{n-k}} (|0\rangle_{r,1} \otimes_{c=2}^{2^{n-k}} |+\rangle_{r,c}) \nonumber \\ &= \otimes_{r=1}^{2^k} Q_{2^{n-k}} ((|+\rangle_{r,1} + |-\rangle_{r,1}) \otimes_{c=2}^{2^{n-k}} |+\rangle_{r,c}) \nonumber \\ &= \otimes_{r=1}^{2^k} (Q_{2^{n-k}} (\otimes_{c=1}^{2^{n-k}} |+\rangle_{r,c}) \nonumber \\ &\quad + Q_{2^{n-k}} (|-\rangle_{r,1} \otimes_{c=2}^{2^{n-k}} |+\rangle_{r,c})) \nonumber \\ &= \otimes_{r=1}^{2^k} (\otimes_{c=1}^{2^{n-k}} |+\rangle_{r,c} + \otimes_{c=1}^{2^{n-k}} |-\rangle_{r,c}) \tag{C1} \end{align} $$
operator corresponding to $Z^{w'}$ gets applied on $S$. However, since we know $w'$, we can reverse this logical operation using (B12). Hence, the logical information encoded in $S$ has not been altered, due to the syndrome extraction.

The second observation concerns the SC decoding, which takes as input the measurement outcome $m = P_N(\mathbf{u} \oplus \mathbf{u}', \mathbf{a}', \mathbf{x}') \oplus e_X \oplus e'_X$, and the frozen vector $\mathbf{u} \oplus \mathbf{u}'$. It produces an estimate of the information vector $(\mathbf{a}', \mathbf{x}')$, from which we can produce an estimate of the total error $e_X \oplus e'_X$. The vector $\mathbf{a}'$ may be correctly estimated, owning to the fact that it corresponds to good virtual channels. Some of the $\mathbf{x}'$ positions may be incorrectly estimated, but this does not matter, as the induced logical error corresponds to an $X$-type stabilizer operator, acting trivially on the code space.

Hence, assuming the vector $\mathbf{a}'$ is decoded correctly, we also get the correct value of the total error $e_X \oplus e'_X$ (up to an $X$-type stabilizer operator). We then correct the $S$ system by applying $X^{e_X \oplus e'_X}$, which will leave the error $X^{e'_X}$ (original error on $S'$) on $S$ after correction. This left-over error, may hopefully be corrected in the next round of correction, where we may similarly add another error from the ancilla system. However, note that the advantage of error correction is that it does not allow errors to accumulate and the only left error on the encoded state is due to the last round of error correction (which may be corrected, when the encoded logical state is eventually measured). Hence, we may stabilize logical qubits against noise, by doing error correction repeatedly.

It is worth noticing that for topological (or some families of quantum LDPC codes), fault tolerant error correction needs the decoding operation to be applied on a time window, composed of several consecutive syndrome extractions, e.g., [10]. For Steane's fault tolerant error correction, decoding is simply applied on each extracted "syndrome" (recall the "syndrome" in this case is actually a noisy codeword).

b. **Z-Error Correction.** The decoding of $Z$ errors can be done similarly to the case of $X$ errors as follows. To extract the syndrome for $Z$ errors (see Fig. 7b), one needs an ancilla system $S'$ prepared in a logical $Z$ basis state,

$$|\tilde{\mathbf{w}}'\rangle_S = Q_N(|\mathbf{u}'\rangle_{Z'} \otimes |\mathbf{w}'\rangle_{\mathcal{I}'} \otimes |\overline{\mathbf{v}}'\rangle_{\mathcal{X}'}) \quad (B25)$$

After preparing the state $|\tilde{\mathbf{w}}'\rangle_S'$ on ancilla system $S'$, the transversal CNOT$_{S' \to S}$ gate is applied on corresponding qubits of systems $S$ and $S'$. Then, each qubit in the ancilla system $S'$ is measured in the Pauli $X$ basis. The measurement output $m$ is a noisy codeword of the classical polar code $\mathcal{P}(N, \pi(\mathcal{X}), \pi(\mathbf{v}))$, induced in $X$ basis (Fig. 6b).

**Lemma 5.** Let $e_Z$ and $e'_Z$ be preparation errors that has happened on systems $S$ and $S'$, respectively. Then, after the Steane's Z-error syndrome extraction, the state of the system $S$ is given by

$$Z^{e_Z} |\tilde{X} \mathbf{w}' \phi\rangle_S = Z^{e_Z} Q_N (|\mathbf{u} \oplus \mathbf{u}'\rangle_Z \otimes X^{\mathbf{w}'} |\phi\rangle_\mathcal{I} \otimes |\overline{\mathbf{v}}\rangle_\mathcal{X}) \quad (B26)$$

Further, the measurement outcome is a noisy codeword of the classical polar code $\mathcal{P}(N, \pi(\mathcal{X}), \pi(\mathbf{v}))$, with frozen set $\mathcal{X}$ and frozen vector $\pi(\mathbf{v} \oplus \mathbf{v}')$, as follows,

$$\mathbf{m} = P_N^\top(\mathbf{z}', \mathbf{a}', \mathbf{v} \oplus \mathbf{v}') \oplus e_Z \oplus e'_Z \quad (B27)$$

where $\mathbf{a}' \in \{0, 1\}^{|\mathcal{I}|}$ and $\mathbf{x}' \in \{0, 1\}^{|\mathcal{X}|}$ are random vectors.

The proof of Lemma 5 is similar to that of Lemma 4, by expanding quantum states of systems $S$ and $S'$ in the Pauli $X$ basis. Finally, based on the frozen vector $\mathbf{v} \oplus \mathbf{v}'$ and the noisy codeword $\mathbf{m}$ in (B27), the SC decoder generates an estimate of $\mathbf{a}'$, and in turn we can obtain an estimate of the error $e_Z \oplus e'_Z$ (up to a Z-type stabilizer operator).

### C. $Q_1$ Codes: Quantum Polar Codes Encoding One Qubit

#### C.1. Shor $Q_1$ Codes (Proof of Theorem 1)

To prove Theorem 1, we will use the decomposition $Q_N = (I_{2^k} \otimes Q_{2^{n-k}})(Q_{2^k} \otimes I_{2^{n-k}})$, for $0 \le k \le n$. This decomposition is illustrated in Fig. 8, where we have $2^{n-k}$ parallel $Q_{2^k}$ blocks, followed by $2^k$ parallel $Q_{2^{n-k}}$ blocks. If one considers the quantum system $S$ as a vector of $N$ qubits, the decomposition illustrated in Fig. 8 is equivalent to reshaping $S$ as a $2^k \times 2^{n-k}$ matrix of qubits, with columns filled in by consecutive qubits from the original vector, then applying $Q_{2^k}$ on each column, and $Q_{2^{n-k}}$ on each row.

For the logical state $|\tilde{0}\rangle_S$, the first $i = 2^k$ inputs of the quantum polar transform $Q_N$ are equal to $|0\rangle$, while the remaining $2^n - 2^k$ inputs are equal to $|+\rangle$ (see Fig. 8). Hence, each of the $2^{n-k}$ parallel $Q_{2^k}$ unitaries in Fig. 8 acts trivially on its input state. Therefore, the input of the $r$-th $Q_{2^{n-k}}$ unitary, where $1 \le r \le 2^k$, is the quantum state $|0\rangle_{r,1} \otimes 2^{2^{n-k}} |+\rangle_{r,c}$. It follows that (omitting normalization factors),

$$ \begin{align} |\tilde{0}\rangle_S &= \otimes_{r=1}^{2^k} Q_{2^{n-k}} (|0\rangle_{r,1} \otimes_{c=2}^{2^{n-k}} |+\rangle_{r,c}) \nonumber \\ &= \otimes_{r=1}^{2^k} Q_{2^{n-k}} ((|+\rangle_{r,1} + |-\rangle_{r,1}) \otimes_{c=2}^{2^{n-k}} |+\rangle_{r,c}) \nonumber \\ &= \otimes_{r=1}^{2^k} (Q_{2^{n-k}} (\otimes_{c=1}^{2^{n-k}} |+\rangle_{r,c}) \nonumber \\ &\quad + Q_{2^{n-k}} (|-\rangle_{r,1} \otimes_{c=2}^{2^{n-k}} |+\rangle_{r,c})) \nonumber \\ &= \otimes_{r=1}^{2^k} (\otimes_{c=1}^{2^{n-k}} |+\rangle_{r,c} + \otimes_{c=1}^{2^{n-k}} |-\rangle_{r,c}) \tag{C1} \end{align} $$
<figure><img src="image_11.png" /><figcaption>Fig. 8: Quantum polar transform decomposition, using $Q_{2^n} = (I_{2^k} \otimes Q_{2^{n-k}})(Q_{2^k} \otimes I_{2^{n-k}})$. Bent wires go under the blocks they cross. In case input qubits are prepared as shown on the left, the encoded state is the logical $|0\rangle$ state of a Shor code.</figcaption></figure>

For the logical state $|\tilde{1}\rangle_S$, the inputs of $Q_N$ is $(|1\rangle_{r,1} \otimes_{c=2}^{2^{n-k}} |+\rangle_{r,c})$. Hence, using $|1\rangle_{r,1} = |+\rangle_{r,1} - |-\rangle_{r,1'}$ it follows similarly that $|\tilde{1}\rangle_S = \otimes_{r=1}^{2^k} (\otimes_{c=1}^{2^{n-k}} |+\rangle_{r,c} - \otimes_{c=1}^{2^{n-k}} |-\rangle_{r,c})$.

## C.2. Construction of General $Q_1$ Codes

In this section, we provide more details about the construction of $Q_1$ codes, and further numerically estimate its performance on Pauli and erasure channels.

For $Q_1$ codes, SC decoder only needs to decode the virtual channels corresponding to the information position $i$ for both $X$ and $Z$ error channels $W_Z$ and $W_X$, respectively. Let $P_e(W_Z^{(i)})$ and $P_e(W_X^{(\pi^{(i)})})$ denote the error probability of the respective virtual channels, corresponding to the information position $i$. Recall that the error probability of a classical channel, is the probability of the maximum a posteriori estimate of the channel input, conditional on the observed channel output, not being equal to the actual input. Hence, the logical error rate of the $Q_1$ code, with respect to the information position $i$, is given by

$$P_e^L(i) = 1 - (1 - P_e(W_Z^{(i)}))(1 - P_e(W_X^{(\pi^{(i)})))). \quad (C2)$$

The information position $i$ should be chosen so as to minimize the corresponding logical error rate in (C2).

Precisely, we have

$$i = \arg\min_{j=1,\dots,N} P_e^L(j), \text{ for } Q_1 \text{ codes.} \quad (C3)$$

$$i = \arg\min_{j=2^0,\dots,2^n} P_e^L(j), \text{ for Shor-}Q_1 \text{ codes.} \quad (C4)$$

## C.3. Numerical Results

Here, we provide numerical results for the construction of $Q_1$ and Shor-$Q_1$ codes, for the quantum depolarizing and quantum erasure channels.

The quantum depolarizing channel with physical error probability $p$, is a Pauli channel as in (B13), with $P_I = 1-p$, and $p_X = p_Y = p_Z = p/3$. We use density evolution [24] to estimate the error probability of virtual channels, i.e., $P_e(W_Z^{(j)})$ and $P_e(W_X^{(\pi^{(j)})})$, $j = 1, \dots, N$. The information positions for the $Q_1$ and Shor-$Q_1$ codes are then determined according to (C3) and (C4). Moreover, we consider the two constructions (or decoding strategies) given in Section B.2, that is, either using or ignoring the correlations between $X$ and $Z$ errors. Here, ignoring correlations between $X$ and $Z$ errors may seem unfounded. We will later provide the rationale for this in Section E.2, under the paragraph “Prepared Codes”.

The quantum erasure channel erases the input qubit, with some probability $\varepsilon$, or transmits it perfectly, with probability $1 - \varepsilon$. When a qubit is erased, it is replaced by a totally mixed state. Further, the channel also outputs a classical flag, which indicates whether the qubit has been erased ($|1\rangle_E$) or not ($|0\rangle_E$). Hence, it can be represented as a quantum operation as follows,

$$W_E(\rho) = (1 - \varepsilon)|0\rangle\langle 0|_E \otimes \rho + \varepsilon|1\rangle\langle 1|_E \otimes \frac{1}{2}. \quad (C5)$$

It is easily seen that $W_E$ acts as a classical erasure channel with erasure probability $\varepsilon$ in both Pauli $Z$ and Pauli $X$ basis. Hence, the induced channels $W_X$ and $W_Z$ are classical erasure channels, with erasure probability $\varepsilon$. The erasure probability of virtual channels ($P_e(W_Z^{(j)})$ and $P_e(W_X^{(\pi^{(j)})})$, $j = 1, \dots, N$) can be computed analytically [3]. The information positions for the $Q_1$ and Shor-$Q_1$ codes are then determined according to (C3) and (C4). For this channel, the two construction strategies (using or ignoring correlations) are easily seen to be equivalent.

Considering the quantum depolarizing channel, Fig. 9 shows the logical error rate $P_e^L(i)$ vs. the physical error probability $p$, for the $Q_1$ and Shor-$Q_1$ codes, with information position determined according to (C3) and (C4). Note that for fixed codelength $N = 2^n$, the information position may vary depending on the physical error
<figure><img src="image_11.png" /><figcaption>Fig. 8: Quantum polar transform decomposition, using $Q_{2^n} = (I_{2^k} \otimes Q_{2^{n-k}})(Q_{2^k} \otimes I_{2^{n-k}})$. Bent wires go under the blocks they cross. In case input qubits are prepared as shown on the left, the encoded state is the logical $|0\rangle$ state of a Shor code.</figcaption></figure>

For the logical state $|\tilde{1}\rangle_S$, the inputs of $Q_N$ is $(|1\rangle_{r,1} \otimes_{c=2}^{2^{n-k}} |+\rangle_{r,c})$. Hence, using $|1\rangle_{r,1} = |+\rangle_{r,1} - |-\rangle_{r,1'}$ it follows similarly that $|\tilde{1}\rangle_S = \otimes_{r=1}^{2^k} (\otimes_{c=1}^{2^{n-k}} |+\rangle_{r,c} - \otimes_{c=1}^{2^{n-k}} |-\rangle_{r,c})$.

## C.2. Construction of General $Q_1$ Codes

In this section, we provide more details about the construction of $Q_1$ codes, and further numerically estimate its performance on Pauli and erasure channels.

For $Q_1$ codes, SC decoder only needs to decode the virtual channels corresponding to the information position $i$ for both $X$ and $Z$ error channels $W_Z$ and $W_X$, respectively. Let $P_e(W_Z^{(i)})$ and $P_e(W_X^{(\pi^{(i)})})$ denote the error probability of the respective virtual channels, corresponding to the information position $i$. Recall that the error probability of a classical channel, is the probability of the maximum a posteriori estimate of the channel input, conditional on the observed channel output, not being equal to the actual input. Hence, the logical error rate of the $Q_1$ code, with respect to the information position $i$, is given by

$$P_e^L(i) = 1 - (1 - P_e(W_Z^{(i)}))(1 - P_e(W_X^{(\pi^{(i)})))). \quad (C2)$$

The information position $i$ should be chosen so as to minimize the corresponding logical error rate in (C2).

Precisely, we have

$$i = \arg\min_{j=1, \dots, N} P_e^L(j), \text{ for } Q_1 \text{ codes.} \quad (C3)$$

$$i = \arg\min_{j=2^0, \dots, 2^n} P_e^L(j), \text{ for Shor-}Q_1 \text{ codes.} \quad (C4)$$

## C.3. Numerical Results

Here, we provide numerical results for the construction of $Q_1$ and Shor-$Q_1$ codes, for the quantum depolarizing and quantum erasure channels.

The quantum depolarizing channel with physical error probability $p$, is a Pauli channel as in (B13), with $P_I = 1-p$, and $p_X = p_Y = p_Z = p/3$. We use density evolution [24] to estimate the error probability of virtual channels, i.e., $P_e(W_Z^{(j)})$ and $P_e(W_X^{(\pi^{(j)})})$, $j = 1, \dots, N$. The information positions for the $Q_1$ and Shor-$Q_1$ codes are then determined according to (C3) and (C4). Moreover, we consider the two constructions (or decoding strategies) given in Section B.2, that is, either using or ignoring the correlations between $X$ and $Z$ errors. Here, ignoring correlations between $X$ and $Z$ errors may seem unfounded. We will later provide the rationale for this in Section E.2, under the paragraph “Prepared Codes”.

The quantum erasure channel erases the input qubit, with some probability $\varepsilon$, or transmits it perfectly, with probability $1 - \varepsilon$. When a qubit is erased, it is replaced by a totally mixed state. Further, the channel also outputs a classical flag, which indicates whether the qubit has been erased ($|1\rangle_E$) or not ($|0\rangle_E$). Hence, it can be represented as a quantum operation as follows,

$$W_E(\rho) = (1 - \varepsilon)|0\rangle\langle 0|_E \otimes \rho + \varepsilon|1\rangle\langle 1|_E \otimes \frac{1}{2}. \quad (C5)$$

It is easily seen that $W_E$ acts as a classical erasure channel with erasure probability $\varepsilon$ in both Pauli $Z$ and Pauli $X$ basis. Hence, the induced channels $W_X$ and $W_Z$ are classical erasure channels, with erasure probability $\varepsilon$. The erasure probability of virtual channels ($P_e(W_Z^{(j)})$ and $P_e(W_X^{(\pi^{(j)})})$, $j = 1, \dots, N$) can be computed analytically [3]. The information positions for the $Q_1$ and Shor-$Q_1$ codes are then determined according to (C3) and (C4). For this channel, the two construction strategies (using or ignoring correlations) are easily seen to be equivalent.

Considering the quantum depolarizing channel, Fig. 9 shows the logical error rate $P_e^L(i)$ vs. the physical error probability $p$, for the $Q_1$ and Shor-$Q_1$ codes, with information position determined according to (C3) and (C4). Note that for fixed codelength $N = 2^n$, the information position may vary depending on the physical error
<figure><img src="image_12.png" /><figcaption>(a) Using correlations between *X* and *Z* errors. Left: *n* odd (for *n* = 3, 5, 7, $Q_1$ and Shor curves virtually coincide). Right: *n* even.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(b) Ignoring correlations between *X* and *Z* errors. Left: *n* odd (for *n* = 3, 5, 7, $Q_1$ and Shor curves virtually coincide). Right: *n* even (for *n* = 4, $Q_1$ and Shor curves virtually coincide).</figcaption></figure>

<caption>Fig. 9: Logical error rate of $Q_1$ and Shor codes, for the depolarizing channel.</caption>

probability value. We consider the two decoding strategies mentioned above, namely, either using or ignoring the correlations between *X* and *Z* errors. It can be observed that using correlations yield (slightly) better decoding performance. Moreover, in both cases, we observe that the logical error rate of the $Q_1$ code is in general lower than that of the Shor code, and the gap is increasing with increasing codelength (i.e., number of polarization steps *n*). We emphasize that the gap in the decoding performance is due to the channel polarization phenomenon and not to the minimum distance ($Q_1$ and Shor-$Q_1$ codes have actually the same minimum distance, see below).

As just mentioned, the information position *i* may vary, depending on the physical error probability *p*. However, numerical results suggests that as *p* goes to zero, the information position *i* reaches a stable (constant) value. These

values are reported in Table II, for both decoding strategies (either using or ignoring correlations), and different values of *n*. We also report in Table II similar results for the quantum erasure channel (we omit the logical error rate curves for the quantum erasure channel, since they are of the same nature as the logical error rate curves in Fig. 9). It can be observed that for $Q_1$ codes, the information position values reported in Table II depend on the noise model (depolarizing or erasure channel), as well as the decoding strategy (using or ignoring correlations).

Finally, we note that for a given *n* value, all $Q_1$ and Shor codes with information positions given in Table II have the same minimum distance, which is reported on the last column of the table. The reported minimum distance is the minimum weight of logical *X* and *Z* operators, and can be computed by using (B11) and (B12).
<figure><img src="image_12.png" /><figcaption>(a) Using correlations between X and Z errors. Left: *n* odd (for *n* = 3, 5, 7, Q₁ and Shor curves virtually coincide). Right: *n* even.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(b) Ignoring correlations between *X* and *Z* errors. Left: *n* odd (for *n* = 3, 5, 7, Q₁ and Shor curves virtually coincide). Right: *n* even (for *n* = 4, Q₁ and Shor curves virtually coincide).</figcaption></figure>

<caption>Fig. 9: Logical error rate of Q₁ and Shor codes, for the depolarizing channel.</caption>

probability value. We consider the two decoding strategies mentioned above, namely, either using or ignoring the correlations between *X* and *Z* errors. It can be observed that using correlations yield (slightly) better decoding performance. Moreover, in both cases, we observe that the logical error rate of the Q₁ code is in general lower than that of the Shor code, and the gap is increasing with increasing codelength (i.e., number of polarization steps *n*). We emphasize that the gap in the decoding performance is due to the channel polarization phenomenon and not to the minimum distance (Q₁ and Shor-Q₁ codes have actually the same minimum distance, see below).

As just mentioned, the information position *i* may vary, depending on the physical error probability *p*. However, numerical results suggests that as *p* goes to zero, the information position *i* reaches a stable (constant) value. These

values are reported in Table II, for both decoding strategies (either using or ignoring correlations), and different values of *n*. We also report in Table II similar results for the quantum erasure channel (we omit the logical error rate curves for the quantum erasure channel, since they are of the same nature as the logical error rate curves in Fig. 9). It can be observed that for Q₁ codes, the information position values reported in Table II depend on the noise model (depolarizing or erasure channel), as well as the decoding strategy (using or ignoring correlations).

Finally, we note that for a given *n* value, all Q₁ and Shor codes with information positions given in Table II have the same minimum distance, which is reported on the last column of the table. The reported minimum distance is the minimum weight of logical *X* and *Z* operators, and can be computed by using (B11) and (B12).
<table><caption>TABLE II: Best information positions for low error probabilities(*)</caption><thead><tr><th rowspan="3">Levels of<br>Recursion (n)</th><th colspan="2">Depolarizing Channel<br>using correlations</th><th colspan="2">Depolarizing Channel<br>ignoring correlations</th><th colspan="2">Erasure Channel</th><th rowspan="3">Min<br>dist.</th></tr><tr><th colspan="4">Information position i for best Q<sub>1</sub> and Shor-Q<sub>1</sub> codes</th><th rowspan="2">Q<sub>1</sub></th><th rowspan="2">Shor</th></tr><tr><th>Q<sub>1</sub></th><th>Shor</th><th>Q<sub>1</sub></th><th>Shor</th></tr></thead><tbody><tr><td>3</td><td>4<br>(6.8 × 10<sup>-2</sup>)</td><td>4<br>(2.0 × 10<sup>-1</sup>)</td><td>4<br>(1.0 × 10<sup>-3</sup>)</td><td>4<br>(1.0 × 10<sup>-3</sup>)</td><td>2<br>(5.0 × 10<sup>-1</sup>)</td><td>2<br>(5.0 × 10<sup>-1</sup>)</td><td>2</td></tr><tr><td>4</td><td>13<br>(2.0 × 10<sup>-1</sup>)</td><td>4<br>(2.0 × 10<sup>-1</sup>)</td><td>7<br>(9.0 × 10<sup>-4</sup>)</td><td>4<br>(2.0 × 10<sup>-1</sup>)</td><td>7<br>(5.0 × 10<sup>-1</sup>)</td><td>4<br>(5.0 × 10<sup>-1</sup>)</td><td>4</td></tr><tr><td>5</td><td>8<br>(2.0 × 10<sup>-1</sup>)</td><td>8<br>(2.0 × 10<sup>-1</sup>)</td><td>8<br>(2.0 × 10<sup>-1</sup>)</td><td>8<br>(2.0 × 10<sup>-1</sup>)</td><td>4<br>(2.0 × 10<sup>-1</sup>)</td><td>4<br>(5.0 × 10<sup>-1</sup>)</td><td>4</td></tr><tr><td>6</td><td>50<br>(1.6 × 10<sup>-1</sup>)</td><td>8<br>(1.8 × 10<sup>-2</sup>)</td><td>23<br>(1.4 × 10<sup>-1</sup>)</td><td>8<br>(8.8 × 10<sup>-2</sup>)</td><td>23<br>(5.0 × 10<sup>-1</sup>)</td><td>8<br>(4.0 × 10<sup>-2</sup>)</td><td>8</td></tr><tr><td>7</td><td>16<br>(8.0 × 10<sup>-3</sup>)</td><td>16<br>(2.0 × 10<sup>-1</sup>)</td><td>16<br>(1.8 × 10<sup>-2</sup>)</td><td>16<br>(2.0 × 10<sup>-1</sup>)</td><td>8<br>(2.6 × 10<sup>-2</sup>)</td><td>8<br>(1.9 × 10<sup>-1</sup>)</td><td>8</td></tr><tr><td>8</td><td>199<br>(1.4 × 10<sup>-2</sup>)</td><td>16<br>(2.0 × 10<sup>-3</sup>)</td><td>91<br>(6.2 × 10<sup>-2</sup>)</td><td>16<br>(4.0 × 10<sup>-3</sup>)</td><td>87<br>(2.6 × 10<sup>-1</sup>)</td><td>16<br>(6.0 × 10<sup>-3</sup>)</td><td>16</td></tr><tr><td>9</td><td>32<br>(1.0 × 10<sup>-3</sup>)</td><td>32<br>(1.6 × 10<sup>-2</sup>)</td><td>32<br>(2.0 × 10<sup>-3</sup>)</td><td>32<br>(2.4 × 10<sup>-2</sup>)</td><td>16<br>(5.0 × 10<sup>-3</sup>)</td><td>16<br>(4.4 × 10<sup>-2</sup>)</td><td>16</td></tr><tr><td>10</td><td>806<br>(6.0 × 10<sup>-5</sup>)</td><td>32<br>(3.0 × 10<sup>-4</sup>)</td><td>363<br>(6.2 × 10<sup>-2</sup>)</td><td>32<br>(6.0 × 10<sup>-4</sup>)</td><td>343<br>(9.0 × 10<sup>-2</sup>)</td><td>32<br>(1.0 × 10<sup>-3</sup>)</td><td>32</td></tr><tr><td>11</td><td>96<br>(3.0 × 10<sup>-4</sup>)</td><td>64<br>(4.0 × 10<sup>-3</sup>)</td><td>96<br>(6.4 × 10<sup>-4</sup>)</td><td>64<br>(6.3 × 10<sup>-3</sup>)</td><td>32<br>(1.0 × 10<sup>-3</sup>)</td><td>32<br>(1.4 × 10<sup>-2</sup>)</td><td>32</td></tr><tr><td>12</td><td>3222<br>(6.0 × 10<sup>-5</sup>)</td><td>64<br>(6.0 × 10<sup>-5</sup>)</td><td>1451<br>(6.6 × 10<sup>-2</sup>)</td><td>64<br>(1.0 × 10<sup>-4</sup>)</td><td>1367<br>(4.4 × 10<sup>-2</sup>)</td><td>64<br>(2.4 × 10<sup>-4</sup>)</td><td>64</td></tr></tbody></table>

## D. Measurement-Based Preparation of Logical $Q_1$ Code States

### D.1. Measurement-Based Preparation Without Noise (Proof of Lemma 1)

We consider the standard “phase kickback trick” implementation of Pauli $X \otimes X$ and $Z \otimes Z$ measurements, using ancilla qubits as in Fig. 10.

#### Case 1: Preparation Using Pauli $Z \otimes Z$ Measurements

In this case, our procedure consists of performing transversal Pauli $Z \otimes Z$ measurements on corresponding qubits of systems $S_1 = \{1, \dots, K/2\}$, and $S_2 = \{K/2 + 1, \dots, K\}$, prepared in $Q_1$ code states $|q_K^{1/2}\rangle_{S_1} := Q_K^{1/2}|u_1, \bar{v}_1\rangle_{S_1}$ and $|q_K^{2/2}\rangle_{S_2} := Q_K^{2/2}|u_2, \bar{v}_2\rangle_{S_2}$, respectively, as illustrated in Fig. 11.

Expanding the quantum state $|\bar{v}_1\rangle_{\chi(n-1)}$ in the Pauli $Z$ basis, and using (B1), we get, up to a normalization factor,

$$|q_K^{1/2}\rangle_{S_1} = \sum_{x_1 \in \{0,1\}^{K/2-i(k-1)}} (-1)^{v_1 \cdot x_1} |P_K^{K/2}(u_1, x_1)\rangle_{S_1}. \quad (\text{D1})$$

Similarly, we may also expand the quantum state

$|q_K^{2/2}\rangle_{S_2}$ in the Pauli $Z$ basis. Further, we consider the circuit in Fig. 10a to perform transversal Pauli $Z \otimes Z$ measurements, which are done in the following two steps (below, we denote by $S_3$ the ancilla system $A$ from Fig. 10a).

(1) We first take an $(K/2)$-qubit ancilla state $|0\rangle_{S_3}$, and then apply transversal CNOT gates, $CNOT_{S_1 \to S_3}$ and $CNOT_{S_2 \to S_3}$. This gives the following joint

<figure><img src="image_14.png" /><figcaption>(a) Pauli $Z \otimes Z$ measurement: shorthand notation (left) and quantum circuit implementing the Pauli $Z \otimes Z$ measurement (right).</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>(b) Pauli $X \otimes X$ measurement: shorthand notation (left) and quantum circuit implementing the Pauli $X \otimes X$ measurement (right).</figcaption></figure>

Fig. 10: Two-qubit Pauli measurements: shorthand notation and quantum circuits implementing the measurements.

<footnote>(*) For the depolarizing channel, we consider physical error rates $p \in [10^{-5}, 2 \times 10^{-1}]$ (note that the coherent information of the channel vanishes for $p \approx 0.1893$). Reported information position values are constant for physical error rates $p \in [10^{-5}, p_0]$. The value of $p_0$ is reported between round brackets, under the value of $i$ (tiny font size). Similarly, for the quantum erasure channel, we consider channel erasure probability values $\varepsilon \in [10^{-5}, 5 \times 10^{-1}]$. Reported information position values are constant for channel erasure probabilities $\varepsilon \in [10^{-5}, \varepsilon_0]$, where the value of $\varepsilon_0$ is reported between round brackets, under the value of $i$.</footnote>
<table><caption>TABLE II: Best information positions for low error probabilities(*)</caption><thead><tr><th rowspan="3">Levels of<br>Recursion (n)</th><th colspan="2">Depolarizing Channel<br>using correlations</th><th colspan="2">Depolarizing Channel<br>ignoring correlations</th><th colspan="2">Erasure Channel</th><th rowspan="3">Min<br>dist.</th></tr><tr><th colspan="4">Information position i for best Q<sub>1</sub> and Shor-Q<sub>1</sub> codes</th><th rowspan="2">Q<sub>1</sub></th><th rowspan="2">Shor</th></tr><tr><th>Q<sub>1</sub></th><th>Shor</th><th>Q<sub>1</sub></th><th>Shor</th></tr></thead><tbody><tr><td>3</td><td>4<br>(6.8 × 10<sup>-2</sup>)</td><td>4<br>(2.0 × 10<sup>-1</sup>)</td><td>4<br>(1.0 × 10<sup>-3</sup>)</td><td>4<br>(1.0 × 10<sup>-3</sup>)</td><td>2<br>(5.0 × 10<sup>-1</sup>)</td><td>2<br>(5.0 × 10<sup>-1</sup>)</td><td>2</td></tr><tr><td>4</td><td>13<br>(2.0 × 10<sup>-1</sup>)</td><td>4<br>(2.0 × 10<sup>-1</sup>)</td><td>7<br>(9.0 × 10<sup>-4</sup>)</td><td>4<br>(2.0 × 10<sup>-1</sup>)</td><td>7<br>(5.0 × 10<sup>-1</sup>)</td><td>4<br>(5.0 × 10<sup>-1</sup>)</td><td>4</td></tr><tr><td>5</td><td>8<br>(2.0 × 10<sup>-1</sup>)</td><td>8<br>(2.0 × 10<sup>-1</sup>)</td><td>8<br>(2.0 × 10<sup>-1</sup>)</td><td>8<br>(2.0 × 10<sup>-1</sup>)</td><td>4<br>(2.0 × 10<sup>-1</sup>)</td><td>4<br>(5.0 × 10<sup>-1</sup>)</td><td>4</td></tr><tr><td>6</td><td>50<br>(1.6 × 10<sup>-1</sup>)</td><td>8<br>(1.8 × 10<sup>-2</sup>)</td><td>23<br>(1.4 × 10<sup>-1</sup>)</td><td>8<br>(8.8 × 10<sup>-2</sup>)</td><td>23<br>(5.0 × 10<sup>-1</sup>)</td><td>8<br>(4.0 × 10<sup>-2</sup>)</td><td>8</td></tr><tr><td>7</td><td>16<br>(8.0 × 10<sup>-3</sup>)</td><td>16<br>(2.0 × 10<sup>-1</sup>)</td><td>16<br>(1.8 × 10<sup>-2</sup>)</td><td>16<br>(2.0 × 10<sup>-1</sup>)</td><td>8<br>(2.6 × 10<sup>-2</sup>)</td><td>8<br>(1.9 × 10<sup>-1</sup>)</td><td>8</td></tr><tr><td>8</td><td>199<br>(1.4 × 10<sup>-2</sup>)</td><td>16<br>(2.0 × 10<sup>-3</sup>)</td><td>91<br>(6.2 × 10<sup>-2</sup>)</td><td>16<br>(4.0 × 10<sup>-3</sup>)</td><td>87<br>(2.6 × 10<sup>-1</sup>)</td><td>16<br>(6.0 × 10<sup>-3</sup>)</td><td>16</td></tr><tr><td>9</td><td>32<br>(1.0 × 10<sup>-3</sup>)</td><td>32<br>(1.6 × 10<sup>-2</sup>)</td><td>32<br>(2.0 × 10<sup>-3</sup>)</td><td>32<br>(2.4 × 10<sup>-2</sup>)</td><td>16<br>(5.0 × 10<sup>-3</sup>)</td><td>16<br>(4.4 × 10<sup>-2</sup>)</td><td>16</td></tr><tr><td>10</td><td>806<br>(6.0 × 10<sup>-5</sup>)</td><td>32<br>(3.0 × 10<sup>-4</sup>)</td><td>363<br>(6.2 × 10<sup>-2</sup>)</td><td>32<br>(6.0 × 10<sup>-4</sup>)</td><td>343<br>(9.0 × 10<sup>-2</sup>)</td><td>32<br>(1.0 × 10<sup>-3</sup>)</td><td>32</td></tr><tr><td>11</td><td>96<br>(3.0 × 10<sup>-4</sup>)</td><td>64<br>(4.0 × 10<sup>-3</sup>)</td><td>96<br>(6.4 × 10<sup>-4</sup>)</td><td>64<br>(6.3 × 10<sup>-3</sup>)</td><td>32<br>(1.0 × 10<sup>-3</sup>)</td><td>32<br>(1.4 × 10<sup>-2</sup>)</td><td>32</td></tr><tr><td>12</td><td>3222<br>(6.0 × 10<sup>-5</sup>)</td><td>64<br>(6.0 × 10<sup>-5</sup>)</td><td>1451<br>(6.6 × 10<sup>-2</sup>)</td><td>64<br>(1.0 × 10<sup>-4</sup>)</td><td>1367<br>(4.4 × 10<sup>-2</sup>)</td><td>64<br>(2.4 × 10<sup>-4</sup>)</td><td>64</td></tr></tbody></table>

## D. Measurement-Based Preparation of Logical $Q_1$ Code States

### D.1. Measurement-Based Preparation Without Noise (Proof of Lemma 1)

We consider the standard “phase kickback trick” implementation of Pauli $X \otimes X$ and $Z \otimes Z$ measurements, using ancilla qubits as in Fig. 10.

#### Case 1: Preparation Using Pauli $Z \otimes Z$ Measurements

In this case, our procedure consists of performing transversal Pauli $Z \otimes Z$ measurements on corresponding qubits of systems $S_1 = \{1, \dots, K/2\}$, and $S_2 = \{K/2 + 1, \dots, K\}$, prepared in $Q_1$ code states $|q_K^1\rangle_{S_1} := Q_K^1|u_1, \bar{v}_1\rangle_{S_1}$ and $|q_K^2\rangle_{S_2} := Q_K^2|u_2, \bar{v}_2\rangle_{S_2}$, respectively, as illustrated in Fig. 11.

Expanding the quantum state $|\bar{v}_1\rangle_{\chi(n-1)}$ in the Pauli $Z$ basis, and using (B1), we get, up to a normalization factor,

$$|q_K^1\rangle_{S_1} = \sum_{x_1 \in \{0,1\}^{K/2-i(k-1)}} (-1)^{v_1 \cdot x_1} |P_K^1(u_1, x_1)\rangle_{S_1}. \quad (\text{D1})$$

Similarly, we may also expand the quantum state

$|q_K^2\rangle_{S_2}$ in the Pauli $Z$ basis. Further, we consider the circuit in Fig. 10a to perform transversal Pauli $Z \otimes Z$ measurements, which are done in the following two steps (below, we denote by $S_3$ the ancilla system $A$ from Fig. 10a).

(1) We first take an $(K/2)$-qubit ancilla state $|0\rangle_{S_3}$, and then apply transversal CNOT gates, $CNOT_{S_1 \to S_3}$ and $CNOT_{S_2 \to S_3}$. This gives the following joint

<figure><img src="image_14.png" /><figcaption>(a) Pauli $Z \otimes Z$ measurement: shorthand notation (left) and quantum circuit implementing the Pauli $Z \otimes Z$ measurement (right).</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>(b) Pauli $X \otimes X$ measurement: shorthand notation (left) and quantum circuit implementing the Pauli $X \otimes X$ measurement (right).</figcaption></figure>

Fig. 10: Two-qubit Pauli measurements: shorthand notation and quantum circuits implementing the measurements.

<footnote>(*) For the depolarizing channel, we consider physical error rates $p \in [10^{-5}, 2 \times 10^{-1}]$ (note that the coherent information of the channel vanishes for $p \approx 0.1893$). Reported information position values are constant for physical error rates $p \in [10^{-5}, p_0]$. The value of $p_0$ is reported between round brackets, under the value of $i$ (tiny font size). Similarly, for the quantum erasure channel, we consider channel erasure probability values $\varepsilon \in [10^{-5}, 5 \times 10^{-1}]$. Reported information position values are constant for channel erasure probabilities $\varepsilon \in [10^{-5}, \varepsilon_0]$, where the value of $\varepsilon_0$ is reported between round brackets, under the value of $i$.</footnote>
<figure><img src="image_16.png" /><figcaption>Fig. 11: Preparation using Pauli Z ⊗ Z measurements
(i(k) = i(k − 1) + K 2 ∈ { K 2 + 1 , . . . , K } ).</figcaption></figure>

quantum state on S₁ ∪ S₂ ∪ S₃.

$$
\begin{equation}
\begin{split}
|\eta\rangle_{S_1 S_2 S_3} = \sum_{\substack{x_1, x_2 \\ \mathcal{X}(n)}} (-1)^{v_1 \cdot x_1 + v_2 \cdot x_2} & |P_{\frac{K}{2}}(\mathbf{u}_1, \mathbf{x}_1)\rangle_{S_1} \\
& |P_{\frac{K}{2}}(\mathbf{u}_2, \mathbf{x}_2)\rangle_{S_2} |P_{\frac{K}{2}}(\mathbf{u}_1 \oplus \mathbf{u}_2, \mathbf{x}_1 \oplus \mathbf{x}_2)\rangle_{S_3}.
\end{split}
\tag{D2}
\end{equation}
$$

(2) Then, we measure each qubit in the ancilla system $S_3$ in the Pauli Z basis. From (D2), the measurement outcome gives a binary vector of length $K/2$ as follows,

$$
m = P_{\frac{K}{2}}(u', x) \in \{0, 1\}^{\frac{K}{2}}, \quad (\text{D3})
$$

where $u' = u_1 \oplus u_2 \in \{0,1\}^{i(k)}$, and $x \in \{0,1\}^{\frac{K}{2}-i(k)}$
is a random vector. Further, from (D2) and (D3), the
state of the joint system $S_1 \cup S_2$ after the measure-
ments is as follows

$$
\begin{equation}
\begin{split}
|\eta'\rangle_{S_1 S_2} = \sum_{\substack{x_1, x_2 \\ x_1 \oplus x_2 = x}} (-1)^{v_1 \cdot x_1 + v_2 \cdot x_2} & |P_{\frac{K}{2}}(\mathbf{u}_1, \mathbf{x}_1)\rangle_{S_1} \\
& |P_{\frac{K}{2}}(\mathbf{u}_2, \mathbf{x}_2)\rangle_{S_2}
\end{split}
\tag{D4}
\end{equation}
$$

It can be seen as follows that the quantum state $|\eta'\rangle_{S_1S_2}$ is the $Q_1$ code state $|q_K\rangle_{S_1S_2}$ as in Case 1 of Lemma 1,

$$
\begin{align*}
|\eta'\rangle_{S_1 S_2} &= \sum_{\substack{x_1, x_2 \\ x_1 \oplus x_2 = x}} (-1)^{v_1 \cdot x_1 + v_2 \cdot x_2} |P_{\frac{K}{2}}(\mathbf{u}_1, \mathbf{x}_1)\rangle_{S_1} \\
&= \sum_{x_2} (-1)^{v_1 \cdot (x+x_2) + v_2 \cdot x_2} |P_{\frac{K}{2}}(\mathbf{u}' \oplus \mathbf{u}_2, \mathbf{x} \oplus \mathbf{x}_2)\rangle_{S_1} \\
&\qquad \times \\
&= \sum_{x_2} (-1)^{v_1 \cdot x} \sum_{\substack{x_2 \\ \mathbf{v}_1 \oplus \mathbf{v}_2 = \mathbf{v}_2}} (-1)^{(v_1+v_2) \cdot x_2} |P_K(\mathbf{u}', \mathbf{x}, \mathbf{u}_2, \mathbf{x}_2)\rangle_{S_1 S_2} \\
&= Q_K |\mathbf{u}', \mathbf{x}, \mathbf{u}_2, \overline{\mathbf{v}_1 \oplus \mathbf{v}_2}\rangle_{S_1 S_2}
\end{align*}
$$

where in the second equality, we have used $\mathbf{u}_1 = \mathbf{u}' \oplus \mathbf{u}_2$
and $\mathbf{x}_1 = \mathbf{x} \oplus \mathbf{x}_2$, and in the third equality, we have used

<figure><img src="image_17.png" /><figcaption>Fig. 12: Preparation using Pauli X ⊗ X measurements
(i(k) = i(k − 1) ∈ {1 , . . . , K 2 } ).</figcaption></figure>

$P_K(\mathbf{a}, \mathbf{b}) = (P_{\frac{K}{2}}(\mathbf{a} \oplus \mathbf{b}), P_{\frac{K}{2}}(\mathbf{b})), \mathbf{a}, \mathbf{b} \in \{0,1\}^{\frac{K}{2}}$, using the recursion of the classical polar transform given in Fig. 5a.

Hence, after the Pauli Z ⊗ Z measurements, we have
prepared the $Q_1$ code state on the joint system $S = S_1 \cup S_2$,

$$
|q_K\rangle_S = Q_K |u', x, u_2, \overline{v_1 \oplus v_2}\rangle_S. \quad (D5)
$$

Finally, from (D3), we have that $P_K(\mathbf{m}) = (\mathbf{u}', \mathbf{x}) \in \{0,1\}^{\frac{K}{2}}$ (using $P_K^2 = I$). Hence, $\mathbf{x}$ is determined by, $\mathbf{x} = P_K(\mathbf{m})|_{\mathcal{X}(n-1)}$, as desired.

Case 2: Preparation Using Pauli X ⊗ X Measurements

In this case, our procedure consists in performing
transversal Pauli X ⊗ X measurements on corresponding
qubits of systems S₁ and S₂, prepared in Q₁ code states
|q₁^K⟩ := Q₁^K |u₁, v₁⟩S₁ and |q₂^K⟩ := Q₂^K |u₂, v₂⟩S₂, as
illustrated in Fig. 12.

We skip the proof here as it is similar to the Case 1. By
expanding |q<sup>1</sup><sub>K/2</sub>⟩<sub>S<sub>1</sub></sub> and |q<sup>2</sup><sub>K/2</sub>⟩<sub>S<sub>2</sub></sub>, in the Pauli X basis instead
and using (B2) it can be seen that the measurement out-
come of Pauli X ⊗ X measurements is given by,

$$
m = P_{\frac{K}{2}}^{\top}(z, v') \in \{0, 1\}^{\frac{K}{2}}, \quad (\text{D6})
$$

where $z \in \{0,1\}^{i(k-1)}$ is a random vector, and $v' =
v_1 \oplus v_2 \in \{0,1\}^{\frac{K}{2}-i(k-1)}$. Further, after measurements,
the state on $S = S_1 \cup S_2$ is a $Q_1$ state is given by,

$$
|q_K\rangle_S = |\mathbf{u}_1 \oplus \mathbf{u}_2, \overline{(\mathbf{v}_1, \mathbf{z}, \mathbf{v}')}\rangle, \quad (D7)
$$

where $z$ can be determined from (D6) as, $z = P_K^\top(m)|_{Z(k-1)}$.
<figure><img src="image_16.png" /><figcaption>Fig. 11: Preparation using Pauli Z ⊗ Z measurements
(i(k) = i(k − 1) + K 2 ∈ { K 2 + 1 , . . . , K } ).</figcaption></figure>

quantum state on S₁ ∪ S₂ ∪ S₃.

$$
\begin{equation}
\begin{split}
|\eta\rangle_{S_1 S_2 S_3} = \sum_{\substack{x_1, x_2 \\ \mathcal{X}(n)}} (-1)^{v_1 \cdot x_1 + v_2 \cdot x_2} & |P_{\frac{K}{2}}(\mathbf{u}_1, \mathbf{x}_1)\rangle_{S_1} \\
& |P_{\frac{K}{2}}(\mathbf{u}_2, \mathbf{x}_2)\rangle_{S_2} |P_{\frac{K}{2}}(\mathbf{u}_1 \oplus \mathbf{u}_2, \mathbf{x}_1 \oplus \mathbf{x}_2)\rangle_{S_3}.
\end{split}
\tag{D2}
\end{equation}
$$

(2) Then, we measure each qubit in the ancilla system $S_3$ in the Pauli Z basis. From (D2), the measurement outcome gives a binary vector of length $K/2$ as follows,

$$
m = P_{\frac{K}{2}}(u', x) \in \{0, 1\}^{\frac{K}{2}}, \quad (\text{D3})
$$

where $u' = u_1 \oplus u_2 \in \{0, 1\}^{i(k)}$, and $x \in \{0, 1\}^{\frac{K}{2}-i(k)}$
is a random vector. Further, from (D2) and (D3), the
state of the joint system $S_1 \cup S_2$ after the measure-
ments is as follows

$$
\begin{equation}
\begin{split}
|\eta'\rangle_{S_1 S_2} = \sum_{\substack{x_1, x_2 \\ x_1 \oplus x_2 = x}} (-1)^{v_1 \cdot x_1 + v_2 \cdot x_2} & |P_{\frac{K}{2}}(\mathbf{u}_1, \mathbf{x}_1)\rangle_{S_1} \\
& |P_{\frac{K}{2}}(\mathbf{u}_2, \mathbf{x}_2)\rangle_{S_2}
\end{split}
\tag{D4}
\end{equation}
$$

It can be seen as follows that the quantum state $|\eta'\rangle_{S_1S_2}$ is the $Q_1$ code state $|q_K\rangle_{S_1S_2}$ as in Case 1 of Lemma 1,

$$
\begin{align*}
|\eta'\rangle_{S_1 S_2} &= \sum_{\substack{x_1, x_2 \\ x_1 \oplus x_2 = x}} (-1)^{v_1 \cdot x_1 + v_2 \cdot x_2} |P_{\frac{K}{2}}(\mathbf{u}_1, \mathbf{x}_1)\rangle_{S_1} \\
&= \sum_{x_2} (-1)^{v_1 \cdot (x+x_2) + v_2 \cdot x_2} |P_{\frac{K}{2}}(\mathbf{u}' \oplus \mathbf{u}_2, \mathbf{x} \oplus \mathbf{x}_2)\rangle_{S_1} \\
&\qquad \times \\
&= \sum_{x_2} (-1)^{v_1 \cdot x} \sum_{x_2} (-1)^{(v_1+v_2) \cdot x_2} |P_K(\mathbf{u}', \mathbf{x}, \mathbf{u}_2, \mathbf{x}_2)\rangle_{S_1 S_2} \\
&= Q_K |\mathbf{u}', \mathbf{x}, \mathbf{u}_2, \overline{\mathbf{v}_1 \oplus \mathbf{v}_2}\rangle_{S_1 S_2}
\end{align*}
$$

where in the second equality, we have used $\mathbf{u}_1 = \mathbf{u}' \oplus \mathbf{u}_2$
and $\mathbf{x}_1 = \mathbf{x} \oplus \mathbf{x}_2$, and in the third equality, we have used

<figure><img src="image_17.png" /><figcaption>Fig. 12: Preparation using Pauli X ⊗ X measurements
(i(k) = i(k − 1) ∈ {1, . . . , K}).</figcaption></figure>

$P_K(\mathbf{a}, \mathbf{b}) = (P_{\frac{K}{2}}(\mathbf{a} \oplus \mathbf{b}), P_{\frac{K}{2}}(\mathbf{b})), \mathbf{a}, \mathbf{b} \in \{0, 1\}^{\frac{K}{2}}$, using the recursion of the classical polar transform given in Fig. 5a.

Hence, after the Pauli Z ⊗ Z measurements, we have
prepared the $Q_1$ code state on the joint system $S = S_1 \cup S_2$,

$$
|q_K\rangle_S = Q_K |u', x, u_2, \overline{v_1 \oplus v_2}\rangle_S. \quad (D5)
$$

Finally, from (D3), we have that $P_K(\mathbf{m}) = (\mathbf{u}', \mathbf{x}) \in \{0, 1\}^{\frac{K}{2}}$ (using $P_K^2 = I$). Hence, $\mathbf{x}$ is determined by, $\mathbf{x} = P_K(\mathbf{m})|_{\mathcal{X}(n-1)}$, as desired.

Case 2: Preparation Using Pauli X ⊗ X Measurements

In this case, our procedure consists in performing
transversal Pauli X ⊗ X measurements on corresponding
qubits of systems S₁ and S₂, prepared in Q₁ code states
|q₁^K⟩ := Q₁^K |u₁, v₁⟩S₁ and |q₂^K⟩ := Q₂^K |u₂, v₂⟩S₂, as
illustrated in Fig. 12.

We skip the proof here as it is similar to the Case 1. By
expanding |q<sup>1</sup><sub>K/2</sub>⟩<sub>S<sub>1</sub></sub> and |q<sup>2</sup><sub>K/2</sub>⟩<sub>S<sub>2</sub></sub>, in the Pauli X basis instead
and using (B2) it can be seen that the measurement out-
come of Pauli X ⊗ X measurements is given by,

$$
m = P_{\frac{K}{2}}^{\top}(z, v') \in \{0, 1\}^{\frac{K}{2}}, \quad (\text{D6})
$$

where $z \in \{0, 1\}^{i(k-1)}$ is a random vector, and $v' =
v_1 \oplus v_2 \in \{0, 1\}^{\frac{K}{2}-i(k-1)}$. Further, after measurements,
the state on $S = S_1 \cup S_2$ is a $Q_1$ state is given by,

$$
|q_K\rangle_S = |u_1 \oplus u_2, \overline{(v_1, z, v')}\rangle, \quad (D7)
$$

where $z$ can be determined from (D6) as, $z = P_K^\top(m)|_{Z(k-1)}$.
## D.2. Fault-tolerant Measurement-Based Preparation with Noise

In this section, supposing a circuit level noise model with Pauli errors, we detail the measurement-based preparation with the error detection from Procedure 2, for both Case 1 and Case 2. Then, we provide a proof of fault tolerance according to Theorem 3.

We suppose that we are given noisy versions of $Q_1$ code states of length $K/2$ on $S_1 = \{1, \dots, K/2\}$, and $S_2 = \{K/2 + 1, \dots, K\}$, as follows.

$$|q_{\frac{K}{2}}^1\rangle_{S_1} = X e_X^1 Z e_Z^1 Q_{\frac{K}{2}} |u_1, \bar{v}_1\rangle_{S_1}, \quad (D8)$$

$$|q_{\frac{K}{2}}^2\rangle_{S_2} = X e_X^2 Z e_Z^2 Q_{\frac{K}{2}} |u_2, \bar{v}_2\rangle_{S_2}, \quad (D9)$$

where $u_1, u_2 \in \{0, 1\}^{i(k-1)}$, $v_1, v_2 \in \{0, 1\}^{\frac{K}{2}-i(k-1)}$, and the errors $e_X^1, e_Z^1, e_X^2, e_Z^2 \in \{0, 1\}^{\frac{K}{2}}$ are unknown.

### Case 1: Preparation Using Noisy Pauli $Z \otimes Z$ Measurements.

We suppose that the following errors happen due to the component failures during transversal Pauli $Z \otimes Z$ measurements (see also Fig. 13, where all errors are given; also recall from the previous section, that $S_3$ denotes the ancilla system needed for the “phase kickback trick” implementation of $Z \otimes Z$ measurements, i.e., system A in Fig. 10a).

(1) Suppose failures during the initialization of $S_3$ in the Pauli $Z$ basis cause an $X$ error $e_X^I \in \{0, 1\}^{K/2}$ on $S_3$.

(2) Suppose CNOT failures in CNOT$_{S_1 \to S_3}$ cause $X, Z$ type errors $e_X^{C_1(1)}, e_Z^{C_1(1)} \in \{0, 1\}^{K/2}$, respectively, on $S_1$, and $X, Z$ type errors $e_X^{C_1(3)}, e_Z^{C_1(3)} \in \{0, 1\}^{K/2}$, respectively, on $S_3$.

(3) Suppose CNOT failures in CNOT$_{S_2 \to S_3}$ cause $X, Z$ type errors $e_X^{C_2(2)}, e_Z^{C_2(2)} \in \{0, 1\}^{K/2}$, respectively, on $S_2$, and $X, Z$ type errors $e_X^{C_2(3)}, e_Z^{C_2(3)} \in \{0, 1\}^{K/2}$, respectively, on $S_3$.

(4) Suppose failures during the measurement of $S_3$ in the Pauli $Z$ basis cause an $X$ error $e_X^M \in \{0, 1\}^{K/2}$ on $S_3$.

The measurement outcome of the transversal Pauli $Z \otimes Z$ measurements and the state of the joint system $S = S_1 \cup S_2$ after measurements is given in Lemma 6.

**Lemma 6.** The measurement outcome of noisy transversal Pauli $Z \otimes Z$ measurements on systems $S_1$ and $S_2$, respectively in (D8) and (D9), is equal to

$$m' = m \oplus e_X \in \{0, 1\}^{\frac{K}{2}}, \quad (D10)$$

where $m$ is the measurement outcome corresponding to the preparation without noise from (D3) and $e_X = e_X^I \oplus e_X^2 \oplus e_X^{C_1(3)} \oplus e_X^2 \oplus e_X^{C_2(3)} \oplus e_X^M$. Further, after the measurement, we get

$$|q'_{K}\rangle_S = X \tilde{e}_X Z \tilde{e}_Z |q_K\rangle_S, \quad (D11)$$

where $|q_K\rangle_S$ is the prepared state without noise from (D5) and the errors are as follows,

$$\tilde{e}_X = (e_X^1 \oplus e_X^{C_1(1)}, e_X^2 \oplus e_X^{C_2(2)}) \in \{0, 1\}^K. \quad (D12)$$

$$\tilde{e}_Z = (e_Z^1 \oplus e_Z^{C_1(1)}, e_Z^2 \oplus e_Z^{C_1(3)} \oplus e_Z^{C_2(2)}) \in \{0, 1\}^K. \quad (D13)$$

*Proof.* Note that $X$ errors in Fig. 13a, and $Z$ errors in Fig. 13b can be propagated from the LHS to RHS, using the following rules.

(1) An $X$ error simply passes through the target of a CNOT gate, and it propagates from the control of the CNOT gate to its target.

(2) An $Z$ error simply passes through the control of a CNOT gate, and it propagates from the target of the CNOT gate to its control.

<figure><img src="image_18.png" /><figcaption>Fig. 13: The representation of errors during the preparation with Pauli $Z \otimes Z$ measurements. The crossed wires represent $K/2$-qubit systems $S_1, S_2$ and $S_3$, respectively. The CNOT gate between two systems represents the transversal CNOT gates between the systems. The errors are represented where they happen. For example, in Fig. 13a, $e_X^1, e_X^2$, and $e_X^I$ represent the initial errors on systems $S_1, S_2$ and $S_3$, respectively. Further, $e_X^{C_1(1)}$ and $e_X^{C_1(3)}$ represent the errors caused by the first CNOT, applied between $S_1$ and $S_3$, respectively. Similarly, the errors due to the second CNOT are represented on systems $S_2$ and $S_3$. Finally, $e_X^M$ represents the $X$ error due to the measurement on system $S_3$.</figcaption></figure>
## D.2. Fault-tolerant Measurement-Based Preparation with Noise

In this section, supposing a circuit level noise model with Pauli errors, we detail the measurement-based preparation with the error detection from Procedure 2, for both Case 1 and Case 2. Then, we provide a proof of fault tolerance according to Theorem 3.

We suppose that we are given noisy versions of $Q_1$ code states of length $K/2$ on $S_1 = \{1, \dots, K/2\}$, and $S_2 = \{K/2+1, \dots, K\}$, as follows.

$$|q_{\frac{K}{2}}^1\rangle_{S_1} = X e_X^1 Z e_Z^1 Q_{\frac{K}{2}} |u_1, \bar{v}_1\rangle_{S_1}, \quad (D8)$$

$$|q_{\frac{K}{2}}^2\rangle_{S_2} = X e_X^2 Z e_Z^2 Q_{\frac{K}{2}} |u_2, \bar{v}_2\rangle_{S_2}, \quad (D9)$$

where $u_1, u_2 \in \{0, 1\}^{i(k-1)}$, $v_1, v_2 \in \{0, 1\}^{\frac{K}{2}-i(k-1)}$, and the errors $e_X^1, e_Z^1, e_X^2, e_Z^2 \in \{0, 1\}^{\frac{K}{2}}$ are unknown.

### Case 1: Preparation Using Noisy Pauli $Z \otimes Z$ Measurements.

We suppose that the following errors happen due to the component failures during transversal Pauli $Z \otimes Z$ measurements (see also Fig. 13, where all errors are given; also recall from the previous section, that $S_3$ denotes the ancilla system needed for the “phase kickback trick” implementation of $Z \otimes Z$ measurements, i.e., system A in Fig. 10a).

(1) Suppose failures during the initialization of $S_3$ in the Pauli $Z$ basis cause an $X$ error $e_X^I \in \{0, 1\}^{K/2}$ on $S_3$.

(2) Suppose CNOT failures in CNOT$_{S_1 \to S_3}$ cause $X, Z$ type errors $e_X^{C_1(1)}, e_Z^{C_1(1)} \in \{0, 1\}^{K/2}$, respectively, on $S_1$, and $X, Z$ type errors $e_X^{C_1(3)}, e_Z^{C_1(3)} \in \{0, 1\}^{K/2}$, respectively, on $S_3$.

(3) Suppose CNOT failures in CNOT$_{S_2 \to S_3}$ cause $X, Z$ type errors $e_X^{C_2(2)}, e_Z^{C_2(2)} \in \{0, 1\}^{K/2}$, respectively, on $S_2$, and $X, Z$ type errors $e_X^{C_2(3)}, e_Z^{C_2(3)} \in \{0, 1\}^{K/2}$, respectively, on $S_3$.

(4) Suppose failures during the measurement of $S_3$ in the Pauli $Z$ basis cause an $X$ error $e_X^M \in \{0, 1\}^{K/2}$ on $S_3$.

The measurement outcome of the transversal Pauli $Z \otimes Z$ measurements and the state of the joint system $S = S_1 \cup S_2$ after measurements is given in Lemma 6.

**Lemma 6.** The measurement outcome of noisy transversal Pauli $Z \otimes Z$ measurements on systems $S_1$ and $S_2$, respectively in (D8) and (D9), is equal to

$$m' = m \oplus e_X \in \{0, 1\}^{\frac{K}{2}}, \quad (D10)$$

where $m$ is the measurement outcome corresponding to the preparation without noise from (D3) and $e_X = e_X^I \oplus e_X^2 \oplus e_X^{C_1(3)} \oplus e_X^2 \oplus e_X^{C_2(3)} \oplus e_X^M$. Further, after the measurement, we get

$$|q'_{K}\rangle_S = X \tilde{e}_X Z \tilde{e}_Z |q_K\rangle_S, \quad (D11)$$

where $|q_K\rangle_S$ is the prepared state without noise from (D5) and the errors are as follows,

$$\tilde{e}_X = (e_X^1 \oplus e_X^{C_1(1)}, e_X^2 \oplus e_X^{C_2(2)}) \in \{0, 1\}^K. \quad (D12)$$

$$\tilde{e}_Z = (e_Z^1 \oplus e_Z^{C_1(1)}, e_Z^2 \oplus e_Z^{C_2(3)} \oplus e_Z^{C_2(2)}) \in \{0, 1\}^K. \quad (D13)$$

*Proof.* Note that $X$ errors in Fig. 13a, and $Z$ errors in Fig. 13b can be propagated from the LHS to RHS, using the following rules.

(1) An $X$ error simply passes through the target of a CNOT gate, and it propagates from the control of the CNOT gate to its target.

(2) An $Z$ error simply passes through the control of a CNOT gate, and it propagates from the target of the CNOT gate to its control.

<figure><img src="image_18.png" /><figcaption>Fig. 13: The representation of errors during the preparation with Pauli $Z \otimes Z$ measurements. The crossed wires represent $K/2$-qubit systems $S_1, S_2$ and $S_3$, respectively. The CNOT gate between two systems represents the transversal CNOT gates between the systems. The errors are represented where they happen. For example, in Fig. 13a, $e_X^1, e_X^2$, and $e_X^I$ represent the initial errors on systems $S_1, S_2$ and $S_3$, respectively. Further, $e_X^{C_1(1)}$ and $e_X^{C_1(3)}$ represent the errors caused by the first CNOT, applied between $S_1$ and $S_3$, respectively. Similarly, the errors due to the second CNOT are represented on systems $S_2$ and $S_3$. Finally, $e_X^M$ represents the $X$ error due to the measurement on system $S_3$.</figcaption></figure>
The X and Z errors on the RHS for $S_1$, $S_2$ and $S_3$ are given in Table III.

<table><caption>TABLE III: Total errors on systems $S_1$, $S_2$, and $S_3$.</caption><thead><tr><th>System</th><th>total X error</th><th>total Z error</th></tr></thead><tbody><tr><td>$S_1$</td><td>$e_X^1 \oplus e_X^{C_1(1)}$</td><td>$e_Z^1 \oplus e_Z^{C_1(1)}$</td></tr><tr><td>$S_2$</td><td>$e_X^2 \oplus e_X^{C_2(2)}$</td><td>$e_Z^2 \oplus e_Z^{C_2(3)}$</td></tr><tr><td>$S_3$</td><td>$e_X^I \oplus e_X^I \oplus e_X^{C_1(3)} \oplus e_X^I \oplus e_X^{C_2(3)} \oplus e_X^M$</td><td>$e_Z^{C_1(3)} \oplus e_Z^{C_2(3)}$</td></tr></tbody></table>

It follows that the noisy measurement outcome $m'$ is equal to the binary sum of the measurement outcome $m$ in the noiseless case and the X error on system $S_3$, therefore, from Table III, we get (D10). Further, the prepared state $|q'_K\rangle_S$ is equal to the noiseless state $|q_K\rangle_S$, with some X and Z errors on it. The X (or Z) error on S is simply the concatenation of the total X (or Z) errors on systems $S_1$ and $S_2$. Therefore, from Table III, we get (D12), and (D13), for X and Z errors in $|q'_K\rangle_S$, respectively. □

We now combine the noisy preparation in Lemma 6 with the error detection gadget according to Procedure 2. We recall here how the error detection gadget works. Consider the error $e_X$ in the measurement outcome $m'$ in (D10) so that its syndrome is a zero vector, i.e.,

$$P_{\frac{K}{2}}(e_X)|_{Z(k-1)} = 0. \qquad (\text{D14})$$

Then the prepared state is accepted and the random vector $x$ in (D11) is estimated as

$$\hat{x} = P_{\frac{K}{2}}(m')|_{\mathcal{X}(k-1)}. \qquad (\text{D15})$$

The total error in the prepared state, with respect to the estimate $\hat{x}$, is given in Lemma 7.

**Lemma 7.** Consider the error $e_X$ in the measurement outcome $m$ from (D10), so that it satisfies (D14), and let $\hat{x}$ be defined according to (D15). Then, the state of the joint system S in (D11) can be written as follows, with respect to $\hat{x}$.

$$|q'_K\rangle_S = X e_X^f Z e_Z^f Q_K |(u', \hat{x}, u_2, \overline{v_1 \oplus v_2})\rangle_S, \qquad (\text{D16})$$

where $e_X^f = \tilde{e}_X + (e_X, 0)$ and $e_Z^f = \tilde{e}_Z$, so that $\tilde{e}_X$ and $\tilde{e}_Z$ are according to (D12) and (D13), respectively.

*Proof.* From (D3), (D10), and (D15), we have that

$$\hat{x} = x \oplus P_{\frac{K}{2}}(e_X)|_{\mathcal{X}(n-1)}. \qquad (\text{D17})$$

We may write $|q'_K\rangle_S$ in (D11), with respect to $\hat{x}$ as follows,

$$\begin{aligned} |q'_K\rangle_S &= X^{\tilde{e}_X} Z^{\tilde{e}_Z} Q_K |(u', x, u_2, \overline{v_1 \oplus v_2})\rangle \\ &= X^{\tilde{e}_X} Z^{\tilde{e}_Z} \sum_{x_2} (-1)^{(v_1 \oplus v_2) \cdot x_2} \\ &= |P_K(u', \hat{x} \oplus P_{\frac{K}{2}}(e_X)|_{\mathcal{X}(n-1)}, u_2, x_2)\rangle \\ &= X^{\tilde{e}_X} Z^{\tilde{e}_Z} \sum_{x_2} (-1)^{(v_1 \oplus v_2) \cdot x_2} X^{(e_X, 0)} |P_K(u', \hat{x}, u_2, x_2)\rangle \\ &= X^{\tilde{e}_X \oplus (e_X, 0)} Z^{\tilde{e}_Z} Q_K |(u', \hat{x}, u_2, \overline{v_1 \oplus v_2})\rangle, \end{aligned} \qquad (\text{D18})$$

where in the second equality, we have expanded the quantum state in the Pauli Z basis and used (D17), and in the third equality, we have used $e_X = P_{\frac{K}{2}}(P_{\frac{K}{2}}(e_X)|_{Z(n-1)}, P_{\frac{K}{2}}(e_X)|_{\mathcal{X}(n-1)}) = P_{\frac{K}{2}}(0, P_{\frac{K}{2}}(e_X)|_{\mathcal{X}(n-1)}). \square$

**Case 2: Preparation Using Noisy Pauli $X \otimes X$ Measurements.**

The errors during the preparation with Pauli $X \otimes X$ measurements are given in Fig. 14. Note that we have Z type initialization and measurement errors on the ancilla system $S_3$, which are denoted by $e_Z^I, e_Z^m \in \{0, 1\}^{K/2}$, respectively. For the errors caused by the CNOT gates, $CNOT_{S_3 \to S_1}$ and $CNOT_{S_3 \to S_2}$, we have used the same notation as in the case of Pauli $Z \otimes Z$ measurements.

Here, we provide Lemmas 8 and 9, which are analogous to Lemmas 6 and 7, respectively, and thus their proofs have been omitted.

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

<figure><img src="image_20.png" /><figcaption>Fig. 14: Errors during preparation with Pauli $X \otimes X$ measurements.</figcaption></figure>
The X and Z errors on the RHS for $S_1, S_2$ and $S_3$ are given in Table III.

<table><caption>TABLE III: Total errors on systems $S_1, S_2$, and $S_3$.</caption><thead><tr><th>System</th><th>total X error</th><th>total Z error</th></tr></thead><tbody><tr><td>$S_1$</td><td>$e_X^1 \oplus e_X^{C_1(1)}$</td><td>$e_Z^1 \oplus e_Z^{C_1(1)}$</td></tr><tr><td>$S_2$</td><td>$e_X^2 \oplus e_X^{C_2(2)}$</td><td>$e_Z^2 \oplus e_Z^{C_2(3)}$</td></tr><tr><td>$S_3$</td><td>$e_X^I \oplus e_X^1 \oplus e_X^{C_1(3)} \oplus e_X^2 \oplus e_X^{C_2(3)} \oplus e_X^M$</td><td>$e_Z^{C_1(3)} \oplus e_Z^{C_2(3)}$</td></tr></tbody></table>

It follows that the noisy measurement outcome $m'$ is equal to the binary sum of the measurement outcome $m$ in the noiseless case and the X error on system $S_3$, therefore, from Table III, we get (D10). Further, the prepared state $|q'_K\rangle_S$ is equal to the noiseless state $|q_K\rangle_S$, with some X and Z errors on it. The X (or Z) error on S is simply the concatenation of the total X (or Z) errors on systems $S_1$ and $S_2$. Therefore, from Table III, we get (D12), and (D13), for X and Z errors in $|q'_K\rangle_S$, respectively. □

We now combine the noisy preparation in Lemma 6 with the error detection gadget according to Procedure 2. We recall here how the error detection gadget works. Consider the error $e_X$ in the measurement outcome $m'$ in (D10) so that its syndrome is a zero vector, i.e.,

$$P_{\frac{K}{2}}(e_X)|_{Z(k-1)} = 0. \qquad (\text{D14})$$

Then the prepared state is accepted and the random vector $x$ in (D11) is estimated as

$$\hat{x} = P_{\frac{K}{2}}(m')|_{\mathcal{X}(k-1)}. \qquad (\text{D15})$$

The total error in the prepared state, with respect to the estimate $\hat{x}$, is given in Lemma 7.

**Lemma 7.** Consider the error $e_X$ in the measurement outcome $m$ from (D10), so that it satisfies (D14), and let $\hat{x}$ be defined according to (D15). Then, the state of the joint system S in (D11) can be written as follows, with respect to $\hat{x}$.

$$|q'_K\rangle_S = X e_X^f Z e_Z^f Q_K |(u', \hat{x}, u_2, \overline{v_1 \oplus v_2})\rangle_S, \qquad (\text{D16})$$

where $e_X^f = \tilde{e}_X + (e_X, 0)$ and $e_Z^f = \tilde{e}_Z$, so that $\tilde{e}_X$ and $\tilde{e}_Z$ are according to (D12) and (D13), respectively.

*Proof.* From (D3), (D10), and (D15), we have that

$$\hat{x} = x \oplus P_{\frac{K}{2}}(e_X)|_{\mathcal{X}(n-1)}. \qquad (\text{D17})$$

We may write $|q'_K\rangle_S$ in (D11), with respect to $\hat{x}$ as follows,

$$
\begin{align*}
|q'_K\rangle_S &= X^{\tilde{e}_X} Z^{\tilde{e}_Z} Q_K |(u', \mathbf{x}, \mathbf{u}_2, \overline{\mathbf{v}_1 \oplus \mathbf{v}_2})\rangle \\
&= X^{\tilde{e}_X} Z^{\tilde{e}_Z} \sum_{\mathbf{x}_2} (-1)^{(\mathbf{v}_1 \oplus \mathbf{v}_2) \cdot \mathbf{x}_2} \\
&= X^{\tilde{e}_X} Z^{\tilde{e}_Z} \sum_{\mathbf{x}_2} (-1)^{(\mathbf{v}_1 \oplus \mathbf{v}_2) \cdot \mathbf{x}_2} X^{(e_X, 0)} |P_K(u', \hat{\mathbf{x}}, \mathbf{u}_2, \mathbf{x}_2)\rangle \\
&= X^{\tilde{e}_X \oplus (e_X, 0)} Z^{\tilde{e}_Z} Q_K |(u', \hat{\mathbf{x}}, \mathbf{u}_2, \overline{\mathbf{v}_1 \oplus \mathbf{v}_2})\rangle, \tag{D18}
\end{align*}
$$

where in the second equality, we have expanded the quantum state in the Pauli Z basis and used (D17), and in the third equality, we have used $e_X = P_{\frac{K}{2}}(P_{\frac{K}{2}}(e_X)|_{Z(n-1)}, P_{\frac{K}{2}}(e_X)|_{\mathcal{X}(n-1)}) = P_{\frac{K}{2}}(0, P_{\frac{K}{2}}(e_X)|_{\mathcal{X}(n-1)}). \square$

**Case 2: Preparation Using Noisy Pauli X $\otimes$ X Measurements.**

The errors during the preparation with Pauli $X \otimes X$ measurements are given in Fig. 14. Note that we have Z type initialization and measurement errors on the ancilla system $S_3$, which are denoted by $e_Z^I, e_Z^m \in \{0, 1\}^{K/2}$, respectively. For the errors caused by the CNOT gates, $CNOT_{S_3 \to S_1}$ and $CNOT_{S_3 \to S_2}$, we have used the same notation as in the case of Pauli $Z \otimes Z$ measurements.

Here, we provide Lemmas 8 and 9, which are analogous to Lemmas 6 and 7, respectively, and thus their proofs have been omitted.

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

<figure><img src="image_20.png" /><figcaption>Fig. 14: Errors during preparation with Pauli $X \otimes X$ measurements.</figcaption></figure>
**Lemma 8.** The measurement outcome of transversal Pauli X ⊗ X measurements on systems S₁ and S₂, respectively in (D8) and (D9), is equal to

$$m' = m \oplus e_Z \in \{0, 1\}^{\frac{K}{2}}, \qquad (D19)$$

where m is the measurement outcome corresponding to the preparation without noise, as in (D6), and $e_Z = e_Z^I \oplus e_Z^1 \oplus e_Z^{C_1(3)} \oplus e_Z^2 \oplus e_Z^{C_2(3)} \oplus e_Z^m$. Further, after the measurement, we get,

$$|q'_K\rangle_S = X^{\tilde{e}_X} Z^{\tilde{e}_Z} |q_K\rangle_S, \qquad (D20)$$

where $|q_K\rangle_S$ is the prepared state without noise, as in (D7) and the errors are as follows,

$$\tilde{e}_X = (e_X^1 \oplus e_X^{C_1(1)}, e_X^2 \oplus e_X^{C_1(3)} \oplus e_X^{C_2(2)}) \in \{0, 1\}^K. \qquad (D21)$$

$$\tilde{e}_Z = (e_Z^1 \oplus e_Z^{C_1(1)}, e_Z^2 \oplus e_Z^{C_2(2)}) \in \{0, 1\}^K. \qquad (D22)$$

We now combine the noisy preparation in Lemma 8 with the error detection gadget according to Procedure 2. Recall that when no error is detected, the prepared state is accepted and the z in (D20) is estimated as

$$\hat{z} = P_{\frac{K}{2}}^{\top}(m')|_{Z(k-1)}. \qquad (D23)$$

**Lemma 9.** Consider the error $e_Z$ in the measurement outcome m from (D19), so that its syndrome is a zero vector, i.e., $P_{\frac{K}{2}}^{\top}(e_Z)|_{X(n-1)} = 0$, and let $\hat{z}$ be defined as in (D23). Then, the state of the joint system S in (D20) can be written as follows, with respect to $\hat{z}$.

$$|q'_K\rangle_S = X e_X^f Z \tilde{e}_Z^f Q_K |u_1 \oplus u_2, \overline{v_1}, \hat{z}, v'\rangle_S, \qquad (D24)$$

where $e_X^f = \tilde{e}_X$ and $e_Z^f = \tilde{e}_Z \oplus (0, e_Z)$, so that $\tilde{e}_X$ and $\tilde{e}_Z$ are according to (D12) and (D13), respectively, and $e_Z$ is the measurement error in (D19).

### Proof of Theorem 3

We provide a proof of Theorem 3, using the mathematical induction. The base case, i.e., the zeroth level of recursion, corresponds to the initialization of N qubits in a Pauli Z basis state. Let $T_0$ be the number of failures in initialization. As a failure in initialization produces only a single qubit X error, therefore, we have that $wt(e_X^f) = T_0$, for the error $e_X^f \in \{0, 1\}^N$ after the zeroth level of recursion. Hence, Theorem 3 holds for the zeroth level of recursion.

We show in Lemma 11 below that if Theorem 3 is true for the $(k-1)^{th}$, $1 \le k \le n$, level of recursion, it remains

true for the k'th level of recursion, therefore, implying that Theorem 3 holds for any $1 \le k \le n$.

Recall that at the k'th level of recursion, we prepare $2^{n-k}$ copies of $|q_K\rangle$, where each copy is prepared by applying transversal two-qubit Pauli measurements on two copies of $|q_{K/2}\rangle$. It is enough to show that Theorem 3 holds for a given preparation instance of $|q_K\rangle$. Hence, we consider $|q_{K/2}\rangle_{S_1}$ and $|q_{K/2}\rangle_{S_2}$ from (D8) and (D9), and for the sake of brevity, we suppose that Pauli Z ⊗ Z measurements are applied at the k'th level of recursion. Similar results to the ones that will be proven here can be obtained for the case of Pauli X ⊗ X measurements.

We suppose that $t_k$ component failures happen during the implementation of transversal Pauli Z ⊗ Z measurements on $S_1$ and $S_2$, using an ancilla system $S_3$ (see also Fig. 13). We decompose $t_k$ as follows,

$$t_k = t_k^I + t_k^{C_1} + t_k^{C_2} + t_k^M, \qquad (D25)$$

where $t_k^I$ is the number of failures during the initialization of $S_3$ in the Pauli Z basis, $t_k^{C_1}$ for $i \in \{1, 2\}$ is the number of CNOT failures in $CNOT_{S_i \to S_3}$, and $t_k^M$ is the number of failures during the Pauli Z measurement on $S_3$. To relate with Fig. 13, note that the errors $e_X^I$ and $e_X^M$ are produced by $t_k^I$ and $t_k^M$-faults, respectively. Further, the errors $e_X^{C_1(1)}, e_X^{C_1(3)}, e_Z^{C_1(1)}, e_Z^{C_1(3)}$ are produced by $t_k^{C_1}$-faults, and finally the errors $e_X^{C_2(2)}, e_X^{C_2(3)}, e_Z^{C_2(2)}, e_Z^{C_2(3)}$ are produced by $t_k^{C_2}$-faults.

We will also need the following notation:

(i) For $i \in \{1, 2\}$, let $t_k^{C_i}(X)$ be the number of CNOT failures in $CNOT_{S_i \to S_3}$ that produce a single qubit X error on the corresponding outputs, i.e., the number of CNOT failures, where one of the following errors $X \otimes I, X \otimes Z, I \otimes X, Z \otimes X, Y \otimes I, Y \otimes I, Y \otimes Z, I \otimes Y, Z \otimes Y$ is produced. Similarly, let $t_k^{C_i}(Z)$ be the number of CNOT failures in $CNOT_{S_i \to S_3}$ that produce a single qubit Z error.

(ii) For $i \in \{1, 2\}$, let $t_k^{C_i}(XX)$ be the number of CNOT failures in $CNOT_{S_i \to S_3}$ that produce a two qubit X error, i.e., the number of CNOT failures, where one of the following errors $X \otimes X, X \otimes Y, Y \otimes X, Y \otimes Y$ is produced. Similarly, let $t_k^{C_i}(ZZ)$ be the number of CNOT failures in $CNOT_{S_i \to S_3}$ that produce a two qubit Z error.

Note that the following inequalities hold trivially for $i \in \{1, 2\}$,

$$t_k^{C_i}(X) + t_k^{C_i}(XX) \le t_k^{C_i}. \qquad (D26)$$

$$t_k^{C_i}(Z) + t_k^{C_i}(ZZ) \le t_k^{C_i}. \qquad (D27)$$
**Lemma 8.** The measurement outcome of transversal Pauli X ⊗ X measurements on systems S₁ and S₂, respectively in (D8) and (D9), is equal to

$$m' = m \oplus e_Z \in \{0, 1\}^{\frac{K}{2}}, \qquad (D19)$$

where m is the measurement outcome corresponding to the preparation without noise, as in (D6), and $e_Z = e_Z^I \oplus e_Z^1 \oplus e_Z^{C_1(3)} \oplus e_Z^2 \oplus e_Z^{C_2(3)} \oplus e_Z^m$. Further, after the measurement, we get,

$$|q'_K\rangle_S = X^{\tilde{e}_X} Z^{\tilde{e}_Z} |q_K\rangle_S, \qquad (D20)$$

where $|q_K\rangle_S$ is the prepared state without noise, as in (D7) and the errors are as follows,

$$\tilde{e}_X = (e_X^1 \oplus e_X^{C_1(1)}, e_X^2 \oplus e_X^{C_1(3)} \oplus e_X^{C_2(2)}) \in \{0, 1\}^K. \qquad (D21)$$

$$\tilde{e}_Z = (e_Z^1 \oplus e_Z^{C_1(1)}, e_Z^2 \oplus e_Z^{C_2(2)}) \in \{0, 1\}^K. \qquad (D22)$$

We now combine the noisy preparation in Lemma 8 with the error detection gadget according to Procedure 2. Recall that when no error is detected, the prepared state is accepted and the z in (D20) is estimated as

$$\hat{z} = P_{\frac{K}{2}}^{\top}(m')|_{Z(k-1)}. \qquad (D23)$$

**Lemma 9.** Consider the error $e_Z$ in the measurement outcome m from (D19), so that its syndrome is a zero vector, i.e., $P_{\frac{K}{2}}^{\top}(e_Z)|_{X(n-1)} = 0$, and let $\hat{z}$ be defined as in (D23). Then, the state of the joint system S in (D20) can be written as follows, with respect to $\hat{z}$.

$$|q'_K\rangle_S = X e_X^f Z \tilde{e}_Z^f Q_K |u_1 \oplus u_2, \overline{v_1}, \hat{z}, v'\rangle_S, \qquad (D24)$$

where $e_X^f = \tilde{e}_X$ and $e_Z^f = \tilde{e}_Z \oplus (0, e_Z)$, so that $\tilde{e}_X$ and $\tilde{e}_Z$ are according to (D12) and (D13), respectively, and $e_Z$ is the measurement error in (D19).

### Proof of Theorem 3

We provide a proof of Theorem 3, using the mathematical induction. The base case, i.e., the zeroth level of recursion, corresponds to the initialization of N qubits in a Pauli Z basis state. Let $T_0$ be the number of failures in initialization. As a failure in initialization produces only a single qubit X error, therefore, we have that $wt(e_X^f) = T_0$, for the error $e_X^f \in \{0, 1\}^N$ after the zeroth level of recursion. Hence, Theorem 3 holds for the zeroth level of recursion.

We show in Lemma 11 below that if Theorem 3 is true for the $(k-1)^{th}$, $1 \le k \le n$, level of recursion, it remains

true for the k'th level of recursion, therefore, implying that Theorem 3 holds for any $1 \le k \le n$.

Recall that at the k'th level of recursion, we prepare $2^{n-k}$ copies of $|q_K\rangle$, where each copy is prepared by applying transversal two-qubit Pauli measurements on two copies of $|q_{K/2}\rangle$. It is enough to show that Theorem 3 holds for a given preparation instance of $|q_K\rangle$. Hence, we consider $|q_{K/2}\rangle_{S_1}$ and $|q_{K/2}\rangle_{S_2}$ from (D8) and (D9), and for the sake of brevity, we suppose that Pauli Z ⊗ Z measurements are applied at the k'th level of recursion. Similar results to the ones that will be proven here can be obtained for the case of Pauli X ⊗ X measurements.

We suppose that $t_k$ component failures happen during the implementation of transversal Pauli Z ⊗ Z measurements on $S_1$ and $S_2$, using an ancilla system $S_3$ (see also Fig. 13). We decompose $t_k$ as follows,

$$t_k = t_k^I + t_k^{C_1} + t_k^{C_2} + t_k^M, \qquad (D25)$$

where $t_k^I$ is the number of failures during the initialization of $S_3$ in the Pauli Z basis, $t_k^{C_1}$ for $i \in \{1, 2\}$ is the number of CNOT failures in $CNOT_{S_i \to S_3}$, and $t_k^M$ is the number of failures during the Pauli Z measurement on $S_3$. To relate with Fig. 13, note that the errors $e_X^I$ and $e_X^M$ are produced by $t_k^I$ and $t_k^M$-faults, respectively. Further, the errors $e_X^{C_1(1)}, e_X^{C_1(3)}, e_Z^{C_1(1)}, e_Z^{C_1(3)}$ are produced by $t_k^{C_1}$-faults, and finally the errors $e_X^{C_2(2)}, e_X^{C_2(3)}, e_Z^{C_2(2)}, e_Z^{C_2(3)}$ are produced by $t_k^{C_2}$-faults.

We will also need the following notation:

(i) For $i \in \{1, 2\}$, let $t_k^{C_i}(X)$ be the number of CNOT failures in $CNOT_{S_i \to S_3}$ that produce a single qubit X error on the corresponding outputs, i.e., the number of CNOT failures, where one of the following errors $X \otimes I, X \otimes Z, I \otimes X, Z \otimes X, Y \otimes I, Y \otimes I, Y \otimes Z, I \otimes Y, Z \otimes Y$ is produced. Similarly, let $t_k^{C_i}(Z)$ be the number of CNOT failures in $CNOT_{S_i \to S_3}$ that produce a single qubit Z error.

(ii) For $i \in \{1, 2\}$, let $t_k^{C_i}(XX)$ be the number of CNOT failures in $CNOT_{S_i \to S_3}$ that produce a two qubit X error, i.e., the number of CNOT failures, where one of the following errors $X \otimes X, X \otimes Y, Y \otimes X, Y \otimes Y$ is produced. Similarly, let $t_k^{C_i}(ZZ)$ be the number of CNOT failures in $CNOT_{S_i \to S_3}$ that produce a two qubit Z error.

Note that the following inequalities hold trivially for $i \in \{1, 2\}$,

$$t_k^{C_i}(X) + t_k^{C_i}(XX) \le t_k^{C_i}. \qquad (D26)$$

$$t_k^{C_i}(Z) + t_k^{C_i}(ZZ) \le t_k^{C_i}. \qquad (D27)$$