# Random Stinespring superchannel: converting channel queries into dilation isometry queries

Filippo Girardi, Francesco Anna Mele, Haimeng Zhao, Marco Fanizza, Ludovico Lami

► To cite this version:

Filippo Girardi, Francesco Anna Mele, Haimeng Zhao, Marco Fanizza, Ludovico Lami. Random Stinespring superchannel: converting channel queries into dilation isometry queries. 2026. hal-05482438

HAL Id: hal-05482438

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

Preprint submitted on 29 Jan 2026

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 CC BY 4.0 - Attribution - International License
Random Stinespring superchannel:
converting channel queries into
dilation isometry queries

Filippo Girardi*\*¹, Francesco Anna Mele\*\dagger¹, Haimeng Zhao\*\ddagger²,
Marco Fanizza\diamond§³, and Ludovico Lami\diamond¶¹

¹Scuola Normale Superiore, Piazza dei Cavalieri 7, 56126 Pisa, Italy

²Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA

³Inria, Télécom Paris – LTCI, Institut Polytechnique de Paris

Abstract

The recently introduced random purification channel, which converts *n* copies of an arbitrary mixed quantum state into *n* copies of the same uniformly random purification, has emerged as a powerful tool in quantum information theory. Motivated by this development, we introduce a channel-level analogue, which we call the *random Stinespring superchannel*. This consists in a procedure to transform *n* parallel queries of an arbitrary quantum channel into *n* parallel queries of the same uniformly random Stinespring isometry, via universal encoding and decoding operations that are efficiently implementable. When the channel is promised to have Choi rank at most *r*, the procedure can be tailored to yield a Stinespring environment of dimension *r*. As a consequence, quantum channel learning reduces to isometry learning, yielding a simple channel learning algorithm, based on existing isometry learning protocols, that matches the performance of the two recently proposed channel tomography algorithms. Complementarily, whereas the optimality of these algorithms had previously been established only up to a logarithmic factor in the dimension, we close this gap by removing this logarithmic factor from the lower bound. Taken together, our results fully establish the optimality of these recently introduced channel learning algorithms, showing that the optimal query complexity of learning a quantum channel with input dimension *d*<sub>A</sub>, output dimension *d*<sub>B</sub>, and Choi rank *r* is Θ(*d*<sub>A</sub>*d*<sub>B</sub>).

<footnote>\*These authors contributed equally.</footnote>

<footnote>†These authors contributed equally.</footnote>

<footnote>*filippo.girardi@sns.it</footnote>

<footnote>†francesco.mele@sns.it</footnote>

<footnote>‡haimengzhao@icloud.com</footnote>

<footnote>§marco.fanizza@inria.fr</footnote>

<footnote>¶ludovico.lami@gmail.com</footnote>
# 1 Introduction

The recently introduced random purification channel [1,2], which converts $n$ copies of a mixed quantum state $\rho$ into $n$ copies of the same randomly chosen purification of $\rho$, has already proved to be a very powerful tool in quantum information theory, with applications spanning quantum learning theory [3–6], quantum Shannon theory [2], and Gaussian quantum information [6,7]. Notably, the random purification channel admits a remarkably simple analytic form [2] and can also be implemented efficiently using quantum circuits [1,3]. More precisely, for any Hilbert space $\mathcal{H}_A$ and any integer $n \ge 1$, there exists a quantum channel

$$ \Lambda_{\text{purify}}^{(n)} : \mathcal{L}(\mathcal{H}_A^{\otimes n}) \to \mathcal{L}((\mathcal{H}_A \otimes \mathcal{H}_B)^{\otimes n}), \quad (1) $$

where $\mathcal{H}_B$ is isomorphic to $\mathcal{H}_A$ and $\mathcal{L}(\mathcal{H})$ denotes the space of linear operators on $\mathcal{H}$, such that, for all states $\rho_A \in \mathcal{D}(\mathcal{H}_A)$, one has [1,2]

$$ \Lambda_{\text{purify}}^{(n)}(\rho_A^{\otimes n}) = \mathbb{E}_{U_B} \left[ (1_A \otimes U_B)(\psi_\rho)_{AB} (1_A \otimes U_B^\dagger) \right]^{\otimes n}. \quad (2) $$

where the expectation value is taken over Haar-random unitaries $U_B$ acting on $\mathcal{H}_B$, $(\psi_\rho)_{AB}$ denotes an arbitrary fixed purification of $\rho_A$ in $\mathcal{H}_A \otimes \mathcal{H}_B$, and $1_A$ is the identity operator on $\mathcal{H}_A$. In other words, this channel transforms $n$ copies of $\rho_A$ into $n$ copies of a uniformly random purification of $\rho_A$. A simpler formula describing its action is [2]

$$ \Lambda_{\text{purify}}^{(n)}(\cdot) = \sqrt{R_n} (\cdot \otimes 1_B^{\otimes n}) \sqrt{R_n}, \quad (3) $$

where $R_n := \mathbb{E}_{U_B} [(1_A \otimes U_B) \Gamma_{AB} (1_A \otimes U_B^\dagger)]^{\otimes n}$, and $\Gamma_{AB} := \sum_{i,j} |i\rangle\langle j|_A \otimes |i\rangle\langle j|_B$ is the unnormalised maximally entangled state.

The concept of purification of a state is only the first instance of the general idea that quantum information manipulation can be conceptually simplified by enlarging the underlying Hilbert space, an attitude colloquially known as the Church of the Larger Hilbert Space. Following this train of thought, the next logical step is the purification of quantum channels, called Stinespring dilation [8]: for any quantum channel $\Phi_{A \to B}: \mathcal{L}(\mathcal{H}_A) \to \mathcal{L}(\mathcal{H}_B)$, there exists a Hilbert space $\mathcal{H}_E$, representing the environment, and an isometry $V_{A \to BE}: \mathcal{H}_A \to \mathcal{H}_B \otimes \mathcal{H}_E$, called the Stinespring isometry, such that

$$ \Phi_{A \to B}(\cdot) = \text{Tr}_E [V_{A \to BE}(\cdot) V_{A \to BE}^{\dagger}]. \quad (4) $$

In particular, letting $d_A := \text{dim} \mathcal{H}_A$ and $d_B := \text{dim} \mathcal{H}_B$ denote the input and output dimensions of the channel, the environment $\mathcal{H}_E$ can always be chosen to have dimension $d_E = d_A d_B$. More generally, if the channel is promised to have Choi rank $r$, defined as the rank of the associated Choi state, then the environment can be taken to have dimension $d_E = r \le d_A d_B$.

In the same spirit as for the random purification channel, one may therefore ask the following question:
<figure><img src="image_2.png" /><figcaption>Figure 1: Schematic representation of the random Stinespring superchannel introduced in Theorem 1.</figcaption></figure>

*Can n queries of a quantum channel $\Phi_{A \to B}$ be converted into n queries of a randomly chosen Stinespring isometry $V_{A \to BE}$?*

In this paper, we answer this question in the affirmative by exhibiting a procedure, called the random Stinespring superchannel—that converts n parallel uses of a quantum channel (that is, a single query of $\Phi_{A \to B}^{\otimes n}$) into n parallel uses of the same random Stinespring isometry (that is, a single query of $V_{A \to BE}^{\otimes n}$). Notably, we also show that this procedure can be implemented efficiently in terms of a quantum circuit. This proves the Conjecture 1.8 in [1] in the case of parallel queries. More precisely, our main result is the following.

**Theorem 1 (Random Stinespring superchannel).** Let $\mathcal{H}_A$ and $\mathcal{H}_B$ be Hilbert spaces of dimensions $d_A$ and $d_B$, respectively, and let $n, r \ge 1$ such that $r \le d_A d_B$. There exist an environment Hilbert space $\mathcal{H}_E$ of dimension $r$, an auxiliary Hilbert space $\mathcal{H}_M$, an encoding quantum channel

$$ \mathcal{E} : \mathcal{L}(\mathcal{H}_A^{\otimes n}) \to \mathcal{L}(\mathcal{H}_A^{\otimes n} \otimes \mathcal{H}_M), $$

and a decoding quantum channel

$$ \mathcal{D} : \mathcal{L}(\mathcal{H}_B^{\otimes n} \otimes \mathcal{H}_M) \to \mathcal{L}(\mathcal{H}_B^{\otimes n} \otimes \mathcal{H}_E^{\otimes n}), $$

such that for every quantum channel $\Phi : \mathcal{L}(\mathcal{H}_A) \to \mathcal{L}(\mathcal{H}_B)$ with Choi rank at most $r$ it holds that

$$ (\mathcal{D} \circ (\Phi^{\otimes n} \otimes \mathrm{Id}_M) \circ \mathcal{E})(\cdot) = \mathbb{E}_{U_E} \left[ \left( (\mathbb{1}_B \otimes U_E) V_{A \to BE} \right)^{\otimes n} (\cdot) \left( V_{A \to BE}^{\dagger} (\mathbb{1}_B \otimes U_E^{\dagger}) \right)^{\otimes n} \right], \quad (5) $$

where the expectation value is taken over Haar-random unitaries $U_E$ acting on $\mathcal{H}_E$, and $V_{A \to BE}$ is any fixed Stinespring isometry associated with $\Phi$. In addition, both $\mathcal{E}$ and $\mathcal{D}$ can be implemented in polynomial time in $n$ and in the logarithm of the dimensions of the Hilbert spaces involved. In other words, $n$ parallel queries of $\Phi$ can be efficiently converted into $n$ parallel queries of a uniformly random Stinespring isometry.

The proof of this theorem is provided at the end of Section 3. The random Stinespring
superchannel is illustrated schematically in Fig. 1. At first glance, one might be tempted
to think that the procedure could be implemented by choosing the encoding channel
$\mathcal{E} = \text{Id}_{A \to A}$ and the decoding channel $\mathcal{D} = \Lambda_{\text{purify}}^{(n)}$, namely the random purification channel
defined in (2). However, this naive approach fails, as $\Lambda_{\text{purify}}^{(n)}$ automatically symmetrizes
its input, meaning that Eq. (5) would not be satisfied. (Another, more intuitive way to
think about this is that the random purification channel at the output would also purify
the input mixed states, which is not what Eq. (5) does.) In fact, our construction does not
employ the random purification channel as a subroutine.

Crucially, the encoding and decoding channels we construct are independent of the
input state and of whatever post-processing to which the output may be subjected. This
stands in contrast with the construction of [9], where the overall transformation depends
on both the input state and on the measurement that is carried out at the output —
jointly referred to as a 'tester'. By contrast, our random Stinespring superchannel is
'universal' and plays, at the level of quantum channels, the same conceptual role the random
purification channel plays for quantum states. When the channel is a replacement channel
that prepares a mixed state, our random Stinespring superchannel recovers the random
purification channel, albeit with a larger environment.

