# Capacities of quantum Markovian noise for large times

Omar Fawzi, Mizanur Rahaman, Mostafa Taheri

► To cite this version:

Omar Fawzi, Mizanur Rahaman, Mostafa Taheri. Capacities of quantum Markovian noise for large times. 2024. hal-04836984

HAL Id: hal-04836984

https://inria.hal.science/hal-04836984v1

Preprint submitted on 13 Dec 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
# Capacities of quantum Markovian noise for large times

Omar Fawzi¹, Mizanur Rahaman¹, and Mostafa Taheri¹

¹Univ Lyon, Inria, ENS Lyon, UCBL, LIP, Lyon, France

August 2, 2024

## Abstract

Given a quantum Markovian noise model, we study the maximum dimension of a classical or quantum system that can be stored for arbitrarily large time. We show that, unlike the fixed time setting, in the limit of infinite time, the classical and quantum capacities are characterized by efficiently computable properties of the peripheral spectrum of the quantum channel. In addition, the capacities are additive under tensor product, which implies in the language of Shannon theory that the one-shot and the asymptotic i.i.d. capacities are the same. We also provide an improved algorithm for computing the structure of the peripheral subspace of a quantum channel, which might be of independent interest.

# 1 Introduction

Consider a quantum system that we would like to use for storing quantum or classical information. This system is affected by noise that we assume is Markovian. It is natural to ask what is the minimum error that can be achieved for storing log $D$ (qu)bits of information for some fixed time $t$. This is a typical question studied in Shannon theory, but here we focus on the limit $t \to \infty$, i.e., the information should remain in the system for arbitrarily long times.

Building a quantum system able to store quantum information for large times is one of the important goals of quantum information theory and it has been studied from different angles. Quantum error correction gives a mechanism to actively preserve the quantum information in a system undergoing local noise [19]. Such methods can achieve much more than a memory and can be used for fault-tolerant quantum computation [8]. A related important area of research is the study of self-correcting (or passive) quantum memories [4], i.e., physical systems that are robust to different forms of imperfections including thermal noise.
In this paper, we study the question of quantum memory from an abstract Shannon theory perspective where given a noise model, the objective is to characterize the fundamental limits that can be achieved without placing computational restrictions on the encoding/decoding operations. As an example, we would like to characterize how many qubits can be stored reliably for time t as a function of the noise model and t? Such questions were studied in the recent work [15] and they obtained, among other results about scrambling, conditions for the classical capacity to be zero as well as lower bounds on the classical capacity of ergodic channels.

**Our results** In this work, we focus on the setting of arbitrarily large time, i.e., $t \to \infty$ and we characterize both the classical and quantum capacities for a fixed error $\delta$ in terms of the peripheral spectrum of the noise model (Theorem 2.1). In addition, we show that such capacities are additive for the tensor product of channels (Theorem 3.1) and can be computed in polynomial-time in the dimension (Theorem 4.1). This algorithm for computing the structure of the peripheral subspace (or the fixed point subspace) of a quantum channel improves on previous works and might of independent interest. We note that the fact that we can efficiently characterize the infinite-time capacities of noisy channels is in contrast with other settings for which capacities or optimal success probabilities correspond to hard problems, such as maximum independent set [14] or maximum coverage problems [2].

## 2 Capacities of quantum noise models

For a Hilbert space $H$, we use the notation $B(H)$ for the bounded linear operators on $H$. When we do not need to make the Hilbert space explicit and when it has dimension $d$, we denote the algebra of linear operators (or $d \times d$ complex matrices) by $M_d(\mathbb{C})$ or simply $M_d$ for short. We recall that a quantum channel $\mathcal{E}: M_D(\mathbb{C}) \to M_d(\mathbb{C})$ is a completely positive and trace preserving linear map. We refer to [21] for more detailed definitions and properties of quantum channels.

We start with the standard definition of an error correcting code for a noisy quantum channel $\mathcal{T}$. Note that throughout the paper $d \ge 1$ is an integer and $\mathcal{T}$ is a quantum channel from $M_d(\mathbb{C})$ to $M_d(\mathbb{C})$.

**Definition 2.1 (Classical and quantum codes).** A quantum channel $\mathcal{E}: M_D(\mathbb{C}) \to M_d(\mathbb{C})$ is a $(D, \delta)$ classical code for a channel $\mathcal{T}: M_d(\mathbb{C}) \to M_d(\mathbb{C})$ if there exists a recovery channel $\mathcal{R}: M_d(\mathbb{C}) \to M_D(\mathbb{C})$ such that the average fidelity of the channel $\mathcal{R} \circ \mathcal{T} \circ \mathcal{E}$ over all diagonal density matrices in $M_D$ is at least $1 - \delta$, i.e.,

$$ \frac{1}{D} \sum_{i=1}^{D} \langle i | \mathcal{R} \circ \mathcal{T} \circ \mathcal{E} ( |i\rangle \langle i| ) |i\rangle \ge 1 - \delta, \quad (1) $$
where $\{|i\rangle\}_{i=1}^D$ is a fixed orthonormal basis of $\mathbb{C}^D$. We say that $\mathcal{E}$ is a $(D, \delta)$ quantum code if there exist channel $\mathcal{R}$ such that the entanglement fidelity of $\mathcal{R} \circ \mathcal{T} \circ \mathcal{E}$ is at least $1 - \delta$, i.e.,

$$F_E(\mathcal{R} \circ \mathcal{T} \circ \mathcal{E}) = \langle \Phi^+ | (\mathcal{I} \otimes (\mathcal{R} \circ \mathcal{T} \circ \mathcal{E})) (|\Phi^+\rangle\langle\Phi^+|) |\Phi^+\rangle \geq 1 - \delta, \quad (2)$$

where $|\Phi^+\rangle = \frac{1}{\sqrt{D}} \sum_{i=1}^D |i\rangle \otimes |i\rangle \in (\mathbb{C}^D)^{\otimes 2}$ and $\mathcal{I}$ is the identity quantum channel on the reference system of dimension $D$.

Then, we introduce the capacity as the dimension of the largest code for the channel $\mathcal{T}$ for a fixed error parameter $\delta$.

**Definition 2.2 (Capacity).** The (one-shot) classical capacity for a channel $\mathcal{T}$ is defined as

$$C_{\delta}(\mathcal{T}) = \sup_{\mathcal{E}} \log D,$$

where the supremum is over all possible $(D, \delta)$ classical codes $\mathcal{E}$ for $\mathcal{T}$. Similarly, the (one-shot) quantum capacity for the channel $\mathcal{T}$ is defined as

$$Q_{\delta}(\mathcal{T}) = \sup_{\mathcal{E}} \log D,$$

where the supremum is taken over all possible $(D, \delta)$ quantum codes.

We now see $\mathcal{T}$ as the noise that is applied for one time unit. Thus, by the Markov assumption, after $t$ time steps, the noise that is applied to the system is given by composing $\mathcal{T}$ $t$ times, which we denote by $\mathcal{T}^t = \mathcal{T} \circ \dots \circ \mathcal{T}$. As mentioned in the introduction, in this paper, we are interested in the limit of large time $t$, which motivates the following definition.

**Definition 2.3.** The infinite-time classical or quantum capacity of a quantum channel $\mathcal{T}$ is defined as

$$C_{\delta}^{\infty}(\mathcal{T}) = \lim_{t \to \infty} C_{\delta}(\mathcal{T}^t) \quad \text{and} \quad Q_{\delta}^{\infty}(\mathcal{T}) = \lim_{t \to \infty} Q_{\delta}(\mathcal{T}^t).$$

We make a few remarks about this definition.

*Remark 2.1.* In this definition, the encoding could in principle depend on the time $t$. However, all the achievability results (i.e., lower bounds of the capacities) we obtain, the same encoder $\mathcal{E}$ works for $\mathcal{T}^t$ for all times $t \geq 1$. In contrast, it is important for the results to hold that the recovery channel $\mathcal{R}$ does depend on the time $t$.

*Remark 2.2.* This definition is concerned about passive error correction where no recovery is allowed at regular intervals. One could define an active capacity as follows:

$$Q_{\delta}^{\text{active},t}(\mathcal{T}) = \log\{\max D : \exists \mathcal{E}, \mathcal{R}_1, \dots, \mathcal{R}_t \text{ s.t. } F_E(\mathcal{R}_t \circ \mathcal{T} \circ \dots \circ \mathcal{T} \circ \mathcal{R}_1 \circ \mathcal{T} \circ \mathcal{E}) \geq 1 - \delta\},$$

where $\mathcal{E}: \mathcal{M}_D \to \mathcal{M}_d$ and $\mathcal{R}_i: \mathcal{M}_d \to \mathcal{M}_d$ for $1 \leq i \leq t-1$ and $\mathcal{R}_t: \mathcal{M}_d \to \mathcal{M}_D$ are quantum channels. Note that the active capacity can be larger than the passive one; in
particular, it is simple to see that for any $t \ge 1$, $Q_0^{\text{active},t}(\mathcal{T}) = Q_0(\mathcal{T})$ by choosing the recovery maps $\mathcal{R}_i$ to decode and re-encode information. The works [13, 6] have studied some Shannon-theoretic aspects of active error correction.

