# Computational aspects of the trace norm contraction coefficient

Idris Delsol, Omar Fawzi, Jan Kochanowski, Akshay Ramachandran

► To cite this version:

Idris Delsol, Omar Fawzi, Jan Kochanowski, Akshay Ramachandran. Computational aspects of the trace norm contraction coefficient. 2025. hal-05273305

HAL Id: hal-05273305

https://hal.science/hal-05273305v1

Preprint submitted on 22 Sep 2025

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

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

<figure><img src="image_1.png" /></figure>
# Computational aspects of the trace norm contraction coefficient

Idris Delsol *

Omar Fawzi *

Jan Kochanowski †

Akshay Ramachandran *

## Abstract

We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. We also establish the NP-hardness of deciding if the contraction coefficient is equal to 1, i.e., the channel can perfectly preserve a bit. As a consequence, deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.

# 1 Introduction

A central question in information theory is how to optimally encode information for a given noise model. The objective of this paper is to study this question from an algorithmic point of view: given as input an explicit classical description of a quantum channel $\Phi$ that represents the noise and an integer $k$, what is the maximum success probability that can be achieved for sending $k$ messages using $\Phi$? When $\Phi$ is a classical channel, Barman and Fawzi [1] showed that this problem is NP-hard to approximate within a factor greater than $1 - e^{-1}$ and that efficient algorithms matching this hardness exist. When $\Phi$ is a quantum channel, much less is known about the complexity of the problem. When $\Phi$ is given implicitly as a quantum circuit on $n$ qubits, this problem is known to be QMA-hard [2, 6]. Approximation algorithms have been proposed for some variants of the problem [3, 11, 19] but the guarantees are in general significantly weaker than the case of classical channels. In fact, the complexity of finding the optimal encoding of a single bit ($k = 2$), which has a trivial efficient algorithm in the classical case, remains unknown.

## 1.1 Main results

The main focus of this paper is to study the maximal success probability $P_{succ}(\Phi, 2)$ for transmitting a bit over the quantum channel $\Phi$. It is simple to connect this expression to the trace norm contraction coefficient (see Proposition 4 for details) of the channel $\Phi$:

$$P_{succ}(\Phi, 2) = \frac{1}{2} + \frac{1}{2}\eta_{tr}(\Phi)$$

where the contraction coefficient is defined as follows.

**Definition 1.** The trace norm contraction coefficient of a channel $\Phi$ is

$$\eta_{tr}(\Phi) = \max_{\substack{\rho,\sigma \in \mathcal{D} \\ \rho \neq \sigma}} \frac{\|\Phi(\rho) - \Phi(\sigma)\|_1}{\|\rho - \sigma\|_1}, \quad (1)$$

where $\mathcal{D}$ is the set of density operators on the input space of $\Phi$.

<footnote>*Inria, ENS Lyon, UCBL, LIP, F-69342 Lyon Cedex 07, France</footnote>

<footnote>†Inria, Télécom Paris - LTCI, Institut Polytechnique de Paris, 91120 Palaiseau, France</footnote>
As such, computing the trace norm contraction coefficient is equivalent to computing the optimal success probability and we focus in the following on the contraction coefficient. We start by establishing hardness results. The first result establishes hardness of approximation within a constant factor.

**Theorem 2 (General hardness).** Given a channel $\Phi$, its contraction coefficient $\eta_{tr}(\Phi)$ is NP-hard to approximate to a factor $1/\sqrt{2} + \varepsilon$ for any $\varepsilon > 0$. The hardness result holds even if $\Phi$ is promised to be unital.

Furthermore, even in the restricted setting where $\Phi$ is promised to be a quantum-classical (i.e., quantum input and classical output) and unital channel, the contraction coefficient is NP-hard to approximate to a factor $\sqrt{2}/\pi + \varepsilon$ for any $\varepsilon > 0$.

This result is proven in Section 3 and is based on a reduction from the Little Grothendieck Problem. We remark that for some special classes of channels, the contraction coefficient can be approximated efficiently. For example, if the channel $\Phi$ is composed $t$ times with $t \to \infty$, the optimal success probability and hence the contraction coefficient can be efficiently computed [10, 22].

Our second result shows that the question of deciding whether $\eta_{tr}(\Phi) = 1$ or $\eta_{tr}(\Phi) < 1$ is also NP-hard.

**Theorem 3 (Hardness for the complete case).** Given a quantum channel $\Phi$, it is NP-hard to distinguish between $\eta_{tr}(\Phi) = 1$ and $\eta_{tr}(\Phi) \le 1 - \Omega(\frac{1}{n^3})$, where $n$ is the dimension of the input Hilbert space.

In terms of channel coding, this corresponds to deciding the existence of a perfect, i.e., zero-error, encoding of a bit. The existence of a zero-error code of size $k$ for a quantum channel $\Phi$ is equivalent to the independence number of the corresponding non-commutative confusability graph of $\Phi$ being greater or equal to $k$ [9]. A non-commutative graph is a subspace $S$ of matrices containing the identity and satisfying $S = S^*$, which is more commonly also known as an operator system.<fnref n="1" /> Theorem 3 shows that deciding whether a non-commutative graph has independence number at least 2 is NP-hard. Note that in the model where the channel is described implicitly by a circuit, the hardness of this problem was studied in depth in [6].

A consequence of this work is that known efficiently computable bounds on the contraction coefficient such as the quantum Doeblin coefficient [14, 16] cannot be always tight, assuming $P \ne NP$. In fact, we give in Proposition 25 an explicit example of channel $\Phi$ where the Doeblin coefficient fails to capture $\eta_{tr}(\Phi) < 1$.

Our final result is applying the methodology of [3] for constrained bilinear problems to obtain a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient (Theorem 26). We illustrate this hierarchy by applying it to some simple channels (Fig. 1, Fig. 2). On all the examples we tried, the first level of our hierarchy gives bounds that are tighter than the quantum Doeblin coefficient introduced in [16]. We note that [14, Corollary 3] considered a semidefinite programming hierarchy for a variant of the Doeblin coefficient called the induced Doeblin coefficient. This hierarchy is different from ours as it cannot converge to the contraction coefficient. In fact, as shown in Proposition 25, the induced Doeblin coefficient fails to capture $\eta_{tr}(\Phi) < 1$.

## 2 Notation and basic statements

In this paper, all Hilbert spaces $\mathcal{H}$ are finite dimensional. We write $\mathcal{B}(\mathcal{H})$ for the set of linear operators from $\mathcal{H}$ to itself. The state of a quantum system modeled by $\mathcal{H}$ is described by a density operator, i.e., a positive and unit trace operator in $\mathcal{B}(\mathcal{H})$. We denote by $\mathcal{D}(\mathcal{H})$ the set of such density operators. Physically possible transformations are mathematically represented by completely positive trace-preserving maps, also called quantum channels. For every quantum channel $\Phi : \mathcal{B}(\mathcal{H}) \to \mathcal{B}(\mathcal{H}')$, we can find a set of operators $\{K_i : K_i \in \mathcal{B}(\mathcal{H}', \mathcal{H})\}$ satisfying $\sum_i K_i^* K_i = I$ such that for all $x \in \mathcal{B}(\mathcal{H})$:

$$ \Phi(x) = \sum_{i} K_{i}xK_{i}^{*}. \qquad (2) $$