Our result is intimately connected with the topic of quantum channel learning [5,9]. In
the same spirit as Ref. [3], where the random purification channel was used to show that
mixed-state learning reduces to pure-state learning (and later generalized in Ref. [5] to
show that quantum channel learning reduces to learning a purification of the Choi state),
our construction immediately implies that quantum channel learning reduces to isometry
learning, specifically to learning a Stinespring isometry of the channel. This observation
has been used very recently in [9] (via a state- and measurement-dependent random Stine-
spring procedure) to provide another proof of the previously established formula for the
query complexity of quantum channel learning, up to logarithmic dimensional factors [5].
Specifically, our procedure — as well as that of [9] — implies that tomography of quantum
channels with input dimension $d_A$, output dimension $d_B$, and Choi rank $r$ reduces to
tomography of isometries with input dimension $d_A$ and output dimension $d_B$. By lever-
aging the upper bound on the query complexity of isometry learning found in [5,9], one
readily obtains the upper bound $O(d_A d_B r)$ on the query complexity of quantum channel
learning, which was recently established by [5] for the first time and was known to be
optimal up to logarithmic dimensional factors. As a complementary result, we also prove
a matching lower bound $\Omega(d_A d_B r)$, which holds even against the most general classes
of queries, including those with inverse and controlled queries and indefinite causal or-
der. We prove this lower bound by developing a proof technique that is purely algebraic
and reinforce the simple intuition from dimension counting, completely circumventing
the heavy representation theory machinery previously used for unitaries [10,11]. Taken
together, these results establish that the optimal query complexity for quantum channel
tomography is $\Theta(d_A d_B r)$, thereby removing the remaining logarithmic gap in the lower
bound.

The paper is organized as follows. In Section 2, we present a remarkably simple
proof of Theorem 1. In Section 3, we describe an explicit and efficient quantum circuit implementation of the random Stinespring superchannel. In Section 4, we apply our construction to the problem of quantum channel tomography and derive the optimal query complexity without additional logarithmic dimensional factors. Finally, in Section 5, we summarize our results and outline several open problems for future work.

## 2 A simple proof of Theorem 1 for $r = d_A d_B$

This section presents a simple proof of the first part of Theorem 1 in the special case of $r = d_A d_B$, without dealing with the implementation efficiency. More precisely, the goal of this section is to prove the existence of a physical supermap implementing the random Stinespring superchannel. Concretely, this amounts to showing that there exist an encoding channel $\mathcal{E}$, a memory system $M$, and a decoding channel $\mathcal{D}$ such that, for any quantum channel $\Phi_{A \to B}$, Eq. (5) holds, where $V_{A \to BE}$ denotes a fixed Stinespring isometry of $\Phi$.

To address this question, we invoke the formalism of superchannels introduced in Ref. [12]. By definition, a superchannel is a supermap $\mathcal{S}$ that maps quantum channels into quantum channels in a completely positive way. Formally, a linear map $\mathcal{S}$ taking as input maps $\mathcal{L}(\mathcal{H}_A) \to \mathcal{L}(\mathcal{H}_B)$ and outputting maps $\mathcal{L}(\mathcal{H}_{\tilde{A}}) \to \mathcal{L}(\mathcal{H}_{\tilde{B}})$ is said to be a superchannel if: (a) it is completely positive, in the sense that, for all completely positive maps $\mathcal{N} : \mathcal{L}(\mathcal{H}_A \otimes \mathcal{H}_E) \to \mathcal{L}(\mathcal{H}_B \otimes \mathcal{H}_F)$, where $E$ and $F$ are auxiliary quantum systems, the transformed map<fnref n="1" /> $(\mathcal{S} \otimes \text{id})[\mathcal{N}] : \mathcal{L}(\mathcal{H}_{\tilde{A}} \otimes \mathcal{H}_E) \to \mathcal{L}(\mathcal{H}_{\tilde{B}} \otimes \mathcal{H}_F)$ is again completely positive; and (b) it maps trace-preserving maps to trace-preserving maps.

To simplify the picture, we can look at the action of $\mathcal{S}$ at the level of Choi operators. Denoting the associated map with $\mathcal{S}_*: \mathcal{L}(\mathcal{H}_A \otimes \mathcal{H}_B) \to \mathcal{L}(\mathcal{H}_{\tilde{A}} \otimes \mathcal{H}_{\tilde{B}})$, condition (a) is equivalent to requiring that $\mathcal{S}_*$ is completely positive, and condition (b) is equivalent to demanding that it sends operators $X_{AB}$ on $\mathcal{H}_A \otimes \mathcal{H}_B$ such that $\text{Tr}_B X_{AB} = \kappa \mathbb{1}_A$, for some $\kappa \in \mathbb{R}$, to operators $Y_{\tilde{A}\tilde{B}}$ such that $\text{Tr}_{\tilde{B}} Y_{\tilde{A}\tilde{B}} = \kappa \mathbb{1}_{\tilde{A}}$.

A central result of Ref. [12] provides a useful characterization of superchannels.

**Lemma 2** [12, Theorem 1]. For any superchannel $\mathcal{S}$ there exist an encoding channel $\mathcal{E}$, a memory system $M$, and a decoding channel $\mathcal{D}$ such that, for any quantum channel $\Phi$,

$$ \mathcal{S}[\Phi] = \mathcal{D} \circ (\Phi \otimes \text{Id}_M) \circ \mathcal{E}. \qquad (6) $$

In light of Lemma 2, proving Theorem 1 reduces to establishing that the mapping

$$ \Phi^{\otimes n}(\cdot) \mapsto \mathbb{E}_{U_E} \left[ \left( (\mathbb{1}_B \otimes U_E) V_{A \to BE} \right)^{\otimes n}(\cdot) \left( V_{A \to BE}^{\dagger} (\mathbb{1}_B \otimes U_E^{\dagger}) \right)^{\otimes n} \right] \qquad (7) $$

is implementable as a superchannel. The following proposition, combined with Lemma 2, ensures that, for any $n \ge 1$, there exists a superchannel $\mathcal{S}^{(n)}$ that implements (7).

<footnote n="1">¹To define the action of $\mathcal{S} \otimes \text{id}$, note that $\mathcal{L}(\mathcal{L}(\mathcal{H}_A \otimes \mathcal{H}_E) \to \mathcal{L}(\mathcal{H}_B \otimes \mathcal{H}_F))$ is canonically isomorphic to $\mathcal{L}(\mathcal{L}(\mathcal{H}_A) \to \mathcal{L}(\mathcal{H}_B)) \otimes \mathcal{L}(\mathcal{L}(\mathcal{H}_E) \to \mathcal{L}(\mathcal{H}_F))$. We think of $\mathcal{S}$ as acting on the first tensor factor, and as id as the identity operator acting on the second.</footnote>
**Proposition 3.** Let us consider the linear map $S_*^{(n)}: \mathcal{L}(\mathcal{H}_{A^n} \otimes \mathcal{H}_{B^n}) \to \mathcal{L}(\mathcal{H}_{A^n} \otimes \mathcal{H}_{(BE)^n})$, where $n \ge 1$ is an arbitrary integer, defined as

$$S_*^{(n)}(X_{(AB)^n}) := \Lambda_{\text{purify}}^{(n)}(X_{(AB)^n}). \qquad (8)$$

Then there exists a superchannel $S^{(n)}$ taking as input maps $\mathcal{L}(\mathcal{H}_{A^n}) \to \mathcal{L}(\mathcal{H}_{B^n})$ and outputting maps $\mathcal{L}(\mathcal{H}_{A^n}) \to \mathcal{L}(\mathcal{H}_{(BE)^n})$ whose action on Choi states is given by $S_*^{(n)}$.

Before proving Proposition 3, let us briefly explain why the existence of the random Stinespring superchannel is a direct consequence of the above statements.

**Corollary 4.** For any $n \ge 1$, there exist an encoding channel $\mathcal{E}$, a memory system $M$, and a decoding channel $\mathcal{D}$ such that, for any quantum channel $\Phi_{A \to B}$,

$$\mathcal{D} \circ (\Phi^{\otimes n} \otimes \text{Id}_M) \circ \mathcal{E} = \mathbb{E}_{U_E} \left[ \left( (1_B \otimes U_E) V_{A \to BE} \right)^{\otimes n} (\cdot) \left( V_{A \to BE}^{\dagger} (1_B \otimes U_E^{\dagger}) \right)^{\otimes n} \right], \quad (9)$$

where the expectation value is taken over Haar-random unitaries $U_E$ acting on $\mathcal{H}_E$, and $V_{A \to BE}$ is any fixed Stinespring isometry associated with $\Phi_{A \to B}$.