*Remark 2.3.* Note that in general $\mathcal{T}^t$ does not have a limit as $t \to \infty$, but for the capacities $C_\delta(\mathcal{T}^t)$ and $Q_\delta(\mathcal{T}^t)$, the limits exist as they are nonnegative nonincreasing sequences.

The characterization of both the classical and quantum capacities will be in terms of the peripheral subspace $\chi_T$ of the quantum channel $\mathcal{T}$. The following proposition summarizes the definition and key properties about the peripheral subspace that will be used in this paper. A proof of these statements and more properties can be found in [21, Section 6.5].

**Proposition 2.1.** The peripheral subspace of a quantum channel $\mathcal{T}$ is defined by

$$ \chi_T = \operatorname{span}\{X \in \mathcal{M}_d(\mathbb{C}) : \mathcal{T}(X) = \lambda X, \text{ for some } |\lambda| = 1\}. $$

It satisfies the following:

* There exists a direct sum decomposition of the Hilbert space $\mathbb{C}^d = H_0 \oplus \bigoplus_{k=1}^K (H_{k,1} \otimes H_{k,2})$ for some nonnegative integer $K$ such that

$$ \chi_T = 0 \oplus \bigoplus_{k=1}^{K} \mathcal{M}_{d_k}(\mathbb{C}) \otimes \omega_k, \qquad (3) $$

where $\mathcal{M}_{d_k}(\mathbb{C})$ is the full matrix algebra on $H_{k,1}$, with $d_k = \dim H_{k,1}$, and $\omega_k$ is a density operator on $H_{k,2}$.

* There exists unitaries $U_k$ acting on $H_{k,1}$ and a permutation $\pi$ which permutes systems $\{1, \dots, K\}$ having the same dimension such that for every $X \in \chi_T$ of the form $X = 0 \oplus \bigoplus_{k=1}^K x_k \otimes \omega_k$, we have

$$ \mathcal{T}(X) = 0 \oplus \bigoplus_{k=1}^{K} U_k x_{\pi^{-1}(k)} U_k^{\dagger} \otimes \omega_k. $$

We are now ready to state our main theorem.

**Theorem 2.1.** Let $\mathcal{T}: \mathcal{M}_d \to \mathcal{M}_d$ be a quantum channel and let $K$ and $\{d_k\}_{k=1}^K$ be the integers from the peripheral subspace decomposition in (3).

For any $\delta \in [0, 1)$, the infinite time classical capacity of $\mathcal{T}$ is given by

$$ C_{\delta}^{\infty}(\mathcal{T}) = \log \left( \left\lfloor \frac{\sum_k d_k}{1 - \delta} \right\rfloor \right), \qquad (4) $$

and the quantum capacity can be bounded as

$$ \log \left( \left\lfloor \frac{\max_k d_k}{\sqrt{1 - \delta}} \right\rfloor \right) \le Q_{\delta}^{\infty}(\mathcal{T}) \le \log(\max_k d_k) + \log \left( \frac{1}{1 - \delta} \right). \qquad (5) $$

In addition, as shown in Theorem 4.1 below, the values $\{d_k\}_k$ determining the structure of $\chi_T$ can be computed in time polynomial in $d$ given the description of $\mathcal{T}$.
We note that, in independent work, the special case $\delta = 0$ of (4) and (5) were proved in [16]. Before proving the Theorem, we make a few remarks.

**Remark 2.4.** For the quantum capacity, we do not have an exact expression for the capacity but upper and lower bounds that differ by roughly $\frac{1}{2}\log(1 - \delta)$. The upper and lower bounds we establish in the proof is slightly stronger and it is simpler to express in terms of the optimal error $\delta$ for a fixed code size $D$:

$$ \max_{(\gamma_k)_k} \frac{\sum_{k=1}^K \gamma_k^2}{D^2} \le \sup\{1 - \delta : \exists (D, \delta) \text{ quantum code for } \mathcal{T}\} \le \max_{(\gamma_k)_k} \frac{\sum_{k=1}^K d_k \gamma_k}{D^2} \quad (6) $$

where the supremum is taken over integers $\gamma_k$ satisfying $\gamma_k \le d_k$ and $\sum_{k=1}^K \gamma_k \le D$. Note that it is simple to see that the optimal choice for $\gamma_k$ is simply to take $\gamma_1 = d_1, \dots, \gamma_s = d_s$ and $\gamma_{s+1} = D - \sum_{k=1}^s \gamma_k$ where $s = \arg\max\{s : \sum_{k=1}^s d_k < D\}$. When $D$ is the sum of the largest $r$ elements of $(d_k)_k$, then the upper and lower bounds match and we obtain an exact characterization. Observe that (5) follows from (6) by observing that $\max_{(\gamma_k)_k} \sum_{k=1}^K \gamma_k^2 \ge \min(D^2, \max_k d_k^2)$ and $\sum_{k=1}^K d_k \gamma_k \le (\max_k d_k)D$. We leave the problem of computing the exact optimal fidelity as an open problem.

**Remark 2.5 (Classical special case).** Note that a classical stochastic $d \times d$ matrix $M$ can be seen as a special case of a quantum channel $\mathcal{T}(|i\rangle\langle i'|) = 0$ if $i \ne i'$ and $\mathcal{T}(|i\rangle\langle i|) = \sum_j M_{j,i}|j\rangle\langle j|$. It is straightforward to verify that the eigenvalues of $M$ are the eigenvalues of $\mathcal{T}$ and that the quantity $\sum_{k=1}^K d_k$ for such a channel is the number of eigenvalues of $M$ of modulus 1 counted with multiplicity or the dimension of the peripheral subspace. This quantity even has a combinatorial interpretation as the sum of the periods of the bottom strongly connected components of the directed graph associated with the Markov chain $M$, as shown in [9]. Note that this combinatorial interpretation holds more generally for nonnegative matrices and such a decomposition into bottom strongly connected components is sometimes called the Frobenius normal form of the matrix [1, Section 1.7], see also e.g., in [11, Theorem 8.5.3 and Remark 8.5.4] for the period of each component. Using the combinatorial interpretation, one can find an algorithm running in linear time in the size of the graph for computing the capacity by using e.g., Tarjan's algorithm [18] to find the bottom strongly connected components and then find the periods of each component using [5].

**Proof.** We start with the achievability statement, i.e., lower bounds on the capacities. Using the decomposition of the space in Proposition 2.1, $\mathbb{C}^d = H_0 \oplus \bigoplus_{k=1}^K (H_{k,1} \otimes H_{k,2})$, let $\{|e_{k,j}\rangle\}_{j=1}^{d_k}$ be orthonormal bases of $H_{k,1}$. For different $H_{k,1}$ having the same dimension, we will identify the orthonormal bases.

We define the classical code $\mathcal{E}$ as follows. Let $\sigma : \{1, \dots, \sum_{k=1}^K d_k\} \to \{(k, j) : k \in \{1, \dots, K\}, j \in \{1, \dots, d_k\}\}$ be an arbitrary bijection, then

$$ \mathcal{E}(|i\rangle\langle i|) = \begin{cases} |e_{\sigma(i)}\rangle\langle e_{\sigma(i)}| \otimes \omega_k & \text{if } 1 \le i \le \sum_{k=1}^K d_k \\ |e_1\rangle\langle e_1| \otimes \omega_k & \text{if } \sum_{k=1}^K d_k < i \le D. \end{cases} $$
For $1 \le i \le \sum_{k=1}^K d_k$, we have $\mathcal{E}(|i\rangle\langle i|) = |e_{k,j}\rangle\langle e_{k,j}| \otimes \omega_k \in B(H_{k,1} \otimes H_{k,2})$ with $(k, j) = \sigma(i)$. As a result, applying $\mathcal{T}$, we get

$$ \mathcal{T}(\mathcal{E}(|i\rangle\langle i|)) = U_{\pi(k)}|e_{k,j}\rangle\langle e_{k,j}| \otimes \omega_{\pi(k)} U_{\pi(k)} \in B(H_{\pi(k),1} \otimes H_{\pi(k),2}), $$

using Proposition 2.1. Composing $t$ times the map $\mathcal{T}$, we get

$$ \mathcal{T}^t(\mathcal{E}(|i\rangle\langle i|)) = U_{\pi^t(k)} \cdots U_{\pi(k)} |e_{k,j}\rangle\langle e_{k,j}| U_{\pi^t(k)}^\dagger \cdots U_{\pi^t(k)}^\dagger \otimes \omega_{\pi^t(k)} \in B(H_{\pi^t(k),1} \otimes H_{\pi^t(k),2}). $$

Note that we always have $\mathcal{T}^t(\mathcal{E}(|i\rangle\langle i|)) \in \chi_{\mathcal{T}}$. For a time $t$, we choose a recovery map $\mathcal{R}$ defined by

$$ \mathcal{R}(X) = \sum_{k=1}^{K} V_k U_{\pi(k)}^{\dagger} \cdots U_{\pi^t(k)}^{\dagger} \mathrm{tr}_{H_{\pi^t(k),2}} (P_{\pi^t(k)} X P_{\pi^t(k)}) U_{\pi^t(k)} \cdots U_{\pi(k)} V_k^{\dagger}, $$

where $P_k$ is the orthogonal projection onto $H_{k,1} \otimes H_{k,2}$ and $V_k = \sum_{j=1}^{d_k} |\sigma^{-1}(k, j)\rangle\langle e_{k,j}|$. Clearly, an error occurs only if $i > \sum_{k=1}^K d_k$ and as such the success probability is given by

$$ \frac{1}{D} \sum_{i=1}^{D} \langle i | \mathcal{R} \circ \mathcal{T}^t \circ \mathcal{E}(|i\rangle\langle i|) | i \rangle = \min\left(1, \frac{\sum_{k=1}^{D} d_k}{D}\right). $$

As a result, if we choose $D = \left\lceil \frac{\sum_{k=1}^K d_k}{1-\delta} \right\rceil$, we obtain the desired achievability.

Now let us construct a quantum code of dimension $D$ satisfying the condition $\max_{(\gamma_k)_k} \left\{ \frac{\sum_{k=1}^K \gamma_k^2}{D^2} \right\} \ge 1 - \delta$. Let $\gamma_k$ achieve the maximum. It is convenient to label the basis of $\mathbb{C}^D$ by elements in $S \cup S'$, where $S = \{(k, j) : k \in \{1, \dots, K\}, j = 1 \in \{1, \dots, \gamma_k\}\}$ and $S' = \{1, \dots, D - \sum_{k=1}^K \gamma_k\}$. By the condition $\sum_{k=1}^K \gamma_k \le D$, the set $S$ is of size at most $D$.

In order to define our encoding map $\mathcal{E}$, we first define the Kraus operators $E_k = \sum_{j=1}^{\gamma_k} |e_{k,j}\rangle\langle(k, j)|$ for $k=1$ to $K$, and $F_i = |e_{(1,1)}\rangle\langle i|$ for $i \in S'$. Then for $X \in \mathcal{M}_D(\mathbb{C})$ we define $\mathcal{E}(X) = \sum_{k=1}^K (E_k X E_k^\dagger) \otimes \omega_k + \sum_{i \in S'} F_i X F_i^\dagger \otimes \omega_1$. As a result, we have