<footnote n="1">¹The way to see an undirected graph $G = (V, E)$ in this setting is by choosing $S = \text{Span}\{E_{i,j} : i, j \in V, i = j \text{ or } (i, j) \in E\}$, where $E_{i,j}$ is the matrix containing 1 in position $(i, j)$ and zero everywhere else.</footnote>
These operators are called Kraus operators of the channel $\Phi$ and there is a Kraus representation of $\Phi$ using at most $\dim(\mathcal{H}) \dim(\mathcal{H}')$ such operators. The Choi state of $\Phi$ is denoted as

$$J(\Phi) = (\mathrm{Id}_{\mathcal{H}} \otimes \Phi)(|\psi^+\rangle\langle\psi^+|), \qquad (3)$$

where $|\psi^+\rangle = \frac{1}{\sqrt{\dim(\mathcal{H})}} \sum_{i=1}^{\dim(\mathcal{H})} |i\rangle|i\rangle$ for some fixed orthonormal basis $|i\rangle$ of $\mathcal{H}$. Given $\Phi$ a channel, we note A its input system and B its output system, so that $J(\Phi)$ is a bipartite state on the compound system $(A, B)$. We will therefore write $J(\Phi)_{AB}$ the Choi state of $\Phi$, whenever the systems on which $J(\Phi)$ acts may be ambiguous, especially in Section 5. Given $S$ a physical system, we use the shorthand notation $d_S := \dim(S)$. We denote $\Phi^*$ for the adjoint (also called the dual) of the map $\Phi : \mathcal{B}(\mathcal{H}) \to \mathcal{B}(\mathcal{H}')$, i.e., we have $\langle\Phi(X), Y\rangle = \langle X, \Phi^*(Y)\rangle$ for all $X \in \mathcal{B}(\mathcal{H}), Y \in \mathcal{B}(\mathcal{H}')$. Here, $\langle\cdot, \cdot\rangle$ is the Hilbert-Schmidt inner product $\langle A, B\rangle = \mathrm{tr}(A^*B)$. Note that $\Phi$ is a quantum channel if and only if $\Phi^*$ is completely positive and unital, i.e., $\Phi^*(I) = I$.

We now give a precise definition for the optimal success probability $\mathbb{P}_{\mathrm{succ}}(\Phi, k)$ for transmitting $k$ messages over the channel $\Phi$. A Positive Operator Valued Measure, or POVM, on a space $\mathcal{B}(\mathcal{H})$ is a collection of positive operators $\{M_i : i\}$ such that $\sum_i M_i = I$. We define

$$\mathbb{P}_{\mathrm{succ}}(\Phi, k) = \max_{\begin{subarray}{l} \{M_i : 1 \le i \le k\} \text{ POVM}, \\ \{\rho_i \in \mathcal{D}(\mathcal{H}) : 1 \le i \le k\} \end{subarray}} \frac{1}{k} \sum_{i=1}^{k} \mathrm{tr}(M_i \Phi(\rho_i)). \qquad (4)$$

We now relate $\mathbb{P}_{\mathrm{succ}}(\Phi, 2)$ to $\eta_{\mathrm{tr}}(\Phi)$ using the Holevo-Helstrom theorem.

**Proposition 4.** Let $\Phi$ be a channel, then

$$\mathbb{P}_{\mathrm{succ}}(\Phi, 2) = \frac{1}{2} + \frac{1}{2}\eta_{\mathrm{tr}}(\Phi). \qquad (5)$$

*Proof.* For any $\rho_1, \rho_2 \in \mathcal{D}(\mathcal{H})$ and any 2-outcome POVM $\{M_1, I - M_1\}$,

$$\begin{align*}
\frac{1}{2} \mathrm{tr}(M_1 \Phi(\rho_1) + (I - M_1) \Phi(\rho_2)) &= \frac{1}{2} + \frac{1}{2} \mathrm{tr}(M_1(\Phi(\rho_1) - \Phi(\rho_2))) \\
&\stackrel{(a)}{\le} \frac{1}{2} + \frac{1}{4} \|\Phi(\rho_1) - \Phi(\rho_2)\|_1 \\
&\stackrel{(a)}{\le} \frac{1}{2} + \frac{1}{2} \frac{\|\Phi(\rho_1) - \Phi(\rho_2)\|_1}{\|\rho_1 - \rho_2\|_1}
\end{align*}$$

where we used the Holevo-Helstrom theorem [15] for (a). For the other direction, we first use Lemma 5 below and choose $\rho_1, \rho_2$ orthogonal, i.e., $\|\rho_1 - \rho_2\|_1 = 2$, such that $\eta_{\mathrm{tr}}(\Phi) = \frac{1}{2}\|\Phi(\rho_1) - \Phi(\rho_2)\|_1$. Then $M_1$ is the positive part of $\Phi(\rho_1) - \Phi(\rho_2)$. $\square$

We summarize in Table 1 the notation used in this paper.

# 3 NP-hardness of computing the trace norm contraction coefficient

In this section, we prove Theorem 2 by reducing the Hermitian non-commutative (resp. real commutative) Little Grothendieck Problem to the problem of computing $\eta_{\mathrm{tr}}(\Phi)$ (resp. computing $\eta_{\mathrm{tr}}(\Phi)$, for $\Phi$ a quantum classical channel). The complexities of various Grothendieck problems are studied in depth in [5] and [17].

Before introducing the Hermitian non-commutative Little Grothendieck Problem let us first reduce the two-parameter optimisation problem which defines $\eta_{\mathrm{tr}}(\Phi)$ into a single-parameter optimisation. Ruskai showed in [20] the following lemma.
<table><caption>Table 1: Notations used throughout this paper</caption><thead><tr><th>Symbol</th><th>Meaning</th><th>Equation</th></tr></thead><tbody><tr><td><i>H</i></td><td>A finite dimensional Hilbert space</td><td></td></tr><tr><td><i>B</i>(<i>H</i>)</td><td>The set of linear operators on <i>H</i></td><td></td></tr><tr><td>Herm(<i>H</i>)</td><td>The set of Hermitian operator on <i>H</i></td><td></td></tr><tr><td><i>D</i>(<i>H</i>)</td><td>The set of density operators on <i>H</i></td><td></td></tr><tr><td><i>I</i> ∈ <i>B</i>(<i>H</i>)</td><td>The identity operator in <i>B</i>(<i>H</i>)</td><td></td></tr><tr><td>Id<sub>n</sub>(.)</td><td>The identity channel on <i>B</i>(<i>C</i><sup>n</sup>)</td><td></td></tr><tr><td>ρ, σ</td><td>Quantum states</td><td></td></tr><tr><td><i>A</i>, <i>B</i>, <i>Ā</i>, <i>B̄</i></td><td>Physical systems</td><td></td></tr><tr><td><i>d</i><sub>S</sub></td><td>Dimension of system <i>S</i></td><td></td></tr><tr><td>Φ</td><td>A quantum channel</td><td></td></tr><tr><td><i>J</i>(Φ)</td><td>The Choi state of Φ</td><td>Eq. (3)</td></tr><tr><td>η<sub>tr</sub>(Φ)</td><td>The trace norm contraction coefficient of Φ</td><td>Eq. (1)</td></tr><tr><td><i>P</i><sub>succ</sub>(Φ, <i>k</i>)</td><td>Opt. success prob. of encoding <i>k</i> messages in Φ</td><td>Eq. (4)</td></tr><tr><td><i>G</i><sub>Φ</sub></td><td>The quantum graph associated to Φ</td><td>Eq. (34)</td></tr><tr><td>||·||<sub>1</sub></td><td>The Schatten 1-norm, a.k.a. the trace norm</td><td></td></tr><tr><td>||·||<sub>2</sub></td><td>The Schatten 2-norm, a.k.a. the Frobenius norm</td><td></td></tr><tr><td>||·||<sub>∞</sub></td><td>The Schatten ∞-norm, a.k.a. the operator norm</td><td></td></tr><tr><td>||·||<sub><i>ℓ</i><sub>p</sub></sub></td><td>The <i>ℓ</i><sub>p</sub> norms</td><td></td></tr><tr><td><i>S</i><sub><i>p</i></sub><sup>n</sup>, <i>p</i> ∈ [1, ∞]</td><td>The complex Banach space (<i>B</i>(<i>C</i><sup>n</sup>), ||·||<sub><i>p</i></sub>)</td><td></td></tr><tr><td><i>S</i><sub><i>p</i></sub><sup>H,n</sup>, <i>p</i> ∈ [1, ∞]</td><td>The real Banach space (Herm(<i>C</i><sup>n</sup>), ||·||<sub><i>p</i></sub>)</td><td></td></tr><tr><td><i>ℓ</i><sub><i>p</i></sub><sup>n</sup>(<i>R</i>), <i>p</i> ∈ [1, ∞]</td><td>The real Banach space (<i>R</i><sup>n</sup>, ||·||<sub><i>ℓ</i><sub>p</sub></sub>)</td><td></td></tr><tr><td>[<i>n</i>], <i>n</i> ∈ <i>N</i></td><td>The integer set {1, ..., <i>n</i>}</td><td></td></tr><tr><td>conv{<i>S</i>}</td><td>The convex hull of the set <i>S</i></td><td>Eq. (32)</td></tr><tr><td><i>E</i><sub><i>i,j</i></sub></td><td>Matrix with 1 in position (<i>i</i>, <i>j</i>) and 0 elsewhere</td><td></td></tr></tbody></table>
**Lemma 5** ([20], Theorem 2; see also Lemma 8.3 of [24]). For a quantum channel $\Phi: \mathcal{B}(\mathcal{H}) \to \mathcal{B}(\mathcal{H}')$,

$$ \eta_{\text{tr}}(\Phi) = \max_{\rho, \sigma \in \mathcal{D}(\mathcal{H}), \rho \perp \sigma} \frac{1}{2} \|\Phi(\rho) - \Phi(\sigma)\|_1, \qquad (6) $$

where $\rho \perp \sigma$ means $\rho$ and $\sigma$ have orthogonal supports. In addition, the maximizing states can be taken pure.

From this lemma, we can reduce the problem of computing the contraction coefficient to the following optimisation problem over Hermitian operators in the unit ball for the Schatten $\infty$-norm:

**Lemma 6.** For a quantum channel $\Phi: \mathcal{B}(\mathcal{H}) \to \mathcal{B}(\mathcal{H}')$,

$$ \eta_{\text{tr}}(\Phi) = \frac{1}{2} \max_{X^*=X, \|X\|_{\infty} \le 1} (\lambda_{\max} - \lambda_{\min})(\Phi^*(X)), \qquad (7) $$

where, for any Hermitian operator $O$, $\lambda_{\max}(O)$, respectively $\lambda_{\min}(O)$, is the maximal, respectively minimal, eigenvalue of $O$.

*Proof.* In the following equations, the vectors $u, v$ are taken of unit length, i.e., $\|u\|_{\ell_2} = \|v\|_{\ell_2} = 1$. By Lemma 5,

$$ \begin{aligned} \eta_{\text{tr}}(\Phi) &= \frac{1}{2} \max_{u,v \in \mathcal{H}, u \perp v} \|\Phi(uu^*) - \Phi(vv^*)\|_1 \\ &\stackrel{(a)}{=} \frac{1}{2} \max_{u,v \in \mathcal{H}, u \perp v} \max_{X^*=X, \|X\|_{\infty} \le 1} |\langle\Phi(uu^* - vv^*), X\rangle| \\ &= \frac{1}{2} \max_{u,v \in \mathcal{H}, u \perp v} \max_{X^*=X, \|X\|_{\infty} \le 1} |\langle uu^* - vv^*, \Phi^*(X)\rangle| \\ &= \frac{1}{2} \max_{X^*=X, \|X\|_{\infty} \le 1} (\lambda_{\max} - \lambda_{\min})(\Phi^*(X)), \end{aligned} $$

where (a) follows from the Hölder duality between the trace and operator norm as well as the fact that $\Phi$ is Hermitian preserving and the last step follows directly from writing an eigendecomposition of $\Phi^*(X)$ and using the fact that $u$ and $v$ have norm 1. $\square$

Hence as claimed the optimisation problem Lemma 6 is only over a single parameter.

We now switch our focus to the Little Grothendieck Problems, which we will reduce to the computation of the contraction coefficient. A Banach space $X = (\mathcal{X}, \| \cdot \|_X)$ is a linear space $\mathcal{X}$ endowed with a norm $\| \cdot \|_X$ with respect to which $\mathcal{X}$ is complete. For any linear map $\mathcal{F}: X \to Y$ between two Banach spaces, its operator norm is defined as

$$ \| \mathcal{F} \|_{X \to Y} = \sup_{\|a\|_X \le 1} \| \mathcal{F}(a) \|_Y, \qquad (8) $$

i.e., the supremum of $\| \mathcal{F}(a) \|_Y$ when $a$ ranges in the unit ball of $X$. The Little Grothendieck Problems are all stated as problems concerning computations of such operator norms of linear maps $\mathcal{F}$ between certain Banach spaces. By abuse of notation, we write $\mathbb{R}^n$ for the Banach space obtained when we endow $\mathbb{R}^n$ with the $\ell_2$ norm. We write $\ell_1^n(\mathbb{R})$ the Banach space $\mathbb{R}^n$ endowed with the $\ell_1$ norm and analogously $\ell_\infty^n(\mathbb{R})$ for the Banach space $(\mathbb{R}^n, \| \cdot \|_{\ell_\infty})$. Furthermore, we write $S_1^n = (\mathcal{B}(\mathbb{C}^n), \| \cdot \|_1)$ and $S_\infty^n = (\mathcal{B}(\mathbb{C}^n), \| \cdot \|_\infty)$ the Banach spaces of complex $n \times n$ matrices endowed with the Schatten 1- and $\infty$-norm (the former being also called the trace norm and the latter the operator norm). Moreover, we write $S_1^{H,n} = (\text{Herm}(\mathbb{C}^n), \| \cdot \|_1)$ and $S_\infty^{H,n} = (\text{Herm}(\mathbb{C}^n), \| \cdot \|_\infty)$ the (real) Banach spaces of $n \times n$ Hermitian complex matrices endowed with, respectively, the Schatten 1- and $\infty$-norm. The real commutative Little Grothendieck Problem consists in computing $\| \mathcal{F} \|_{\mathbb{R}^n \to \ell_1^d(\mathbb{R})}$ for $\mathcal{F}: \mathbb{R}^n \to \ell_1^d(\mathbb{R})$ a linear operator. This problem can be generalized to non-commutative settings by taking $\mathcal{F}$ operator-valued. The variant we use for our proof is the Hermitian non-commutative Little Grothendieck Problem, which can be stated as computing $\| \mathcal{F} \|_{\mathbb{R}^n \to S_1^{H,d}}$, given a linear operator $\mathcal{F}: \mathbb{R}^n \to S_1^{H,d}$ with output space endowed with the Schatten 1-norm.

Briët et al. proved the following hardness theorems for the commutative and Hermitian non-commutative Little Grothendieck Problem in [5].
**Theorem 7 (Theorem 1.3 in [5]).** For any constant $\varepsilon > 0$, it is NP-hard to approximate the real commutative Little Grothendieck Problem to within a factor greater than $\sqrt{2}/\pi + \varepsilon$.

**Theorem 8 (Theorem 1.2 and Sec. 5.1 in [5]).** For any constant $\varepsilon > 0$, it is NP-hard to approximate the Hermitian non-commutative Little Grothendieck Problem to within a factor greater than $1/\sqrt{2} + \varepsilon$.

Finally note that we can express the Little Grothendieck Problems in terms of the dual of $\mathcal{F}$ as per the argument given in Section 6 of [5]. Indeed, for any Banach spaces $X, Y$ and any linear map $\mathcal{F}: X \to Y$, it is a standard fact that the operator norm of $\mathcal{F}$ is equal to that of its dual $\mathcal{F}^*: Y^* \to X^*$, i.e. $\|\mathcal{F}\|_{X \to Y} = \|\mathcal{F}^*\|_{Y^* \to X^*}$. For the Hermitian non-commutative Little Grothendieck Problem, we have $\mathcal{F}: \mathbb{R}^n \to S_1^{H,d}$, $\mathbb{R}^n$ is a Hilbert space and thus self-dual and the dual of $S_1^{H,d}$ is $S_\infty^{H,d}$, hence $\mathcal{F}^*: S_\infty^{H,d} \to \mathbb{R}^n$. Therefore,

$$ \|\mathcal{F}\|_{\mathbb{R}^n \to S_1^{H,d}} = \|\mathcal{F}^*\|_{S_\infty^{H,d} \to \mathbb{R}^n} = \sup_{\|Y\|_\infty \le 1, Y^*=Y} \|\mathcal{F}^*(Y)\|_{\ell_2}. \quad (9) $$

Since the action of a linear map $\mathcal{F}: \mathbb{R}^n \to S_1^{H,d}$ is fully determined by where it maps a basis of $\mathbb{R}^n$ to, for all $x \in \mathbb{R}^n$ we can write:

$$ \mathcal{F}(x) = \sum_{i=1}^{n} x_i F_i, \quad (10) $$

with, for all $i \in [n]$, $F_i = \mathcal{F}(e_i) \in S_1^{H,d}$, with $\{e_i: 1 \le i \le n\}$ the canonical basis of $\mathbb{R}^n$. Then we can express $\mathcal{F}^*$ as:

$$ \forall Y \in S_\infty^{H,d}: \quad \mathcal{F}^*(Y) = (\langle F_i, Y \rangle)_{i \in [n]}. \quad (11) $$

Therefore,

$$ \|\mathcal{F}\|_{\mathbb{R}^n \to S_1^{H,d}} = \|\mathcal{F}^*\|_{S_\infty^{H,d} \to \mathbb{R}^n} = \sup_{\|Y\|_\infty \le 1, Y^*=Y} \|\langle F_i, Y \rangle\|_{i \in [n]} \|\ell_2. \quad (12) $$

The same line of argument also holds mutatis mutandis for the real commutative Little Grothendieck Problem. In this case, we have $\mathcal{F}: \mathbb{R}^n \to \ell_1^d(\mathbb{R})$, we write for all $x \in \mathbb{R}^n$

$$ \mathcal{F}(x) = \sum_{i=1}^{n} x_i f_i, $$

with $\{f_i = \mathcal{F}(e_i) \in \mathbb{R}^d: 1 \le i \le n\}$. Then, for all $y \in \mathbb{R}^d$,

$$ \mathcal{F}^*(y) = (\langle f_i, y \rangle)_{i \in [n]}, $$

and

$$ \|\mathcal{F}\|_{\mathbb{R}^n \to \ell_1^d(\mathbb{R})} = \|\mathcal{F}^*\|_{\ell_\infty^d(\mathbb{R}) \to \mathbb{R}^n} = \sup_{\|y\|_{\ell_\infty} \le 1} \|\mathcal{F}^*(y)\|_{\ell_2}. $$

We now have all the tools to prove Theorem 2.

*Proof of Theorem 2.* We start with the hardness result for unital channels as it implies the one for general channels. Let $\mathcal{F}: \mathbb{R}^n \to S_1^{H,d}$ be a linear map, and let $\{F_i = \mathcal{F}(e_i): 1 \le i \le n\}$, with $\{e_i \in \mathbb{R}^n: i \in [n]\}$ the canonical basis of $\mathbb{R}^n$, so that, for all $x \in \mathbb{R}^n$,

$$ \mathcal{F}(x) = \sum_{i=1}^{n} x_i F_i. \quad (13) $$

The proof then proceeds in two steps. First, we construct a unital channel $\Phi_\alpha$ out of $\mathcal{F}$, then, we relate the difference $(\lambda_{\max} - \lambda_{\min})(\Phi_\alpha^*(Y))$ to $\|\mathcal{F}^*(Y)\|_{\ell_2}$. Finally, we use on the one hand Lemma 5 to deduce
$\eta_{\text{tr}}(\Phi_{\alpha})$ from the difference $(\lambda_{\text{max}} - \lambda_{\text{min}})(\Phi_{\alpha}^{*}(Y))$ and, on the other, that, from Theorem 8, it is NP-hard to maximise $\|\mathcal{F}^{*}(Y)\|_{\ell_2}$ on the operators $Y \in S_{\infty}^{H,d}$, with $\|Y\|_{\infty} \le 1$, to then conclude that it is also NP-hard to compute $\eta_{\text{tr}}(\Phi_{\alpha})$.

Thus, let us perform some changes to $\mathcal{F}$ so as to construct a valid quantum channel. Let $k \in \mathbb{N}$ be such that $2kd \ge n + 1$. Let $\tilde{\mathcal{F}}: \mathbb{R}^n \to S_1^{H,2kd}$ be the linear map defined as

$$ \forall x \in \mathbb{R}^n, \quad \tilde{\mathcal{F}}(x) = \sum_{i=1}^{n} x_i \oplus_{s=1}^{k} (F_i \oplus (-F_i)) = \begin{pmatrix} \mathcal{F}(x) & & & \\ & -\mathcal{F}(x) & & \\ & & \ddots & \\ & & & \mathcal{F}(x) \\ & & & -\mathcal{F}(x) \end{pmatrix}. \quad (14) $$

Then, $\tilde{\mathcal{F}}^*(I_{2kd}) = (\langle \oplus_{s=1}^k (F_i \oplus (-F_i)), I_{2kd} \rangle)_{i \in [n]} = (k[\langle F_i, I_d \rangle - \langle F_i, I_d \rangle])_{i \in [n]} = 0$. Furthermore, for all $x \in \mathbb{R}^n$, $\|\tilde{\mathcal{F}}(x)\|_1 = 2k\|\mathcal{F}(x)\|_1$, so that

$$ \| \mathcal{F} \|_{\mathbb{R}^n \to S_1^{H,d}} = \frac{1}{2k} \| \tilde{\mathcal{F}} \|_{\mathbb{R}^n \to S_1^{H,2kd}}. \quad (15) $$

We write $\{\tilde{F}_i = \tilde{\mathcal{F}}(e_i) = \oplus_{s=1}^k (F_i \oplus (-F_i)) : 1 \le i \le n\}$. Let $\Psi: \mathcal{B}(\mathbb{C}^{2kd}) \to \mathcal{B}(\mathbb{C}^{n+1}) \subseteq \mathcal{B}(\mathbb{C}^{2kd})$ be defined as:

$$ \forall Y \in \mathcal{B}(\mathbb{C}^{2kd}), \quad \Psi(Y) = \left( \sum_{i=1}^{n} \langle \tilde{F}_i, Y \rangle e_i \right) e_{n+1}^{T} + e_{n+1} \left( \sum_{i=1}^{n} \langle \tilde{F}_i, Y \rangle e_i \right)^{T} = \tilde{\mathcal{F}}^{*}(Y) e_{n+1}^{T} + \tilde{\mathcal{F}}^{*}(Y)^{T} e_{n+1}. \quad (16) $$

Note that $\Psi$ is linear over $\mathbb{C}$, so that we can turn it into the dual of a unital channel $\Phi$ by shifting and renormalizing. Let $\Phi_{\alpha}^{*}$ be defined as:

$$ \forall Y \in \mathcal{B}(\mathbb{C}^{2kd}), \quad \Phi_{\alpha}^{*}(Y) := \alpha \Psi(Y) + \frac{\text{tr}(Y)}{2kd} I_{2kd}, \quad (17) $$

with $\alpha > 0$. For $\alpha$ small enough, $\Phi_{\alpha}^{*}$ is completely positive (cf. [23]). Furthermore, as $\tilde{\mathcal{F}}^*(I_{2kd}) = 0$, $\Phi_{\alpha}^{*}$ is unital, so that, for $\alpha$ small enough, $\Phi_{\alpha}$ is a channel. Moreover, it is easy to see that the output of $\Psi$ is always traceless, so that $\Phi_{\alpha}^{*}$ is trace preserving. Thus, its dual $\Phi_{\alpha}$ is also unital. Finally, remark that, for $Y \in \text{Herm}(\mathbb{C}^{2kd})$,

$$ (\lambda_{\text{max}} - \lambda_{\text{min}})(\Phi_{\alpha}^{*}(Y)) = (\lambda_{\text{max}} - \lambda_{\text{min}})(\alpha\Psi(Y)) \quad (18) $$

$$ \stackrel{(a)}{=} 2\alpha \| (\langle \tilde{F}_i, Y \rangle)_{i \in [n]} \|_{\ell_2} \quad (19) $$

$$ = 2\alpha \| \tilde{\mathcal{F}}^*(Y) \|_{\ell_2} \quad (20) $$

$$ = 4k\alpha \| \mathcal{F}^*(Y) \|_{\ell_2}, \quad (21) $$

where (a) follows from the fact that any operator $A = be^* + eb^*$ with $e \perp b$ satisfies $\lambda_{\text{max}}(A) = -\lambda_{\text{min}}(A) = 2\|b\|_{\ell_2}\|e\|_{\ell_2}$. Note that because $\tilde{F}_i$ and $Y$ are Hermitian, the vector $\sum_{i=1}^n \langle \tilde{F}_i, Y \rangle e_i$ is real so its transpose and complex conjugate are the same. Thus, combining the last system of equations with both Eq. (9) and Lemma 6, we have that:

$$ \| \mathcal{F} \|_{\mathbb{R}^n \to S_1^{H,d}} = 2k\alpha \cdot \eta_{\text{tr}}(\Phi_{\alpha}), $$

which ends the reduction and shows by Theorem 8 that it is NP-hard to approximate $\eta_{\text{tr}}(\Phi_{\alpha})$ to within a factor $1/\sqrt{2} + \varepsilon$ for $\varepsilon > 0$.
Let us now move to the second point of Theorem 2 about quantum-classical channels. The proof uses exactly the same techniques as the proof of the first point. In fact, given $\mathcal{F}: \mathbb{R}^n \to \ell_1^d(\mathbb{R})$, we write as before $\mathcal{F}(e_i) = f_i \in \mathbb{R}^d$ for $\{e_i\}_{i \in [n]}$ the canonical basis of $\mathbb{R}^n$. Then,

$$ \mathcal{F}(x) = \sum_{i=1}^{n} x_i f_i, \qquad \mathcal{F}^*(y) = \sum_{i=1}^{n} \langle f_i, y \rangle e_i, \qquad (22) $$

with $\mathcal{F}^*: \ell_\infty^d(\mathbb{R}) \to \mathbb{R}^n$ the dual of $\mathcal{F}$. Similarly to the general quantum case, we set $\tilde{f}_i = \oplus_{s=1}^k (f_i \oplus (-f_i)) \in \mathbb{R}^{2kd}$ with $k$ such that $2kd \ge n+1$ and $\tilde{F}_i = \text{diag}(\tilde{f}_i)$ the diagonal $2d \times 2d$ matrix whose diagonal entries are the entries of $\tilde{f}_i$. We then define the map $\Psi: \mathcal{B}(\mathbb{C}^{2kd}) \to \mathcal{B}(\mathbb{C}^{n+1})$:

$$ \forall Y \in S_{\infty}^{2kd}, \quad \Psi(Y) = \left( \sum_{i=1}^{n} \langle \tilde{F}_i, Y \rangle e_i \right) e_{n+1}^T + e_{n+1} \left( \sum_{i=1}^{n} \langle \tilde{F}_i, Y \rangle e_i \right)^T. \qquad (23) $$

Then, for $\alpha > 0$ small enough, the map $\Phi_\alpha^*$ defined as

$$ \forall Y \in \mathcal{B}(\mathbb{C}^{2kd}), \quad \Phi_{\alpha}^{*}(Y) = \alpha \Psi(Y) + \frac{\text{tr}(Y)}{2d} I_{n+1}, \qquad (24) $$

is unital completely positive and trace preserving, so that $\Phi_\alpha$ is a unital channel. Note that, as the $\tilde{F}_i$ are diagonal, $\Phi_\alpha$ is a quantum-classical channel, i.e., its output is diagonal for all inputs. Finally, using Lemma 6,

$$ \eta_{\text{tr}}(\Phi_{\alpha}) = \frac{1}{2} \sup_{Y^*=Y, \|Y\|_{\infty} \le 1} (\lambda_{\max} - \lambda_{\min})(\Phi_{\alpha}^*(Y)) \qquad (25) $$

$$ = \frac{\alpha}{2} \sup_{Y^*=Y, \|Y\|_{\infty} \le 1} (\lambda_{\max} - \lambda_{\min})(\Psi(Y)) \qquad (26) $$

$$ \stackrel{(a)}{=} \alpha \sup_{Y^*=Y, \|Y\|_{\infty} \le 1} \|(\langle \tilde{F}_i, Y \rangle)_{i \in [n]}\|_{\ell_2} \qquad (27) $$

$$ \stackrel{(b)}{=} \alpha \sup_{y \in \mathbb{R}^{2d}, \|y\|_{\ell_{\infty}} \le 1} \|(\langle \tilde{f}_i, y \rangle)_{i \in [n]}\|_{\ell_2} \qquad (28) $$

$$ = 2k\alpha \sup_{y \in \mathbb{R}^d, \|y\|_{\ell_{\infty}} \le 1} \|(\langle f_i, y \rangle)_{i \in [n]}\|_{\ell_2} \qquad (29) $$

$$ = 2k\alpha \| \mathcal{F}^* \|_{\ell_\infty^d(\mathbb{R}) \to \mathbb{R}^n} \qquad (30) $$

$$ = 2k\alpha \| \mathcal{F} \|_{\mathbb{R}^n \to \ell_1^d(\mathbb{R})}, \qquad (31) $$

Finally by Theorem 7 it is NP-hard to approximate $\| \mathcal{F} \|_{\mathbb{R}^n \to \ell_1^d(\mathbb{R})}$ to a factor greater than $\sqrt{2/\pi} + \varepsilon$ for all $\varepsilon > 0$, from which we conclude that it is NP-hard to approximate $\eta_{\text{tr}}(\Phi_\alpha)$ to the same factors. $\square$

# 4 NP-hardness of the complete case

In the previous section, we showed that it is NP-hard to approximate the contraction coefficient of a channel. In this section we strengthen this result, showing it is NP-hard even in the ‘complete’ case where we want to test whether a channel has contraction coefficient 1.

For the proof, we use several characterizations of channels with $\eta_{\text{tr}}(\Phi) = 1$: one in terms of optimisation over separable states and the second one in terms of the confusability graph of $\Phi$. We start by defining the set of separable states.

**Definition 9 (Separable states).**

$$ \text{SEP}(\mathcal{H} \otimes \mathcal{H}') := \text{conv}\{\rho \otimes \sigma \mid \rho \in \mathcal{D}(\mathcal{H}), \sigma \in \mathcal{D}(\mathcal{H}')\} = \text{conv}\{uu^* \otimes vv^* \mid u \in \mathcal{H}, v \in \mathcal{H}'\}. \qquad (32) $$
For $A \in \mathcal{B}(\mathcal{H} \otimes \mathcal{H}')$,

$$ \ell_{\text{SEP}}(A) := \min_{X \in \text{SEP}(\mathcal{H} \otimes \mathcal{H}')'} \langle A, X \rangle = \min_{u \in \mathcal{H}, v \in \mathcal{H}'} \langle A, uu^* \otimes vv^* \rangle. \quad (33) $$

Now, we introduce the confusability graph of a channel. The *confusability graph* of a classical channel was introduced by Shannon in [21] to study the zero-error capacity of the channel. This graph has the set of inputs of the channel as its vertex set and two inputs are connected by an edge if and only if there is a non-zero probability that the channel maps them to the same output. This structure was generalized to quantum channels in [8].

**Definition 10** (Quantum confusability graph, Eq. 3 in [8]). For $\Phi: \mathcal{B}(\mathcal{H}) \to \mathcal{B}(\mathcal{H}')$ defined by $\Phi(x) = \sum_i K_i x K_i^*$, for all $x \in \mathcal{B}(\mathcal{H})$, its quantum confusability graph is

$$ G_{\Phi} = \text{Span}\{K_i^* K_j : i, j\}. \quad (34) $$

It is simple to see that $G_{\Phi}$ does not depend on the specific choice of Kraus operators and forms an operator system, i.e., a unital self-adjoint subset of $\mathcal{B}(\mathcal{H})$. In fact, any operator system is the confusability graph of some channel $\Phi$:

**Lemma 11** (Lemma 2 in [8]). For a subspace $S \subseteq \mathcal{B}(\mathbb{C}^n)$, there is a channel $\Phi$ such that $G_{\Phi} = S$ if and only if $S$ is self-adjoint (i.e., if $x \in S$ then $x^* \in S$) and contains the identity.

Furthermore, if $S$ is self-adjoint and contains the identity, we can choose a Hermitian basis $\{M_1, \dots, M_d\}$ for $S$ and construct a channel $\Phi: \mathcal{B}(\mathbb{C}^n) \to \mathcal{B}(\mathbb{C}^{n'})$ with $n'$ polynomial in $n$ with Kraus operators $\{K_i : 1 \le i \le d\}$, satisfying $G_{\Phi} = S$ and, for all $1 \le i, j \le d$, $K_i^* K_j = \delta_{i,j} M_i$. In addition, given such a basis of $S$, the Kraus operators of $\Phi$ can be computed in polynomial time in $n$.

**Remark 12.** The second paragraph of the previous Lemma is not in the statement of Lemma 2 of [8] but is explicitly shown in its proof in [8].

**Remark 13.** Note also that given $S \subseteq \mathcal{B}(\mathbb{C}^n)$ self-adjoint containing the identity, any channel $\Phi$ such that $G_{\Phi} = S$ and $K_i^* K_j = \delta_{i,j} M_i$ as in the second part of the previous lemma can not be chosen unital, unless $S = \mathcal{B}(\mathbb{C}^n)$, in which case one can trivially take $\Phi = \text{Id}_n(\cdot)$. Therefore, although we have shown in Theorem 2 that it is NP-hard to approximate $\eta_{\text{tr}}(\Phi)$ for $\Phi$ promised to be unital, we do not show that it is hard to decide whether $\eta_{\text{tr}}(\Phi) = 1$ for such a channel.

**Theorem 14.** Let $\Phi: \mathcal{B}(\mathcal{H}) \to \mathcal{B}(\mathcal{H}')$ be a quantum channel, then the following are equivalent

1. $\eta_{\text{tr}}(\Phi) = 1$;

2. there exists a rank-one matrix $x$ such that $x \in G_{\Phi}^{\perp}$;

3. $\ell_{\text{SEP}}(J(\Phi^* \circ \Phi)) = 0$.

This result follows from [8]; see [22, Theorem SI.11] for a synthesis of related characterizations.

We now introduce the NP-hard problem that we will embed into a channel $\Phi$ such that “yes” instances are mapped to channels satisfying the equivalent properties in Theorem 14 and “no” instances are mapped to channels that do not. The problem we use is Graph 2-CSP.

**Definition 15** (Graph 2-CSP, see Definition 3 in [13]). A constraint graph $G = (V, E)$ is an *undirected graph* (possibly with self-loops) along with a set $\Sigma$ of “colours” and a mapping $R_e: \Sigma \times \Sigma \to \{0, 1\}$ for each edge $e = (v, u) \in E$ (called the constraint to $e$). A mapping $\tau: V \to \Sigma$ (called a *colouring*) satisfies the constraint $R_e$ if $R_e(\tau(v), \tau(u)) = 1$ for an edge $e = (v, u)$ in $E$. The graph $G$ is said to be *satisfiable* if there is a colouring $\tau$ that satisfies all the constraints, while $G$ is said to be $(1-\eta)$-unsatisfiable if for all colourings $\tau$, the fraction of constraints satisfied by $\tau$ is at most $1 - \eta$.

**Theorem 16.** There is a universal constant $\gamma > 0$ such that, given a Graph 2-CSP instance promised to be either (1) satisfiable, or (2) $(1-\gamma)$-unsatisfiable, it is NP-hard to distinguish between the two cases.
Proof. Follows from Theorem 3 of [13]. □

In order to embed Graph 2-CSP into the confusability graph of a quantum channel, we will follow the ideas of [4] and [13] relating to languages with short quantum proofs.

**Definition 17.** A promise problem $(L, \bar{L})$ (i.e., $L, \bar{L}$ disjoint subsets of $\{0, 1\}^*)$ is in $\mathcal{QMA}_{\log}(2, a, b)$ if there is a polynomial $p(m)$ and a polynomial-time classical verification algorithm $V$ that on input $x$ of length $m$ prepares a quantum circuit $V(x)$ acting on $O(\log m)$ qubits such that for any $m$ and any instance of size $m$, we have

* If $x \in L$, there are $u, v \in \mathbb{C}^{p(m)}$ unit vectors such that

$$ \mathrm{tr}(\Pi_{V(x)}uu^* \otimes vv^*) \geq a $$

where $\Pi_{V(x)}$ is the acceptance projector of the verification circuit $V(x)$.

* If $x \in \bar{L}$, for any unit vectors $u, v \in \mathbb{C}^{p(m)}$, we have

$$ \mathrm{tr}(\Pi_{V(x)}uu^* \otimes vv^*) \leq b. $$

The main result of [13] relates Graph 2-CSP to the above class.

**Theorem 18.** For the constant $\gamma > 0$ given in Theorem 16, let $L$ be the set of satisfiable Graph 2-CSP instances, and $\bar{L}$ be the set of $(1 - \gamma)$-unsatisfiable Graph 2-CSP instances. Then $(L, \bar{L}) \in \mathcal{QMA}_{\log}(2, 1, 1 - \Omega(1/n))$. In addition, the protocol is such that $p(m) = O(m)$.

We now describe the steps of the reduction from Graph 2-CSP to the contraction coefficient problem. For improved readability, we state a lemma for each step of the reduction. The first step is given a Graph 2-CSP instance $G$ to construct a projector $\Pi$.

**Lemma 19** (From $G$ to $\Pi$). Given a Graph 2-CSP instance $G$, we can construct in polynomial time a projector $\Pi \in \mathcal{B}(\mathcal{H} \otimes \mathcal{H})$ with $\dim \mathcal{H} = n$ such that if $G$ is satisfiable then $\ell_{\mathrm{SEP}}(\Pi) = 0$ and if $G$ is $(1 - \gamma)$-unsatisfiable $\ell_{\mathrm{SEP}}(\Pi) = \Omega(\frac{1}{n})$.

*Proof.* Let $\mathcal{V}$ be the verifier coming from Theorem 18. Consider an instance $G$ of Graph 2-CSP of size $m$ and we let $\Pi = I - \Pi_{V(G)}$, where $\Pi_{V(G)} \in \mathcal{B}(\mathcal{H} \otimes \mathcal{H})$ is the acceptance projector on input $G$. Let $\mathcal{H} = \mathbb{C}^{p(m)}$ and $n := p(m) = O(m)$. Then we know that if $G$ is satisfiable, there exists $u, v \in \mathcal{H}$ such that $\mathrm{tr}(\Pi_{V(G)}uu^* \otimes vv^*) = 1$ so $\mathrm{tr}(\Pi uu^* \otimes vv^*) = 0$. As a result $\ell_{\mathrm{SEP}}(\Pi) = 0$. If $G$ is $(1 - \gamma)$-unsatisfiable, then for any $u, v \in \mathcal{H}$, $\mathrm{tr}(\Pi_{V(G)}uu^* \otimes vv^*) \le 1 - \Omega(\frac{1}{m})$ which can be rewritten as $\ell_{\mathrm{SEP}}(\Pi) = \Omega(\frac{1}{m}) = \Omega(\frac{1}{n})$. In addition, note that as $\mathcal{V}$ is a polynomial-time classical algorithm and the circuit $\mathcal{V}(G)$ acts on $O(\log m)$ qubits, $\Pi$ can be computed in polynomial time. □

The next step is to construct a subspace $S$ from $\Pi$ such that $\ell_{\mathrm{SEP}}(\Pi)$ is related to the distance between rank-one matrices and $S$. For that, it is useful to introduce a correspondence between $\mathbb{C}^{p \times q}$ and $\mathbb{C}^p \otimes \mathbb{C}^q$. Let $\{|i\rangle : i \in [p]\}$ and $\{|j\rangle : j \in [q]\}$ be fixed orthonormal bases of $\mathbb{C}^p$ and $\mathbb{C}^q$, then we define the linear map $\mathrm{vec} : \mathbb{C}^{p \times q} \to \mathbb{C}^p \otimes \mathbb{C}^q$ as

$$ \mathrm{vec}(|i\rangle\langle j|) := |i\rangle \otimes |j\rangle. \qquad (35) $$

This map is an isometry in the sense that $\langle x, y \rangle = \langle \mathrm{vec}(x), \mathrm{vec}(y) \rangle$. Note that an operator $x \in \mathbb{C}^{p \times q}$ is rank one if and only if $x = uv^*$ with $u \in \mathbb{C}^p \setminus \{0\}$, $v \in \mathbb{C}^q \setminus \{0\}$ and thus if and only if $\mathrm{vec}(x) = u \otimes \bar{v}$ with $\bar{v}$ the complex conjugate of $v$ in the basis $\{|j\rangle : j \in [q]\}$.

**Lemma 20** (From $\Pi$ to $S$). Let $\Pi \in \mathcal{B}(\mathcal{H} \otimes \mathcal{H})$ be an orthonormal projection and $K$ be the kernel of $\Pi$. We construct the subspace $S$ of $\mathcal{B}(\mathcal{H})$ as $S := \mathrm{vec}^{-1}(K)$. We have

$$ \langle \Pi, uu^* \otimes vv^* \rangle = \mathrm{dist}(u \otimes v, K)^2 = \mathrm{dist}(uv^T, S)^2, $$

with

$$ \mathrm{dist}(x, K) := \min_{y \in K} \|x - y\|_{\ell_2}, \quad \mathrm{dist}(x, S) := \min_{y \in S} \|x - y\|_2. $$
Proof. Let {$a_i \in \mathcal{H} \otimes \mathcal{H} : i$} be an orthonormal basis of the support of $\Pi$ so that $\Pi = \sum_i a_i a_i^*$. Then

$$
\begin{align*}
\langle \Pi, uu^* \otimes vv^* \rangle &= \sum_i \langle a_i a_i^*, uu^* \otimes vv^* \rangle \\
&= \sum_i |\langle a_i, u \otimes v \rangle|^2 \\
&= \mathrm{dist}(u \otimes v, K)^2 \\
&= \mathrm{dist}(\mathrm{vec}^{-1}(u \otimes v), \mathrm{vec}^{-1}(K))^2,
\end{align*}
$$

which gives the desired result.

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

The constructed subspace $S$ has an orthogonal complement that is not necessarily the confusability graph of a quantum channel. But we can construct a subspace $\hat{S}$ that has this property and that behaves in the same way as $S$.

**Lemma 21** (From $S$ to $\hat{S} = G_{\Phi}^{\perp}$). Let $S \subseteq \mathbb{C}^{n \times m}$ be a subspace, then

$$
\hat{S} := E_{01} \otimes S + E_{10} \otimes S^* = \left\{ \begin{pmatrix} 0 & A \\ B^* & 0 \end{pmatrix} : A, B \in S \right\} \subseteq \mathcal{B}(\mathbb{C}^{n+m}) \quad (36)
$$

satisfies (a) $\hat{S}^{\perp} = \hat{S}^{\perp*}$, (b) $I_{n+m} \in \hat{S}^{\perp}$ and (c) there is a constant $C > 0$ such that

$$
\inf_{\substack{x \in \mathcal{B}(\mathbb{C}^{n+m}) \\ \mathrm{rank}(x)=1, \|x\|_2=1}} \mathrm{dist}(x, \hat{S}) \le \inf_{\substack{x \in \mathbb{C}^{n \times m} \\ \mathrm{rank}(x)=1, \|x\|_2=1}} \mathrm{dist}(x, S) \le C \inf_{\substack{x \in \mathcal{B}(\mathbb{C}^{n+m}) \\ \mathrm{rank}(x)=1, \|x\|_2=1}} \mathrm{dist}(x, \hat{S}). \quad (37)
$$

Furthermore, let ($s_1^\perp, \dots, s_d^\perp$) be an orthonormal basis of $S^\perp$, with $d = \dim(S^\perp)$, let ($h_1^{(1)}, \dots, h_{n_2}^{(1)}$) and ($h_1^{(2)}, \dots, h_{m_2}^{(2)}$) be, respectively, a Hermitian orthonormal basis of $\mathcal{B}(\mathbb{C}^n)$ and $\mathcal{B}(\mathbb{C}^m)$, let

$$
\begin{align*}
B_1 &= \left\{ \begin{pmatrix} h_p^{(1)} & 0 \\ 0 & 0 \end{pmatrix} : 1 \le p \le n^2 \right\} \\
B_2 &= \left\{ \begin{pmatrix} 0 & 0 \\ 0 & h_p^{(2)} \end{pmatrix} : 1 \le p \le m^2 \right\} \\
B_3 &= \left\{ \frac{1}{\sqrt{2}} \begin{pmatrix} 0 & s_p^{\perp} \\ s_p^{\perp*} & 0 \end{pmatrix} : 1 \le p \le d \right\} \\
B_4 &= \left\{ \frac{1}{\sqrt{2}} \begin{pmatrix} 0 & i s_p^{\perp} \\ -i s_p^{\perp*} & 0 \end{pmatrix} : 1 \le p \le d \right\}.
\end{align*}
$$

Then,

$$
B_{\hat{S}^{\perp}} = B_1 \cup B_2 \cup B_3 \cup B_4
$$

is a Hermitian orthonormal basis of $\hat{S}^{\perp}$.

Proof. Points (a) and (b) are easy. For (c), we have

$$
\mathrm{dist}\left(\begin{pmatrix} 0 & x \\ 0 & 0 \end{pmatrix}, \hat{S}\right) = \mathrm{dist}(x, S), \qquad (38)
$$

and this proves that the first inequality in (37) holds. For the second one, let

$$
\begin{pmatrix} a & b \\ c & d \end{pmatrix} \in \mathcal{B}(\mathbb{C}^{n+m}) \text{ with } \left\| \begin{pmatrix} a & b \\ c & d \end{pmatrix} \right\|_2 = 1, \qquad (39)
$$
and let

$$ \delta^2 := \mathrm{dist}\left(\begin{pmatrix} a & b \\ c & d \end{pmatrix}, \hat{S}\right)^2 = \|a\|_2^2 + \|d\|_2^2 + \mathrm{dist}(b, S)^2 + \mathrm{dist}(c, S^*)^2. $$

We will show that there exists $x \in \mathbb{C}^{n \times m}$ with $\|x\|_2 = 1$ such that $\mathrm{rank}(x) \le \mathrm{rank}\left(\begin{pmatrix} a & b \\ c & d \end{pmatrix}\right)$ and $\mathrm{dist}(x, S) \le 2\delta$. If $\delta \ge 1/2$, then the property clearly holds by taking an arbitrary $x$ of rank 1 and using the fact that $0 \in S$. Now assume $\delta < 1/2$. The normalization condition can be written as

$$ \|a\|_2^2 + \|b\|_2^2 + \|c\|_2^2 + \|d\|_2^2 = 1. $$

Therefore,

$$ 1 - (\|b\|_2^2 + \|c\|_2^2) + \mathrm{dist}(b, S)^2 + \mathrm{dist}(c, S^*)^2 = \delta^2. $$

As the distances between $b$, $c$ and $S$, $S^*$ are non-negative, we end up with:

$$ \max\{\|b\|_2^2, \|c\|_2^2\} \ge \frac{\|b\|_2^2 + \|c\|_2^2}{2} \ge \frac{1 - \delta^2}{2}. $$

We may assume without loss of generality that $\|b\|_2 \ge \|c\|_2$ (otherwise we exchange the role of $b$ and $c$). Using additionally $\mathrm{dist}(b, S) \le \delta < 1/2$ we get

$$ \mathrm{dist}\left(\frac{b}{\|b\|_2}, S\right) \le \frac{\delta}{\sqrt{\frac{1-\delta^2}{2}}} \le \sqrt{\frac{8}{3}}\delta \le 2\delta $$

and we have that $\mathrm{rank}(b) \le \mathrm{rank}\left(\begin{pmatrix} a & b \\ c & d \end{pmatrix}\right)$. This proves the claimed statement and by taking the infimum over $a, b, c, d$ leads to the second inequality in (37).

We now move on to the explicit construction of an orthonormal basis of $\hat{S}^{\perp}$. Observe that

$$ \hat{S}^{\perp} = E_{00} \otimes \mathcal{B}(\mathbb{C}^n) + E_{01} \otimes S^{\perp} + E_{10} \otimes S^{\perp*} + E_{11} \otimes \mathcal{B}(\mathbb{C}^m). \quad (40) $$

In fact, let $x \in \mathcal{B}(\mathbb{C}^{n+m})$ be written as $x = E_{00} \otimes x_{00} + E_{01} \otimes x_{01} + E_{10} \otimes x_{10} + E_{11} \otimes x_{11}$,

$$ \begin{align*} x \in \hat{S}^{\perp} &\iff \forall y \in \hat{S}, \langle x, y \rangle = 0 \\ &\iff \forall y, z \in S, \langle E_{00} \otimes x_{00} + E_{01} \otimes x_{01} + E_{10} \otimes x_{10} + E_{11} \otimes x_{11}, E_{01} \otimes y + E_{10} \otimes z^{*} \rangle = 0 \\ &\iff \forall y, z \in S, \langle x_{00}, 0 \rangle + \langle x_{11}, 0 \rangle + \langle x_{01}, y \rangle + \langle x_{10}, z^{*} \rangle = 0 \\ &\iff x \in E_{00} \otimes \mathcal{B}(\mathbb{C}^n) + E_{01} \otimes S^{\perp} + E_{10} \otimes S^{\perp*} + E_{11} \otimes \mathcal{B}(\mathbb{C}^m), \end{align*} $$

where, in the last equivalence, we used the fact that we could choose $y = 0$ (resp. $z = 0$) to conclude that, necessarily, for all $z \in S$, $\langle x_{10}, z^{*} \rangle = 0$ (resp. for all $y \in S$, $\langle x_{01}, y \rangle = 0$). Now to construct a basis of this subspace, note first that for all $n \in \mathbb{N}$, we can construct an orthonormal Hermitian basis for $\mathcal{B}(\mathbb{C}^n)$. It suffices to take

$$ \left\{ \frac{1}{\sqrt{2}}(E_{p,q} + E_{q,p}), \frac{1}{\sqrt{2}}i(E_{p,q} - E_{q,p}) : 1 \le p < q \le n \right\} \cup \{E_{p,q} : 1 \le p \le n\}. $$

Then, we can easily check that $B_{\hat{S}^{\perp}}$ is a Hermitian orthonormal basis of $\hat{S}^{\perp}$, i.e. that $\mathrm{Span}(B_{\hat{S}^{\perp}}) = \hat{S}^{\perp}$, all $x \in B_{\hat{S}^{\perp}}$ are Hermitian and for all $x, y \in B_{\hat{S}^{\perp}}$, $\langle x, y \rangle = \delta_{x=y}$. $\square$

Now $\hat{S}^{\perp}$ is an operator system and so by Lemma 11, there exists a quantum channel $\Phi$ such that $G_{\Phi} = \hat{S}^{\perp}$. By Theorem 14, the property $\eta_{\mathrm{tr}}(\Phi) = 1$ exactly captures the property that $\hat{S}$ contains a rank-one element. To establish Theorem 3, it only remains to quantitatively control some of the steps in the reduction.
Proof of Theorem 3. We start with an instance G from Graph 2-CSP. As in Lemma 19, we construct Π ∈ B(Cⁿ ⊗ Cⁿ) and then a subspace S of B(Cⁿ) as in Lemma 20. Then, we construct ̂S a subspace of B(C²ⁿ) as in Lemma 21 and then let Φ : B(C²ⁿ) → B(C²ⁿ) be such that G_Φ = ̂S⊥ as per Lemma 11. Note that each step of the construction can be done in polynomial time.

For G satisfiable, we have $\ell_{SEP}(\Pi) = 0$, so S contains a rank-one matrix, so $\hat{S} = G_{\Phi}^{\perp}$ contains a rank-one matrix and so $\eta_{tr}(\Phi) = 1$.

For $G(1-\gamma)$-unsatisfiable, we have $\ell_{SEP}(\Pi) = \Omega(\frac{1}{n})$ (Lemma 19). Then by Lemma 20, we have $\inf_{x,\text{rank}(x)=1,\|x\|=1} \text{dist}(x, S)^2 = \Omega(\frac{1}{n})$. Using Lemma 21, we get $\inf_{x,\text{rank}(x)=1,\|x\|=1} \text{dist}(x, G_{\Phi}^{\perp})^2 = \Omega(\frac{1}{n})$. By Theorem 14, this implies $\eta_{tr}(\Phi) < 1$, but we want a quantitative bound.

By Lemma 21, $\hat{S}^{\perp}$ admits a Hermitian orthonormal basis. Let $\{s_1, \dots, s_l\}$ be an orthonormal basis of $\hat{S}$ and $\{s_1^{\perp}, \dots, s_l^{\perp}\}$ be a Hermitian orthonormal basis of $\hat{S}^{\perp}$. Then, every rank one operator $uv^*$ can be decomposed as:

$$ uv^* = \sum_{i=1}^{l} \langle s_i, uv^* \rangle s_i + \sum_{j=1}^{l'} \langle s_j^{\perp}, uv^* \rangle s_j^{\perp}. $$

As $\text{dist}(uv^*, \hat{S}) = \Omega(\frac{1}{\sqrt{n}})$, we have

$$ \begin{aligned} \Omega\left(\frac{1}{\sqrt{n}}\right) & \le \|uv^* - \sum_{i=1}^{l} \langle s_i, uv^* \rangle s_i\|_2 \\ &= \left\| \sum_{j=1}^{l'} \langle s_j^{\perp}, uv^* \rangle s_j^{\perp} \right\|_2 \\ &= \sqrt{\sum_{j=1}^{l'} |\langle s_j^{\perp}, uv^* \rangle|^2} \\ & \le \sqrt{l'} \max_j |\langle s_j^{\perp}, uv^* \rangle|. \end{aligned} $$

Thus there exists $\tilde{j}$ such that $|\langle s_{\tilde{j}}^{\perp}, uv^* \rangle| \ge \frac{1}{\sqrt{l'}} \Omega(\frac{1}{\sqrt{n}})$. As $l' \le \dim(\hat{S}^{\perp}) \le \dim(B(C^{2n})) = 4n^2$ we have $|\langle s_j^{\perp}, uv^* \rangle| \ge \Omega(\frac{1}{n\sqrt{n}})$.

As we explained in the previous paragraph, $\hat{S}^{\perp}$ is the quantum confusability graph of some channel $\Phi$ with Kraus operators $\{K_i\}_i$. By the second paragraph of Lemma 11, we can choose the Kraus operators $\{K_i\}_i$ so that, for all $i, j$, $K_i^* K_j = \delta_{i,j} s_i^{\perp}$. In particular, we have

$$ |\langle K_j^* K_j, uv^* \rangle| = |\langle s_j^{\perp}, uv^* \rangle| \ge \Omega\left(\frac{1}{n\sqrt{n}}\right). \quad (41) $$

Consider $u, v \in \mathbb{C}^{2n}$ such that

$$ \eta_{\text{tr}}(\Phi) = \frac{1}{2} \| \Phi(uu^*) - \Phi(vv^*) \|_1, $$

which exist as per Lemma 5. We now use the Fuchs-van de Graaf inequality [12] to upper-bound the trace distance between $\Phi(uu^*)$ and $\Phi(vv^*)$. For two states $\rho, \sigma$, we write $F(\rho, \sigma) = \|\sqrt{\rho}\sqrt{\sigma}\|_1^2$ the fidelity between $\rho$ and $\sigma$, the Fuchs-van de Graaf inequality then states that:

$$ \frac{1}{2} \|\rho - \sigma\|_1 \le \sqrt{1 - F(\rho, \sigma)}. $$

Therefore, we have:

$$ \eta_{\text{tr}}(\Phi) \le \sqrt{1 - F(\Phi(uu^*), \Phi(vv^*))}. $$
Then,

$$
\begin{align*}
F(\Phi(uu^*), \Phi(vv^*)) &= \|\sqrt{\Phi(uu^*)} \sqrt{\Phi(vv^*)}\|_1^2 \\
&\ge \|\sqrt{\Phi(uu^*)} \sqrt{\Phi(vv^*)}\|_2^2 \\
&= \langle \sqrt{\Phi(uu^*)} \sqrt{\Phi(vv^*)}, \sqrt{\Phi(uu^*)} \sqrt{\Phi(vv^*)} \rangle \\
&= \langle \Phi(uu^*), \Phi(vv^*) \rangle \\
&= \left\langle \sum_i K_i uu^* K_i^*, \sum_j K_j vv^* K_j^* \right\rangle \\
&= \sum_{i,j} |\langle K_i^* K_j, uv^* \rangle|^2 \\
&\ge |\langle K_j^* K_j, uv^* \rangle|^2 \\
&\ge \Omega\left(\frac{1}{n^3}\right),
\end{align*}
$$

where the last inequality follows from Eq. (41). Finally,

$$
\eta_{\text{tr}}(\Phi) \le \sqrt{1 - \Omega\left(\frac{1}{n^3}\right)} \le 1 - \Omega\left(\frac{1}{n^3}\right).
$$

□

4.1 Quantum Doeblin Coefficients

The trace norm (or total-variation) contraction coefficient of a classical channel is upper bounded by the
Doeblin coefficient [7]. In [24, Theorem 8.17], a quantum version of Doeblin’s theorem was proposed.
Quantum Doeblin coefficients were defined and studied in a systematic way more recently in [14, 16].

Recall that for any channel Φ, we denote A its input system, B its output system, d_A and d_B their respective dimension and J(Φ) the Choi state of Φ.

**Definition 22** (Corollary 3.7 in [16]). Given a channel $\Phi$, the quantum Doeblin coefficient of $\Phi$ is defined as

$$
\alpha(\Phi) := \sup_{X_B \in \text{Herm}(B)} \{\text{tr}[X_B] : I_A \otimes X_B \preceq d_A J(\Phi)\}, \quad (42)
$$

where, for matrices $X$, $Y$, $X \preceq Y$ if and only if $Y - X$ is positive semidefinite.

Furthermore, a relaxation of the quantum Doeblin coefficient, called the induced Doeblin coefficient, was
also proposed in [14].

**Definition 23** (Induced Doeblin coefficient, Proposition 7 in [14]). Let $\alpha_I(\Phi)$, the induced Doeblin coefficient, be defined as

$$
\alpha_I(\Phi) = \max_{\substack{d_A J(\Phi) - I_A \otimes X_B \in \text{Sep}^*(A:B), \\ X_B \in \text{Herm}(B)}} \text{tr}(X_B), \quad (43)
$$

where $\text{Sep}^*(A:B)$ is the dual of the cone of separable operators on the compound system $(A, B)$, which corresponds to the cone of block-positive operators.

The induced Doeblin coefficient is *not* easy to compute but gives an upper bound on $\alpha(\Phi)$ by Proposition 5 of [14]. Both the Doeblin coefficient and the induced Doeblin coefficient give upper bounds on the trace norm contraction coefficient.
**Proposition 24** (Lemma 3.2 in [16] and Equation (6.34) in [14]). Let $\Phi$ be a channel, then

$$ \eta_{\text{tr}}(\Phi) \le 1 - \alpha_I(\Phi) \le 1 - \alpha(\Phi). \qquad (44) $$

Therefore, for any channel $\Phi$, whenever $\alpha_I(\Phi) \ge \alpha(\Phi) > 0$, we have $\eta_{\text{tr}}(\Phi) < 1$. It is natural to ask whether the converse is true, i.e., does $\eta_{\text{tr}}(\Phi) < 1$ imply $\alpha_I(\Phi) > 0$ or $\alpha(\Phi) > 0$? In [14, Remark 5], this question is answered negatively for $\alpha(\Phi)$. We give another entanglement-breaking example of this fact that also answers the question for $\alpha_I(\Phi)$.

**Proposition 25.** Let $\mathcal{H}$ be a Hilbert space of dimension $d > 2$ and $\{|i\rangle : 1 \le i \le d\}$ an orthonormal basis of $\mathcal{H}$. The channel $\Phi: \mathcal{B}(\mathcal{H}) \to \mathcal{B}(\mathcal{H})$ with Kraus operators $\{\frac{1}{\sqrt{d-1}}|i\rangle\langle j| : i \ne j, 1 \le i, j \le d\}$ is such that:

$$ \eta_{\text{tr}}(\Phi) < 1 \text{ but } \alpha(\Phi) = \alpha_I(\Phi) = 0. \qquad (45) $$

*Proof.* We first show that $\eta_{\text{tr}}(\Phi) < 1$. We have

$$ G_{\Phi} = \text{Span}\{|j\rangle\langle i| | k\rangle\langle l| : (i, j, k, l) \in [d]^4, i \ne j, k \ne l\}. $$

As $d \ge 3$, for all $(j, l) \in [d]^2$, there is an integer $k \in [d]$ such that $i \ne k, k \ne l$. Thus, for every $(j, l) \in [d]^2$, $|j\rangle\langle l| \in G_{\Phi}$. Therefore, $G_{\Phi} = \mathcal{B}(\mathcal{H})$ and thus $G_{\Phi}^{\perp} = \{0\}$. Hence, there is no rank one element in $G_{\Phi}^{\perp}$ and by Theorem 14, $\eta_{\text{tr}}(\Phi) < 1$.

On the other hand, $J(\Phi) = \frac{1}{d(d-1)} \sum_{i \ne j} |i\rangle\langle i| \otimes |j\rangle\langle j|$ and thus

$$ dJ(\Phi) - I_A \otimes X_B = \sum_i |i\rangle\langle i| \otimes \left( \frac{1}{d-1} \sum_{j \ne i} |j\rangle\langle j| - X_B \right). \qquad (46) $$

Positivity of this operator means that for any $i, 0 \le \left( \frac{1}{d-1} \sum_{j \ne i} |j\rangle\langle j| - X_B \right)$, which implies that $\langle i | X_B | i \rangle \le 0$ and so $\text{tr}(X_B) \le 0$. This means $\alpha(\Phi) = 0$. In fact, the operator in (46) is block-diagonal and hence block-positivity implies positivity and we also have $\alpha_I(\Phi) = 0$. $\square$

# 5 Converging hierarchy of efficiently computable upper bounds

In this section, we use [3] to propose a hierarchy of semidefinite programming upper bounds on $\mathbb{P}_{\text{succ}}(\Phi, k)$, which in the special case $k = 2$ gives bounds on $\eta_{\text{tr}}(\Phi)$. Recall that for every channel $\Phi$ and input operator $X_A$, we can express $\Phi(X_A)$ as:

$$ \Phi(X_A) = d_A \text{tr}_A(J(\Phi)(X_A^T \otimes I_B)). \qquad (47) $$

We will introduce copies of the system $B$ that we will denote $B_1, \dots, B_m$. As a shorthand, we write $B_1^m = B_1, \dots, B_m$. An operator on $AB_1^m$ will be denoted $W_{AB_1^m}$ and we write $W_{B_1^m} = \text{tr}_A(W_{AB_1^m})$ and $W_{AB_1^m} = \text{tr}_{B_1^m}(W_{AB_1^m})$ with $B_{l+1}^m = B_{l+1}, \dots, B_m$. Furthermore, let $\mathfrak{S}_m$ be the symmetric group on $m$ elements. For $\pi \in \mathfrak{S}_m$, let $\mathcal{U}_{B_1^m}^{\pi}$ be the unitary which permutes the systems $B_1, \dots, B_m$ according to the permutation $\pi$. Its action on product operators over $B_1^m$ is as follows:

$$ \mathcal{U}_{B_1^m}^{\pi}(W_{B_1} \otimes \dots \otimes W_{B_m}) := W_{B_{\pi(1)}} \otimes \dots \otimes W_{B_{\pi(m)}}. $$

A multipartite operator $W_{AB_1^m}$ on $AB_1^m$ is called symmetric with respect to A if

$$ (\text{Id}_A \otimes \mathcal{U}_{B_1^m}^{\pi})(W_{AB_1^m}) = W_{AB_1^m}, \quad \forall \pi \in \mathfrak{S}_m. $$

We use the shorthand $j_1^m$ for $j_1, \dots, j_m$.

The following Theorem 26 gives a hierarchy of semidefinite programs which forms a non-increasing sequence of upper bounds on $\mathbb{P}_{\text{succ}}(\Phi, k)$. We will show in Theorem 28 that this hierarchy corresponds to the hierarchy proposed in [3] for general constrained bilinear optimisation and thus we can use their convergence result.
**Theorem 26.** For $m, k \in \mathbb{N}$, the semidefinite programs

$$ \text{SDP}_m(\Phi, k) = \max \left\{ \begin{array}{ll} \frac{d_A}{k} \sum_{i=1}^k \text{tr}(J(\Phi)W_{AB_1}^{(i,i)}) & \text{if } m=1, \\ \frac{d_A}{kd_B^{m-1}} \sum_{i=1}^k \sum_{j_2^m \in [k]^{m-1}} \text{tr}(J(\Phi)W_{AB_1}^{(i,j_2^m)}) & \text{else,} \end{array} \right. \quad (48) $$

$$ \text{s.t.} \quad \forall (i, j_1^m) \in [k]^{m+1}, \quad W_{AB_1^m}^{(i, j_1^m)} \succeq 0, \quad (49) $$

$$ \text{tr}(\sum_{(ij_1^m) \in [k]^{m+1}} W_{AB_1^m}^{(i, j_1^m)}) = kd_B^m, \quad (50) $$

$$ \forall \pi \in \mathfrak{S}_m, W_{AB_1^m}^{(i, j_{\pi(1)}, \dots, j_{\pi(m)})} = (\mathcal{I}_A \otimes \mathcal{U}_{B_1^m}^{\pi}) (W_{AB_1^m}^{(i, j_1^m)}), \quad (51) $$

$$ \forall (i, j_1^{m-1}) \in [k]^m, \quad \sum_{j=1}^{k} W_{AB_1^m}^{(i, j_1^{m-1}, j)} = \sum_{j=1}^{k} W_{AB_1^{m-1}}^{(i, j_1^{m-1}, j)} \otimes \frac{I_B}{d_B}, \quad (52) $$

$$ \forall (i, j_1^m) \in [k]^{m+1}, \quad W_{B_1^m}^{(i, j_1^m)} = \frac{1}{k} \sum_{l=1}^{k} W_{B_1^m}^{(l, j_1^m)}, \quad (53) $$

form a non-increasing sequence of upper bounds on $\mathbb{P}_{\text{succ}}(\Phi, k)$. We write $\text{SDP}_m(\Phi) = 2\text{SDP}_m(\Phi, 2) - 1$ for the corresponding upper bound on the contraction coefficient.

Before proving this theorem, we express the success probability $\mathbb{P}_{\text{succ}}(\Phi, k)$ defined in Eq. (4) using the Choi state of $\Phi$.

**Lemma 27.** We have:

$$ \mathbb{P}_{\text{succ}}(\Phi, k) = \max_{\substack{\{M_i : 1 \le i \le k\} \text{ POVM}, \\ \{\rho_i \in \mathcal{D}(\mathcal{H}) : 1 \le i \le k\}}} \frac{d_A}{k} \sum_{i=1}^{k} \text{tr}(J(\Phi)\rho_i^T \otimes M_i). \quad (54) $$

*Proof.* We have the following equalities:

$$ \mathbb{P}_{\text{succ}}(\Phi, k) = \max_{\substack{\{M_i : 1 \le i \le k\} \text{ POVM}, \\ \{\rho_i \in \mathcal{D}(\mathcal{H}) : 1 \le i \le k\}}} \frac{1}{k} \sum_{i=1}^{k} \text{tr}(M_i \Phi(\rho_i)) $$

$$ \stackrel{(a)}{=} \max_{\substack{\{M_i : 1 \le i \le k\} \text{ POVM}, \\ \{\rho_i \in \mathcal{D}(\mathcal{H}) : 1 \le i \le k\}}} \frac{d_A}{k} \sum_{i=1}^{k} \text{tr}(M_i \text{tr}_A(J(\Phi)(\rho_i^T \otimes I_B))) $$

$$ = \max_{\substack{\{M_i : 1 \le i \le k\} \text{ POVM}, \\ \{\rho_i \in \mathcal{D}(\mathcal{H}) : 1 \le i \le k\}}} \frac{d_A}{k} \sum_{i=1}^{k} \text{tr}(J(\Phi)\rho_i^T \otimes M_i), $$

where (a) follows from Eq. (47). $\square$

*Proof of Theorem 26.* We just have to show that the semidefinite programs defined in the theorem are relaxations of the optimisation problem in the right-hand side of Eq. (54).

It suffices to take, at the level $m \in \mathbb{N}$ of the hierarchy, the variables $W_{AB_1^m}^{(i, j_1^m)}$ to be equal to the product operator $\rho_i^T \otimes \otimes_{p=1}^m M_{j_p}$, with $\{\rho_i\}_i, \{M_j\}_j$ being the states and POVMs on which the optimisation in
Eq. (54) is done. Then, the positivity and symmetry constrains Eq. (49) and Eq. (51) are trivially satisfied. Furthermore, we have:

$$ \mathrm{tr} \left( \sum_{(i,j_1^m) \in [k]^{m+1}} \rho_i^T \bigotimes_{p=1}^m M_{j_p} \right) = \left( \sum_{i=1}^k \left( \sum_{j=1}^k \mathrm{tr}(M_j) \right)^m \right) = kd_B^m, $$

so Eq. (50) is satisfied. Then, let $(i, j_1^{m-1}) \in [k]^m$ be fixed, we have on the one hand:

$$ \sum_{j=1}^{k} \rho_i^T \bigotimes_{p=1}^{m-1} M_{j_p} \otimes M_j = \rho_i^T \bigotimes_{p=1}^{m-1} M_{j_p} \otimes \left( \sum_{j=1}^{k} M_j \right) = \rho_i^T \bigotimes_{p=1}^{m-1} M_{j_p} \otimes I_B; $$

and, on the other hand:

$$ \sum_{j=1}^{k} \mathrm{tr}_{B_m} \left( \rho_i^T \bigotimes_{p=1}^{m-1} M_{j_p} \otimes M_j \right) = \sum_{j=1}^{k} \mathrm{tr}(M_j) \rho_i^T \bigotimes_{p=1}^{m-1} M_{j_p} = d_B \rho_i^T \bigotimes_{p=1}^{m-1} M_{j_p}, $$

so these variables satisfy Eq. (52). Finally, for $(i, j_1^m) \in [k]^{m+1}$ fixed, we have:

$$ \begin{aligned} \mathrm{tr}_A(\rho_i^T \bigotimes_{p=1}^m M_{j_p}) &= \bigotimes_{p=1}^m M_{i_p} \\ &= \frac{1}{k} \sum_{l=1}^k \bigotimes_{p=1}^m M_{i_p} \\ &= \frac{1}{k} \sum_{l=1}^k \mathrm{tr}_A \left( \rho_l^T \bigotimes_{p=1}^m M_{i_p} \right), \end{aligned} $$

so that this choice of variables also satisfies Eq. (53). Then, we have to show that, for this choice of variables, the objective function gives the same value as the objective function in the right-hand side of Eq. (54). We present the case $m \ge 2$ as the case $m = 1$ is trivial.

$$ \begin{aligned} \frac{d_A}{kd_B^{m-1}} \sum_{i=1}^k \sum_{j_2^m \in [k]^{m-1}} \mathrm{tr}(J(\Phi)W_{AB_1}^{(i,j_2^m)}) &= \frac{d_A}{kd_B^{m-1}} \sum_{i=1}^k \mathrm{tr}(J(\Phi)) \sum_{j_2^m \in [k]^{m-1}} \mathrm{tr}_{B_2^m} \left( \rho_i^T \bigotimes_{p=2}^m M_{i_p} \right) \\ &= \frac{d_A}{kd_B^{m-1}} \sum_{i=1}^k \mathrm{tr}(J(\Phi)(\rho_i^T \otimes M_i)) \mathrm{tr} \left( \sum_{j_2^m \in [k]^{m-1}} \bigotimes_{p=2}^m M_{j_p} \right) \\ &= \frac{d_A}{kd_B^{m-1}} \mathrm{tr}(I_B)^{m-1} \sum_{i=1}^k \mathrm{tr}(J(\Phi)(\rho_i^T \otimes M_i)) \\ &= \frac{d_A}{k} \sum_{i=1}^k \mathrm{tr}(J(\Phi)(\rho_i^T \otimes M_i)). \end{aligned} $$

□

Note that it is clear from the proof that we can add positive partial transpose (PPT) constraints to the SDP. Indeed, for all $(i, j_1, \dots, j_m) \in [k]^{m+1}$, we can additionally ask the variables $W_{AB_1^m}^{(i,j_1^m)}$ to satisfy

$$ T_A(W_{AB_1^m}^{(i,j_1^m)}) \succeq 0, \quad T_{B_1}(W_{AB_1^m}^{(i,j_1^m)}) \succeq 0, \quad T_{B_1^2}(W_{AB_1^m}^{(i,j_1^m)}) \succeq 0, \dots, \quad T_{B_1^{m-1}}(W_{AB_1^m}^{(i,j_1^m)}) \succeq 0, \qquad (55) $$
where $T_S$ denote the partial transpose on system S. Note that products of positive operators satisfy the PPT constraints of Eq. (55), therefore the SDP we obtain by adding Eq. (55) is still a relaxation of $\mathbb{P}_{\text{succ}}(\Phi, k)$ (Eq. (4)). We denote $\text{SDP}_m^{\text{PPT}}$ the value of the corresponding SDP when adding the PPT constraints.

In the remainder of this section, we show that the hierarchy of semidefinite programs defined in Theorem 26 actually converges to $\mathbb{P}_{\text{succ}}(\Phi, k)$. Note that, although semidefinite programs are efficiently computable, the number of variables of $\text{SDP}_m(\Phi, k)$ grows exponentially in $m$, while we prove only a convergence speed in poly(d)/$\sqrt{m}$, therefore, the convergence of this hierarchy to $\mathbb{P}_{\text{succ}}(\Phi, k)$ does neither contradict Theorem 2 nor Theorem 3.

**Theorem 28** (Convergence of the SDP of Theorem 26). For all $\Phi, k, m \in \mathbb{N}$, we have

$$0 \le \text{SDP}_m(\Phi, k) - \mathbb{P}_{\text{succ}}(\Phi, k) \le \frac{\text{poly}(d)}{\sqrt{m}}, \qquad (56)$$

with $d = \max\{d_A, d_B\}$ with A the input system of $\Phi$ and B its output system, so that

$$\mathbb{P}_{\text{succ}}(\Phi, k) = \lim_{m \to \infty} \text{SDP}_m(\Phi, k). \qquad (57)$$

In order to prove the convergence, we express $\mathbb{P}_{\text{succ}}(\Phi, k)$ as a constrained bilinear program [3] and show that the SDP hierarchy we propose in Theorem 26 is the same as the general converging one derived in [3]. We write $\Psi_{\bar{A}\bar{B}}^{(k)} = \sum_{i=1}^k |i\rangle\langle i| \otimes |i\rangle\langle i|$, with $k = \dim(\bar{A}) = \dim(\bar{B})$ the (unnormalized) maximally correlated operator between systems $\bar{A}$ and $\bar{B}$.

**Lemma 29.** We can express $\mathbb{P}_{\text{succ}}(\Phi, k)$ as the following constrained bilinear program:

$$\mathbb{P}_{\text{succ}}(\Phi, k) = d_A d_B \max \operatorname{tr} \left( (J(\Phi)_{AB} \otimes \Psi_{\bar{A}\bar{B}}^{(k)})(W_{A\bar{A}} \otimes W_{B\bar{B}}) \right), \qquad (58)$$

$$\text{s.t. } W_{A\bar{A}} \succeq 0, \quad W_{B\bar{B}} \succeq 0, \qquad (59)$$

$$\operatorname{tr}(W_{A\bar{A}}) = 1, \quad \operatorname{tr}(W_{B\bar{B}}) = 1, \qquad (60)$$

$$\operatorname{tr}_A(W_{A\bar{A}}) = \frac{I_{\bar{A}}}{k}, \qquad (61)$$

$$\operatorname{tr}_{\bar{B}}(W_{B\bar{B}}) = \frac{I_{\bar{B}}}{d_{\bar{B}}}. \qquad (62)$$

*Proof.* The proof proceeds in two steps, first we show that we can suppose without loss of generality that the variables $W_{A\bar{A}}$ and $W_{B\bar{B}}$ are block-diagonal with respect to the systems $\bar{A}$ and $\bar{B}$. Then, we show that for such block-diagonal variables, the program of the theorem is equivalent to the optimisation problem of Lemma 27.

For the first part of the proof, recall that $k = \dim(\bar{A}) = \dim(\bar{B})$. Then, we can write

$$W_{A\bar{A}} = \frac{1}{k} \sum_{i,j=1}^{k} W_{A}^{(i,j)} \otimes |i\rangle\langle j|_{\bar{A}}, \quad W_{B\bar{B}} = \frac{1}{d_{\bar{B}}} \sum_{i,j=1}^{k} W_{B}^{(i,j)} \otimes |i\rangle\langle j|_{\bar{B}}. \qquad (63)$$

From these variables we construct the block-diagonal operators $W_{A\bar{A}}^D, W_{B\bar{B}}^D$ obtained from $W_{A\bar{A}}$ and $W_{B\bar{B}}$ by keeping only the diagonal blocks in the decomposition of Eq. (63), i.e. write

$$W_{A\bar{A}}^D = \frac{1}{k} \sum_{i=1}^{k} W_{A}^{(i,i)} \otimes |i\rangle\langle i|_{\bar{A}}, \quad W_{B\bar{B}}^D = \frac{1}{d_{\bar{B}}} \sum_{i=1}^{k} W_{B}^{(i,i)} \otimes |i\rangle\langle i|_{\bar{B}}. \qquad (64)$$

The objective function of the program of Lemma 29 evaluated on the two variables $W_{A\bar{A}}, W_{B\bar{B}}$ can be
written as:

$$d_A d_B \operatorname{tr} \left( (J(\Phi)_{AB} \otimes \Psi_{\bar{A}\bar{B}}^{(k)})(W_{A\bar{A}} \otimes W_{B\bar{B}}) \right) \quad (65)$$

$$= \frac{d_A}{k} \operatorname{tr} \left( \left( J(\Phi)_{AB} \otimes \left[ \sum_{i=1}^{k} |i\rangle\langle i|_{\bar{A}} \otimes |i\rangle\langle i|_{\bar{B}} \right] \right) \left( \left[ \sum_{i,j=1}^{k} W_A^{(i,j)} \otimes |i\rangle\langle j|_{\bar{A}} \right] \otimes \left[ \sum_{i,j=1}^{k} W_B^{(i,j)} \otimes |i\rangle\langle j|_{\bar{B}} \right] \right) \right) \quad (66)$$

$$= \frac{d_A}{k} \operatorname{tr} \left( \sum_{i,j,j'=1}^{k} J(\Phi)_{AB} (W_A^{(i,j)} \otimes W_B^{(i,j')}) \otimes |i\rangle\langle j|_{\bar{A}} \otimes |i\rangle\langle j'|_{\bar{B}} \right) \quad (67)$$

$$= \frac{d_A}{k} \operatorname{tr} \left( \sum_{i=1}^{k} J(\Phi)_{AB} (W_A^{(i,i)} \otimes W_B^{(i,i)}) \right) \quad (68)$$

$$= d_A d_B \operatorname{tr} \left( (J(\Phi)_{AB} \otimes \Psi_{\bar{A}\bar{B}}^{(k)})(W_{A\bar{A}}^{D} \otimes W_{B\bar{B}}^{D}) \right). \quad (69)$$

Furthermore, if $W_{A\bar{A}}$ and $W_{B\bar{B}}$ satisfy the constraints of the bilinear optimisation program of the lemma, then so do $W_{A\bar{A}}^D$, $W_{B\bar{B}}^D$. If $W_{A\bar{A}}$ and $W_{B\bar{B}}$ are positive semidefinite, then so are all their diagonal blocks $W_A^{(i,i)} \otimes |i\rangle\langle i|_{\bar{A}}$ and $W_B^{(i,i)} \otimes |i\rangle\langle i|_{\bar{B}}$, thus $W_{A\bar{A}}^D$ and $W_{B\bar{B}}^D$ are constrained to be positive semidefinite. The three other conditions involve traces or partial traces and are also easily satisfied by $W_{A\bar{A}}^D$ and $W_{B\bar{B}}^D$ as we have the equalities $\operatorname{tr}(W_{A\bar{A}}) = \operatorname{tr}(W_{A\bar{A}}^D)$, $\operatorname{tr}(W_{B\bar{B}}) = \operatorname{tr}(W_{B\bar{B}}^D)$, $\operatorname{tr}_A(W_{A\bar{A}}) = \operatorname{tr}_A(W_{A\bar{A}}^D)$ and $\operatorname{tr}_{\bar{B}}(W_{B\bar{B}}) = \operatorname{tr}_B(W_{B\bar{B}}^D)$.

Therefore we can suppose without loss of generality that we optimise the SDP on the block-diagonal variables $W_{A\bar{A}}^D$, $W_{B\bar{B}}^D$ of the form given in Eq. (63).

Now, by Lemma 27, we have

$$\mathbb{P}_{\text{succ}}(\Phi, k) = \max_{\begin{subarray}{l} \{M_i : 1 \le i \le k\} \text{ POVM,} \\ \{\rho_i \in \mathcal{D}(\mathcal{H}) : 1 \le i \le k\} \end{subarray}} \frac{d_A}{k} \sum_{i=1}^{k} \operatorname{tr}(J(\Phi)\rho_i^T \otimes M_i).$$

For $\{\rho_i \in \mathcal{D}(\mathcal{H}) : 1 \le i \le k\}$ any set of states and $\{M_i \succeq 0 : 1 \le i \le k\}$ any POVM, we associate the block-diagonal variables:

$$W_{A\bar{A}}^D = \frac{1}{k} \sum_{i=1}^{k} \rho_{i,A}^T \otimes |i\rangle\langle i|_{\bar{A}}, \quad W_{B\bar{B}}^D = \frac{1}{d_B} \sum_{i=1}^{k} M_{i,B} \otimes |i\rangle\langle i|_{\bar{B}}.$$

It is easy to check that these variables satisfy the constraints of the program of Lemma 29 and, furthermore,

$$d_A d_B \operatorname{tr} \left[ (J(\Phi)_{AB} \otimes \Psi_{\bar{A}\bar{B}}^{(k)})(W_{A\bar{A}}^D \otimes W_{B\bar{B}}^D) \right] \stackrel{(a)}{=} \frac{d_A}{k} \operatorname{tr} \left[ \sum_{i=1}^{k} J(\Phi)_{AB} (W_A^{(i,i)} \otimes W_B^{(i,i)}) \right] \\ = \frac{d_A}{k} \operatorname{tr} \left[ \sum_{i=1}^{k} J(\Phi)_{AB} (\rho_{i,A}^T \otimes M_{i,B}) \right],$$

where (a) follows from Eq. (68). Therefore, the bilinear optimisation program proposed in this lemma is an upper bound on $\mathbb{P}_{\text{succ}}(\Phi, k)$.

To show the inequality in the other direction, consider two block diagonal variables $W_{A\bar{A}}^D$, $W_{B\bar{B}}^D$ as in Eq. (63) which satisfy the constraints of the optimisation program. By the previous system of equations, we have:

$$d_A d_B \operatorname{tr} \left[ (J(\Phi)_{AB} \otimes \Psi_{\bar{A}\bar{B}}^{(k)})(W_{A\bar{A}}^D \otimes W_{B\bar{B}}^D) \right] = \frac{d_A}{k} \operatorname{tr} \left[ \sum_{i=1}^{k} J(\Phi)_{AB} (W_A^{(i,i)} \otimes W_B^{(i,i)}) \right].$$
As $W_{A\bar{A}}^D \succeq 0$ and $W_{B\bar{B}}^D \succeq 0$, we have that each of their diagonal blocks $W_A^{(i,i)}$ and $W_B^{(i,i)}$ are positive semidefinite. Then, we have

$$ \frac{I_{\bar{A}}}{k} = \mathrm{tr}_A(W_{A\bar{A}}^D) = \frac{1}{k} \sum_{i=1}^{k} \mathrm{tr}(W_A^{(i,i)}) \otimes |i\rangle\langle i|_{\bar{A}}. $$

Therefore, for each $i \in [k]$, we have $\mathrm{tr}(W_A^{(i,i)}) = \langle i | I_{\bar{A}} | i \rangle = 1$, so that all operators $W_A^{(i,i)}$ are states (or, equivalently, transposes of states). Analogously

$$ \frac{I_B}{d_B} = \mathrm{tr}_{\bar{B}}(W_{B\bar{B}}^D) = \frac{1}{d_B} \sum_{i=1}^{k} W_B^{(i,i)} \mathrm{tr}(|i\rangle\langle i|_{\bar{B}}) = \frac{1}{d_B} \sum_{i=1}^{k} W_B^{(i,i)}. $$

So that $\{W_B^{(i,i)}: 1 \le i \le k\}$ forms a POVM. $\square$

Now, from the bilinear optimisation program of Lemma 29, we can construct a hierarchy of semidefinite programs of the form of Eq. 5 in [3] that will automatically converge to $\mathbb{P}_{\mathrm{succ}}(\Phi, k)$ by the results of [3, Theorem 3.1]. This hierarchy can be written as

$$ \widetilde{\mathrm{SDP}}_m(\Phi, k) = d_A d_B \max \mathrm{tr}[(J(\Phi)_{AB} \otimes \Psi_{\bar{A}\bar{B}}^{(k)})(W_{A\bar{A}B\bar{B}})], \quad (70) $$

$$ \text{s.t.} \quad W_{A\bar{A}(B\bar{B})_1^n} \succeq 0, \quad \mathrm{tr}(W_{A\bar{A}(B\bar{B})_1^n}) = 1, \quad (71) $$

$$ \forall \pi \in \mathcal{S}_n, \quad (\mathrm{Id}_{A\bar{A}} \otimes \mathcal{U}_{(B\bar{B})_1^n}^{\pi})(W_{A\bar{A}(B\bar{B})_1^n}) = W_{A\bar{A}(B\bar{B})_1^n}, \quad (72) $$

$$ \mathrm{tr}_A(W_{A\bar{A}(B\bar{B})_1^n}) = \frac{I_{\bar{A}}}{k} \otimes W_{(B\bar{B})_1^n}, \quad (73) $$

$$ \mathrm{tr}_{\bar{B}_m}(W_{(B\bar{B})_1^n}) = W_{(B\bar{B})_1^{m-1}} \otimes \frac{I_{B_m}}{d_B}. \quad (74) $$

It is easy to see that

$$ \mathrm{SDP}_m(\Phi, k) = \widetilde{\mathrm{SDP}}_m(\Phi, k). $$

In fact, given a feasible solution $W_{AB_1^n}^{(i,j_1^m)}$ for $\mathrm{SDP}_m(\Phi, k)$, we define

$$ W_{A\bar{A}(B\bar{B})_1^n} = \frac{1}{kd_B^m} \sum_{i=1}^{k} \sum_{j_1^n \in [k]^m} |i\rangle\langle i|_{\bar{A}} \otimes |j_1^m\rangle\langle j_1^m|_{\bar{B}_1^n} \otimes W_{AB_1^n}^{(i,j_1^m)}. $$

We then check that it achieves the same value for the objective function and it satisfies the constraints. In the other direction, given a feasible solution $W_{A\bar{A}(B\bar{B})_1^n}$ for $\widetilde{\mathrm{SDP}}_m(\Phi, k)$, we define

$$ W_{AB_1^n}^{(i,j_1^m)} = \langle i|_{\bar{A}} \langle j_1^m|_{\bar{B}_1^n} W_{A\bar{A}(B\bar{B})_1^n} |i\rangle_{\bar{A}} |j_1^m\rangle_{\bar{B}_1^n}, $$

and also check that it is feasible and achieves the same value for the objective function. Theorem 28 then follows.

## 5.1 Numerical illustration

We now briefly illustrate this hierarchy on some simple channels. We tested the first level of the hierarchy of Theorem 26 on the channel $\Phi$ of Proposition 25, i.e., the one with vanishing quantum Doeblin coefficients and obtained a bound of

$$ \eta_{\mathrm{tr}}(\Phi) \le \frac{1}{2} < 1. \quad (75) $$
Thus, this hierarchy already detects at the first level that this channel has a contraction coefficient < 1.

We now consider (multiple copies of) amplitude damping channels $\mathcal{A}_{p,\eta}$ as in [16]. Amplitude damping channels are defined via their Kraus operators:

$$ 
\begin{aligned}
A_1 &= \sqrt{p} \begin{pmatrix} 1 & 0 \\ 0 & \sqrt{\eta} \end{pmatrix} & A_2 &= \sqrt{p} \begin{pmatrix} 0 & \sqrt{1-\eta} \\ 0 & 0 \end{pmatrix} \\
A_3 &= \sqrt{1-p} \begin{pmatrix} \sqrt{\eta} & 0 \\ 0 & 1 \end{pmatrix} & A_4 &= \sqrt{1-p} \begin{pmatrix} 0 & 0 \\ \sqrt{1-\eta} & 0 \end{pmatrix},
\end{aligned}
$$

where $p, \eta \in [0, 1]$. We obtain the upper bounds given in Fig. 1. Note that this improves on the bounds obtained in [16, Fig. 2]. In fact, it is simple to see that

$$ \eta_{\text{tr}}(\mathcal{A}_{p,\eta}) \ge \frac{1}{2} \|\mathcal{A}_{p,\eta}(|+\rangle\langle+) - \mathcal{A}_{p,\eta}(|-\rangle\langle-|)\|_1 = \sqrt{\eta}, \quad (76) $$

with $|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$, $|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ so our upper bounds for $\eta_{\text{tr}}(\mathcal{A}_{p,\eta})$ are numerically tight. Furthermore, we tested the two first levels of our hierarchy on two copies of the amplitude damping channel and obtained a tighter upper bound with the second level.

We then also tested the first level of the hierarchy in Theorem 26 on (multiple copies of) qubit depolarizing channels $\mathcal{D}_p$, for $p \in [0, 1]$ defined by:

$$ \mathcal{D}_p(\cdot) = (1-p)\text{Id}_2(\cdot) + \text{tr}(\cdot)p\frac{I_2}{2}. \quad (77) $$

We obtain numerically tight upper bounds for up to 3 copies of $\mathcal{D}_p$ as shown in Fig. 2. Note that by Equation 3.31 in [16], $\eta_{\text{tr}}(\mathcal{D}_p) = 1 - p = 1 - \alpha(\mathcal{D}_p)$.

The simulations were implemented in Julia and using the solver SCS [18].

<figure><img src="image_3.png" /><figcaption>Figure 1: Upper bounds on the contraction coefficient of (multiple copies of) amplitude damping channels obtained via the first and second levels of the hierarchy proposed in Theorem 26.</figcaption></figure>

## Acknowledgements

We thank Christoph Hirche for discussions about [16] and for helpful comments on the manuscript. We also thank Arthur Mehta for discussions about the independence number of quantum confusability graphs and for feedback on the manuscript. OF would also like to thank Mario Berta for numerous discussions over the years about optimal channel coding. This work is funded by the European Research Council (ERC Grant AlgoQIP, Agreement No. 851716).
<figure><img src="image_4.png" /><figcaption>Figure 2: Upper bounds on the contraction coefficient of (multiple copies of) depolarizing channels obtained via the first level of the hierarchy proposed in Theorem 26. By choosing states of the form $|0\rangle^{\otimes i}$ and $|1\rangle^{\otimes i}$, it is simple to see that the bounds given by our SDP are numerically tight.</figcaption></figure>

## References

[1] Siddharth Barman and Omar Fawzi. Algorithmic aspects of optimal channel coding. *IEEE Transactions on Information Theory*, 64(2):1038-1045, 2017.

[2] Salman Beigi and Peter W. Shor. On the complexity of computing zero-error and Holevo capacity of quantum channels, 2008, arXiv:0709.2090.

[3] Mario Berta, Fransesco Borderi, Omar Fawzi, and Volker B. Scholz. Semidefinite programming hierarchies for constrained bilinear optimization. *Mathematical Programming*, 196:781-829, April 2021, arXiv:1810.12197v3.

[4] Hugue Blier and Alain Tapp. All languages in NP have very short quantum proofs. In *2009 Third International Conference on Quantum, Nano and Micro Technologies*, pages 34-37. IEEE, 2009, arXiv:0709.0738v1.

[5] Jop Briët, Oded Regev, and Rishi Saket. Tight hardness of the non-commutative Grothendieck problem. In *2015 IEEE 56th Annual Symposium on Foundations of Computer Science*, pages 1108-1122. IEEE, 2015, arXiv:1412.4413.

[6] Eric Culf and Arthur Mehta. New approaches to complexity via quantum graphs. *arXiv preprint arXiv:2309.12887*, 2023.

[7] Wolfgang Doeblin. Sur les propriétés asymptotiques de mouvement régis par certains types de chaines simples. *Bulletin mathématique de la Société roumaine des sciences*, 39(1):57-115, 1937.

[8] Runyao Duan. Super-activation of zero-error capacity of noisy quantum channels, 2009, arXiv:0906.2527.
[9] Runyao Duan, Simone Severini, and Andreas Winter. Zero-error communication via quantum channels and a quantum Lovász $\theta$-function. In *2011 IEEE International Symposium on Information Theory Proceedings*, pages 64–68. IEEE, 2011.

[10] Omar Fawzi, Mizanur Rahaman, and Mostafa Taheri. Capacities of quantum markovian noise for large times, February 2025, arXiv:2408.00116.

[11] Omar Fawzi, Johanna Seif, and Dániel Szilágyi. Approximation algorithms for classical-quantum channel coding. In *2019 IEEE International Symposium on Information Theory (ISIT)*, pages 2569–2573. IEEE, 2019.

[12] Christopher A. Fuchs and Jeroen van de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. *IEEE Transactions on Information Theory*, 45(4):1216–1227, May 1999.

[13] François Le Gall, Shota Nakagawa, and Harumichi Nishimura. On QMA protocols with two short quantum proofs. *Quantum Information & Computation*, 12(7-8):589–600, 2012, arXiv:1108.4306v2.

[14] Ian George, Christoph Hirche, Theshani Nuradha, and Mark Wilde. Quantum Doeblin coefficients: interpretations and applications, March 2025, arXiv:2503.22823v1.

[15] Carl W. Helstrom. Quantum detection and estimation theory. *Journal of Statistical Physics*, 1(2):231–252, March 1969.

[16] Christoph Hirche. Quantum Doeblin coefficients: a simple upper bound on contraction coefficients, 2024, arXiv:2405.00105.

[17] Assaf Naor, Oded Regev, and Thomas Vidick. Efficient rounding for the noncommutative Grothendieck inequality. In *Proceedings of the forty-fifth annual ACM symposium on Theory of computing*, pages 71–80. ACM, 2013, arXiv:1210.7656v2.

[18] Brendan O'Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. SCS: Splitting conic solver, version 3.2.8. https://github.com/cvxgrp/scs, November 2023.

[19] Aadil Oufkir and Mario Berta. Quantum channel coding: approximation algorithms and strong converse exponents, arXiv:2410.21124.

[20] Marie Beth Ruskai. Beyond strong subadditivity? Improved bounds on the contraction of generalized relative entropy. *Reviews in Mathematical Physics*, 6(5a):1147–1161, 1994.

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

[22] Satvik Singh, Mizanur Rahaman, and Nilanjana Datta. Zero-error communication under discrete-time markovian dynamics, July 2024, arXiv:2402.18703v2.

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

[24] Michael Wolf. Quantum channels & operations guided tour, July 2012.