*Proof.* Let $S^{(n)}$ be the superchannel constructed in Proposition 3. Then, for any channel $\Phi_{A \to B}$, the Choi operator $J_{(A'BE)^n}^{S^{(n)}[\Phi^{\otimes n}]}$ of $S^{(n)}[\Phi^{\otimes n}]$ can be written in terms of the Choi operator $J_{(A'B)^n}^{\Phi^{\otimes n}} = (J_{A'B}^{\Phi})^{\otimes n}$ of $\Phi^{\otimes n}$, where $J_{A'B} := \Phi_{A \to B}(\Gamma_{AA'})$, as

$$\begin{align}
J_{(A'BE)^n}^{S^{(n)}[\Phi^{\otimes n}]} &= S_*^{(n)}(J_{(A'B)^n}^{\Phi^{\otimes n}}) \nonumber \\
&= \Lambda_{\text{purify}}^{(n)}((J_{A'B}^{\Phi})^{\otimes n}) \nonumber \\
&= \Lambda_{\text{purify}}^{(n)}\left(\text{Tr}_{E^n} \left[V_{A \to BE}^{\otimes n} \Gamma_{A'A}^{\otimes n} V_{A \to BE}^{\dagger \otimes n}\right]\right) \tag{10} \\
&\stackrel{(i)}{=} \mathbb{E}_{U_E} \left[ \left( (1_B \otimes U_E) V_{A \to BE} \right)^{\otimes n} \Gamma_{A'A}^{\otimes n} (V_{A \to BE}^{\dagger} (1_B \otimes U_E^{\dagger}))^{\otimes n} \right], \nonumber
\end{align}$$

where $S_*^{(n)}$ was introduced in (8), and $V_{A \to BE}$ is any arbitrary Stinespring representation of $\Phi_{A \to B}$. In (i) we have observed that $V_{A \to BE} |\Gamma_{A'A}|$ is a legitimate purification of $J_{A'B}^{\Phi}$. The last identity follows from (2). Now, by Choi's theorem, (10) immediately implies that, for any $\rho_{A^n} \in \mathcal{L}(\mathcal{H}_{A^n})$,

$$\begin{align}
S^{(n)}[\Phi^{\otimes n}](\rho_{A^n}) &= \text{Tr}_{A^n'} \left[ (\rho_{A^n'}^{\top} \otimes 1_{B^n E^n}) J_{(A'BE)^n}^{S[\Phi^{\otimes n}]} \right] \nonumber \\
&\stackrel{(ii)}{=} \mathbb{E}_{U_E} \text{Tr}_{A^n'} \left[ \left( (1_B \otimes U_E) V_{A \to BE} \right)^{\otimes n} (1_{A^n'} \otimes \rho_{A^n}) \Gamma_{A'A}^{\otimes n} (V_{A \to BE}^{\dagger} (1_B \otimes U_E^{\dagger}))^{\otimes n} \right] \nonumber \\
&\stackrel{(iii)}{=} \mathbb{E}_{U_E} \left[ \left( (1_B \otimes U_E) V_{A \to BE} \right)^{\otimes n} \rho_{A^n} (V_{A \to BE}^{\dagger} (1_B \otimes U_E^{\dagger}))^{\otimes n} \right], \tag{11}
\end{align}$$
where in (ii) we have commuted $\rho_{A'}^T$ past the isometry and transferred its action on $A^n$ using the transpose trick, while in (iii) we have observed that $\text{Tr}_{A'} \Gamma_{A'A} = 1_A$.

Since $\mathcal{S}$ is a superchannel, according to Lemma 2 it can be implemented by means of an encoder, a decoder and a memory. Hence (9) holds true, and this concludes the proof. $\square$

We are only left with the proof of Proposition 3, which consists in a simple verification of the conditions (a) and (b) discussed at the beginning of this section.

**Proof of Proposition 3.** The map $\mathcal{S}_*^{(n)}$ is manifestly completely positive, as $\Lambda_{\text{purify}}^{(n)}$ is completely positive. Now, let $X_{(AB)^n}$ be an operator on $\mathcal{H}_{A^n} \otimes \mathcal{H}_{B^n}$ such that $\text{Tr}_{B^n} X_{(AB)^n} = \kappa 1_{A^n}$. Then,

$$ \begin{aligned} \text{Tr}_{B^n E^n} \mathcal{S}_*^{(n)}(X_{(AB)^n}) &\stackrel{(i)}{=} \text{Tr}_{B^n} \text{Tr}_{E^n} \Lambda_{\text{purify}}^{(n)} (\mathcal{P}_{AB}^{(n)}(X_{(AB)^n})) \\ &\stackrel{(ii)}{=} \text{Tr}_{B^n} [\mathcal{P}_{AB}^{(n)}(X_{(AB)^n})] \\ &\stackrel{(iii)}{=} \mathcal{P}_A^{(n)} (\text{Tr}_{B^n}[X_{(AB)^n}]) \\ &\stackrel{(iii)}{=} \kappa 1_{A^n}, \end{aligned} \quad (12) $$

where we have called $\mathcal{P}_{AB}^{(n)}$ and $\mathcal{P}_A^{(n)}$ the unital channels

$$ \begin{aligned} \mathcal{P}_{AB}^{(n)}(\cdot) &:= \frac{1}{n!} \sum_{\pi \in S_n} (P_{\pi}^{A^n} \otimes P_{\pi}^{B^n})(\cdot) (P_{\pi}^{A^n} \otimes P_{\pi}^{B^n})^{\dagger}, \\ \mathcal{P}_{A}^{(n)}(\cdot) &:= \frac{1}{n!} \sum_{\pi \in S_n} P_{\pi}^{A^n}(\cdot) P_{\pi}^{A^n \dagger}, \end{aligned} \quad (13) $$

respectively. In (i) we have used that the random purification channel symmetrizes the input, in (ii) we have recalled that, for permutation invariant inputs, the output of the random purification reduces to the original state when tracing out the auxiliary system $E^n$, and in (iii) we have noticed that the unital channel $\mathcal{P}_A^{(n)}$ acts on $\text{Tr}_{B^n}[X_{(AB)^n}] = \kappa 1_{A^n}$. This concludes the proof. $\square$

# 3 Proof of Theorem 1 and quantum circuit for the random Stinespring superchannel

## 3.1 Representation theory

In this section, we provide a brief overview of the representation-theoretic tools required for our analysis. For a detailed introduction to these topics, we refer the readers to Refs. [13, 14].

Let $\mathcal{H}$ be a Hilbert space of dimension $d$. Let $U(d)$ be the group of unitary matrices of size $d \times d$, and let $S_n$ be the symmetric group of $n$ elements. The space $\mathcal{H}^{\otimes n}$ hosts a representation of the group $U(d)$ as the action of $U^{\otimes n}$, where $U \in U(d)$, and a representation
of $S_n$, as the action of permutations of the $n$ systems. We denote the permutation unitary corresponding to the permutation $\sigma$ as $U_\sigma$. The irreducible representations of $U(d)$ and $S_n$ are labeled by Young diagrams, i.e. ordered partitions $\lambda$ of $n$. The action of the representations of $U(d)$ and $S_n$ commute, and as a representation of $S_n \times U(d)$ we have the following decomposition into irreducible representations of $\mathcal{H}^{\otimes n}$ (Schur-Weyl duality [13, 15]):

$$ \mathcal{H}^{\otimes n} = \bigoplus_{\lambda \vdash n} [\lambda] \otimes \mathcal{U}_{d, \lambda}, \qquad (14) $$

where the sum runs over all list of integers $\lambda = (\lambda_1, \dots, \lambda_{l(\lambda)})$ with $l(\lambda) \le d$ and $\lambda_1 + \dots + \lambda_{l(\lambda)} = n$. Moreover, $\mathcal{U}_{d,\lambda}$ is an irreducible representation of $U(n)$ of dimension $\dim[\mathcal{U}_{\lambda}]$, and $[\lambda]$ is an irreducible representation of $S_n$ of dimension $\dim[\lambda]$. A preferred basis for each representation space $[\lambda]$ is the Young-Yamanouchi basis; we denote the associated matrix elements of the representation $\lambda$ evaluated on $\sigma \in S_n$ as $R_\lambda(\sigma)_{k,l}$. Note that, with this choice, the representations matrices are real-valued. The character of the representation $[\lambda]$ is denoted as $\chi_\lambda(\sigma) = \text{Tr}[R_\lambda(\sigma)]$, and it is also clearly real-valued. For the unitary representation spaces $\mathcal{U}_{d,\lambda}$, a canonical choice is the Gelfand-Tsetlin basis. These two basis choices give rise to a basis of $\mathcal{H}^{\otimes n}$ that respects the structure of the decomposition of Eq. (14): we write that basis as $\{|\lambda, i, \alpha\}_{\lambda \vdash n, i \in [\dim[\lambda]]}, \alpha \in \dim[\mathcal{U}_{d,\lambda}]$. The Schur transform is the unitary operator that rotates this basis into the canonical basis [16-19]. The isotypical projector $\Pi_\lambda$ on the subspace $[\lambda] \otimes \mathcal{U}_{d,\lambda}$ in (14) can be written as

$$ \Pi_{\lambda} = \frac{\dim[\lambda]}{n!} \sum_{\sigma \in S_n} \chi_{\lambda}(\sigma) U_{\sigma}. \qquad (15) $$

We also recall that in any unitary representation $R: S_n \to \mathcal{L}(\mathcal{H})$ of the symmetric group, the operators $\Pi_\lambda^\mathcal{H} := \sum_{\sigma \in S_n} \frac{\dim[\lambda]}{n!} \sum_{\sigma \in S_n} \chi_\lambda(\sigma) R(\sigma)$ either project onto the subspace $[\lambda] \otimes M_\lambda$ where $M_\lambda$ is the multiplicity space of the irreducible representation $[\lambda]$, if $[\lambda]$ is in the decomposition into irreducible of $R$, or are equal to zero otherwise. Together with standard representation theory tools, we will also use the machinery of Weingarten calculus [20-23]. The following expression for the $U(d)$ twirl of an operator holds [23]:

$$ \mathbb{E}_{U} [U^{\otimes n} A U^{\dagger \otimes n}] = \sum_{\sigma, \tau \in S_n} \mathrm{Wg}(\tau^{-1} \sigma, d) \mathrm{Tr}[U_{\sigma}^{\dagger} A] U_{\tau}, \qquad (16) $$

where $\mathbb{E}_U$ denotes the expectation value over the Haar measure on $U(d)$, and $\mathrm{Wg}(\cdot)$ is the Weingarten function, which can be computed as [24]

$$ \mathrm{Wg}(\sigma, d) = \frac{1}{(n!)^2} \sum_{\lambda \vdash n, l(\lambda) \le d} \frac{\dim^2[\lambda]}{\dim[\mathcal{U}_{d,\lambda}]} \chi_{\lambda}(\sigma). \qquad (17) $$

We will also need the quantum Fourier transform for $S_n$. Let $\tilde{S}_n$ be a Hilbert space of dimension $n!$, and let $\{|\sigma\rangle\}_{\sigma \in S_n}$ be a basis of $\tilde{S}_n$. This space hosts the commuting left and
right regular representations $\rho_L, \rho_R$ of the symmetric group, acting as $\rho_L(\sigma)\rho_R(\sigma')|\tau\rangle = |\sigma\tau(\sigma')^{-1}\rangle$. It is well known that, as a representation space for $S_n \times S_n$, the Hilbert space $\widehat{S_n}$ decomposes as

$$ \widehat{S_n} = \bigoplus_{\lambda \vdash n} [\lambda] \otimes [\lambda]. \qquad (18) $$

Therefore, a basis for $\widehat{S_n}$ is also given by $\{|\lambda, i, j\rangle\}_{\lambda \vdash n, i, j \in [\dim[\lambda]]}$. The map QFT is the unitary map [25–27] such that:

$$ \text{QFT } |\sigma\rangle = \sum_{\lambda \vdash n, i,j \in [\dim[\lambda]]} \sqrt{\frac{\dim[\lambda]}{n!}} R_{\lambda}(\sigma)_{i,j} |\lambda, i, j\rangle. \qquad (19) $$

For any $\pi \in S_n$ we also define the unitary $C\pi$, known as controlled permutation unitary, acting on $\widehat{S_n} \otimes \mathcal{H}^{\otimes n}$ as

$$ C\pi (|\sigma\rangle \otimes |\psi\rangle) = |\sigma\rangle \otimes U_{\sigma} |\psi\rangle. \qquad (20) $$

Moreover, its inverse acts as

$$ (C\pi)^{\dagger} (|\sigma\rangle \otimes |\psi\rangle) = |\sigma\rangle \otimes U_{\sigma}^{\dagger} |\psi\rangle. \qquad (21) $$

## 3.2 An explicit formula for the random Stinespring isometry

In this subsection, we derive an explicit expression for the random Stinespring isometry in terms of the channel $\Phi$ and permutation unitaries, using the representation theoretic tools and the notation introduced above.

**Lemma 5** (Explicit formula for random Stinespring isometry). Let $\Omega$ denote the channel induced by the random Stinespring isometry appearing on the right-hand side of Eq. (5), namely

$$ \Omega(\cdot) := \mathbb{E}_{U_E} \left[ (1_{B^n} \otimes U_E)^{\otimes n} V^{\otimes n} (\cdot) V^{\dagger \otimes n} (1_{B^n} \otimes U_E^{\dagger})^{\otimes n} \right], \qquad (22) $$

where we recall that the dimension of the Stinespring environment E is r. Then, this channel can also be expressed as:

$$ \Omega(\cdot) = \sum_{\sigma \in S_n} \sum_{\lambda \vdash n, l(\lambda) \le r} \frac{1}{n!} \frac{\dim[\lambda]}{\dim[\mathcal{U}_{r,\lambda}]} (U_{\sigma} \Phi^{\otimes n} (U_{\sigma}^{\dagger}(\cdot))) \otimes (U_{\sigma} \Pi_{\lambda}). \qquad (23) $$

*Proof.* Without loss of generality, it is sufficient to verify (23) for pure states as inputs. Using (16), we have

$$ \Omega(|\psi\rangle\langle\psi|) = \sum_{\sigma, \tau \in S_n} \mathrm{Wg}(\sigma^{-1}\tau) \mathrm{Tr}_{E^n} [(1_{B^n} \otimes U_{\sigma}^{\dagger}) V^{\otimes n} (|\psi\rangle\langle\psi|) V^{\dagger \otimes n}] \otimes U_{\tau}. \qquad (24) $$
Now, we note that

$$ (1_{B^n} \otimes U_\sigma^\dagger) V^{\otimes n} |\psi\rangle = (U_\sigma \otimes 1_{E^n})(U_\sigma^\dagger \otimes U_\sigma^\dagger) V^{\otimes n} |\psi\rangle \tag{25} \\ = (U_\sigma \otimes 1_{E^n}) V^{\otimes n} (U_\sigma^\dagger |\psi\rangle) \tag{26} $$

where we used that $V_{A \to BE}^{\otimes n}(U_\sigma^\dagger |\psi\rangle) = (U_\sigma^\dagger \otimes U_\sigma^\dagger) V_{A \to BE}^{\otimes n} |\psi\rangle$. Inserting this into (24), we have

$$ \begin{align} \Omega(|\psi\rangle\langle\psi|) &= \sum_{\sigma, \tau \in S_n} \mathrm{Wg}(\sigma^{-1}\tau) \mathrm{Tr}_{E^n} \left[ (U_\sigma \otimes 1_{E^n}) V^{\otimes n} (U_\sigma^\dagger |\psi\rangle\langle\psi|) V^{\dagger\otimes n} \right] \otimes U_\tau \nonumber \\ &= \sum_{\sigma, \tau \in S_n} \mathrm{Wg}(\sigma^{-1}\tau) (U_\sigma \Phi^{\otimes n} (U_\sigma^\dagger |\psi\rangle\langle\psi|)) \otimes U_\tau \nonumber \\ \stackrel{(i)}{=} & \sum_{\sigma, \tau \in S_n} \frac{1}{(n!)^2} \sum_{\lambda \vdash n, l(\lambda) \le r} \frac{\dim^2[\lambda]}{\dim[\mathcal{U}_{r,\lambda}]} \chi_\lambda(\sigma^{-1}\tau) (U_\sigma \Phi^{\otimes n} (U_\sigma^\dagger |\psi\rangle\langle\psi|)) \otimes U_\tau \tag{26} \\ \stackrel{(ii)}{=} & \sum_{\sigma, \tau' \in S_n} \frac{1}{(n!)^2} \sum_{\lambda \vdash n, l(\lambda) \le r} \frac{\dim^2[\lambda]}{\dim[\mathcal{U}_{r,\lambda}]} \chi_\lambda(\tau') (U_\sigma \Phi^{\otimes n} (U_\sigma^\dagger |\psi\rangle\langle\psi|)) \otimes (U_\sigma U_{\tau'}) \nonumber \\ \stackrel{(iii)}{=} & \sum_{\sigma \in S_n} \frac{1}{n!} \sum_{\lambda \vdash n, l(\lambda) \le r} \frac{\dim[\lambda]}{\dim[\mathcal{U}_{r,\lambda}]} (U_\sigma \Phi^{\otimes n} (U_\sigma^\dagger |\psi\rangle\langle\psi|)) \otimes (U_\sigma \Pi_\lambda) \nonumber \end{align} $$

where in (i) we used (17), in (ii) we have changed variable $\tau \to \tau' = \sigma^{-1}\tau$, which is a one-to-one mapping, and in (iii) we used (15). $\square$

### 3.3 An explicit circuit for the random Stinespring superchannel

In this subsection, we present an explicit quantum circuit that implements the random Stinespring superchannel. A schematic representation of the circuit is shown in Fig. 2. We begin by introducing the individual components that make up the circuit.

Let $E: \mathcal{H}_A^{\otimes n} \to \tilde{S}_n \otimes \mathcal{H}_A^{\otimes n}$ denote the (encoding) isometry defined by its action on any state $|\psi\rangle \in \mathcal{H}_A^{\otimes n}$ as

$$ E |\psi\rangle := C\pi \left[ \left( \frac{1}{\sqrt{n!}} \sum_{\sigma \in S_n} |\sigma\rangle \right) \otimes |\psi\rangle \right], \tag{27} $$

and let $\mathcal{E}(\cdot) := E(\cdot)E^\dagger$ be the corresponding isometry channel. Moreover, it is known that the uniform superposition over permutations can be efficiently prepared as

$$ \frac{1}{\sqrt{n!}} \sum_{\sigma \in S_n} |\sigma\rangle = \mathrm{QFT}^\dagger |(n, 0, \dots, 0), 1, 1\rangle, \tag{28} $$

where the input state is expressed in the basis $\{|\lambda, i, j\rangle\}_{\lambda \vdash n, i, j \in [\dim[\lambda]]}$ of $\tilde{S}_n$. Next, let $D: \tilde{S}_n \otimes \mathcal{H}_B^{\otimes n} \to \tilde{S}_n \otimes \mathcal{H}_B^{\otimes n}$ denote the (decoding) unitary acting on any $|\phi\rangle \in \tilde{S}_n \otimes \mathcal{H}_B^{\otimes n}$ as

$$ D |\phi\rangle := (\mathrm{QFT} \otimes 1_{B^n}) C \pi^\dagger |\phi\rangle, \tag{29} $$
<figure><img src="image_3.png" /><figcaption>Figure 2: Circuit implementation of the random Stinespring superchannel from Theorem 6.</figcaption></figure>

and let $\mathcal{D}(\cdot) := \mathcal{D}(\cdot)\mathcal{D}^{\dagger}$ be the associated (decoding) channel. Finally, we define a quantum channel $\mathcal{T}: \mathcal{L}(\widehat{S}_n) \to \mathcal{L}(\mathcal{H}_E^{\otimes n})$ by its action on the basis operators as

$$ \mathcal{T}(|\lambda, i, j \rangle_{\lambda, \lambda'} \otimes \mathcal{U}_{r, \lambda}|k, l\rangle) := \delta_{\lambda, \lambda'} \delta_{i, k} |\lambda, j \rangle_{\lambda, \lambda'} \otimes \frac{\mathcal{U}_{r, \lambda}}{\dim[\mathcal{U}_{r, \lambda}]}, \quad (30) $$

if $l(\lambda) \le r$, and as the replacer with the maximally mixed state over $E^n$ otherwise. Note that the channel $\mathcal{T}$ acts as a measurement of the index $\lambda$, and as a $\lambda$-dependent replacer channel on the subsystem hosting $i, k$: the overall action is depicted as $\mathcal{P}_{\lambda, r}$ in Figure 2, and it consists in preparing the state $|\lambda \rangle_{\lambda} \otimes \frac{\mathcal{U}_{\lambda}}{\dim[\mathcal{U}_{\lambda, \lambda}]}$ upon recording the outcome $\lambda$.

With this notation in place, we are now ready to state and prove the main result of this subsection.

**Theorem 6 (Circuit implementing the random Stinespring superchannel).** *The quantum channel*

$$ \mathcal{C}_{A^n \to B^n E^n} := (\mathcal{U}_{\text{Schur}} \otimes \text{Id}_{B^n}) \circ (\mathcal{T}_{\widehat{S}_n \to E^n} \otimes \text{Id}_{B^n}) \circ \mathcal{D} \circ (\text{Id}_{\widehat{S}_n} \otimes \Phi_{A \to B}^{\otimes n}) \circ \mathcal{C}_{A^n \to \widehat{S}_n A^n}, \quad (31) $$

which corresponds to the circuit depicted in Fig. 2, is exactly equal to the channel $\Omega_{A^n \to B^n E^n}$ induced by the random Stinespring isometry as defined in Eq. (22), namely

$$ \mathcal{C}_{A^n \to B^n E^n}(\cdot) = \Omega_{A^n \to B^n E^n}(\cdot), \quad (32) $$

where the equality is understood with the appropriate identification of the subsystems in the tensor product.<fnref n="2" />

*Proof.* It suffices to prove that

$$ \mathcal{C}(|\psi\rangle\langle\psi|) = \Omega(|\psi\rangle\langle\psi|) \quad \forall |\psi\rangle \in \mathcal{H}_A^{\otimes n}. \quad (33) $$

<footnote n="2">²In contrast to Lemma 5, throughout this section we adopt, for ease of presentation, the convention of writing the system $B^n$ on the right-hand side of tensor products, while placing the auxiliary register $\widehat{S}_n$ and the dilation environment $E^n$ on the left. This choice simplifies the notation for controlled operations, for which it is natural to display the control system on the left.</footnote>
Let us first compute the left-hand side:

$$ \mathcal{E}(|\psi\rangle\langle\psi|) = \frac{1}{n!} \sum_{\sigma, \tau \in S_n} |\sigma\rangle\langle\tau| \otimes U_{\sigma} |\psi\rangle\langle\psi| U_{\tau}^{\dagger}. \quad (34) $$

Then, applying $\Phi^{\otimes n}$ on the register $A^n$, we obtain

$$ \begin{aligned} (\mathrm{Id}_{\widehat{S_n}} \otimes \Phi^{\otimes n}) \circ \mathcal{E}(|\psi\rangle\langle\psi|) &= \frac{1}{n!} \sum_{\sigma, \tau \in S_n} |\sigma\rangle\langle\tau| \otimes \Phi^{\otimes n} (U_{\sigma} |\psi\rangle\langle\psi| U_{\tau}^{\dagger}) \\ &= \frac{1}{n!} \sum_{\sigma, \tau \in S_n} |\sigma\rangle\langle\tau| \otimes U_{\tau} \Phi^{\otimes n} (U_{\tau^{-1}\sigma} |\psi\rangle\langle\psi|) U_{\tau}^{\dagger}, \end{aligned} \quad (35) $$

where in the last line we exploited that $\Phi^{\otimes n}(\cdot) = U_{\tau}\Phi^{\otimes n}(U_{\tau}^{\dagger}(\cdot)U_{\tau})U_{\tau}^{\dagger}$. Going forward, let us now apply $\mathcal{D}$:

$$ \begin{aligned} \mathcal{D} \circ (\mathrm{Id}_{\widehat{S_n}} \otimes \Phi^{\otimes n}) \circ \mathcal{E}(|\psi\rangle\langle\psi|) &= \frac{1}{n!} \sum_{\sigma, \tau \in S_n} \sum_{\lambda, \lambda', i, j, k, l} \frac{\sqrt{\dim[\lambda]\dim[\lambda']}}{n!} R_{\lambda}(\sigma)_{i,j} |\lambda, i, j \rangle\langle \lambda', k, l| R_{\lambda'}(\tau)_{k,l} \otimes \\ &\qquad \otimes U_{\sigma^{-1}\tau} \Phi^{\otimes n} (U_{\tau^{-1}\sigma} |\psi\rangle\langle\psi|), \end{aligned} \quad (36) $$

where we used (19) and the fact that representation matrices $R_{\lambda}(\sigma)$ are real-valued.

Now, we would like to apply the channel $\mathcal{T}$ to the auxiliary register $\widehat{S}_n$. Recall that $\mathcal{T}$, defined in Eq. (30), acts differently depending on whether the associated Young diagram $\lambda$ satisfies $l(\lambda) \le r$ or not. In order to simplify the analysis, we first observe that only the terms with $l(\lambda) \le r$ give a nonzero contribution. Indeed, note that

$$ \begin{aligned} & \sum_{\sigma, \tau \in S_n} \frac{\dim[\lambda]}{n!^2} \sum_{\lambda, j, l} R_{\lambda}(\sigma)_{i,j} R_{\lambda}(\tau)_{i,l} |\lambda, j \rangle \langle \lambda, l| \otimes U_{\sigma^{-1}\tau} \Phi^{\otimes n} (U_{\tau^{-1}\sigma} |\psi \rangle \langle \psi|) \\ &\stackrel{(v)}{=} \sum_{\sigma, \tau \in S_n} \frac{\dim[\lambda]}{n!^2} \sum_{\lambda, j, l} R_{\lambda}(\sigma^{-1})_{j,i} R_{\lambda}(\tau)_{i,l} |\lambda, j \rangle \langle \lambda, l| \otimes U_{\sigma^{-1}\tau} \Phi^{\otimes n} (U_{\tau^{-1}\sigma} |\psi \rangle \langle \psi|) \\ &\stackrel{(vi)}{=} \sum_{\sigma \in S_n} \frac{\dim[\lambda]}{n!} \sum_{\lambda, j, l} R_{\lambda}(\sigma)_{j,l} |\lambda, j \rangle \langle \lambda, l| \otimes U_{\sigma} \Phi^{\otimes n} (U_{\sigma^{-1}} |\psi \rangle \langle \psi|) \\ &\stackrel{(vii)}{=} \sum_{\sigma \in S_n} \frac{\dim[\lambda]}{n!} \sum_{\lambda, j, l} R_{\lambda}(\sigma)_{j,l} |\lambda, j \rangle \langle \lambda, l| \otimes U_{\sigma} \mathrm{Tr}_{E^n} [V^{\otimes n} (U_{\sigma^{-1}} |\psi \rangle \langle \psi|) V^{+ \otimes n}] \\ &\stackrel{(viii)}{=} \sum_{\sigma \in S_n} \frac{\dim[\lambda]}{n!} \sum_{\lambda, j, l} R_{\lambda}(\sigma)_{j,l} |\lambda, j \rangle \langle \lambda, l| \otimes \mathrm{Tr}_{E^n} [(1_{B^n} \otimes U_{\sigma^{-1}}) V^{\otimes n} (|\psi \rangle \langle \psi|) V^{+ \otimes n}], \end{aligned} \quad (37) $$

where in (v) we used that the $R_{\lambda}(\sigma)^{\dagger} = R_{\lambda}(\sigma)^{\mathrm{T}} = R_{\lambda}(\sigma^{-1})$ are real, and in (vi) we contracted the two representation matrices $R_{\lambda}$ and changed variable, in (vii) we wrote $\Phi$ in terms of
its dilation, and in (viii) we used the permutation covariance of $V^{\otimes n}$. By using that the dimension of the Stinespring environment $E^n$ is $r$, we can now insert the resolution of the identity in the $E^n$ space

$$1_{E^n} = \sum_{\lambda' \vdash n, l(\lambda') \le r} \Pi_{\lambda'} = \sum_{\lambda' \vdash n, l(\lambda') \le r} \frac{\dim[\lambda']}{n!} \chi_{\lambda'}(\pi) U_{\pi}, \quad (38)$$

and use the invariance of the measure on the group to obtain

$$
\begin{align}
& \sum_{\sigma \in S_n} \sum_{\lambda, j, l} R_{\lambda}(\sigma)_{j,l} |\lambda, j \times \lambda, l| \otimes \operatorname{Tr}_{E^n} [(1_{B^n} \otimes U_{\sigma^{-1}}) V^{\otimes n} (|\psi \times \psi|) V^{\dagger \otimes n}] \nonumber \\
& \stackrel{(\text{ix})}{=} \sum_{\lambda' \vdash n, l(\lambda') \le r} \sum_{\sigma, \pi \in S_n} \sum_{\lambda, j, l} \frac{\dim[\lambda']}{n!} \chi_{\lambda'}(\pi) R_{\lambda}(\sigma)_{j,l} |\lambda, j \times \lambda, l| \nonumber \\
& \qquad \otimes \operatorname{Tr}_{E^n} [(1_{B^n} \otimes U_{\sigma^{-1}} U_{\pi}) V^{\otimes n} (|\psi \times \psi|) V^{\dagger \otimes n}] \nonumber \\
& \stackrel{(\text{x})}{=} \sum_{\lambda' \vdash n, l(\lambda') \le r} \sum_{\sigma, \pi \in S_n} \sum_{\lambda, j, l} \frac{\dim[\lambda']}{n!} \chi_{\lambda'}(\pi) R_{\lambda}(\sigma \pi)_{j,l} |\lambda, j \times \lambda, l| \nonumber \\
& \qquad \otimes \operatorname{Tr}_{E^n} [(1_{B^n} \otimes U_{\sigma^{-1}}) V^{\otimes n} (|\psi \times \psi|) V^{\dagger \otimes n}] \tag{39} \\
& \stackrel{(\text{xi})}{=} \sum_{\lambda' \vdash n, l(\lambda') \le r} \sum_{\sigma \in S_n} \sum_{\lambda, j, l} R_{\lambda}(\sigma)_{j,l} \hat{\Pi}_{\lambda'}^{S_n} |\lambda, j \times \lambda, l| \otimes \operatorname{Tr}_{E^n} [(1_{B^n} \otimes U_{\sigma^{-1}}) V^{\otimes n} (|\psi \times \psi|) V^{\dagger \otimes n}] \nonumber \\
& \stackrel{(\text{xii})}{=} \sum_{\lambda \vdash n, l(\lambda) \le r} \sum_{\sigma \in S_n} \sum_{j, l} R_{\lambda}(\sigma)_{j,l} |\lambda, j \times \lambda, l| \otimes \operatorname{Tr}_{E^n} [(1_{B^n} \otimes U_{\sigma^{-1}}) V^{\otimes n} (|\psi \times \psi|) V^{\dagger \otimes n}] \nonumber \\
& = \sum_{\lambda \vdash n, l(\lambda) \le r} \sum_{\sigma \in S_n} \sum_{j, l} R_{\lambda}(\sigma)_{j,l} |\lambda, j \times \lambda, l| \otimes U_{\sigma} \Phi^{\otimes n} (U_{\sigma^{-1}} |\psi \times \psi|), \nonumber
\end{align}
$$

where in (ix) we inserted the resolution of the identity in terms of $\Pi_{\lambda}$ and their expression as linear combinations of permutations, in (x) we used the invariance of the measure on the group, in (xi) we recollected the isotypical projector $\hat{\Pi}_{\lambda'}^{S_n}$ in the representation space $\bigoplus_{\lambda \vdash n}[\lambda]$ and in (xii) we used that $\hat{\Pi}_{\lambda'}^{S_n} |\lambda, i\rangle = \delta_{\lambda, \lambda'} |\lambda, i\rangle$. This means that when $V$ is defined with an environment of dimension at most $r$, we can restrict the sum over Young diagrams with length less than $r$.

Then, applying $\mathcal{T}$ to the register $\hat{S}_n$, we obtain:

$$(\mathcal{T} \otimes \mathrm{Id}_{B^n}) \circ \mathcal{D} \circ (\mathrm{Id}_{\hat{S}_n} \otimes \Phi^{\otimes n}) \circ \mathcal{C}(|\psi \times \psi|) \\
= \sum_{\sigma, \tau \in S_n} \sum_{\lambda \vdash n, l(\lambda) \le r} \frac{\dim[\lambda]}{n!^2 \dim[\mathcal{U}_{r,\lambda}]} \sum_{j,l} R_{\lambda}(\sigma)_{j,l} |\lambda, j \times \lambda, l| \otimes \mathbb{1}_{\mathcal{U}_{r,\lambda}} \otimes U_{\sigma} \Phi^{\otimes n} (U_{\sigma}^{\dagger} |\psi \times \psi|) \quad (40)$$

As a consequence, we conclude that

$$\mathcal{C}(|\psi \times \psi|) = \sum_{\sigma \in S_n} \sum_{\lambda \vdash n, l(\lambda) \le r} \frac{\dim[\lambda]}{n! \dim[\mathcal{U}_{r,\lambda}]} \Pi_{\lambda} U_{\sigma} \otimes U_{\sigma} \Phi^{\otimes n} (U_{\sigma}^{\dagger} |\psi \times \psi|), \quad (41)$$
where we used the Schur–Weyl duality in (14) to write that

$$ U_{\text{Schur}}^{\dagger} \Pi_{\lambda} U_{\sigma} U_{\text{Schur}} = \sum_{j,l} R_{\lambda}(\sigma)_{j,l} |\lambda, j \rangle \langle \lambda, l| \otimes \mathbb{1}_{u_{r,\lambda}}. \qquad (42) $$

Comparing with (23) (with the appropriate identification of the subsystems in the tensor product), we obtain the claim. □

**Remark 7** (Efficiency of the circuit). The circuit of Theorem 6 requires $O(\text{poly}(n, \log d, \log \frac{1}{\eta}))$ depth, with $\eta$ being the diamond norm error due to finite gate set approximations. The circuit of QFT can be implemented in $\text{poly}(n)$ time, see [25, 26] and a refined analysis in [27]. In the implementation of [27] the permutations are arranged in the memory through their canonical encoding $\sigma = (c_{1,...,n})^{i_{n-1}}(c_{1,...,n-1})^{i_{n-2}} \dots (c_{1,2})^{i_1}$, where $c_{1,...,k}$ is the cycle on $\{1,...,k\}$ and $i_k \in \{0,...,k\}$ for any $k \in \{2,...,n\}$, so that $i_1$ can be stored in a qubit, $i_2$ in a qutrit, and so on until $i_{n-1}$, which is stored in a $n$-dimensional space. By applying cycles controlled by each of these registers in sequence, one can implement $C\pi$ in time $O(\text{poly}(n, \log d))$. The channel $\mathcal{T}$ is just a partial trace composed with a preparation of a maximally mixed state: this preparation is depicted as $\mathcal{P}_{\lambda,r}$ in Figure 2 and it consists in preparing the state $|\lambda \rangle \langle \lambda| \otimes \frac{1}{\dim[\mathcal{U}_{r,\lambda}]}$. Finally, the last step is a Schur transform: circuits with complexity polynomial in the number of copies and dimension were first proposed in [16], and Harrow [17] sketched a method in his thesis to lower the dimension dependence to $O(\log d)$. A detailed proposal to achieve this was presented in [18], which was recently found to contain a mistake [28]. A corrected version of this proposal and an improved version of the original algorithm [16] have been established by [19], confirming the $O(\text{poly}(n, \log d))$ complexity.

**Remark 8** (Intuition behind the circuit). The reader may wonder how we came up with the circuit, and whether there is some intuition behind it. The process involved some trial and error to reproduce the desired supermap for $n = 1$ and $n = 2$ using controlled permutations, and the general ansatz was found by observing that the QFT method for weak Schur sampling based on the QFT in Chapter 8 of Harrow's thesis [17] was, in fact, implementing the main step of the random purification channel of [1]. A more systematic, representation-theoretic derivation of the random Stinespring superchannel will be presented in a future version of this manuscript.

We are now ready to prove our main result, stated in Theorem 1.

*Proof of Theorem 1.* The existence of encoding maps, a memory system, and decoding maps satisfying (5) follows directly from Theorem 6. Furthermore, the efficiency of the circuit implementing the random Stinespring superchannel is established by Remark 7. □

# 4 Applications to quantum channel learning

In this section, we apply the random Stinespring superchannel to the application of quantum channel learning. It allows us to reduce general channel tomography to isometry
tomography, and obtain the optimal query complexity $O(r d_A d_B)$ of learning rank-$r$ quantum channels. We also develop an algebraic lower bound technique based on polynomial method [29] that allows us to prove a clean $\Omega(r d_A d_B)$ lower bound without any logarithmic factors and is secure against arbitrary types of queries (e.g., queries to the inverse or controlled versions of the channel, or with indefinite causal order). Together, this establishes $\Theta(r d_A d_B)$ as the optimal query complexity of learning rank-$r$ quantum channels.

We note that alternative learning algorithms achieving the same $O(r d_A d_B / \epsilon^2)$ query complexity have recently been developed in [5] via a random purification channel on Choi states and in [9] via a tester-dependent random dilation procedure (i.e., its construction depends explicitly on both the input state and on the measurement carried out at the output). Our results provide an alternative, state- and measurement-agnostic way to reduce channel learning to isometry learning. Meanwhile, the only known lower bound for general non-isometry channels is $\Omega(d_A^2 d_B^2 / \log(d_A d_B))$ when the channels have full rank ($r = d_A d_B$). It has undesired logarithmic factors and holds when we only allow sequential queries of the channel [30]. We now restate the main result of this section in the form of a quotable theorem.

**Theorem 9 (Optimal query complexity of channel learning).** Let $\Phi: \mathcal{L}(\mathcal{H}_A) \to \mathcal{L}(\mathcal{H}_B)$ be any quantum channel with input dimension $d_A$, output dimension $d_B \ge 2$, and rank at most $r$. From [5,9] it is known that there is a quantum learning algorithm that makes

$$n = O(r d_A d_B / \epsilon^2) \qquad (43)$$

parallel queries to the channel $\Phi$ and outputs a classical description of a channel $\hat{\Phi}$ such that $\|\hat{\Phi} - \Phi\|_{\diamond} \le \epsilon$ with probability at least $2/3$. Furthermore, any quantum algorithm that learns $\Phi$ to constant error with success probability at least $2/3$ must make at least

$$n \ge \Omega(r d_A d_B) \qquad (44)$$

queries even if it is allowed to query $\Phi$ in an arbitrary way (e.g., query the inverse and controlled versions of $\Phi$ if they exist, or with indefinite causal order).

**Note added.** The improved lower bound on the query complexity of channel learning presented in Theorem 9, without logarithmic factors, has been obtained independently by Antonio Anna Mele and Lennart Bittel, as we learned through private communication. Accordingly, this lower bound will also appear in version 2 of [5] or in a future work.

The upper bound in Theorem 9 follows immediately from our random Stinespring superchannel and existing isometry learning algorithms, such us the one provided in [5] via Choi-state learning or the one in [9, Appendix A], which is a slight modification of the unitary tomography algorithm in [10]. These subroutines of isometry learning only makes parallel queries to the isometry and therefore our random Stinespring superchannel can be directly applied.

On the lower bound front, it is intuitive that an $\Omega(r d_A d_B)$ bound should hold by dimension counting. But the only lower bound known for general non-isometry channels
is $\Omega(d_A^2 d_B^2 / \log(d_A d_B))$ when $r = d_A d_B$ with an undesired logarithmic factor and holds when we only allow sequential queries of the channel [30]. This logarithmic factor comes from a crude information-theoretic analysis that does not take into account the permutation symmetry between queries of the channel (i.e., they are the same channel). A natural way to make use of the permutation symmetry is via the heavy machinery of group representation theory. For example, [10] shows an $\Omega(d^2/\epsilon)$ lower bound for unitary tomography ($r = 1, d_A = d_B = d$) that does not have any logarithmic factor using a unitary distinguishing bound [11] proved via Schur-Weyl duality.

However, this route is undesirable for several reasons: (1) it uses heavy group representation theory machinery that departs significantly from our simple intuition of dimension counting; (2) whether it can be generalised to channels is unclear since channels do not even form a group; (3) when we are allowed to make queries to the inverse or controlled versions of the channel (if they exist), the queries are no longer permutation symmetric.

To overcome these difficulties, we develop a lower bound proof technique that is purely algebraic and only depends on the linearity of quantum mechanics. It completely circumvents the representation theory machinery and reduces everything to simple dimension counting. The permutation symmetry is then used transparently in dimension counting. This allows us to prove a channel distinguishing bound that extends the unitary version [11] and is secure against any type of queries to the channel. The claimed query lower bound for channel tomography follows directly from the standard reduction from learning to distinguishing using packing net. We expect that this proof strategy can be applied to quantum channels with other parameterization beyond bounded rank.

In the following, we detail the proof of the lower bound in Theorem 9. We begin by explaining the algebraic proof that leads to the following channel distinguishing bound.

**Theorem 10 (Polynomial method for channel distinguishing).** Let $\{\Phi_x\}_{x=1}^M$ be a set of quantum channels with input dimension $d_A$, output dimension $d_B$, and Choi rank $r \le d_A d_B$. Given any quantum channel $\Phi_x$, $x \in [M]$ from the set, any quantum algorithm (even with indefinite causal order) that makes $n$ queries to the channel $\Phi_x$ and produces an outcome $\hat{X} \in [M]$ with correct probability $\Pr[\hat{X} = x | \Phi_x] > 1/2$ for any $x \in [M]$ must satisfy

$$ \frac{1}{2} \log M \le \log \binom{n + r d_A d_B - 1}{n} \qquad (45) $$

This still holds when the quantum algorithm is allowed to query the inverse and controlled versions of $\Phi_x$ if they exist.

*Proof.* The proof generalises the polynomial method developed in [29,31]. The key idea is to exploit the linearity of quantum mechanics, which implies that the measurement probability of any quantum algorithm that makes $n$ queries to a channel must be a polynomial of the channel parameters with degree determined by $n$. But the degree cannot be too small in order to distinguish many channels. This gives a lower bound on the query complexity $n$.
Suppose that there is a quantum algorithm that makes $n$ queries to the channel $\Phi_x$ and produce an outcome $\hat{X} \in [M]$ that has correct probability $\text{Pr}[\hat{X} = x | \Phi_x] > 1/2$ for any $x \in [M]$. We consider the confusion matrix $P \in \mathbb{R}^{M \times M}$ of this quantum algorithm. It is an $M \times M$ matrix with matrix elements $P_{\hat{x}x}, \hat{x}, x \in [M]$ representing the probability that the quantum algorithm predicts $\hat{x}$ when the quantum channel that it truly queries is $\Phi_x$. We have $\sum_{\hat{x}=1}^M P_{\hat{x}x} = 1$ for all $x \in [M]$. The guarantee of correct probability implies that $P_{xx} > 1/2$ for any $x \in [M]$. Therefore,

$$ \sum_{\hat{x} \neq x} P_{\hat{x}x} = 1 - P_{xx} < \frac{1}{2} < P_{xx}, \quad \forall x \in [M], \qquad (46) $$

meaning that the confusion matrix $P$ is strictly diagonally dominant. This implies that $P$ has full rank:

$$ \text{rank}(P) = M. \qquad (47) $$

On the other hand, all these matrix elements are measurement probabilities of a quantum algorithm querying the channel $\Phi_x$. Let

$$ \Phi_x(\rho) = \sum_{i=1}^{r} K_i^x(\rho) K_i^{x\dagger} \qquad (48) $$

be the Kraus operator representation of the quantum channel $\Phi_x$. We use a complex vector $z^x \in \mathbb{C}^{rd_A d_B}$ to collect all the parameters in the Kraus operators:

$$ z_{i \cdot d_A d_B + j \cdot d_A + k}^{x} = (K_{i}^{x})_{jk}. \qquad (49) $$

Then the matrix elements of the output of the quantum channel $\Phi_x$ can be regarded as a polynomial of $z^x$ and its complex conjugate $\bar{z}^x$:

$$ (\Phi_x(\rho))_{ij} = \sum_{a,b=1}^{rd_A d_B} w_{ij,ab} z_a^x \bar{z}_b^x, \quad \forall i,j \in [d_B], \qquad (50) $$

where the coefficients $w_{ij,ab} \in \mathbb{C}$ are determined by the input state $\rho$.

We generalise this polynomial representation to the measurement probability of an arbitrary quantum algorithm (possibly with indefinite causal order) querying the channel $\Phi_x$. The most general form of the measurement probability $P_{\hat{x}x}$ is represented as the contraction of a general *algorithm tensor* $(T_{\hat{x}})_{i_1 i'_1 o_1 o'_1 \dots i_n i'_n o_n o'_n}, i_1, \dots, i_n, i'_1, \dots, i'_n \in [d_A], o_1, \dots, o_n, o'_1, \dots, o'_n \in [d_B]$ with $n$ copies of the channel tensor $(\Phi_x)_{ii'oo'}, i, i' \in [d_A], o, o' \in [d_B]$:

$$ P_{\hat{x}x} = \sum_{\substack{i_1, \dots, i_n, i'_1, \dots, i'_n \in [d_A] \\ o_1, \dots, o_n, o'_1, \dots, o'_n \in [d_B]}} (T_{\hat{x}})_{i_1 i'_1 o_1 o'_1 \dots i_n i'_n o_n o'_n} (\Phi_x)_{i_1 i'_1 o_1 o'_1 \dots} \dots (\Phi_x)_{i_n i'_n o_n o'_n}. \qquad (51) $$
Here, for each $j \in [n]$, the indices $i_j i'_j o_j o'_j$ of the tensor $T_{\hat{x}}$ are contracted with the $n$-th copy of the channel $\Phi_x$. Note that the tensor $T_{\hat{x}}$ must satisfy certain conditions to ensure that the outcome is a proper probability (e.g., $P_{\hat{x}} \in [0,1], \sum_{\hat{x}} P_{\hat{x}} = 1$), but for our purposes we do not use those conditions. Plugging in the $z^x, \bar{z}^x$ parameterization of the channel $\Phi_x$, we have

$$P_{\hat{x}} = \sum_{\substack{a_1, \dots, a_n \in [rd_A d_B] \\ b_1, \dots, b_n \in [rd_A d_B]}} w_{a_1 \dots a_n b_1 \dots b_n}^{\hat{x}} z_{a_1}^x \cdots z_{a_n}^x \bar{z}_{b_1}^x \cdots \bar{z}_{b_n}^x, \qquad (52)$$

where the coefficients $w_{a_1 \dots a_n b_1 \dots b_n}^{\hat{x}}$ are determined by the algorithm tensor $T_{\hat{x}}$ and the terms $z_{a_j}^x \bar{z}_{b_j}^x$ that are contributed by the $j$-th copy of the channel tensor $\Phi_x$.

We note that this way of organising coefficients has redundancy, because the $n$ copies of $z$'s (and $\bar{z}$'s) are symmetric to each other. For example, the terms $z_1 z_2$ and $z_2 z_1$ are the same and can be grouped together to share one coefficient. In other words, the order in the indices $(a_1, \dots, a_n)$ and $(b_1, \dots, b_n)$ does not matter. We use $\mathrm{Sym}(rd_A d_B, n)$ to denote the set of such unordered indices and use $Z_{\alpha}^x, \bar{Z}_{\beta}^x \in \mathbb{C}, \alpha, \beta \in \mathrm{Sym}(rd_A d_B, n)$ to denote the terms $z_{a_1}^x \cdots z_{a_n}^x, \bar{z}_{b_1}^x \cdots \bar{z}_{b_n}^x$ corresponding to the unordered indices $\alpha, \beta$. Then we have the following polynomial representation of the probability

$$P_{\hat{x}} = \sum_{\alpha, \beta \in \mathrm{Sym}(rd_A d_B, n)} W_{\alpha\beta}^{\hat{x}} Z_{\alpha}^{x} \bar{Z}_{\beta}^{x}, \qquad (53)$$

where the coefficients $W_{\alpha\beta}^{\hat{x}}$ are the sum of all $w_{a_1 \dots a_n b_1 \dots b_n}^{\hat{x}}$ with $(a_1, \dots, a_n), (b_1, \dots, b_n)$ corresponding to $\alpha, \beta$. To count the size of $\mathrm{Sym}(rd_A d_B, n)$, we note that each $\alpha \in \mathrm{Sym}(rd_A d_B, n)$ can be labeled by the number of times $n_a$ each symbol $a \in [rd_A d_B]$ appears in the unordered indices $\alpha$. They satisfy

$$\sum_{a=1}^{rd_A d_B} n_a = n, \quad n_a \ge 0, \quad \forall a \in [rd_A d_B]. \qquad (54)$$

Standard combinatorial counting yields

$$|\mathrm{Sym}(rd_A d_B, n)| = \binom{n + rd_A d_B - 1}{n}. \qquad (55)$$

The polynomial representation gives us a matrix decomposition of the confusion matrix $P$:

$$P = \mathcal{W} \mathcal{X}, \qquad (56)$$

where the matrices

$$\mathcal{W} \in \mathbb{C}^{M \times |\mathrm{Sym}(rd_A d_B, n)|^2}, \quad \mathcal{X} \in \mathbb{C}^{|\mathrm{Sym}(rd_A d_B, n)|^2 \times M}, \qquad (57)$$
are given by the coefficients $W_{\alpha\beta}^{\hat{x}}$ and monomials $Z_{\alpha}^{x} \bar{Z}_{\beta}^{x}$: for each $x, \hat{x} \in [M]$, the $\hat{x}$-th row of $\mathcal{W}$ is the row vector $(W_{\alpha\beta}^{\hat{x}})_{\alpha,\beta \in \text{Sym}(rd_{A}d_{B},n)}$ and the $x$-th column of $\mathcal{X}$ is the column vector $((Z_{\alpha}^{x} \bar{Z}_{\beta}^{x})_{\alpha,\beta \in \text{Sym}(rd_{A}d_{B},n)})^{T}$. In other words,

$$P_{\hat{x}x} = \sum_{\gamma=1}^{|\text{Sym}(rd_{A}d_{B},n)|^2} \mathcal{W}_{\hat{x},\gamma} \mathcal{X}_{\gamma,x}. \qquad (58)$$

Therefore, the rank of the confusion matrix satisfies

$$M = \text{rank}(P) \le |\text{Sym}(rd_{A}d_{B}, n)|^2 = \binom{n + rd_{A}d_{B} - 1}{n}^2. \qquad (59)$$

Taking the logarithm, we arrive at the desired result

$$\log M \le 2 \log \binom{n + rd_{A}d_{B} - 1}{n}. \qquad (60)$$

When we are allowed to query the inverse and controlled versions of $\Phi_x$ if they exist, the contracted channel tensor is the same as that of $\Phi_x$ itself with $z^x$ and $\bar{z}^x$ swapped or padded with fixed numbers that represents the control pattern. This does not change the polynomial representation and the counting. Therefore, we still have have

$$\log M \le 2 \log \binom{n + rd_{A}d_{B} - 1}{n}. \qquad (61)$$

This completes the proof of Theorem 10. $\square$

To prove a query complexity lower bound for learning, we instantiate the $M$ quantum channels with the maximal cardinality while keeping their distinguishability under a learning algorithm. This can be done by constructing an $\varepsilon$-packing net of the set of rank-$r$ channels.

**Definition 11 (Packing net).** Let $(X, d)$ be a metric space. Let $K \subseteq X$ be a subset and $\varepsilon > 0$. Then, a subset $N \subseteq K$ is an $\varepsilon$-packing net of $K$ if for any $x, y \in N$, $d(x, y) > \varepsilon$. The packing number $\mathcal{M}(K, d, \varepsilon)$ of $K$ is the largest possible cardinality of an $\varepsilon$-packing net of $K$.

To construct a packing net for channels, we first construct a packing net for isometries.

**Lemma 12 (Packing number of isometries [32]).** Let $d_2 \ge d_1$ be positive integers and $\| \cdot \|$ be the operator norm. Let $\mathcal{V}_{d_1 \to d_2} = \{V \in \mathbb{C}^{d_2 \times d_1} : V^\dagger V = \mathbb{1}_{d_1}\}$ be the set of isometries with input dimension $d_1$ and output dimension $d_2$, also known as the Stiefel manifold. It has dimension $\dim(\mathcal{V}_{d_1 \to d_2}) = 2d_1d_2 - d_1^2 \in [d_1d_2, 2d_2d_2]$ and packing number

$$\left(\frac{C_1}{\varepsilon}\right)^{\dim(\mathcal{V}_{d_1 \to d_2})} \le \mathcal{M}(\mathcal{V}_{d_1 \to d_2}, \| \cdot \|, \varepsilon) \le \left(\frac{C_2}{\varepsilon}\right)^{\dim(\mathcal{V}_{d_1 \to d_2})} \qquad (62)$$
for some universal constants $C_1, C_2 > 0$. In particular, when $d_2 = d_1 = d$, we have that the packing number of the $d$-dimensional unitary group satisfies

$$ \left(\frac{C_1}{\epsilon}\right)^{d_2} \le \mathcal{M}(\mathcal{V}_{d \to d}, \|\cdot\|, \epsilon) \le \left(\frac{C_2}{\epsilon}\right)^{d_2}. \qquad (63) $$

The diamond norm on channels are connected to the operator norm on their Stinespring dilations by the following continuity lemma.

**Lemma 13 (Continuity of Stinespring dilation [33]).** Let $\Phi_1, \Phi_2 : \mathcal{L}(\mathcal{H}_A) \to \mathcal{L}(\mathcal{H}_B)$ be two quantum channels with Stinespring dilations $V_1, V_2 : \mathcal{H}_A \to \mathcal{H}_B \otimes \mathcal{H}_E$. Then, we have

$$ \inf_U \|(1_B \otimes U)V_1 - V_2\|^2 \le \|\Phi_1 - \Phi_2\|_{\diamond} \le 2 \inf_U \|(1_B \otimes U)V_1 - V_2\|, \qquad (64) $$

where the infimum is over all unitary $U$ on $\mathcal{H}_E$, $\|\cdot\|_{\diamond}$ is the diamond norm, and $\|\cdot\|$ is the operator norm.

This shows that channels can be viewed as isometries with the unitary group on the environment quotient out. This observation enables us to bound the packing number of channels in diamond norm as follows.

**Lemma 14 (Packing number of channels).** Let $\mathcal{C}_{d_A, d_B, r}$ be the set of quantum channels with input dimension $d_A$, output dimension $d_B$, and rank $r$. Assume that $d_B \ge 2$. We have

$$ \log \mathcal{M}(\mathcal{C}_{d_A, d_B, r}, \|\cdot\|_{\diamond}, \epsilon) = \Theta\left(r d_A d_B \log(1/\epsilon)\right). \qquad (65) $$

*Proof.* The proof of Lemma 4 in [34, arXiv version] (see also Lemma 10 in [35]), combined with Lemma 13, shows that $\mathcal{M}(\mathcal{C}_{d_A, d_B, r}, \|\cdot\|_{\diamond}, \epsilon)$ is asymptotically bounded from both sides by the packing number of $\mathcal{V}_{d_A \to r d_B}$ in $\|\cdot\|$ divided by the packing number of $\mathcal{V}_{r \to r}$ in $\|\cdot\|$ up to a quadratic difference in $\epsilon$. When we take the logarithm, the division becomes subtraction. Using Lemma 12, we have

$$ \log \mathcal{M}(\mathcal{C}_{d_A, d_B, r}, \|\cdot\|_{\diamond}, \epsilon) = \Theta\left((2rd_A d_B - d_A^2) \log(1/\epsilon)\right) - \Theta(r^2 \log(1/\epsilon)) \\ = \Theta\left((2rd_A d_B - d_A^2 - r^2) \log(1/\epsilon)\right) \qquad (66) $$

Further note that $2rd_A d_B - d_A^2 - r^2 \le 2rd_A d_B$ and

$$ \begin{aligned} 2rd_A d_B - d_A^2 - r^2 &= rd_A d_B \left(2 - \frac{1}{d_B} \left(\frac{d_A}{r} + \frac{r}{d_A}\right)\right) \\ &\ge rd_A d_B \left(2 - \frac{1}{d_B} \left(d_B + \frac{1}{d_B}\right)\right) \\ &= rd_A d_B \left(1 - \frac{1}{d_B^2}\right) \\ &\ge \frac{3}{4}rd_A d_B, \end{aligned} \qquad (67) $$
when $d_B \ge 2$. Here, we used the fact that $r \le d_A d_B$ and $rd_B \ge d_A$, and that the function $f(x) = x + 1/x$ is convex and hence its maximum on $d_A/r \in [1/d_B, d_B]$ must be attained at the endpoints. This means that $2rd_A d_B - d_A^2 - r^2 = \Theta(rd_A d_B)$ and therefore

$$ \log \mathcal{M}(\mathcal{C}_{d_A, d_B, r}, \| \cdot \|_{\diamond}, \varepsilon) = \Theta(rd_A d_B \log(1/\varepsilon)). \quad (68) $$

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

The following lemma helps us work through the binomial factors and calculate the query complexity bound.

**Lemma 15.** Let $n, d$ be positive integers. Suppose $\log \binom{n+d-1}{n} \ge c(d-1)$ for some constant $c > 0$; then $n \ge g^{-1}(c)(d-1)$, where $g(x) = (1+x)\log(1+x) - x\log(x)$, called the 'bosonic entropy function', is monotonically increasing.

*Proof.* When $d=1$, the lemma clearly holds. When $d \ge 2$, we begin by relating the log binomial coefficient to the binary entropy function $H_2(p) := -p \log p - (1-p) \log(1-p)$. Note that

$$ \begin{aligned} 1 &= \left( \frac{d-1}{n+d-1} + 1 - \frac{d-1}{n+d-1} \right)^{n+d-1} \\ &= \sum_{i=0}^{n+d-1} \binom{n+d-1}{i} \left( \frac{d-1}{n+d-1} \right)^i \left( 1 - \frac{d-1}{n+d-1} \right)^{(n+d-1)-i} \\ &\ge \binom{n+d-1}{d-1} \left( \frac{d-1}{n+d-1} \right)^{d-1} \left( 1 - \frac{d-1}{n+d-1} \right)^{(n+d-1)-(d-1)} \\ &= \binom{n+d-1}{d-1} 2^{-(n+d-1)H_2\left(\frac{d-1}{n+d-1}\right)}. \end{aligned} \quad (69) $$

Thus,

$$ c(d-1) \le \log \binom{n+d-1}{n} = \log \binom{n+d-1}{d-1} \le (n+d-1)H_2\left(\frac{d-1}{n+d-1}\right). \quad (70) $$

Let $x = \frac{n}{d-1} > 0$. We have

$$ g(x) = (1+x)H_2\left(\frac{1}{1+x}\right) \ge c. \quad (71) $$

Note that the bosonic entropy function $g(x)$ is monotonically increasing, since it has derivative $\log(1+1/x) > 0$ for all $x > 0$. Therefore, we have $x \ge g^{-1}(c)$ and

$$ n \ge g^{-1}(c)(d-1). \quad (72) $$

This concludes the proof.

<figure><img src="image_5.png" /></figure>
Now we are ready to prove the lower bound in Theorem 9.

*Proof of the lower bound in Theorem 9.* Consider any quantum algorithm that learns $\Phi$ to $\varepsilon = \Theta(1)$ error with success probability at least 2/3 using $n$ queries. It is allowed to query $\Phi$ in an arbitrary way (e.g., query the inverse and controlled versions of $\Phi$ if they exist, or with indefinite causal order), as in Theorem 10. We take a maximal $3\varepsilon$-packing net $\mathcal{M} = \{\Phi_x\}_{x=1}^{|\mathcal{M}|}$ in diamond norm over the set of channels with input dimension $d_A$, output dimension $d_B$, and rank $r$. Lemma 14 asserts that the cardinality of this net satisfies

$$ \log |\mathcal{M}| = \Theta(r d_A d_B \log(1/\varepsilon)). \qquad (73) $$

Now we construct a channel distinguishing algorithm that identifies elements of the net $\mathcal{M}$. Specifically, we run the channel learning algorithm that makes $n$ queries to any $\Phi_x \in \mathcal{M}$ and outputs a classical description of a channel $\hat{\Phi}$. The learning guarantee implies that with probability at least 2/3, we have $\|\hat{\Phi} - \Phi_x\|_{\diamond} \le \varepsilon$. Triangle inequality then asserts that for any $x' \in [|\mathcal{M}|], x' \ne x$, we have

$$ \|\hat{\Phi} - \Phi_{x'}\|_{\diamond} \ge \|\Phi_x - \Phi_{x'}\|_{\diamond} - \|\hat{\Phi} - \Phi_x\|_{\diamond} \ge 3\varepsilon - \varepsilon = 2\varepsilon > \varepsilon = \|\hat{\Phi} - \Phi_x\|_{\diamond}. \qquad (74) $$

This means that the channel in the net that is closest to the estimate $\hat{\Phi}$ is unique and exactly $\Phi_x$ itself. We can find this closest channel by brute force enumerating all elements of the net. This gives a channel distinguishing algorithm with success probability at least 2/3. The channel distinguishing bound Theorem 10 immediately implies that

$$ \Theta(r d_A d_B \log(1/\varepsilon)) = \frac{1}{2} \log |\mathcal{M}| \le \binom{n + r d_A d_B - 1}{n}. \qquad (75) $$

Using Lemma 15, we arrive at

$$ n \ge \Omega(r d_A d_B), \qquad (76) $$

as desired. This completes the proof of Theorem 9. $\square$

# 5 Conclusion

In this work, we introduce the random Stinespring superchannel, a channel-level analogue of random purification for quantum states. This procedure enables the conversion of multiple parallel uses of an arbitrary quantum channel into equally many parallel uses of the same uniformly random Stinespring isometry, using universal and efficiently implementable encoding and decoding operations. Our proof combines techniques from quantum Shannon theory [12] to establish the existence of such encoding and decoding operations with representation-theoretic tools based on Schur-Weyl duality to construct an explicit and efficient circuit that realizes it.

Beyond its conceptual relevance, the random Stinespring superchannel has concrete implications for quantum learning theory. In particular, it directly implies that tomography of quantum channels reduces to tomography of isometries, leading to recently
established query-complexity upper bounds for quantum channel learning [5,9]. As a complementary result, we derive an improved lower bound on the query complexity that holds even for the most general classes of queries, including those with inverse and controlled queries and indefinite causal order. This is shown by developing a lower bound technique that is purely algebraic and reinforce the simple intuition from dimension counting, completely circumventing the heavy representation theory machinery previously used for unitaries. We expect that this proof strategy can be applied to quantum channels with other parameterization beyond bounded rank. Taken together, these results establish that the optimal query complexity for tomography of quantum channels with input dimension $d_A$, output dimension $d_B$, and Choi rank $r$ scales as $Θ(d_A d_B r)$, without additional logarithmic factors. In particular, this shows that the upper bound first obtained in [5] and later reproved in [9] is indeed optimal.

We expect our efficient construction of the random Stinespring superchannel to have applications in other fields beyond quantum learning theory. For example, it may lead to simplified proofs of fundamental information theory results on quantum channels, similar to the proof of Ulmhann theorem for divergences using random purification channel [2]. It may also help in designing quantum thermodynamic protocols by reducing many copies of mixed states to pure states, where energy-optimal and provably-efficient thermodynamic protocols have been developed [36].

An intriguing open problem concerns the adaptive setting. Specifically, it remains unclear whether *n* uses of a quantum channel can be converted into *n* possibly adaptive uses of a randomly chosen Stinespring isometry associated with the channel. Another promising open direction is whether, in the same spirit as in [6,7], where a protocol is introduced to convert *n* copies of a Gaussian mixed state into *n* copies of a randomly chosen Gaussian purification, one can convert *n* queries of a Gaussian bosonic or fermionic channel into *n* queries of a randomly chosen Gaussian Stinespring isometry. Such a result would have direct applications to bounding the query complexity of learning Gaussian channels, which has currently been done only in the special case of Gaussian unitary channels [37].

## Acknowledgments

We are grateful to Lennart Bittel, Hsin-Yuan Huang, Iman Marvian, Antonio Anna Mele, and John Wright for inspiring discussions. In particular, we are deeply grateful to Lennart Bittel: early in this project, we had arrived at an incorrect argument purporting to rule out the existence of a random Stinespring superchannel; then his careful feedback revealed the flaw in that reasoning and prompted us to revisit the problem, ultimately leading to the results presented here. MF thanks Giacomo De Palma for his kind hospitality at the University of Bologna, where part of this work was done. FG, FAM, and LL acknowledge financial support from the European Union (ERC StG ETQO, Grant Agreement no. 101165230). The Institute for Quantum Information and Matter is an NSF Physics Frontiers Center (PHY-2317110).
References

[1] Ewin Tang, John Wright, and Mark Zhandry. Conjugate queries can help. *arXiv preprint arXiv:2510.07622*, 2025. 2, 3, 14

[2] Filippo Girardi, Francesco Anna Mele, and Ludovico Lami. Random purification channel made simple. *Preprint arXiv:2511.23451*, 2025. 2, 23

[3] Angelos Pelecanos, Jack Spilecki, Ewin Tang, and John Wright. Mixed state tomography reduces to pure state tomography. *arXiv preprint arXiv:2511.15806*, 2025. 2, 4

[4] Takeru Utsumi, Yoshifumi Nakata, Qisheng Wang, and Ryuji Takagi. Quantum algorithms for Uhlmann transformation. *arXiv preprint arXiv:2509.03619*, 2025. 2

[5] Antonio Anna Mele and Lennart Bittel. Optimal learning of quantum channels in diamond distance. *Preprint arXiv:2512.10214*, 2025. 2, 4, 15, 23

[6] Michael Walter and Freek Witteveen. A random purification channel for arbitrary symmetries with applications to fermions and bosons. *Preprint arXiv:2512.15690*, 2025. 2, 23

[7] Francesco Anna Mele, Filippo Girardi, Senrui Chen, Marco Fanizza, and Ludovico Lami. Random purification channel for passive gaussian bosons. *arXiv preprint arXiv:2512.16878*, 2025. 2, 23

[8] W. F. Stinespring. Positive functions on $C^*$-algebras. *Proc. Am. Math. Soc.*, 6(2):211–216, 1955. 2

[9] Kean Chen, Nengkun Yu, and Zhicheng Zhang. Quantum channel tomography and estimation by local test. *arXiv preprint arXiv:2512.13614*, 2025. 4, 15, 23

[10] Jeongwan Haah, Robin Kothari, Ryan O'Donnell, and Ewin Tang. Query-optimal estimation of unitary channels in diamond distance. In *2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)*, pages 363–390. IEEE, 2023. 4, 15, 16

[11] Jessica Bavaresco, Mio Murao, and Marco Túlio Quintino. Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies. *Journal of Mathematical Physics*, 63(4), 2022. 4, 16

[12] G. Chiribella, G. M. D'Ariano, and P. Perinotti. Transforming quantum operations: Quantum supermaps. *EPL*, 83(3):30004, 2008. 5, 22

[13] Masahito Hayashi. *Group Representation for Quantum Theory*. Springer International Publishing, Cham, 2017. 7, 8
[14] Masahito Hayashi. *A group theoretic approach to quantum information*. Springer International Publishing, Basel, Switzerland, 1 edition, October 2016. 7

[15] Roe Goodman and Nolan R. Wallach. *Symmetry, Representations, and Invariants*, volume 255 of *Graduate Texts in Mathematics*. Springer, New York, NY, 2009. 8

[16] Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms. *Physical Review Letters*, 97(17):170502, October 2006. Publisher: American Physical Society. 8, 14

[17] Aram W. Harrow. Applications of coherent classical communication and the Schur transform to quantum information theory, December 2005. arXiv:quant-ph/0512255. 8, 14

[18] Hari Krovi. An efficient high dimensional quantum Schur transform. *Quantum*, 3:122, February 2019. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften. 8, 14

[19] Adam Burchardt, Jiani Fei, Dmitry Grinko, Martin Larocca, Maris Ozols, Sydney Timmerman, and Vladyslav Visnevskyi. High-dimensional quantum Schur transforms, September 2025. arXiv:2509.22640 [quant-ph]. 8, 14

[20] Benoît Collins, Sho Matsumoto, and Jonathan Novak. The Weingarten Calculus. *Notices of the American Mathematical Society*, 69(05):1, May 2022. arXiv:2109.14890 [math-ph]. 8

[21] Georg Köstenberger. Weingarten Calculus, February 2021. arXiv:2101.00921 [math]. 8

[22] Aram W. Harrow. Approximate orthogonality of permutation operators, with application to quantum information. *Letters in Mathematical Physics*, 114(1):1, December 2023. arXiv:2309.00715 [quant-ph]. 8

[23] Antonio Anna Mele. Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial. *Quantum*, 8:1340, May 2024. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften. 8

[24] Benoît Collins and Piotr Śniady. Integration with Respect to the Haar Measure on Unitary, Orthogonal and Symplectic Group. *Communications in Mathematical Physics*, 264(3):773–795, June 2006. 8

[25] Robert Beals. Quantum computation of Fourier transforms over symmetric groups. In *Proceedings of the twenty-ninth annual ACM symposium on Theory of computing*, STOC '97, pages 48–53, New York, NY, USA, May 1997. Association for Computing Machinery. 9, 14
[26] Cristopher Moore, Alexander Russell, and Leonard J. Schulman. The Symmetric Group Defies Strong Fourier Sampling. *SIAM Journal on Computing*, 37(6):1842–1864, January 2008. Publisher: Society for Industrial and Applied Mathematics. 9, 14

[27] Yasuhito Kawano and Hiroshi Sekigawa. Quantum Fourier transform over symmetric groups — improved result. *Journal of Symbolic Computation*, 75:219–243, July 2016. 9, 14

[28] Jiani Fei, Sydney Timmerman, and Patrick Hayden. Quantum algorithm for reducing induced representations with applications to port-based teleportation. In *Quantum Information Processing (QIP 2024)*, Taipei, Taiwan, January 2024. Contributed talk, Jan 15, 16:30–17:00. 14

[29] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald De Wolf. Quantum lower bounds by polynomials. *Journal of the ACM (JACM)*, 48(4):778–797, 2001. 15, 16

[30] Gregory Rosenthal, Hugo Aaronson, Sathyawageeswar Subramanian, Animesh Datta, and Tom Gur. Quantum channel testing in average-case distance. *arXiv preprint arXiv:2409.12566*, 2024. 15, 16

[31] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Information-theoretic bounds on quantum advantage in machine learning. *Physical Review Letters*, 126(19):190505, 2021. 16

[32] Stanislaw J Szarek. Metric entropy of homogeneous spaces. *arXiv preprint math/9701213*, 1997. 19

[33] Dennis Kretschmann, Dirk Schlingemann, and Reinhard F Werner. The information-disturbance tradeoff and the continuity of stinespring's representation. *IEEE transactions on information theory*, 54(4):1708–1717, 2008. 20

[34] Thomas Barthel and Jianfeng Lu. Fundamental limitations for measurements in quantum many-body systems. *Physical Review Letters*, 121(8):080406, 2018. 20

[35] Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C Caro. Learning quantum states and unitaries of bounded gate complexity. *PRX Quantum*, 5(4):040306, 2024. 20

[36] Haimeng Zhao, Yuzhen Zhang, and John Preskill. Learning to erase quantum states: thermodynamic implications of quantum learning theory. *arXiv preprint arXiv:2504.07341*, 2025. 23

[37] Marco Fanizza, Vishnu Iyer, Junseo Lee, Antonio A. Mele, and Francesco A. Mele. Efficient learning of bosonic gaussian unitaries. *arXiv preprint arXiv:2510.05531*, 2025. 23