$$ \mathcal{E}(|(k, j)\rangle\langle(k, j')|) = |e_{k,j}\rangle\langle e_{k,j'}| \otimes \omega_k, $$

and $\mathcal{E}(|(k, j)\rangle\langle(k', j')|) = 0$ for $k \ne k'$. For $i, i' \in S'$ we get

$$ \mathcal{E}(|(k, j)\rangle\langle i|) = 0, $$

$$ \mathcal{E}(|i\rangle\langle i|) = |e_{1,1}\rangle\langle e_{1,1}| \otimes \omega_1 \quad \text{and} \quad \mathcal{E}(|i\rangle\langle i'|) = 0 \text{ for } i \ne i' $$

Thus, applying $\mathcal{T}^t$, we get

$$ (\mathcal{T}^t \circ \mathcal{E})(|(k, j)\rangle\langle(k, j')|) = U_{\pi^t(k)} \cdots U_{\pi(k)} |e_{k,j}\rangle\langle e_{k,j'}| U_{\pi^t(k)}^\dagger \cdots U_{\pi^t(k)}^\dagger \otimes \omega_{\pi^t(k)}. $$
Note that $\mathcal{T}^t \circ \mathcal{E}(|(k, j)\rangle\langle(k', j')|) \in \chi_{\mathcal{T}}$. We choose $\mathcal{R}$ as

$$ \mathcal{R}(X) = \sum_{k=1}^{K} V_k U_{\pi(k)}^{\dagger} \cdots U_{\pi^{t(k)}}^{\dagger} \mathrm{tr}_{H_{\pi^{t(k)},2}} (P_{\pi^{t(k)}} X P_{\pi^{t(k)}}) U_{\pi^{t(k)}} \cdots U_{\pi(k)} V_k^{\dagger}, $$

where $P_k$ is the orthogonal projection onto $H_{k,1} \otimes H_{k,2}$ and $V_k = \sum_{j=1}^{\gamma_k} |(k, j)\rangle\langle e_{k,j}|$.

Then we can compute the entanglement fidelity as

$$ \begin{aligned} & \langle \Phi^+ | (\mathcal{I} \otimes \mathcal{R} \circ \mathcal{T}^t \circ \mathcal{E}) (|\Phi^+\rangle\langle\Phi^+|) |\Phi^+\rangle \\ & \geq \frac{1}{D^2} \sum_{(k,j),(k',j') \in S} \langle (k,j) | \mathcal{R} \circ \mathcal{T}^t \circ \mathcal{E} (|(k,j)\rangle\langle(k',j')|) | (k',j') \rangle \\ & = \frac{1}{D^2} \sum_{k=1}^{K} \sum_{j,j'=1}^{\gamma_k} 1 \\ & = \frac{\sum_{k=1}^{K} \gamma_k^2}{D^2} \\ & \geq 1 - \gamma, \end{aligned} $$

which proves the desired result.

We now move to the converse bound. For this, it is convenient to consider the peripheral projection channel $\mathcal{T}_P$ [21, Proposition 6.3] which satisfies the following properties: [21]

* $\mathcal{T}_P(\mathcal{M}_d) = \chi_{\mathcal{T}}$

* there exist an increasing sequence $\{t_i\}$ such that $\lim_{i \to \infty} \mathcal{T}^{t_i} = \mathcal{T}_P$

* $\mathcal{T}_P(X) = X$ for any $X \in \chi_{\mathcal{T}}$.

Note that if $\mathcal{E}$ is a $(D, \delta)$ code for $\mathcal{T}$, and $\|\mathcal{T} - \mathcal{T}'\|_{\diamond} \leq \eta$, where the diamond norm is defined as $\|\mathcal{T} - \mathcal{T}'\|_{\diamond} = \sup_{\rho} \|(\mathcal{I} \otimes (\mathcal{T} - \mathcal{T}'))(\rho)\|_1$, then $\mathcal{E}$ is also a $(D, \delta + \eta)$ code for $\mathcal{T}'$.

Consider a sequence $t_i$ such that $\lim_{i \to \infty} \mathcal{T}^{t_i} = \mathcal{T}_P$ and let $\eta_i = \|\mathcal{T}^{t_i} - \mathcal{T}_P\|_{\diamond}$. Let $\mathcal{E}_i$ be a $(D, \delta)$ code for the channel $\mathcal{T}^{t_i}$. Then $\mathcal{E}_i$ is also a $(D, \delta + \eta_i)$ code for the channel $\mathcal{T}_P$. Thus $C_{\delta}(\mathcal{T}^{t_i}) \leq C_{\delta+\eta_i}(\mathcal{T}_P)$. Taking the limit $i \to \infty$, we have that $\sup_{\delta' < \delta} C_{\delta'}(\mathcal{T}_P) \leq C_{\delta}^{\infty}(\mathcal{T}) \leq \inf_{\delta' > \delta} C_{\delta'}(\mathcal{T}_P)$. The exact same result holds for the quantum capacity as well. It now suffices to find upper bounds on the capacities of the channel $\mathcal{T}_P$.

First, let us show that the classical and quantum capacities of $\mathcal{T}_P$ and $\sum_{k=0}^K A_k \circ \mathcal{T}_P$ are the same, where we define $A_k$ as follows. Define $P_0$ to be the orthogonal projector onto $H_0$ and $A_0(X) = P_0XP_0$. Then define $P_k$ to be the orthogonal projector onto $H_{k,1} \otimes H_{k,2}$ and $A_k : B(\mathbb{C}^d) \to B(H_{k,1})$ by $A_k(X) = \mathrm{tr}_{H_{k,2}}(P_kXP_k)$. Then $\sum_{k=0}^K A_k \circ \mathcal{T}_P$ is clearly a quantum channel. As $\mathcal{T}_P(\mathcal{M}_d) = \chi_{\mathcal{T}}$, $\sum_{k=0}^K A_k \circ \mathcal{T}_P = \sum_{k=1}^K A_k \circ \mathcal{T}_P$ so $\sum_{k=1}^K A_k \circ \mathcal{T}_P$ is a quantum channel mapping $B(\mathbb{C}^d)$ to $\bigoplus_{k=1}^K B(H_{k,1})$. The inequality $C_{\delta}(\sum_{k=1}^K A_k \circ \mathcal{T}_P) \leq C_{\delta}(\mathcal{T}_P)$ is clear. For the other inequality, let $\mathcal{E}$ be a code for $\mathcal{T}_P$ and
$\mathcal{R}$ be a corresponding recovery map. We define the recovery map $\mathcal{R}' = \sum_{k=1}^{K} \mathcal{R} \circ \mathcal{B}_k$ where $\mathcal{B}_k : B(H_{k,1}) \to B(H_{k,1} \otimes H_{k,2})$ and maps $\mathcal{B}_k(x_k) = x_k \otimes \omega_k$. It is easy to see that

$$ \mathcal{R}' \circ \sum_{k=1}^{K} \mathcal{A}_k \circ \mathcal{T}_P \circ \mathcal{E} = \mathcal{R} \circ \mathcal{T}_P \circ \mathcal{E}, $$

which proves the desired statement. For this reason, in what follows, we assume that $\dim H_0 = 0$ and $\dim H_{k,2} = 1$ and the space decomposes as $\mathbb{C}^d = \bigoplus_{k=1}^{K} H_{k,1}$.

Let $\mathcal{E}$ be a $(D, \delta)$ classical code for $\mathcal{T}_P$ and $\mathcal{R}$ a corresponding recovery channel. Note that because $\mathcal{T}_P(\mathcal{M}_d) = \chi_{\mathcal{T}}$, for any density operator $\rho \in B(\mathbb{C}^d)$, there exists positive operators $\rho_k$ on $H_{k,1}$, $\mathcal{T}_P(\rho) = \bigoplus_{k=1}^{K} \rho_k$. In addition, as $\mathcal{T}_P$ is trace-preserving $\sum_k \mathrm{tr}(\rho_k) = 1$ and $\rho_k \le I_{H_{k,1}}$, where $I_{H_{k,1}}$ is the identity on $H_{k,1}$. As a result, $\mathcal{T}_P(\rho) \le \bigoplus_{k=1}^{K} I_{H_{k,1}}$. Thus,

$$ \begin{aligned} \frac{1}{D} \sum_{i=1}^{D} \langle i | \mathcal{R} \circ \mathcal{T}_P \circ \mathcal{E} (|i\rangle\langle i|) |i\rangle &\le \frac{1}{D} \sum_{i=1}^{D} \langle i | \mathcal{R} \left( \bigoplus_{k=1}^{K} I_{H_{k,1}} \right) |i\rangle \\ &= \frac{1}{D} \mathrm{tr} \left( \bigoplus_{k=1}^{K} I_{H_{k,1}} \right) \\ &= \frac{\sum_{k=1}^{K} d_k}{D}. \end{aligned} $$

Thus, for any $(D, \delta)$ code, we should have $\frac{\sum_{k=1}^{K} d_k}{D} \ge 1 - \delta$ which implies $D \le \left\lfloor \frac{\sum_{k=1}^{K} d_k}{1-\delta} \right\rfloor$. This implies that $C_{\delta}(\mathcal{T}_P) \le \left\lfloor \frac{\sum_{k=1}^{K} d_k}{1-\delta} \right\rfloor$. As a result $C_{\delta}^{\infty}(\mathcal{T}) \le \left\lfloor \frac{\sum_{k=1}^{K} d_k}{1-\delta'} \right\rfloor$ for any $\delta' > \delta$ which gives the desired result.

Let us now move to the quantum capacity. Let $\mathcal{E}$ be a $(D, \delta)$ classical code for $\mathcal{T}_P$ and $\mathcal{R}$ a corresponding recovery channel. In order to compute the entanglement fidelity, recall that the entanglement fidelity of channel $\mathcal{E}$ with Kraus operators $\{E_i\}$ is given by $F_E(\mathcal{E}) = \sum_i |\mathrm{tr}(E_i)|^2$. Let us introduce Kraus operators for $\{E_j\}_j$ for $\mathcal{T}_P \circ \mathcal{E}$, $\{R_i\}_i$ for $\mathcal{R}$. As $\mathcal{T}_P(\mathcal{M}_d) = \chi_{\mathcal{T}}$, the operator $\{P_k E_j\}_{k,j}$ are also Kraus operators for the map $\mathcal{T}_P \circ \mathcal{E}$, where we recall that $P_k$ is the projector onto $H_{k,1}$.

Then we have

$$ F_E(\mathcal{R} \circ \mathcal{T}_P \circ \mathcal{E}) = \frac{1}{D^2} \sum_{i,j,k} |\mathrm{tr}(R_i P_k E_j)|^2. $$

Let us denote $\alpha_k^2 = \sum_{i,j} |\mathrm{tr}(R_i P_k E_j)|^2$. We show two properties on $\alpha_k$: $\alpha_k^2 \le d_k \beta_k$ with $\sum_k \beta_k = D$ and $\alpha_k^2 \le d_k^2$. We start with the first property

$$ \begin{aligned} \alpha_k^2 &\le \sum_{i,j} \mathrm{tr}(R_i P_k P_k^\dagger R_i^\dagger) \mathrm{tr}(E_j^\dagger P_k^\dagger P_k E_j) \\ &= \mathrm{tr}(P_k) \sum_j \mathrm{tr}(E_j^\dagger P_k E_j). \end{aligned} $$
For the first inequality, we used the Cauchy-Schwarz inequality $|\text{tr}(A^\dagger B)|^2 \le \text{tr}(A^\dagger A)\text{tr}(B^\dagger B)$. Then we used the fact that $\mathcal{R}$ is trace preserving. Now note that because $\mathcal{T}_P \circ \mathcal{E}$ is a quantum channel, we have $\sum_{k,j} \text{tr}(E_j^\dagger P_k^\dagger P_k E_j) = D$. Calling $\beta_k = \sum_j \text{tr}(E_j^\dagger P_k^\dagger P_k E_j)$, we proved the first claimed inequality.

To show the second inequality $\alpha_k^2 \le d_k^2$, we write

$$ 
\begin{aligned}
\alpha_k^2 &\le \sum_{i,j} \text{tr}(E_j R_i P_k P_k^\dagger R_i^\dagger E_j^\dagger) \text{tr}(P_k^\dagger P_k) \\
&= \text{tr}(P_k) d_k \\
&= d_k^2.
\end{aligned}
$$

where we used again the Cauchy-Schwarz inequality and the fact that $\mathcal{T}_P \circ \mathcal{E} \circ \mathcal{R}$ is trace-preserving. Defining $\gamma_k = \min(d_k, \beta_k)$, we have that $\sum_{k=1}^K \gamma_k \le D$ and $\gamma_k \le d_k$ and the entanglement fidelity can be bounded as

$$ 
\begin{aligned}
F_E(\mathcal{R} \circ \mathcal{T}_P \circ \mathcal{E}) &\le \frac{1}{D^2} \sum_{k=1}^K \alpha_k^2 \\
&\le \frac{1}{D^2} \sum_{k=1}^K d_k \gamma_k,
\end{aligned}
$$

which concludes the proof of (6). □

## 2.1 Continuous-time dynamical system

We now consider a quantum Markovian evolution with a continuous time parameter. Such an evolution is called a quantum dynamical semigroup or quantum Markov semigroup and is a family of quantum channels $(\mathcal{T}_t)_{t \ge 0}$ satisfying the property $\mathcal{T}_{t+s} = \mathcal{T}_t \circ \mathcal{T}_s$ for $t, s \ge 0$. As we show below, the infinite-time capacities of such evolutions can be easily related to the discrete time case considered above. We note that a quantum Markov semigroup $(\mathcal{T}_t)_{t \ge 0}$ is characterized by a linear map $\mathcal{L}$ (called the generator) satisfying $\mathcal{T}_t = e^{\mathcal{L}t}: (\mathcal{T}_t)_{t \ge 0}$ forms a quantum Markov semigroup if and only if there exists a Hermitian matrix $H$ and matrices $\{L_j\}_j$ such that [7, 12][21, Theorem 7.1]

$$ \mathcal{L}(\rho) = i[\rho, H] + \sum_j L_j \rho L_j^\dagger - \frac{1}{2} (L_j^\dagger L_j \rho + \rho L_j^\dagger L_j). \quad (7) $$

**Proposition 2.2.** Let $(\mathcal{T}_t)_{t \ge 0}$ be a quantum Markov semigroup. Then we have

$$ 
\begin{aligned}
\lim_{t \to \infty} C_\delta(\mathcal{T}_t) &= C_\delta^\infty(\mathcal{T}_1) \\
\lim_{t \to \infty} Q_\delta(\mathcal{T}_t) &= Q_\delta^\infty(\mathcal{T}_1).
\end{aligned}
$$

In addition, the peripheral subspace $\chi_{\mathcal{T}_1}$ can be expressed in terms of the spectrum of generator $\mathcal{L}$ as follows:

$$ \chi_{\mathcal{T}_1} = \operatorname{span}\{X \in \mathcal{M}_d(\mathbb{C}) | \exists \theta \in \mathbb{R}, \mathcal{L}(X) = i\theta X\}. $$
Proof. Let $\mathcal{E}$ be a $(D, \delta)$ classical (or quantum) code for $\mathcal{T}_t$, and $\mathcal{R}$ be its corresponding recovery channel. If $t' \le t$, then $\mathcal{E}$ is a $(D, \delta)$ classical (or quantum) code for $\mathcal{T}_{t'}$ with recovery operator $\mathcal{R} \circ \mathcal{T}_{t-t'}$. Therefore, we have the following inequalities:

$$C_{\delta}(\mathcal{T}_{[t]}) \ge C_{\delta}(\mathcal{T}_t) \ge C_{\delta}(\mathcal{T}_{[t]})$$

and

$$Q_{\delta}(\mathcal{T}_{[t]}) \ge Q_{\delta}(\mathcal{T}_t) \ge Q_{\delta}(\mathcal{T}_{[t]}).$$

In the limit as $t \to \infty$, both $C_{\delta}(\mathcal{T}_{[t]})$ and $C_{\delta}(\mathcal{T}_{[t]})$ converge to $C_{\delta}^{\infty}(\mathcal{T}_1)$. Therefore, we have

$$\lim_{t \to \infty} C_{\delta}(\mathcal{T}_t) = C_{\delta}^{\infty}(\mathcal{T}_1) \quad \text{and} \quad \lim_{t \to \infty} Q_{\delta}(\mathcal{T}_t) = Q_{\delta}^{\infty}(\mathcal{T}_1).$$

Next, we examine the peripheral subspace of $\mathcal{T}_1$. It is straightforward to see that if $\mathcal{L}(X) = i\theta X$ for some operator $X$ and real number $\theta$, then $\mathcal{T}_t(X) = e^{t\mathcal{L}}(X) = e^{i\theta t}X$, which implies $X \in \chi_{\mathcal{T}_t}$. Consequently, if $X$ is spanned by eigenoperators of $\mathcal{L}$ corresponding to imaginary eigenvalues, then $X$ belongs to $\chi_{\mathcal{T}_1}$.

To show the converse, we use the “super-operator form” which represents the linear map $\mathcal{E}$ as a matrix $\hat{E}$ acting on the vector space of operators. Specifically, for a quantum channel $\mathcal{E}$ and a density matrix $\rho$, the action of $\mathcal{E}$ can be written as $\text{vec}(\mathcal{E}(\rho)) = \hat{E}\text{vec}(\rho)$, where $\text{vec}(\cdot)$ denotes the column-stacking vectorization of a matrix. Let $L$ be the super-operator form of $\mathcal{L}$, with a Jordan decomposition given by

$$L = V \left( \bigoplus_{\ell=1}^{s} J_{\ell}(\lambda_{\ell}) \right) V^{-1},$$

where $J_{\ell}(\lambda_{\ell})$ is a Jordan block corresponding to an eigenvalue $\lambda_{\ell}$ of $L$, i.e., $J_{\ell}(\lambda_{\ell}) = \lambda_{\ell}I + J_{\ell}(0)$ with $J_{\ell}(0) = \begin{pmatrix} 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & \dots & \dots & \dots & 0 \end{pmatrix} \in \mathcal{M}_{d_{\ell}}$, where $d_{\ell}$ is the size of the block.

Thus the super-operator of $\mathcal{T}_1 = e^{\mathcal{L}}$ has the form

$$e^{\mathcal{L}} = V \left( \bigoplus_{\ell=1}^{s} e^{J_{\ell}(\lambda_{\ell})} \right) V^{-1}, \qquad (8)$$

with

$$e^{J_{\ell}(\lambda_{\ell})} = e^{\lambda_{\ell}} \cdot \begin{pmatrix} 1 & 1 & \frac{1}{2!} & \cdots & \frac{1}{(d_{\ell}-1)!} \\ 0 & 1 & 1 & \cdots & \frac{1}{(d_{\ell}-2)!} \\ 0 & 0 & 1 & \cdots & \frac{1}{(d_{\ell}-3)!} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \end{pmatrix}.$$

Thus the eigenvalues of $\mathcal{T}_1$ are $\{e^{\lambda_{\ell}}\}_{\ell}$. Now let $X$ be an eigenvector of $\mathcal{T}_1$ with eigenvalue $e^{\lambda_{\ell}}$ with $|e^{\lambda_{\ell}}| = 1$. We know from [21, Proposition 6.2] that for such eigenvalues $d_{\ell} = 1$. Therefore, $X$ is also an eigenvector of $L$ with eigenvalue $\lambda_{\ell}$ and $\lambda_{\ell}$ is pure imaginary. $\square$
### 3 Tensor Product of Quantum Channels

In this Section, we show the infinite-time capacities are basically additive under tensor product. To show that, we start with the following lemma about the peripheral subspace.

**Lemma 3.1.** Consider two quantum channels, $\mathcal{T}: \mathcal{M}_d(\mathbb{C}) \to \mathcal{M}_d(\mathbb{C})$ and $\mathcal{S}: \mathcal{M}_{d'}(\mathbb{C}) \to \mathcal{M}_{d'}(\mathbb{C})$, with their respective peripheral projections denoted by $\mathcal{T}_P$ and $\mathcal{S}_P$, and their respective peripheral subspaces denoted by $\chi_T$ and $\chi_S$. For the tensor product of these channels, $\mathcal{T} \otimes \mathcal{S}$, the peripheral projection is given by $\mathcal{T}_P \otimes \mathcal{S}_P$, and the corresponding peripheral subspace is $\chi_T \otimes \chi_S$.

*Proof.* By definition there exist increasing sequences $\{m_i\}$, $\{n_i\}$, and $\{k_i\}$ such that

$$ \lim_{i \to \infty} \mathcal{T}^{m_i} = \mathcal{T}_P, \quad \lim_{i \to \infty} \mathcal{S}^{n_i} = \mathcal{S}_P, \text{ and } \lim_{i \to \infty} (\mathcal{T} \otimes \mathcal{S})^{k_i} = (\mathcal{T} \otimes \mathcal{S})_P. $$

Since any power of a peripheral projection is itself, we have

$$ \lim_{i \to \infty} \mathcal{T}^{m_i n_i k_i} = \mathcal{T}_P, \quad \lim_{i \to \infty} \mathcal{S}^{m_i n_i k_i} = \mathcal{S}_P, \text{ and } \lim_{i \to \infty} (\mathcal{T} \otimes \mathcal{S})^{m_i n_i k_i} = (\mathcal{T} \otimes \mathcal{S})_P. $$

Therefore, $(\mathcal{T} \otimes \mathcal{S})_P = \mathcal{T}_P \otimes \mathcal{S}_P$.

Next, we consider the peripheral subspaces. The peripheral subspace is the fixed-point subspace of the peripheral projection. If $X \in \chi_T \otimes \chi_S$, then it can be written as $X = \sum_i Y_i \otimes Z_i$ where $Y_i \in \chi_T$ and $Z_i \in \chi_S$. So we have

$$ \mathcal{T}_P \otimes \mathcal{S}_P(X) = \sum_i \mathcal{T}_P(Y_i) \otimes \mathcal{S}_P(Z_i) = \sum_i Y_i \otimes Z_i = X, $$

showing that $X$ is a fixed point of $\mathcal{T}_P \otimes \mathcal{S}_P$. Therefore $\chi_T \otimes \chi_S \subseteq \chi_T \otimes \chi_S$.

For the other direction, let $X \in \mathcal{M}_d(\mathbb{C}) \otimes \mathcal{M}_{d'}(\mathbb{C})$ belongs to peripheral subspace of $\mathcal{T} \otimes \mathcal{S}$, and decompose $X$ as $X = \sum_i Y_i \otimes Z_i$ where $Y_i \in \mathcal{M}_d(\mathbb{C})$ and $Z_i \in \mathcal{M}_{d'}(\mathbb{C})$. Since $X$ is a fixed point of $\mathcal{T}_P \otimes \mathcal{S}_P$, we have

$$ X = \mathcal{T}_P \otimes \mathcal{S}_P(X) = \sum_i \mathcal{T}_P(Y_i) \otimes \mathcal{S}_P(Z_i). $$

Because $\mathcal{T}_P(Y_i) \in \chi_T$ and $\mathcal{S}_P(Z_i) \in \chi_S$, it follows that $X \in \chi_T \otimes \chi_S$. Thus $\chi_T \otimes \chi_S \subseteq \chi_T \otimes \chi_S$. Therefore, we conclude that $\chi_T \otimes \chi_S = \chi_T \otimes \chi_S$. $\square$

**Theorem 3.1.** For any two quantum channels $\mathcal{T}$ and $\mathcal{S}$, the infinite-time zero-error classical and quantum capacities are additive under the tensor product. Specifically, we have:

$$ C_0^\infty (\mathcal{T} \otimes \mathcal{S}) = C_0^\infty (\mathcal{T}) + C_0^\infty (\mathcal{S}), $$

$$ Q_0^\infty (\mathcal{T} \otimes \mathcal{S}) = Q_0^\infty (\mathcal{T}) + Q_0^\infty (\mathcal{S}). $$
Proof. By Lemma 3.1, the peripheral subspace of $\mathcal{T} \otimes \mathcal{S}$ is the tensor product of the peripheral subspace of $\mathcal{T}$ and $\mathcal{S}$. So if $\chi_{\mathcal{T}} = 0 \oplus \bigoplus_{k=1}^{K} \mathcal{M}_{d_k}(\mathbb{C}) \otimes \omega_k$ for the decomposition $\mathbb{C}^d = H_0 \oplus \bigoplus_{k=1}^{K} H_{k,1} \otimes H_{k,2}$ and $\chi_{\mathcal{S}} = 0 \oplus \bigoplus_{k'=1}^{K'} \mathcal{M}_{d'_{k'}}(\mathbb{C}) \otimes \omega'_{k'}$ for the decomposition $\mathbb{C}^{d'} = H'_0 \oplus \bigoplus_{k'=1}^{K'} H'_{k',1} \otimes H'_{k',2}$, then we can decompose

$$ \mathbb{C}^d \otimes \mathbb{C}^{d'} = \overline{H}_0 \oplus \bigoplus_{k \in \{1, \dots, K\}, k' \in \{1, \dots, K'\}} H_{k,1} \otimes H'_{k',1} \otimes H_{k,2} \otimes H'_{k',2}, $$

where

$$ \overline{H}_0 = (H_0 \otimes H'_0) \oplus \left( H_0 \otimes \left( \bigoplus_{k'=1}^{K'} H'_{k',1} \otimes H'_{k',2} \right) \right) \oplus \left( \left( \bigoplus_{k=1}^{K} H_{k,1} \otimes H_{k,2} \right) \otimes H'_0 \right) $$

and get for this decomposition

$$ \chi_{\mathcal{T} \otimes \mathcal{S}} = 0 \oplus \bigoplus_{k,k'} \mathcal{M}_{d_k \times d'_{k'}}(\mathbb{C}) \otimes \omega_k \otimes \omega'_{k'}. $$

By Theorem 2.1, $C_0^\infty(\mathcal{T} \otimes \mathcal{S}) = \log(\sum_{k,k'} d_k d'_{k'}) = C_0^\infty(\mathcal{T}) + C_0^\infty(\mathcal{S})$ and $Q_0^\infty(\mathcal{T} \otimes \mathcal{S}) = \log(\max_{k,k'} d_k d'_{k'}) = Q_0^\infty(\mathcal{T}) + Q_0^\infty(\mathcal{S})$. $\square$

A simple corollary is that when taking tensor powers of a channel, as is common in Shannon theory, the classical and quantum capacities are given by the zero-error capacities at infinite time.

**Proposition 3.1.** Let $\delta \in [0, 1)$ and $\mathcal{T}: \mathcal{M}_d \to \mathcal{M}_d$ be a quantum channel. Then

$$ \lim_{m \to \infty} \frac{1}{m} C_0^\infty (\mathcal{T}^{\otimes m}) = C_0^\infty (\mathcal{T}), $$

and

$$ \lim_{m \to \infty} \frac{1}{m} Q_0^\infty (\mathcal{T}^{\otimes m}) = Q_0^\infty (\mathcal{T}). $$

*Proof.* By Theorem 2.1 and Theorem 3.1, we have

$$ \begin{aligned} C_\delta^\infty (\mathcal{T}^{\otimes m}) &= \log \left( \left\lfloor \frac{2^{C_0^\infty (\mathcal{T}^{\otimes m})}}{1 - \delta} \right\rfloor \right) \\ &= \log \left( \left\lfloor \frac{2^{m C_0^\infty (\mathcal{T})}}{1 - \delta} \right\rfloor \right). \end{aligned} $$

But

$$ m C_0^\infty (\mathcal{T}) + \log \left( \frac{1}{1 - \delta} \right) - 1 \le \log \left( \left\lfloor \frac{2^{m C_0^\infty (\mathcal{T})}}{1 - \delta} \right\rfloor \right) \le m C_0^\infty (\mathcal{T}) + \log \left( \frac{1}{1 - \delta} \right), $$

which proves the desired result.

For the quantum capacity, the same argument gives

$$ m Q_0^\infty (\mathcal{T}) + \frac{1}{2} \log \left( \frac{1}{1 - \delta} \right) - 1 \le Q_\delta^\infty (\mathcal{T}^{\otimes m}) \le m Q_0^\infty (\mathcal{T}) + \log \left( \frac{1}{1 - \delta} \right), $$

which proves the desired result. $\square$
# 4 An efficient algorithm for the structure of the peripheral subspace

In this section, we describe an algorithm to efficiently determine the structure of the peripheral subspace of a quantum channel. An algorithm using $O(d^8)$ operations for this task was previously described in [22] and a related algorithm in [9]. Here, we improve it and show that it can be done in $O(d^6 \log d)$. The paper [3] also describes an algorithm to represent the peripheral subspace as a linear span but relies on [10] for the structure, and for the latter, it is not clear whether it is efficient. Note that here, we work under a simplifying assumption that standard operations on a $d \times d$ matrix can be done in time $O(d^3)$ (e.g., matrix multiplication, spectral decomposition, Jordan normal form). We leave for future work a more detailed complexity analysis for finding the structure of the peripheral subspace.

**Theorem 4.1.** Let $\mathcal{T}: \mathcal{M}_d(\mathbb{C}) \to \mathcal{M}_d(\mathbb{C})$ be a quantum channel, and let $\chi_{\mathcal{T}} = 0 \oplus \bigoplus_{k=1}^K \mathcal{M}_{d_k}(\mathbb{C}) \otimes \omega_k$ be the decomposition of its peripheral subspace as described in Proposition 2.1. Algorithm 1, takes the super-operator form of $\mathcal{T}$ as input and returns a representation of the Hilbert space decomposition and the fixed density matrices $\omega_k$ in time $O(d^6 \log d)$.

*Remark 4.1.* An implementation of this algorithm with examples can be found in [17].

*Proof.* The first step is to compute the peripheral projection channel $\mathcal{T}_P$. Let $\hat{T} \in \mathcal{M}_{d_2}$ be the super-operator form of $\mathcal{T}$. Using the Jordan normal form, we can express $\hat{T}$ as $\hat{T} = \sum_{\ell=1}^s \lambda_\ell P_\ell + N_\ell$, where $\lambda_\ell$ are the eigenvalues of $\hat{T}$, $P_\ell$ are projections and $N_\ell$ are nilpotent. The super-operator form of $\mathcal{T}_P$ is given by [21, Proposition 6.3]

$$ \hat{T}_P = \sum_{\ell:|\lambda_\ell|=1} P_\ell. $$

Thus, $\hat{T}_P$ can be computed using the Jordan normal form of $\hat{T}$ which can be obtained in time $O((d^2)^3) = O(d^6)$.

Recall that $\chi_{\mathcal{T}} = \text{Fix}(\mathcal{T}_P)$, where $\text{Fix}(\mathcal{S})$ is the fixed point space of a map $\mathcal{S}$, i.e., $\text{Fix}(\mathcal{S}) = \text{span}\{X \in \mathcal{M}_d : \mathcal{S}(X) = X\}$. The rest of the algorithm computes the structure of the fixed point space of the quantum channel $\mathcal{T}_P$.

Let $\chi_{\mathcal{T}} = \text{Fix}(\mathcal{T}_P) = 0 \oplus \bigoplus_{k=1}^K \mathcal{M}_{d_k} \otimes \omega_k$ for the Hilbert space decomposition

$$ \mathbb{C}^d = H_0 \oplus \bigoplus_{k=1}^K H_{k,1} \otimes H_{k,2}. \qquad (9) $$

Instead of working directly with $\chi_{\mathcal{T}}$, it is convenient to work with the matrix algebra $\mathcal{A} \subseteq B(\mathbb{C}^d)$ which is defined as

$$ \mathcal{A} = \bigoplus_{k=1}^{K} \mathcal{M}_{d_k} \otimes I_{d'_k}. \qquad (10) $$
for the Hilbert space decomposition (9) with $d_k = \dim H_{k,1}$ and $d'_k = \dim H_{k,2}$. Then, $\chi_T$ is called a distortion of the matrix algebra $\mathcal{A} = \bigoplus_{k=1}^K \mathcal{M}_{d_k} \otimes I_{d'_k}$, i.e., there is a completely positive map $\mathcal{D}$ such that $\mathcal{D}(\mathcal{A}) = \chi_T$.

In [3, Theorem 5 and Section V], an algorithm is given to find operators $A_1, \dots, A_N \in \mathcal{M}_d$ such that $\mathcal{A} = \operatorname{span}(A_1, \dots, A_N)$. This is done by computing left and right eigenvectors of $\hat{T}$ and thus can be done in time $O(d^6)$.

What remains is now to determine the structure of $\mathcal{A}$. Let us call $P_k$ the orthogonal projector on $H_{k,1} \otimes H_{k,2}$. The first step is to compute the projectors $P_k$ and the second step is to find the dimensions $d_k$ and $d'_k$.

We start with the first step, i.e., computing $P_k$. For that we use that the projectors $P_k$ are the minimal projections in the center of $\mathcal{A}$. Recall that the center $Z(\mathcal{A}) = \{X \in \mathcal{A} : XY = YX \ \forall Y \in \mathcal{A}\}$ and that $Z(\mathcal{A}) = \mathcal{A} \cap \mathcal{A}'$ where $\mathcal{A}'$ is the commutant of $\mathcal{A}$ defined by $\mathcal{A}' = \{X \in B(\mathbb{C}^d) : XY = YX \ \forall Y \in \mathcal{A}\}$.

Note that for the matrix algebra $\mathcal{A}$ in (10), we have $\mathcal{A}' = \bigoplus_{k=1}^K I_{H_{k,1}} \otimes \mathcal{M}_{d'_k}$ and $Z(\mathcal{A}) = \bigoplus_{k=1}^K C I_{H_{k,1}} \otimes I_{H_{k,2}}$. Given an algebra $\mathcal{B}$, a minimal projection in $\mathcal{B}$ is an orthogonal projection $P$ such that $P\mathcal{B}P = \mathcal{C}P$ [10]. The minimal projections of $Z(\mathcal{A})$, that are also called the minimal central projections, are exactly the projectors $P_k$ we are looking for.

Thus, in order to compute the projectors $\{P_k\}_{k=1}^K$, we first compute a representation of $Z(\mathcal{A})$ as a linear span. We do this by computing a representation of the commutant $\mathcal{A}'$ as the linear span of some operators $B_1, \dots, B_{N'}$, which can be done by computing the kernel of the matrix $\Gamma$ described in Lemma 4.1. Then, the center can be computed by taking the intersection of subspaces $\mathcal{A}$ and $\mathcal{A}'$; see Algorithm 3. Then Algorithm 6 described a general algorithm to find all minimal projections of an algebra in $B(\mathbb{C}^d)$ in time $O(Nd^3 \log d)$, where $N$ is the number of operators describing the algebra as a linear span. Note that the center $Z(\mathcal{A})$ has dimension at most $d$ and so we may assume $N \le d$. As such, we have computed all the $\{P_k\}_{k=1}^K$ in time $O(d^5 \log d)$.

Now, the second step is within each block $k$, we want to compute $d_k = \dim H_{k,1}$ and $d'_k = \dim H_{k,2}$. For that we now compute minimal projections $P_{k,j}$ in $\mathcal{A}$ satisfying $P_{k,j}P_k = P_{k,j}$ in algebra $\mathcal{A}$ by using Algorithm 6 with inputs $P_k$ and $\{A_1, \dots, A_N\}$. From the form of the algebra $\mathcal{A}$, we know that any minimal projection $Q$ with $QP_k = Q$ is of the form $Q = |\psi\rangle\langle\psi| \otimes I_{H_{k,2}}$ for some $|\psi\rangle \in H_{k,1}$. As a result, there exists orthogonal unit vectors $|e_{k,j}\rangle$ such that $P_{k,j} = |e_{k,j}\rangle\langle e_{k,j}| \otimes I_{H_{k,2}}$. We have that $d'_k = \operatorname{rank}(P_{k,j})$ and $d_k$ is the number of minimal projections found $\{P_{k,j}\}_j$. For each $k$, the runtime for finding the minimal projections $\{P_{k,j}\}_{j=1}^k O(d_k \times d^5 \log d)$ (as the dimension $N$ of the algebra $\mathcal{A}$ can be up to $d^2$). As $\sum_{k=1}^K d_k \le d$, the runtime of this step is $O(d^6 \log d)$. $\square$

Below we provide a lemma that was used in the above proof. For this lemma we need the concept of operator-vector correspondence: given a matrix $X \in \mathcal{M}_n(\mathbb{C})$, it represents a vector, $|X\rangle\rangle \in \mathbb{C}^n \otimes \mathbb{C}^n$.
**Lemma 4.1.** Let $\mathcal{A}$ be a matrix algebra generated by $\{A_1, \dots, A_N\}$, and $\mathcal{A}'$ be the commutant of $\mathcal{A}$. Then $X$ belongs to $\mathcal{A}'$ if and only if $|X\rangle\rangle$ belongs to the kernel of $\Gamma$, where

$$ \Gamma = \sum_{i=1}^{N} (A_i \otimes I - I \otimes A_i^T)^{\dagger} (A_i \otimes I - I \otimes A_i^T). \quad (11) $$

*Proof.* By the fact that $A \otimes B|C\rangle\rangle = |ACB^T\rangle\rangle$ (see [20, Proposition 2.20]) applies if the dimensions of $A$, $B$, and $C$ indicate $ACB^T$ is a valid matrix. So $X \otimes I|Y\rangle\rangle = |XY\rangle\rangle$ and $I \otimes X^T|Y\rangle\rangle = |YX\rangle\rangle$. Therefore if we define

$$ \Gamma_{A_i} := (A_i \otimes I - I \otimes A_i^T)^{\dagger} (A_i \otimes I - I \otimes A_i^T), $$

then an operator $X$ commutes with $A_i$ if and only if $\Gamma_{A_i}|X\rangle\rangle = 0$. As $\Gamma_{A_i}$ is positive, the kernel of $\Gamma$ is the intersection of kernels of all $\Gamma_{A_i}$. Thus, $X \in \mathcal{A}'$ if and only if $|X\rangle\rangle \in \Gamma$. $\square$

**Algorithm 1** Find the structure of $\chi_T$

1: **Input:** $\hat{T}$, the super-operator form of $\mathcal{T}$

2: **Output:** The structure of $\chi_T$ as in (3)

3: **procedure** PERIPHERAL-SUBSPACE-STRUCTURE($\mathcal{T}$)

4: $\hat{T} = \sum_{\ell=1}^{s} \lambda_{\ell} P_{\ell} + N_{\ell}$ ▷ Jordan decomposition

5: $\hat{T}_P \leftarrow \sum_{\ell:|\lambda_{\ell}|=1} P_{\ell}$ ▷ Algorithm 2

6: **return** FIXED-SUBSPACE-STRUCTURE($\hat{T}_P$)

**Algorithm 2** Find the fixed point structure Fix($\mathcal{S}$)

1: **Input:** $\hat{S}$, the super-operator form of $\mathcal{S}$

2: **Output:** The structure of Fix($\mathcal{S}$)

3: **procedure** FIXED-SUBSPACE-STRUCTURE($\mathcal{S}$)

4: $\{A_1, \dots, A_N\} \leftarrow \text{PER-ALGEBRA-AS-LINEAR-SPAN}(\mathcal{S})$ ▷ [3] repr. of $\mathcal{A}$ as a linear span

5: $\{C_1, \dots, C_M\} \leftarrow \text{CENTER-OF-ALGEBRA}(A_1, \dots, A_N)$ ▷ Algorithm 3

6: Ensure $\{A_j\}_j$ and $\{C_j\}_j$ are Hermitian via $A \to A + A^\dagger$ and $A \to i(A - A^\dagger)$

7: $P \leftarrow$ projector on support of the center of $\mathcal{A}$ ▷ $P$ projector onto $\oplus_{k=1}^K H_{k,1} \otimes H_{k,2}$

8: minimalCentralProj $\leftarrow$ MINIMAL-PROJECTIONS($P, \{C_i\}$) ▷ Algorithm 6

9: **for** $k \leftarrow 1$ **to** $K$ **do**

10: $P_k \leftarrow$ minimalCentralProj[$k$]

11: minimalProj[$k$] $\leftarrow$ FIND-MINIMAL-PROJECTIONS($P_k, \{A_i\}$) ▷ Algorithm 6

12: Construct basis $\{|e_{k,j}\rangle\}_{j=1}^{d_k}$ of $H_{k,1}$

13: **end for**

14: Compute $\{\omega_k\}$ as in [3, Lemma 5.4]

15: **return** for each $k = 1, \dots, K$, minimalCentralProj, minimalProj, a basis $\{|e_{k,j}\rangle\}_{j=1}^{d_k}$ of $H_{k,1}$ and $\omega_k$

16: **end procedure**
<caption>**Algorithm 3** Compute center of algebra $\mathcal{A} = \text{span}\{A_1, \dots, A_N\}$</caption>

1: **Input:** $A_1, A_2, \dots, A_N \in \mathcal{M}_d$ \quad $\triangleright \mathcal{A} = \text{span}(A_1, \dots, A_N)$
2: **Output:** $\{C_1, \dots, C_M\}$ that span the center of $\mathcal{A}$
3: **procedure CENTER-OF-ALGEBRA($A_1, A_2, \dots, A_N$)**
4: &nbsp;&nbsp;&nbsp;&nbsp;Γ $\leftarrow \sum_i (A_i^\dagger A_i) \otimes I - A_i^\dagger \otimes A_i^T - A_i \otimes \bar{A}_i + I \otimes (\bar{A}_i A_i^T)$ \quad $\triangleright \bar{A}$ is the complex conjugate of $\mathcal{A}$
5: &nbsp;&nbsp;&nbsp;&nbsp;Compute the kernel of Γ as $\text{span}\{B_1, \dots, B_{N'}\}$ \quad $\triangleright$ See Lemma 4.1, $\text{span}\{B_1, \dots, B_{N'}\} = \mathcal{A}'$
6: &nbsp;&nbsp;&nbsp;&nbsp;Γ' $\leftarrow \sum_i (B_i^\dagger B_i) \otimes I - B_i^\dagger \otimes B_i^T - B_i \otimes \bar{B}_i + I \otimes (\bar{B}_i B_i^T)$ \quad $\triangleright$ ker $\Gamma'$ corresponds to $\mathcal{A}'' = \mathcal{A}$
7: &nbsp;&nbsp;&nbsp;&nbsp;Compute the kernel of $\Gamma + \Gamma'$ as $\text{span}\{C_1, \dots, C_M\}$ \quad $\triangleright \Gamma, \Gamma' \ge 0$, so $\text{ker } \Gamma + \Gamma' = \text{ker } \Gamma \cap \text{ker } \Gamma'$
8: &nbsp;&nbsp;&nbsp;&nbsp;return $\{C_1, \dots, C_M\}$
9: **end procedure** \quad $\triangleright$ The runtime of this procedure is $O(Nd^4 + d^6)$

<caption>**Algorithm 4** Find projection smaller than $P$</caption>

1: **Input:** Orthogonal projection $P$ and $\{A_i\}_{i=1}^N$ spanning $\mathcal{A}$
2: **Output:** Projection $Q \in \mathcal{A}$ such that $QP = Q$, and $\text{tr}(Q) \le \text{tr}(P)/2$ if $P$ is not minimal
3: **procedure REDUCE-PROJECTION($P, \{A_i\}$)**
4: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\exists i$ is such that $PA_iP \notin \mathbb{C}P$ **then** \quad $\triangleright P$ is not minimal
5: &nbsp;&nbsp;&nbsp;&nbsp;Write spectral decomposition $PA_iP = \sum_j \lambda_j P_j$ \quad $\triangleright$ At least 2 nonzero eigenvalues
6: &nbsp;&nbsp;&nbsp;&nbsp;**else** \quad $\triangleright$ [10] shows that $P_j \in \mathcal{A}$ for all $j$
7: &nbsp;&nbsp;&nbsp;&nbsp;**return** $Q = \arg\min\{\text{tr}(P_j)\}$ \quad $\triangleright$ We have $\text{tr}(Q) \le \text{tr}(P)/2$ as $\sum_j P_j \le P$
8: &nbsp;&nbsp;&nbsp;&nbsp;**end** \quad $\triangleright P$ is minimal
9: **Return** $P$
10: **end if**
11: **end procedure** \quad $\triangleright$ The runtime of this procedure is $O(Nd^3)$

<caption>**Algorithm 5** Find one minimal projection in the range of projection $P$</caption>

1: **Input:** Orthogonal projection $P$ and $\{A_i\}$ spanning $\mathcal{A}$
2: **Output:** A minimal projection $Q \in \mathcal{A}$ such that $Q \le P$
3: **procedure FIND-ONE-MINIMAL-PROJECTION($P, \{A_i\}$)**
4: &nbsp;&nbsp;&nbsp;&nbsp;Q $\leftarrow$ REDUCE-PROJECTION($P, \{A_i\}$) \quad $\triangleright$ Algorithm 4
5: &nbsp;&nbsp;&nbsp;&nbsp;**while** $P \ne Q$ **do** \quad $\triangleright$ As the trace is divided by 2 at each step, at most $\log d$ steps
6: &nbsp;&nbsp;&nbsp;&nbsp;P $\leftarrow$ Q
7: &nbsp;&nbsp;&nbsp;&nbsp;Q $\leftarrow$ REDUCE-PROJECTION($P, \{A_i\}$)
8: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
9: **return** $P$
10: **end procedure** \quad $\triangleright$ REDUCE-PROJECTION is called at most $\log d$ times
<caption>**Algorithm 6** Decomposing *P* to minimal projection in algebra *A*</caption>

1: **Input:** Orthogonal projection *P* ∈ *A* and {*A*ᵢ} spanning *A*
2: **Output:** A set of minimal projections *Q*₁, ..., *Q*�s in *A* such that *Q*₁ + ... + *Q*�s = *P*
3: **procedure** FIND-MINIMAL-PROJECTIONS(*P*, {*A*ᵢ})
4:     minimalProjections ← {}
5:     **while** *P* ≠ 0 **do**
6:         *Q* ← FIND-ONE-MINIMAL-PROJECTION(*P*)
7:         Add *Q* to minimalProjections
8:         *P* ← *P* − *Q*
9:     **do**
10:     Update *P* by removing the minimal projector that was found
11:     Note that *P* − *Q* is also an orthogonal projector
12: end procedure

5 Concluding remarks

In summary, we have shown that in the setting of infinite time, the classical and quantum capacities are essentially given by the zero-error capacities and can be efficiently computed, unlike the fixed time setting. We see this result as a first step towards understanding channel capacities for quantum evolutions. It would be interesting to study the behaviour of capacities for finite *t* both for active and passive error correction.

Acknowledgements

We acknowledge support from the European Research Council (ERC Grant AlgoQIP, Agreement No. 851716). MR is supported by the Marie Skłodowska- Curie Fellowship from the European Union's Horizon Research and Innovation programme, grant Agreement No. HORIZON-MSCA-2022-PF-01 (Project number: 101108117). We would like to thank Nilanjanna Datta for a talk at the "Quantum information" conference at the SwissMAP Research Station in Les Diablerets on [15] which stimulated this work.

References

[1] Ravi B Bapat and Tirukkannamangai ES Raghavan. *Nonnegative matrices and applications*. Number 64. Cambridge university press, 1997.

[2] Siddharth Barman and Omar Fawzi. Algorithmic aspects of optimal channel coding. *IEEE Transactions on Information Theory*, 64(2):1038–1045, 2017.
[3] Robin Blume-Kohout, Hui Khoon Ng, David Poulin, and Lorenza Viola. Information-preserving structures: A general framework for quantum zero-error information. *Phys. Rev. A*, 82:062306, Dec 2010.

[4] Benjamin J. Brown, Daniel Loss, Jiannis K. Pachos, Chris N. Self, and James R. Wootton. Quantum memories at finite temperature. *Rev. Mod. Phys.*, 88:045005, Nov 2016.

[5] Eric V Denardo. Periods of connected networks and powers of nonnegative matrices. *Mathematics of Operations Research*, 2(1):20–24, 1977.

[6] Omar Fawzi, Alexander Müller-Hermes, and Ala Shayeghi. A lower bound on the space overhead of fault-tolerant quantum computation. In *13th Innovations in Theoretical Computer Science Conference (ITCS 2022)*. Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2022.

[7] Vittorio Gorini, Andrzej Kossakowski, and E. C. G. Sudarshan. Completely positive dynamical semigroups of N-level systems. *Journal of Mathematical Physics*, 17(5):821–825, 05 1976.

[8] Daniel Gottesman. Surviving as a quantum computer in a classical world. *Textbook manuscript preprint*, 2016.

[9] Ji Guan, Yuan Feng, and Mingsheng Ying. Decomposition of quantum markov chains and its applications. *Journal of Computer and System Sciences*, 95:55–68, 2018.

[10] John A Holbrook, David W Kribs, and Raymond Laflamme. Noiseless subsystems and the structure of the commutant in quantum error correction. *Quantum Information Processing*, 2:381–419, 2003.

[11] R. A. Horn and C. R. Johnson. *Matrix Analysis*. Cambridge University Press, 2013.

[12] Goran Lindblad. On the generators of quantum dynamical semigroups. *Communications in mathematical physics*, 48:119–130, 1976.

[13] Alexander Müller-Hermes, David Reeb, and Michael M Wolf. Quantum subdivision capacities and continuous-time quantum coding. *IEEE Transactions on Information Theory*, 61(1):565–581, 2014.

[14] Claude Shannon. The zero error capacity of a noisy channel. *IRE Transactions on Information Theory*, 2(3):8–19, 1956.

[15] Satvik Singh, Mizanur Rahaman, and Nilanjana Datta. Zero-error communication, scrambling, and ergodicity. *arXiv preprint arXiv:2402.18703v1*, 2024. Available at https://arxiv.org/abs/2402.18703v1.
[16] Satvik Singh, Mizanur Rahaman, and Nilanjana Datta. Zero-error communication under discrete-time markovian dynamics. *arXiv preprint arXiv:2402.18703v2*, 2024. Available at https://arxiv.org/abs/2402.18703v2.

[17] Mostafa Taheri. https://github.com/mostafataheri75/structure-of-the-peripheral-subspace.

[18] Robert Tarjan. Depth-first search and linear graph algorithms. *SIAM journal on computing*, 1(2):146–160, 1972.

[19] Barbara M. Terhal. Quantum error correction for quantum memories. *Rev. Mod. Phys.*, 87:307–346, Apr 2015.

[20] John Watrous. *The Theory of Quantum Information*. Cambridge University Press, 2018.

[21] Michael M. Wolf. Quantum channels and operations - guided tour, 2012. Graue Literatur.

[22] Vrej Zarikian. Algorithms for operator algebra calculations. preprint, 2003.