# Reversing Unknown Quantum Processes via Virtual Combs:
for Channels with Limited Information

Chengkai Zhu Chengkai Zhu and Yin Mo contributed equally to this work. Thrust
of Artificial Intelligence, Information Hub,The Hong Kong University of
Science and Technology (Guangzhou), Guangdong, China Yin Mo11footnotemark: 1
Thrust of Artificial Intelligence, Information Hub,The Hong Kong University of
Science and Technology (Guangzhou), Guangdong, China Yu-Ao Chen  Thrust of
Artificial Intelligence, Information Hub,The Hong Kong University of Science
and Technology (Guangzhou), Guangdong, China Xin Wang felixxinwang@hkust-
gz.edu.cn Thrust of Artificial Intelligence, Information Hub,The Hong Kong
University of Science and Technology (Guangzhou), Guangdong, China

###### Abstract

The inherent irreversibility of quantum dynamics for open systems poses a
significant barrier to the inversion of unknown quantum processes. To tackle
this challenge, we propose the framework of virtual combs that exploit the
unknown process iteratively with additional classical post-processing to
simulate the process inverse. Our research establishes a path to achieving the
exact inverse of unknown channels with certain conditions, accompanied by a
no-go theorem that underscores the intrinsic limitations imposed by quantum
mechanics on such tasks. Notably, we demonstrate that an $n$-slot virtual comb
can exactly reverse a depolarizing channel with one unknown noise parameter
out of $n+1$ potential candidates, and a 1-slot virtual comb can exactly
reverse an arbitrary pair of quantum channels. We further explore the
approximate inverse of an unknown channel within a given channel set. For any
unknown depolarizing channels within a specified noise region, we unveil a
worst-case error decay of ${\cal O}(n^{-1})$ of reversing the channel via
virtual combs. Moreover, we show that virtual combs with constant slots can be
applied to universally reverse unitary operations and investigate the trade-
off between the slot number and the sampling overhead.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 Exact channel inverse
  4. 4 Approximate channel inverse
  5. 5 Application to error cancellation of unknown depolarizing noises
  6. 6 Application to universal unitary inverse
  7. 7 Concluding remarks
  8. A Preliminaries
  9. B Proof of Theorems

##  1 Introduction

Suppose a physical apparatus is provided that is guaranteed to perform some
unknown process ${\cal N}$, it can be regarded as a black box with no more
prior information. Is it possible to simulate the inverse of this process by
employing this black box multiple times? For such a task of executing a
desired transformation based on the given operations, the most comprehensive
method entails using a quantum network [CDP08b]. Formally, the problem here is
to construct a feasible quantum network ${\cal C}$ connected to the black box
${\cal N}$ for $n$ times to perform its inverse satisfying ${\cal C}({\cal
N}^{\otimes n})\circ{\cal N}$ be the identity channel, where such a quantum
network is generally an $n$-slot quantum comb [CDP08b].

A simple strategy is to apply process tomography to obtain the full matrix
representation which is usually resourceful [CN97, HKOT23]. If the unknown
process is restricted to unitary operations, numerous works have been carried
out to explore efficient methods that can implement the inverse of any unknown
unitary (see, e.g., [TDN20, Nav18, TDN23, SST+23, CE16, SCHL16, SBZ19,
QDS+19b]). Although it is uncertain whether a comb with finite uses of the
unknown unitary exists for general qudit unitary inversion, a probabilistic
exact protocol has been proposed, which has a failure probability tends to
zero exponentially fast with increasing the usage of the unitary gate
[QDS+19a, SBZ19]. Recently, for qubit unitaries, a deterministic and exact
protocol requiring four calls of the unknown unitary to simulate its inverse
was discovered [SST+23], indicating that full knowledge of the process through
tomography is not necessary for this task. Nevertheless, how to extend such
protocols to cases where the process is a general quantum channel remains an
open question.

The challenge of reversing general unknown quantum processes is twofold.
First, the inverse map of a quantum channel is generally not a physical
process as it is not even positive. Such unphysical inverse maps fall under a
broader scope of quantum operations, specifically Hermitian-preserving and
trace-preserving (HPTP) linear maps. Second, even though we know that all such
linear maps are simulatable via classical sampling and post-processing [JWW21]
or measurement-controlled post-processing [ZZZW23], implementing the inverse
map via existing methods unavoidably requires the complete description of the
quantum process.

In this paper, to explore the full potential of reversing an unknown quantum
process, we introduce the notion of virtual combs by lifting the positivity
requirement on quantum combs. Physically, a virtual comb corresponds to
sampling quantum combs with positive and negative coefficients and performing
post-processing. We find an affirmative answer that the simulation of the
inverse of an unknown channel could be achieved with a virtual comb under
certain conditions. Taking into account the unknown channel belonging to a
given set without any prior information about its specific identity, we find
that for arbitrary given two quantum channels, the exact inverse could always
be realized with a 1-slot virtual comb without knowing which specific channel
is provided. For depolarizing channels, we unveil the remarkable capability of
an $n$-slot virtual comb to exactly reverse a depolarizing channel with an
unknown noise parameter among $n+1$ possible parameters (see Fig. 1).
Intriguingly, we also establish a no-go theorem, elucidating the impossibility
of a virtual comb to universally reverse an arbitrary quantum channel with
finite uses of the channel.

Beyond exact inversion, our investigation extends to the realm of
approximately reversing unknown quantum channels through virtual combs. For
depolarizing channels within an arbitrary noise region, we find a protocol
with worst-case error decay of ${\cal O}(n^{-1})$ using $n$ calls of the
channel. Notably, the virtual comb framework finds compelling application in
error cancellation, where our protocol works for mitigating depolarizing
noises without requiring prior knowledge of noise parameters. This protocol
not only bears significance in theory but also has a clear and simple format,
presenting the potential for experimental realizations. Furthermore, virtual
combs are applied to reverse unknown unitary operations. We show that a 1-slot
virtual comb suffices to reverse any $d$-dimensional unitary operation and
explore its relationship with the previous unitary inverse problem. Our
findings could offer fresh perspectives on the interplay between the
information reversibility and irreversibility in quantum dynamics, and provide
new avenues for higher-order quantum transformations.

The structure of this paper is as follows. In Sec. 3, we introduce the notion
of virtual combs and explore the task of exactly reversing a depolarizing
channel with one unknown parameter out of given possibilities via virtual
combs. In Sec. 4, we extend our results to the approximate inversion of
unknown quantum channels within a given set where the average error and the
worst-case error are considered. In Sec. 5, we present an application of
virtual combs for error cancellation of unknown depolarizing noises with a
detailed protocol given. In Sec. 6, we apply the virtual combs to unknown
unitary inversion and illustrate its intriguing relationship with previous
results.

##  2 Preliminaries

Figure 1: Schematic diagram of reversing depolarizing channels with unknown
parameters via a 2-slot virtual comb. A virtual comb is represented as a
quasi-probabilistic mixture of quantum combs ${\widetilde{\cal
C}}=\sum_{j=0}^{l-1}\eta_{j}{\cal C}_{j}$ where ${\cal C}_{j}$ is a quantum
comb. The systems of a quantum comb ${\cal C}_{j}$ are labeled as ${\cal
P},{\cal I}_{i},{\cal O}_{i},{\cal F}$. Given a depolarizing channel ${\cal
D}_{p_{i}}$ with an unknown parameter $p_{i}$ out of three distinct choices,
${\widetilde{\cal C}}$ can exactly reverse ${\cal D}_{p_{i}}$ by
${\widetilde{\cal C}}({\cal D}_{p}^{\otimes 2})\circ{\cal
D}_{p}={\operatorname{id}}$ for any $i$.

#### Notations.

We consider a finite-dimensional Hilbert space ${\cal H}_{d}$ with dimension
$d$. Let $\\{|j\rangle\\}_{j=0}^{d-1}$ be a standard computational basis, and
denote $|I_{d}\rangle\rangle\mathrel{\mathop{\mathchar
58\relax}}=\sum_{i=0}^{d-1}|i\rangle|i\rangle$ as the unnormalized maximally
entangled state. Denote ${\cal H}_{A}$ as the Hilbert space associated with a
system $A$, and ${\cal L}({\cal H}_{A})$ as the set of linear operators that
map from ${\cal H}_{A}$ to itself. Quantum unitary operations can be
mathematically represented by linear unitary operators $U_{d}\in SU(d)$, the
group of unitary matrices with determinant one. A quantum channel ${\cal
N}_{A\to B}$ is a linear map from ${\cal L}({\cal H}_{A})$ to ${\cal L}({\cal
H}_{B})$ that is completely positive and trace-preserving (CPTP). Its
associated Choi-Jamiołkowski operator is expressed as $J_{{\cal
N}}\mathrel{\mathop{\mathchar
58\relax}}=\sum_{i,j=0}^{d_{A}-1}|i\rangle\\!\langle j|\otimes{\cal N}_{A\to
B}(|i\rangle\\!\langle j|)$. We denote
$J_{{\operatorname{id}}}\mathrel{\mathop{\mathchar
58\relax}}=|I_{d}\rangle\rangle\langle\langle I_{d}|$ as the Choi operator of
an identity channel, and $J_{{\cal D}}\mathrel{\mathop{\mathchar
58\relax}}=\frac{1}{d}I_{d}\otimes I_{d}$ as the Choi operator of a
$d$-dimensional fully depolarizing channel. Throughout the paper, we consider
a quantum channel that transforms a Hilbert space into itself and omits the
labels of systems unless stated otherwise. A channel ${\cal N}$ is said to be
an invertible (linear) map if there exists a linear map ${\cal N}^{-1}$ such
that ${\cal N}^{-1}\circ{\cal N}={\operatorname{id}}$ where
‘${\operatorname{id}}$’ is the identity channel. We briefly say ${\cal
N}^{-1}$ is the inverse of ${\cal N}$.

#### Implementing unphysical maps.

Realizing HPTP maps is highly valuable for tasks aiming to reproduce the same
measurement statistics for extracting significant features of the quantum
system [JWW21, ZJZ+23, RTG21, WLL+23, WCW23]. A general HPTP map can be
simulated via the quasiprobability decomposition (QPD) where the sampling
overhead quantifies its physical implementability [JWW21]. For more general
Hermitian-preserving maps, Ref. [ZZZW23] proposes the measurement-controlled
post-processing method and achieves lower simulation costs than the
conventional QPD method, which also assigns diamond norm an operational
meaning as a map’s simulability. Such techniques of simulating unphysical maps
lead to applications in error mitigation [CBB+23, JWW21, ZZXW23], quantum
circuit knitting [MF21, PS23], fault-tolerant quantum computation [PSB+21],
resource distillation [YRTG23], and quantum broadcasting [PFBC23, YLZW23].

#### Superchannel.

A general superchannel, also called a quantum comb [CDP08b, CDP08a], is a
linear map that transforms $n$ quantum channels into a resulting quantum
channel. An $n$-slot quantum comb is defined as a linear transformation ${\cal
C}$ from input quantum channels ${\cal N}_{\rm in}\mathrel{\mathop{\mathchar
58\relax}}{\cal L}(\otimes_{i=1}^{n}{\cal I}_{i})\rightarrow{\cal
L}(\otimes_{i=1}^{n}{\cal O}_{i})$ to an output channel ${\cal N}_{\rm
out}\mathrel{\mathop{\mathchar 58\relax}}{\cal L}({\cal P})\rightarrow{\cal
L}({\cal F})$, as shown in Fig. 1. Here we denote ${\cal I}_{i},{\cal O}_{i}$
as the input and output space of the quantum channel inserted to the $i$-th
slot, respectively. ${\cal P}$ and ${\cal F}$ refer to the input and output
space of the resulting quantum channel by the comb, respectively.

##  3 Exact channel inverse

Consider the following scenario: a quantum physicist is presented with a
physical apparatus that is assured to execute a specific quantum process,
e.g., a general unknown quantum channel ${\cal N}$ belonging to a given set
$\Theta$. Is it possible to reverse this quantum process without knowing
additional information? Recall that the inverse of a quantum channel is not
necessarily completely positive (CP) and a legitimate quantum comb has to be
CP, as reflected in the positivity of its Choi operator [Cho75]. To explore
the aforementioned task and fully explore the power of supermaps, we introduce
the virtual comb as follows.

######  Definition 1 (Virtual comb)

Let ${\cal C}_{0},{\cal C}_{1},\cdots,{\cal C}_{l-1}$ be quantum combs. An
affine combination of them ${\widetilde{\cal C}}=\sum_{i=0}^{l-1}\eta_{i}{\cal
C}_{i}$ is called a virtual comb where
$\sum_{i=0}^{l-1}\eta_{i}=1,\eta_{i}\in\mathbb{R},\forall i$.

We remark that the name virtual comb is bestowed for two reasons: first, its
functionality extends beyond that of a conventional comb; second, its virtual
nature considering negative values of $\eta_{i}$ is manifested through its
feasibility, achieved by sampling its quasiprobability decomposition and
subsequent post-processing.

Now we will focus on a scenario where the quantum process is guaranteed to be
within a set of depolarizing channels characterized by varying degrees of
noise. We discovered some intriguing results in this context. First, the exact
inversion of all channels in this set can be achieved with explicit
construction of the virtual comb, which cannot be accomplished by a quantum
comb, even probabilistically. Second, we establish a no-go theorem for this
task, which highlights the limitations in process reversibility imposed by
quantum mechanics.

Specifically, the unknown channel belongs to a family of $d$-dimensional
depolarizing channels with $m$ elements $\\{{\cal D}_{p_{1}},{\cal
D}_{p_{2}},...{\cal D}_{p_{m}}\\}$, where ${\cal
D}_{p}(\cdot)=(1-p)(\cdot)+pI_{d}/d$ is a depolarizing channel with a noise
parameter $p$. The task is to implement the inverse of an arbitrary channel
${\cal D}_{p_{i}}$ by querying the unknown channel $n$ times. Based on this
setting, we present our main result as follows.

###### Theorem 1

For any $n\geq 1$, let ${\cal D}_{p_{1}},...,{\cal D}_{p_{n+1}}$ be $n+1$
$d$-dimensional depolarizing channels with distinct noise parameters
$p_{1},...,p_{n+1}\in[0,1)$. There exists an $n$-slot virtual comb
${\widetilde{\cal C}}$ satisfying ${\widetilde{\cal C}}({\cal
D}_{p_{i}}^{\otimes n})={\cal D}_{p_{i}}^{-1},\quad\forall\,i=1,...,n+1.$ (1)

Theorem 1 unveils an intrinsic application of the virtual comb framework,
enabling the exact inverse of a family of depolarizing channels. Remarkably,
the protocol is independent of the noise parameter of the input channel,
rendering it broadly applicable to a set of noises. The number of distinct
channels within the set, which the virtual comb can exactly reverse, increases
with the number of slots, i.e., calls for the unknown channel. Here, we
provide proof for $n=1$ as an example. For cases $n\geq 2$, see Supplementary
Note 1 for details.

###### Proof.

Denote the Choi operator of the virtual comb as ${\widetilde{C}}_{{\cal
P}{\cal I}{\cal O}{\cal F}}$ and the Choi operator of a qudit depolarizing
channel ${\cal D}_{p}$ as:

$\displaystyle J_{{\cal D}_{p}}=(1-p)J_{{\operatorname{id}},{\cal I}{\cal
O}}+pJ_{{\cal D},{\cal I}{\cal O}}\,,$ (2)

where $J_{{\operatorname{id}}}=|I_{d}\rangle\rangle\langle\langle I_{d}|$ and
$J_{{\cal D}}=\frac{1}{d}I_{d}\otimes I_{d}$ are the Choi operators of the
identity channel and fully depolarizing channel respectively, and ${\cal P}$,
${\cal I}$, ${\cal O}$, ${\cal F}$ represent the corresponding systems in Fig
1. By direct calculation, the Choi operator of ${\cal D}_{p}^{-1}$ can be
written as

$\displaystyle J_{{\cal
D}_{p}^{-1}}=\dfrac{1}{1-p}J_{{\operatorname{id}}}-\dfrac{p}{1-p}J_{{\cal
D}}\,.$ (3)

Notice that $[J_{{\cal D}_{p}^{-1}},U\otimes\overline{U}]=0$ for arbitrary $U$
in $SU(d)$, which means ${\cal U}^{\dagger}\circ{\cal D}_{p}^{-1}\circ{\cal
U}={\cal D}_{p}^{-1}$. Thus for arbitrary virtual comb ${\widetilde{\cal C}}$
satisfying Eq. (1), ${\widetilde{\cal C}}^{\prime}=\int dU\,{\cal
U}^{\dagger}\circ{\widetilde{\cal C}}\circ{\cal U}$ is also a feasible one. As
quantum channels from ${\cal L}({\cal P})$ to ${\cal L}({\cal F})$ with Choi
operator commute with $U_{\cal P}\otimes\overline{U}_{\cal F}$ could always be
decomposed into a linear combination of the identity channel and the fully
depolarizing channel, without loss of generality, we could focus on a virtual
comb satisfying $[{\widetilde{C}},U_{\cal P}\otimes\overline{U}_{\cal
F}\otimes I_{{\cal I}{\cal O}}]=0$ and get

$\displaystyle\left\\{\begin{aligned} {\widetilde{\cal
C}}({\operatorname{id}}_{{\cal I}{\cal O}})=\alpha{\operatorname{id}}_{{\cal
P}{\cal F}}+(1-\alpha){\cal D}_{{\cal P}{\cal F}}\\\ {\widetilde{\cal
C}}({\cal D}_{{\cal I}{\cal O}})=\beta{\operatorname{id}}_{{\cal P}{\cal
F}}+(1-\beta){\cal D}_{{\cal P}{\cal F}}\\\ \end{aligned}\right.$ (4)

Inserting Eq.(4) into Eq. (1) gives us the following linear equations with
variables $\alpha,\beta$.

$\left\\{\begin{aligned} &(1-p_{1})\alpha+p_{1}\beta=\frac{1}{1-p_{1}}\\\
&(1-p_{2})\alpha+p_{2}\beta=\frac{1}{1-p_{2}}\end{aligned}\right.\implies\alpha=\frac{1-p_{1}-p_{2}}{(1-p_{1})(1-p_{2})},\beta=\frac{2-p_{1}-p_{2}}{(1-p_{1})(1-p_{2})}.$
(5)

Therefore, we have that the linear map satisfying Eq. (4) with $\alpha$,
$\beta$ given by Eq. (5) could exactly reverse ${\cal D}_{p_{1}}$ and ${\cal
D}_{p_{2}}$ using one-call of the channel.

Now the last step is to show that the linear map derived for two distinct
depolarizing channels could always be realized with a 1-slot virtual comb.
Consider three quantum combs ${\cal C}_{1},{\cal C}_{2},{\cal C}_{3}$
satisfying the following condition for arbitrary ${\cal N}\in\text{\rm
CPTP}({\cal I},{\cal O})$

${\cal C}_{1}({\cal N})={\cal D},\;{\cal C}_{2}({\cal
N})={\operatorname{id}},\;{\cal C}_{3}({\cal N})={\cal N}\,.$ (6)

It is easy to see that ${\cal C}_{1}$ corresponds to always passing through a
fully depolarizing channel, ${\cal C}_{2}$ corresponds to bypassing channel
${\cal N}$ and the input state is directly output from ${\cal P}$ to ${\cal
F}$, and ${\cal C}_{3}({\cal N})$ corresponds to go through channel ${\cal
N}$. For any given $\alpha,\beta\in\mathbb{R}$, we could then construct a
virtual comb ${\widetilde{\cal C}}$ such that

${\widetilde{\cal C}}({\cal N})=\beta{\cal C}_{2}({\cal
N})+(\alpha-\beta){\cal C}_{3}({\cal N})+(1-\alpha){\cal C}_{1}({\cal N})\,.$
(7)

It is easy to check that ${\widetilde{\cal C}}$ satisfies Eq. (4) when the
input ${\cal N}$ is chosen to be ${\cal D}$ and ${\operatorname{id}}$,
respectively.  $\sqcap$$\sqcup$

To highlight the unique power of reversing a family of depolarizing channels
with unknown noises provided by virtual combs, we show that such an exact
channel inversion task cannot be accomplished via a quantum comb, even
probabilistically.

###### Proposition 2

For any $n\geq 1$, let ${\cal D}_{p_{1}},...,{\cal D}_{p_{n+1}}$ be $n+1$
$d$-dimensional depolarizing channels with distinct noise parameters
$p_{1},...,p_{n+1}\in[0,1)$. There does not exist an $n$-slot quantum comb
that can reverse ${\cal D}_{p_{i}}$ for each $i$, even probabilistically.

The detailed proof can be found in Supplementary Note 1, where the key point
is that Eq. (3) shows the inverse of a depolarizing channel is not positive,
necessitating that the comb here should also have negative eigenvalues.

Significantly, from the proof of Theorem 1 we also obtain a no-go theorem that
an $n$-slot virtual comb is not universally capable of exactly reversing every
set of $n+2$ channels. This is indicated by the fact that the theoretical
maximum for an $n$-slot virtual comb to exactly invert a collection of
depolarizing channels is limited to $n+1$. Beyond this threshold, for
instance, the protocol fails when attempting to invert one out of $n+2$ or
more distinct depolarizing channels.

###### Theorem 3

For any $n\geq 1$, let ${\cal D}_{p_{1}},...,{\cal D}_{p_{n+2}}$ be $n+2$
$d$-dimensional depolarizing channels with distinct noise parameters
$p_{1},...,p_{n+2}\in[0,1)$. There is no $n$-slot virtual comb
${\widetilde{\cal C}}$ such that ${\widetilde{\cal C}}({\cal
D}_{p_{i}}^{\otimes n})={\cal D}_{p_{i}}^{-1},\quad\forall\,i=1,...,n+2.$ (8)

The main idea is to formulate Eq. (8) into a linear system. The coefficient
matrix and the augmented matrix can both be converted into Vandermonde
matrices, and the solvability condition could be derived. The scenario where
the number of distinct parameters larger than $n+2$ results in an inequality
which makes the linear system have no solution. Theorem 3 exposes the inherent
limit in reversing an unknown channel, affirming that virtual combs with
finite slots cannot achieve the reversal of arbitrary unknown quantum
channels.

##  4 Approximate channel inverse

Although Theorem 3 imposes restrictions on achieving the exact inverse, we
further consider the inverse of an unknown channel belonging to a defined set
approximately. In this case, the search for the optimal virtual comb becomes a
semidefinite programming (SDP) problem. Based on this, we could analyze the
performance of the corresponding virtual comb when the set of depolarizing
channels is not limited to a finite number of elements but belongs to a
certain noise interval. We have also observed some remarkable phenomena when
the set elements are general quantum channels.

In approximate inverse, given a set of quantum channels
$\Theta=\\{(p_{i},{\cal N}_{i})\\}_{i}$ where $p_{i}$ is the prior probability
for ${\cal N}_{i}$, we want to find an $n$-slot virtual comb that can make
${\widetilde{\cal C}}({\cal N}_{i}^{\otimes n})\circ{\cal N}_{i}$ as close to
the identity channel as possible. Since the involvement of a virtual comb may
render the entire process not necessarily a quantum channel, we quantify the
performance by considering the completely bounded trace distance from
${\widetilde{\cal C}}({\cal N}_{i}^{\otimes n})\circ{\cal N}_{i}$ to the
identity channel. With an $n$-slot virtual comb ${\widetilde{\cal C}}$, the
average error 111For cases where the number of channels in the set is
infinite, consider the channel to be continuous over a set of parameters
$\vec{\theta}$, with $p(\vec{\theta})$ being the probability distribution of
obtaining the corresponding channel, the average error is expressed by the
integral:  $e_{\rm ave}^{n}({\widetilde{\cal C}},\Theta)=\frac{1}{2}\int
d\vec{\theta}p(\vec{\theta})\left\|{\widetilde{\cal C}}({\cal
N}(\vec{\theta})^{\otimes n})\circ{\cal
N}(\vec{\theta})-{\operatorname{id}}\right\|_{\diamond}\,.$ of the channel set
$\Theta$ can be expressed as

$\displaystyle e_{\rm ave}^{n}({\widetilde{\cal
C}},\Theta)=\frac{1}{2}\sum_{i=1}^{m}p_{i}\left\|{\widetilde{\cal C}}({\cal
N}_{i}^{\otimes n})\circ{\cal N}_{i}-{\operatorname{id}}\right\|_{\diamond},$
(9)

where $\|{\cal F}\|_{\diamond}\mathrel{\mathop{\mathchar
58\relax}}=\sup_{k\in\mathbb{N}}\sup_{\|X\|_{1}\leq 1}\|({\cal
F}\otimes{\operatorname{id}}_{k})(X)\|_{1}$ denotes the diamond norm of a
linear operator ${\cal F}$. The worst-case error is defined as

$e_{\rm wc}^{n}({\widetilde{\cal
C}},\Theta)=\max\left\\{\frac{1}{2}\left\|{\widetilde{\cal C}}({\cal
N}_{i}^{\otimes n})\circ{\cal
N}_{i}-{\operatorname{id}}\right\|_{\diamond}\mathrel{\mathop{\mathchar
58\relax}}{\cal N}_{i}\in\Theta\right\\}.$ (10)

Note that for any two HPTP maps ${\cal N}_{1},{\cal N}_{2}$ from system $A$ to
$B$, the completely bounded trace distance can be evaluated using the
following SDP [Wat09].

$\displaystyle\frac{1}{2}\|{\cal N}_{1}-{\cal N}_{2}\|_{\diamond}=$
$\displaystyle\min\;\mu$ (11a) $\displaystyle{\rm s.t.}$
$\displaystyle\;\;Z_{AB}\geq 0,\operatorname{Tr}_{B}[Z_{AB}]\leq\mu I_{A},$
(11b) $\displaystyle\;\;Z_{AB}\geq J_{{\cal N}_{1}}-J_{{\cal N}_{2}}.$ (11c)

Then the optimal average error for approximately reversing quantum channels in
set $\Theta$ can be evaluated by the following SDP.

$\displaystyle e_{\rm ave,opt}^{n}(\Theta)=$
$\displaystyle\min\;\frac{1}{2}\sum_{i=1}^{m}p_{i}\left\|{\widetilde{\cal
C}}({\cal N}^{\otimes n})\circ{\cal
N}-{\operatorname{id}}\right\|_{\diamond},$ (12a) $\displaystyle{\rm s.t.}$
$\displaystyle\;\;{\widetilde{\cal C}}=(1+\eta){\cal C}_{0}-\eta{\cal
C}_{1},\eta\geq 0,$ (12b) $\displaystyle\;\;{\cal C}_{0},{\cal C}_{1}\text{
are $n$-slot quantum combs,}$ (12c)

where we can express each constraint by Choi operators. With SDP (12), we can
obtain a virtual comb ${\widetilde{\cal C}}$ that approximately reverses each
channel in the given set $\Theta$ with the minimum average error.

Based on the numerical calculations of the SDP, we first show some intriguing
results for inverting general quantum channels. The numerical calculations are
implemented in MATLAB [Inc22] with the interpreter CVX [GB14, GB08] and QETLAB
[Joh16]. We generate $m$ quantum channels randomly by the proposed measures in
[KNP+21], e.g., generating random Choi operators, and calculate the average
error of approximately reversing them (with equal prior probability) via
virtual combs by the SDP in Eq. (12). Then we apply the computer-assisted
proofs given in Ref. [BMQ21] to construct a feasible solution for the virtual
combs. It is worth noting that when $m\leq 13$, the average errors in 1000
repetitions of the experiment are all within a tolerance of $1\cdot 10^{-5}$
whenever the channels are invertible. However, intriguingly, when $m\geq 14$,
the average errors increase up to the first decimal place, indicating that no
virtual comb could achieve near-exact inversion for all these channels.
Therefore, we may conjecture that for reversing a given set of quantum
channels by virtual combs, when randomly selecting qubit channels, the upper
limit for the number of elements in the channel set is $13$. Notably, for the
scenario where the number of different random channels is $2$, we give the
following theorem to show that exact inversion is always possible for any pair
of quantum channels.

###### Theorem 4

For any two invertible quantum channels ${\cal N}_{1}$, ${\cal N}_{2}$, there
exists a $1$-slot virtual comb ${\widetilde{\cal C}}$ satisfying
${\widetilde{\cal C}}({\cal N}_{i})={\cal N}_{i}^{-1},\quad\forall\,i=1,2.$
(13)

The proof can be found in Supplementary Note 2. This can also be seen as a
generalization of Theorem 1 in a 1-slot scenario. It highlights the remarkable
capability of a 1-slot virtual comb to reverse an arbitrary given pair of
quantum channels, even when the input and output systems of the channels have
different dimensions. Interestingly, for amplitude damping channels, we find
any three distinct ones can be exactly reversed via a 1-slot virtual comb
based on the numerical calculation of SDP for the worst-case error under
tolerance of $1\cdot 10^{-8}$.

For depolarizing channels, we now consider that the noise levels are not a few
fixed values but fall within a specified range $[p_{1},p_{2}]$. As an $n$-slot
virtual comb ${\widetilde{\cal C}}$ could exactly reverse $n+1$ distinct noise
level, using the unknown channel more times is surely to enhance performance.
To optimize the average error within this range for an $n$-slot virtual comb
${\widetilde{\cal C}}$ over $n$ uses of the channel, we can utilize the SDP
approach presented in Eq. (12), replacing summation with integration. Here we
show that as the number of slots in the virtual comb (or the calls for the
channel) increases, the worst-case error in channel inversion diminishes at
least at a rate of ${\cal O}(n^{-1})$.

###### Theorem 5

Let $0\leq p_{1}<p_{2}\leq 1$, the minimum worst-case error of approximately
reversing a depolarizing channel ${\cal D}_{p}$ with $p\in[p_{1},p_{2}]$ using
an $n$-slot virtual comb is at most ${\cal O}(n^{-1})$.

We leave the detailed proof in Supplementary Note 1 and discuss the main idea
as follows. Based on Theorem 1, we could always have an $n$-slot virtual comb
do exact inverse for depolarizing channels with the noise level in
$\\{p_{1}^{\prime},...,p_{n+1}^{\prime}\\}$. With this virtual comb, when the
actual noise level of the depolarizing channel is $p\in[p_{1},p_{2}]$, the
error is an ‘$n+1$’-degree function of $p$ in the formula
$e^{n}(p)=\xi\prod_{i}(p-p_{i}^{\prime})$, where $\xi$ is a coefficient
determined by $\\{p_{1}^{\prime},...,p_{n+1}^{\prime}\\}$. By choosing the
virtual comb that can exactly reverse depolarizing channels with noise
parameters equal to $p_{1}$, $p_{2}$, and all points evenly spaced between
them, i.e.
$\\{p_{1}^{\prime}=p_{1},p_{2}^{\prime}=p_{1}+\frac{p_{2}-p_{1}}{n},...,p_{n+1}^{\prime}=p_{2}\\}$,
it could be proved to have the worst-case error at most ${\cal O}(n^{-1})$. In
Fig. 2, we display the worst-case error for the case $p_{1},p_{2}$ are
$(0,0.2)$, $(0,0.4)$ and $(0,0.6)$. We can see that as the calls of the
unknown channel increase, the performance tends to become exact for all these
channels very fast.

Figure 2: Worst-case error for reversing a depolarizing channel with an
unknown noise parameter $p\in[p_{1},p_{2}]$. The $x$-axis represents the
number of slots in a virtual comb (or the number of calls for the given
channel). The $y$-axis corresponds to the worst-case error.

##  5 Application to error cancellation of unknown depolarizing noises

The task of reversing an unknown quantum channel is interlinked with error
cancellation. In quantum information processing and quantum computing,
estimating the expectation value $\operatorname{Tr}[O\rho]$ for a given
observable $O$ and a quantum state plays an essential role. In practice, a
state $\rho$ is inevitably affected by noise which is modeled by a quantum
channel ${\cal N}$. Consequently, many methods have been proposed to recover
$\operatorname{Tr}[O\rho]$ against noises rather than obtaining
$\operatorname{Tr}[O{\cal N}(\rho)]$ [TBG17, EBL18, Tak21].

One of the primary techniques employed is the probabilistic error cancellation
[TBG17, JWW21] wherein the key idea is to represent the inverse map ${\cal
N}^{-1}$ of the noisy channel as a quasi-probabilistic mixture of quantum
channels. A crucial assumption in this protocol is that the noise is given a
prior, otherwise, a high-precision tomography of the noise channel is
required. In contrast, we present a method that can achieve high-precision
error cancellation for certain unknown channels, e.g., depolarizing channels
with unknown parameters within a given range. In the following, we first
present a general physical interpretation of a virtual comb in estimating the
expectation values. Then, we provide a detailed protocol for error
cancellation on depolarizing noises with unknown parameters.

Note that any $n$-slot quantum comb ${\cal C}$ can be equivalently realized by
a sequence of quantum channels $\\{{\cal E}_{j}\\}_{j=1}^{n+1}$ with an
ancillary system [CDP08b], i.e.,

${\cal C}({\cal N}_{1}\otimes{\cal N}_{2}\otimes\cdots\otimes{\cal
N}_{n})={\cal E}_{n+1}\circ{\cal N}_{n}\circ\cdots\circ{\cal E}_{2}\circ{\cal
N}_{1}\circ{\cal E}_{1}.$ (14)

Thus, we can obtain a set of channels $\\{{\cal E}_{ij}\\}_{j}$ for each comb
${\cal C}_{i}$ in a decomposition of a virtual comb ${\widetilde{\cal
C}}=\sum_{i}\eta_{i}{\cal C}_{i}$. Given an unknown quantum channel oracle
${\cal N}$ and a noisy state ${\cal N}(\rho)$, if ${\widetilde{\cal C}}({\cal
N}^{\otimes n})={\cal N}^{-1}$, then we can obtain
$\operatorname{Tr}[O\rho]=\operatorname{Tr}[O\cdot{\widetilde{\cal C}}({\cal
N}^{\otimes n})\circ{\cal N}(\rho)]$ by querying ${\cal N}$, performing
quantum operations and post-processing.

In each round out of $S$ times sampling, we sample a sequence of quantum
channels $\\{{\cal E}_{sj}\\}_{j=1}^{n+1}$ from $\\{{\cal E}_{ij}\\}_{ij}$
with probability $|\eta_{s}|/\gamma$, where $\gamma=\sum_{i}|\eta_{i}|$. Apply
${\cal E}_{s1},{\cal N},{\cal E}_{s2},\cdots,{\cal N},{\cal E}_{s,n+1}$ to the
target state sequentially to obtain

${\cal E}_{s,n+1}\circ{\cal N}\circ\cdots\circ{\cal E}_{s2}\circ{\cal
N}\circ{\cal E}_{s1}\circ{\cal N}(\rho)={\widetilde{\cal C}}_{s}({\cal
N}^{\otimes n})\circ{\cal N}(\rho)$ (15)

and measure each qubit on a computational basis. We then denote $\lambda_{s}$
as the measurement outcome and obtain a random variable

$X^{(s)}=\gamma\cdot{\rm sgn}(\eta_{s})\lambda_{s}\in[-\gamma,\gamma].$ (16)

After $S$ rounds sampling, we calculate the empirical mean value
$\zeta\mathrel{\mathop{\mathchar 58\relax}}=\frac{1}{S}\sum_{s=1}^{S}X^{(s)}$
as an estimation for the expectation value
$\operatorname{Tr}[O\cdot{\widetilde{\cal C}}({\cal N}^{\otimes n})\circ{\cal
N}(\rho)]$. By Hoeffding’s inequality [Hoe12], to estimate the expectation
value within error $\epsilon$ with probability no less than $1-\delta$, the
number of samples required to be

$S\geq 2\gamma^{2}\log(2/\delta)/\epsilon^{2}.$ (17)

Hence, $\gamma$ is known as the sampling overhead. We note that the optimal
sampling overhead can be calculated as the following SDP.

$\displaystyle\gamma_{\rm opt}=\min$ $\displaystyle\;\;2\eta+1,$ (18a)
$\displaystyle{\rm s.t.}$ $\displaystyle\;\;{\widetilde{\cal C}}=(1+\eta){\cal
C}_{0}-\eta{\cal C}_{1},$ (18b) $\displaystyle\;\;{\cal C}_{0},{\cal
C}_{1}\text{ are $n$-slot quantum combs,}$ (18c)
$\displaystyle\;\;{\widetilde{\cal C}}({\cal N})\circ{\cal
N}={\operatorname{id}}.$ (18d)

In particular, if we aim to cancel the effect of an unknown depolarizing noise
${\cal D}_{p}$ from a set of distinct noise parameters simultaneously as
described in Theorem 1, we have the following protocol to obtain an estimation
of $\operatorname{Tr}[O\rho]$. We denote three types of operations for our
protocol:

  1. 1)

${\cal C}_{{\operatorname{id}}}$: Do nothing to the received state.

  2. 2)

${\cal C}_{{\cal D}}$: Replace the received state with a maximally mixed
state.

  3. 3)

${\cal C}_{i}$: Apply the unknown process to the received state iteratively
for $i$ times.

Based on the above, the protocol is shown as Protocol 1.

Input : Unknown depolarizing process ${\cal D}_{p}$ with $p$ in a given set
$\\{p_{1},...,p_{n+1}\\}$, unknown state after depolarizing noise ${\cal
D}_{p}(\rho)$, a given observable $O$, and given error parameters
$\epsilon,\delta\in(0,1)$;

Output : An estimator $\zeta$ of $\operatorname{Tr}[O\rho]$

1 Divide the inversion virtual comb into different implementable processes:
${\widetilde{\cal C}}=\eta_{id}\cdot{\cal C}_{id}+\eta_{{\cal D}}\cdot{\cal
C}_{{\cal D}}+\sum_{1}^{n}\eta_{i}\cdot{\cal C}_{i}$, with coefficients given
by the solution of the linear equations in Eq. (S26) determined by
$\\{p_{1},...,p_{n+1}\\}$ and $n$;

2 Calculate the sampling rounds for error cancellation: $S=\lceil
2\gamma^{2}\cdot\log(2/\delta)/\epsilon^{2}\rceil$, where
$\gamma=|\eta_{id}|+|\eta_{{\cal D}}|+\sum_{i}|\eta_{i}|$;

3 for  _$s$ from $1$ to $S$_ do

4 Sample an operation ${\cal C}_{s}$ from $\\{{\cal
C}_{{\operatorname{id}}},{\cal C}_{{\cal D}},{\cal C}_{1},{\cal
C}_{2},...,{\cal C}_{n}\\}$ with probability $|\eta_{s}|/\gamma$;

5 For the input state ${\cal D}_{p}(\rho)$, which has passed through the
unknown depolarizing process, apply the randomly sampled inversion process
${\cal C}_{s}$, followed by a measurement of the corresponding observable $O$,
with the result denoted as $\lambda_{s}$;

6 $X^{(s)}\leftarrow\gamma\cdot{\rm sgn}(\eta_{s})\lambda_{s}$ ;

7

8 end for

9Get the estimator $\zeta$ of $\operatorname{Tr}[O\rho]$:
$\zeta\leftarrow\frac{1}{S}\sum_{s=1}^{S}X^{(s)}$;

10 Return $\zeta$;

Protocol 1 Error cancellation for getting $\operatorname{Tr}[O\rho]$ through
unknown depolarizing noise

It is encouraging that the three types of operations considered in this
protocol are quite simple. Notably, if the depolarizing noise is from a
continuous region, i.e., $p\in[p_{1},p_{n+1}]$, from the analysis presented in
Theorem 5, we could notice that with an increasing number of slots in the
virtual comb, Protocol 1 exhibits a worst-case error diminishing at least as
${\cal O}(n^{-1})$. The precision gains hold valid for a broad class of
depolarizing channels, ensuring robustness across a continuum of noise levels.
It is foreseeable that, as this approach allows for noise within a certain
range while maintaining high-precision performance, it will reduce the initial
precision requirements for error tomography. It will also ensure the
robustness in overall operation, i.e. the protocol remains effective even if
the error changes a little bit during the experiment.

##  6 Application to universal unitary inverse

In this section, we investigate a particular scenario where the quantum
process is known to be a unitary operation. Previously, several works have
studied the problem of reversing unknown unitary operations, including
deterministic non-exact protocol [CE16, SCHL16] and probabilistic exact
protocols [SBZ19, QDS+19b, QDS+19a]. Notably, it is proved that the inverse
operation $U^{-1}$ cannot be implemented deterministically and exactly with a
single use of $U$ [CE16]. To go beyond this no-go theorem, a deterministic and
exact qubit-unitary inversion protocol that utilizes four calls of the input
qubit-unitary operation was proposed [YSM23]. However, whether there are
deterministic and exact protocols for $d>2$ remains unknown.

Since unitary operations are unital channels with rank-1 Choi operators, the
task of unitary inverse can be regarded as a special case of channel inverse.
As it has been proved that utilizing $n$-slot quantum combs, there is no
deterministic and exact protocol to realize unitary inversion for an arbitrary
unitary operation when $n<4$, and even no probabilistic protocol exists for
$d>2$ when $n=1$, it is interesting to ask whether there exists a 1-slot
virtual comb that can exactly reverse an arbitrary unitary operation. Here we
find the answer is positive by showing a 1-slot virtual comb is enough for
reversing any unknown $d$-dimensional unitary channel ${\cal
U}_{d}(\cdot)=U_{d}(\cdot)U_{d}^{\dagger}$.

###### Proposition 6

For any dimension $d$, there exists a $1$-slot virtual comb ${\widetilde{\cal
C}}$ that transforms any qudit-unitary channel ${\cal U}_{d}$ into its inverse
${\cal U}_{d}^{-1}$, i.e. ${\widetilde{\cal C}}({\cal
U}_{d})(\cdot)=U_{d}^{{\dagger}}(\cdot)U_{d}$.

The proof can be found in Supplementary Note 3. Proposition 6 reveals that
with a virtual comb, a deterministic and exact protocol can be achieved with
just one call of the unitary. Furthermore, this universal protocol applies to
quantum systems of any dimension $d$, transcending the current understanding
for quantum combs, which is limited to $d=2$ [YSM23]. Proposition 6 also shows
the difference between unitary channels and general quantum channels. Recall
that in section 4, our numerical calculation shows that when the set consists
of random channels, if the number of the set elements is larger than $13$, no
perfect 1-slot inversion protocol could be found. While if the set consists of
random unitaries, the number of the set elements could be infinite.

Besides, in the same spirit of Eq. (18), the optimal sampling overhead for the
$n$-slot virtual comb that can exactly reverse a $d$-dimensional unitary can
be characterized via the following SDP.

$\displaystyle\nu(d,n)=\min$ $\displaystyle\;2\eta+1,$ (19a)
$\displaystyle{\rm s.t.}$
$\displaystyle\;\operatorname{Tr}[{\widetilde{C}}\Omega]=1,$ (19b)
$\displaystyle\;\;{\widetilde{\cal C}}=(1+\eta){\cal C}_{0}-\eta{\cal
C}_{1},\eta\geq 0,$ (19c) $\displaystyle\;\;{\cal C}_{0},{\cal C}_{1}\text{
are $n$-slot quantum combs,}$ (19d)

where Eq. (19b) ensures that ${\widetilde{\cal C}}$ is a desired map that can
exactly reverse an arbitrary unitary operation and $\Omega$ is a
$d^{2(n+1)}\times d^{2(n+1)}$ positive matrix called the performance operator
[CE16, QE22]. It is defined by

$\Omega\mathrel{\mathop{\mathchar 58\relax}}=\frac{1}{d^{2}}\int
dU|U^{\dagger}\rangle\rangle\langle\langle U^{\dagger}|_{{\cal P}{\cal
F}}\otimes|U^{*}\rangle\rangle\langle\langle U^{*}|^{\otimes n}_{{\cal I}{\cal
O}},$ (20)

where $dU$ corresponds to the Haar measure, and $|U\rangle\rangle=(U\otimes
I)|I\rangle\rangle$ corresponds to the Choi operator of unitary ${\cal U}$.
Notably, the optimal sampling overhead for the virtual comb that can exactly
reverse unknown unitary operations has a dual relationship with the problem of
finding the optimal average fidelity of reversing unknown unitary operations
by a quantum comb [QE22] as the following theorem.

###### Theorem 7

Let $F_{\rm opt}(d,n)$ be the optimal channel fidelity of reversing
$d$-dimensional unitary operations with an $n$-slot quantum comb and
$\nu(d,n)$ be the optimal sampling overhead for the $n$-slot virtual comb that
can exactly reverse a $d$-dimensional unitary operation. It satisfies
$\nu(d,n)=\frac{2}{F_{\rm opt}(d,n)}-1,\quad\forall d\geq 2,n\geq 1.$ (21)

Here, the optimal average channel fidelity of reversing $d$-dimensional
unitary operations with an $n$-slot quantum comb is given by the following SDP
[QE22]:

$\displaystyle F_{\rm opt}(d,n)=\max$
$\displaystyle\;\operatorname{Tr}[C\Omega],$ (22a) $\displaystyle{\rm s.t.}$
$\displaystyle\;\;{\cal C}\text{ is an $n$-slot quantum comb,}$ (22b)

where $\Omega$ is the same performance operator as appeared in Eq. (19b) and
$C$ is the Choi operator of comb ${\cal C}$. A deterministic exact unitary
inversion protocol is obtained when the solution equals 1. The proof of
Theorem 7 is shown in Supplementary Note 3. Based on the result for the
optimal channel fidelity shown in Ref. [QE22], we provide the optimal sampling
overhead for different $d$ and $n$ in Table 1.

|  $n=1$ |  $n=2$ |  $n=3$ |  $n=4$ |  $n=5$
---|---|---|---|---|---
$d=2$ |  3.0000 |  1.6667 |  1.1436 |  1.0000 |  1.0000
$d=3$ |  8.0000 |  5.0000 |  3.5000 |  2.6000 |  2.0000
$d=4$ |  15.0000 |  9.6667 |  7.0000 |  5.4000 |  4.3691
$d=5$ |  24.0000 |  15.6667 |  11.5000 |  9.0000 |  7.3333
$d=6$ |  35.0000 |  23.0000 |  17.0000 |  13.3988 |  11.0000
Table 1: The optimal sampling overhead for an $n$-slot virtual comb that can
exactly reverse arbitrary $d$-dimensional unitary operations.

##  7 Concluding remarks

In this work, we address the problem of reversing an unknown quantum process
by introducing virtual combs, which are Hermitian-preserving and trace-
preserving supermaps. We demonstrate that an $n$-slot virtual comb can exactly
reverse a depolarizing channel with an unknown noise parameter out of $n+1$
possible parameters, and a $1$-slot virtual comb can exactly reverse an
arbitrary channel set with $2$ elements. Moreover, a no-go theorem is provided
that an $n$-slot virtual comb cannot reverse arbitrary $n+2$ quantum channels.
In addition to exact inversion, we explore the problem of approximately
reversing unknown quantum channels through virtual combs. We establish the SDP
for the average error and reveal a worst-case error decay of ${\cal
O}(n^{-1})$ for a family of depolarizing channels within a specified noise
region.

As applications, the virtual comb framework for reversing unknown quantum
channels can be applied to both error cancellation and universal unitary
inverse. We present a protocol for mitigating depolarizing noises without
prior information on the noise parameters. This protocol may also pave the way
for experimental realizations. Furthermore, virtual combs can be applied to
reversing unknown unitary operations where a 1-slot virtual comb is enough for
reversing any $d$-dimensional unitary operation. Our findings contribute
valuable insights into the limits and potentials of reversing unknown quantum
processes or noises, offering new perspectives on information preservation and
manipulation.

For future study, the virtual combs could be explored in many aspects for
specific problems, including determining the virtual comb with the minimum
sampling overhead for a given set of channels or identifying the protocol with
the best performance under approximate conditions. Another research direction
for unknown processes is about learning, where the unknown process is learned
by allowing quantum states to pass through it. The learned information can
then be utilized to replicate the process or perform related operations. Such
studies have been done for learning unitary gates [BCD+10, SBZ19, MC19],
measurements [SZ14, CHY15], and Pauli noises [CYZW23]. How to further extend
this setting to learning and using unknown channels remains open. The virtual
combs may shed light on further exploration of this direction.

## Acknowledgement

Chengkai Zhu would like to thank Xuanqiang Zhao for the helpful discussions.
We thank Benchi Zhao, Hongshun Yao, Xuanqiang Zhao, and Kun Wang for their
comments. This work was supported by the Start-up Fund from The Hong Kong
University of Science and Technology (Guangzhou), the Guangdong Quantum
Science and Technology Strategic Fund (Grant No. GDZX2303007), and the
Education Bureau of Guangzhou Municipality.

## References

  * [BCD+10] Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D’Ariano, Stefano Facchini, and Paolo Perinotti.  Optimal of a unitary transformation.  Physical Review A, 81(3), March 2010.
  * [BMQ21] Jessica Bavaresco, Mio Murao, and Marco Túlio Quintino.  Strict hierarchy between parallel, sequential, and indefinite-causal-order strategies for channel discrimination.  Physical Review Letters, 127(20), November 2021.
  * [CBB+23] Zhenyu Cai, Ryan Babbush, Simon C. Benjamin, Suguru Endo, William J. Huggins, Ying Li, Jarrod R. McClean, and Thomas E. O’Brien.  Quantum error mitigation.  Rev. Mod. Phys., 95:045005, Dec 2023.
  * [CDP08a] G. Chiribella, G. M. D’Ariano, and P. Perinotti.  Quantum circuit architecture.  Physical Review Letters, 101(6), aug 2008.
  * [CDP08b] G. Chiribella, G. M. D'Ariano, and P. Perinotti.  Transforming quantum operations: Quantum supermaps.  EPL (Europhysics Letters), 83(3):30004, jul 2008.
  * [CE16] Giulio Chiribella and Daniel Ebler.  Optimal quantum networks and one-shot entropies.  New Journal of Physics, 18(9):093053, September 2016.
  * [Cho75] Man-Duen Choi.  Completely positive linear maps on complex matrices.  Linear algebra and its applications, 10(3):285–290, 1975.
  * [CHY15] Hao-Chung Cheng, Min-Hsiu Hsieh, and Ping-Cheng Yeh.  The learnability of unknown quantum measurements, 2015.
  * [CN97] Isaac L. Chuang and M. A. Nielsen.  Prescription for experimental determination of the dynamics of a quantum black box.  Journal of Modern Optics, 44(11–12):2455–2467, November 1997.
  * [CYZW23] Yifei Chen, Zhan Yu, Chenghong Zhu, and Xin Wang.  Efficient information recovery from Pauli noise via classical shadow.  arXiv preprint arXiv:2305.04148, may 2023.
  * [EBL18] Suguru Endo, Simon C. Benjamin, and Ying Li.  Practical quantum error mitigation for near-future applications.  Phys. Rev. X, 8:031027, Jul 2018.
  * [GB08] Michael Grant and Stephen Boyd.  Graph implementations for nonsmooth convex programs.  In V. Blondel, S. Boyd, and H. Kimura, editors, Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences, pages 95–110. Springer-Verlag Limited, 2008.  http://stanford.edu/~boyd/graph_dcp.html.
  * [GB14] Michael Grant and Stephen Boyd.  CVX: Matlab software for disciplined convex programming, version 2.1.  http://cvxr.com/cvx, March 2014.
  * [HKOT23] Jeongwan Haah, Robin Kothari, Ryan O’Donnell, and Ewin Tang.  Query-optimal estimation of unitary channels in diamond distance, 2023.
  * [Hoe12] Wassily Hoeffding.  The collected works of Wassily Hoeffding.  Springer Science & Business Media, 2012.
  * [Inc22] The MathWorks Inc.  Matlab version: 9.13.0 (r2022b), 2022.
  * [Joh16] Nathaniel Johnston.  QETLAB: A MATLAB toolbox for quantum entanglement, version 0.9.  https://qetlab.com, Jan 2016.
  * [JWW21] Jiaqing Jiang, Kun Wang, and Xin Wang.  Physical Implementability of Linear Maps and Its Application in Error Mitigation.  Quantum, 5:600, dec 2021.
  * [KNP+21] Ryszard Kukulski, Ion Nechita, Lukasz Pawela, Zbigniew Puchala, and Karol Zyczkowski.  Generating random quantum channels.  Journal of Mathematical Physics, 62(6), June 2021.
  * [MC19] Yin Mo and Giulio Chiribella.  Quantum-enhanced learning of rotations about an unknown direction.  New Journal of Physics, 21(11):113003, November 2019.
  * [MF21] Kosuke Mitarai and Keisuke Fujii.  Overhead for simulating a non-local channel with local channels by quasiprobability sampling.  Quantum, 5:388, jan 2021.
  * [Nav18] Miguel Navascués.  Resetting uncontrolled quantum systems.  Physical Review X, 8(3), July 2018.
  * [PFBC23] Arthur J. Parzygnat, James Fullwood, Francesco Buscemi, and Giulio Chiribella.  Virtual quantum broadcasting, 2023.
  * [PS23] Christophe Piveteau and David Sutter.  Circuit knitting with classical communication.  IEEE Transactions on Information Theory, pages 1–1, apr 2023.
  * [PSB+21] Christophe Piveteau, David Sutter, Sergey Bravyi, Jay M. Gambetta, and Kristan Temme.  Error Mitigation for Universal Gates on Encoded Qubits.  Physical Review Letters, 127(20):200505, nov 2021.
  * [QDS+19a] Marco Túlio Quintino, Qingxiuxiong Dong, Atsushi Shimbo, Akihito Soeda, and Mio Murao.  Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations.  Physical Review Letters, 123(21):1–6, 2019.
  * [QDS+19b] Marco Túlio Quintino, Qingxiuxiong Dong, Atsushi Shimbo, Akihito Soeda, and Mio Murao.  Probabilistic exact universal quantum circuits for transforming unitary operations.  Physical Review A, 100(6), December 2019.
  * [QE22] Marco Tulio Quintino and Daniel Ebler.  Deterministic transformations between unitary operations: Exponential advantage with adaptive quantum circuits and the power of indefinite causality.  Quantum, 6:1–37, 2022.
  * [RTG21] Bartosz Regula, Ryuji Takagi, and Mile Gu.  Operational applications of the diamond norm and related measures in quantifying the non-physicality of quantum maps.  Quantum, 5:522, aug 2021.
  * [SBZ19] Michal Sedlák, Alessandro Bisio, and Mário Ziman.  Optimal probabilistic storage and retrieval of unitary channels.  Physical Review Letters, 122(17), May 2019.
  * [SCHL16] Imdad S. B. Sardharwalla, Toby S. Cubitt, Aram W. Harrow, and Noah Linden.  Universal refocusing of systematic quantum noise, 2016.
  * [SST+23] P. Schiansky, T. Strömberg, D. Trillo, V. Saggio, B. Dive, M. Navascués, and P. Walther.  Demonstration of universal time-reversal for qubit processes.  Optica, 10(2):200, January 2023.
  * [SZ14] Michal Sedlák and Mário Ziman.  Optimal single-shot strategies for discrimination of quantum measurements.  Physical Review A, 90(5), November 2014.
  * [Tak21] Ryuji Takagi.  Optimal resource cost for error mitigation.  Phys. Rev. Res., 3:033178, Aug 2021.
  * [TBG17] Kristan Temme, Sergey Bravyi, and Jay M. Gambetta.  Error mitigation for short-depth quantum circuits.  Physical Review Letters, 119(18), November 2017.
  * [TDN20] David Trillo, Benjamin Dive, and Miguel Navascués.  Translating uncontrolled systems in time.  Quantum, 4:374, December 2020.
  * [TDN23] D. Trillo, B. Dive, and M. Navascués.  Universal quantum rewinding protocol with an arbitrarily high probability of success.  Physical Review Letters, 130(11), March 2023.
  * [Wat09] John Watrous.  Semidefinite programs for completely bounded norms, 2009.
  * [Wat18] John Watrous.  The theory of quantum information.  Cambridge university press, 2018.
  * [WCW23] Kun Wang, Yu-Ao Chen, and Xin Wang.  Mitigating quantum errors via truncated neumann series.  Science China Information Sciences, 66(8), July 2023.
  * [WLL+23] Fuchuan Wei, Zhenhuan Liu, Guoding Liu, Zizhao Han, Xiongfeng Ma, Dong-Ling Deng, and Zhengwei Liu.  Realizing Non-Physical Actions through Hermitian-Preserving Map Exponentiation.  arXiv preprint arXiv:2308.07956, 2023.
  * [YLZW23] Hongshun Yao, Xia Liu, Chengkai Zhu, and Xin Wang.  Optimal uni-local virtual quantum broadcasting, 2023.
  * [YRTG23] Xiao Yuan, Bartosz Regula, Ryuji Takagi, and Mile Gu.  Virtual quantum resource distillation, 2023.
  * [YSM23] Satoshi Yoshida, Akihito Soeda, and Mio Murao.  Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly.  Physical Review Letters, 131(12), 2023.
  * [ZJZ+23] Benchi Zhao, Mingrui Jing, Lei Zhang, Xuanqiang Zhao, Kun Wang, and Xin Wang.  Retrieving non-linear features from noisy quantum states.  arXiv preprint arXiv:2309.11403, 2023.
  * [ZZXW23] Xuanqiang Zhao, Benchi Zhao, Zihan Xia, and Xin Wang.  Information recoverability of noisy quantum states.  Quantum, 7:978, apr 2023.
  * [ZZZW23] Xuanqiang Zhao, Lei Zhang, Benchi Zhao, and Xin Wang.  Power of quantum measurement in simulating unphysical operations, 2023.

Appendix for
Reversing Unknown Quantum Processes via Virtual Combs:
for Channels with Limited Information

##  Appendix A Preliminaries

###  Supplementary Note 1 Comb, virtual comb and link product

#### Comb and virtual comb.

Formally, a quantum comb can be characterized by its Choi operator as the
following lemma.

######  Lemma S1 ([CDP08a])

Given a matrix $C\in{\cal L}\left({\cal P}\otimes{\cal I}^{n}\otimes{\cal
O}^{n}\otimes\mathcal{F}\right)$, it is the Choi operator of a quantum comb
$\mathcal{C}$ if and only if it satisfies $C\geq 0$ and

$\displaystyle C^{(0)}=1,\;\operatorname{Tr}_{{\cal
I}_{i}}[C^{(i)}]=C^{(i-1)}\otimes I_{{\cal O}_{i-1}},\,i=1,\cdots,n+1$ (S1)

where $C^{(n+1)}\mathrel{\mathop{\mathchar
58\relax}}=C,C^{(i-1)}\mathrel{\mathop{\mathchar
58\relax}}=\operatorname{Tr}_{{\cal I}_{i}{\cal O}_{i-1}}[C^{(i)}]/d$,
$I_{{\cal H}}$ is the identity operator on ${\cal H}$ and ${\cal
I}_{n+1}\mathrel{\mathop{\mathchar 58\relax}}=\mathcal{F},{\cal
O}_{0}\mathrel{\mathop{\mathchar 58\relax}}={\cal P}$.

Conventionally, a legitimate quantum transformation has to be completely
positive (CP) reflected in the positivity of its Choi operator [Cho75]. In the
main text, we lift the constraint for a map to be completely positive and
introduce the notion of virtual comb, which can be decomposed into quantum
combs as ${\widetilde{\cal
C}}=\eta_{0}\mathcal{C}_{0}+\eta_{1}\mathcal{C}_{1}$, with $\eta_{0}$ and
$\eta_{1}$ be arbitrary real numbers. We can easily notice that a virtual comb
can be characterized by its Choi operator shown as follows.

###### Lemma S2

Given a matrix ${\widetilde{C}}\in{\cal L}\left({\cal P}\otimes{\cal
I}^{n}\otimes{\cal O}^{n}\otimes\mathcal{F}\right)$, it is the Choi operator
of a virtual comb ${\widetilde{\cal C}}$ if and only if it satisfies

$\displaystyle{\widetilde{C}}^{(0)}=1,\;\operatorname{Tr}_{{\cal
I}_{i}}[{\widetilde{C}}^{(i)}]={\widetilde{C}}^{(i-1)}\otimes I_{{\cal
O}_{i-1}},\,i=1,\cdots,n+1$ (S2)

where ${\widetilde{C}}^{(n+1)}\mathrel{\mathop{\mathchar
58\relax}}={\widetilde{C}},{\widetilde{C}}^{(i-1)}\mathrel{\mathop{\mathchar
58\relax}}=\operatorname{Tr}_{{\cal I}_{i}{\cal
O}_{i-1}}[{\widetilde{C}}^{(i)}]/d$, $I_{{\cal H}}$ is the identity operator
on ${\cal H}$ and ${\cal I}_{n+1}\mathrel{\mathop{\mathchar
58\relax}}=\mathcal{F},{\cal O}_{0}\mathrel{\mathop{\mathchar 58\relax}}={\cal
P}$.

###### Proof.

For the ‘if part’: without loss of generality, we let ${\widetilde{C}}$ be the
Choi operator of a virtual comb ${\widetilde{\cal C}}=\eta_{0}{\cal
C}_{0}+\eta_{1}{\cal C}_{1}$, where $\eta_{0}+\eta_{1}=1$. ${\widetilde{C}}$
satisfies Eq. (S2) by the linearity of partial trace. For the ‘Only if’ part:
let $C=I$, $\eta_{1}=\|{\widetilde{C}}\|_{1}$, and
$C^{\prime}=[(\|{\widetilde{C}}\|_{1}+1)I-{\widetilde{C}}]/\|{\widetilde{C}}\|_{1}$.
If ${\widetilde{C}}$ satisfies the conditions in Eq. (S2), it is easy to check
that ${\widetilde{C}}=(1+\eta_{1})C-\eta_{1}C^{\prime}$, $C,C^{\prime}\geq 0$
and both satisfy the conditions in Eq. (S2). Hence we complete the proof.
$\sqcap$$\sqcup$

#### Link product.

For any two given processes, they can be connected whenever the input system
of one matches the output system of the other. Upon connection, the Choi
operator of the overall process can be derived through the link product
operation [CDP08b], denoted as $*$. Considering two processes ${\cal
N}_{A\rightarrow B}$ and ${\cal M}_{B\rightarrow C}$, the Choi operator of the
composite process from ${\cal H}_{A}$ to ${\cal H}_{C}$ can be represented as

$\displaystyle J_{{\cal M}\circ{\cal N}}=J_{{\cal N}}*J_{{\cal
M}}=\operatorname{Tr}_{B}[(J_{{\cal N}}\otimes I_{C})\cdot(I_{A}\otimes
J_{{\cal M}}^{T_{B}})]\,,$ (S3)

where $J_{{\cal N}},J_{{\cal M}}$ are the Choi operators of ${\cal N},{\cal
M}$, respectively, and $T_{B}$ denotes taking partial transpose on ${\cal
H}_{B}$. This representation holds for any processes. It is noteworthy that
the link product exhibits both associative and commutative properties:

$\displaystyle J_{1}*(J_{2}*J_{3})$ $\displaystyle=(J_{1}*J_{2})*J_{3}$
$\displaystyle J_{1}*J_{2}$ $\displaystyle=J_{2}*J_{1}$

###  Supplementary Note 2 Hermitian decomposition of virtual channels and
combs

To analyze the capability of using a virtual comb to invert general channels
and to prove that any two quantum channels can be exactly reversed by a 1-slot
virtual comb as stated in Theorem 4, we apply Hermitian decomposition to
represent the Choi operator for general channels and conduct analysis using
this formulation. In this subsection, we introduce the mathematical form of
this decomposition and some of its properties. We then show the representation
of quantum processes in this form.

For the $d$-dimensional Hilbert space ${\cal H}_{d}$, with a group of
orthonormal basis

${\cal B}_{d}\mathrel{\mathop{\mathchar
58\relax}}=\left\\{\sigma_{0}=I_{d}/\sqrt{d},\sigma_{1},\cdots,\sigma_{d^{2}-1}\right\\}\subset{\cal
H}_{d},$ (S4)

where $\operatorname{Tr}[\sigma_{j}\sigma_{k}]=\delta_{jk}$ and $\delta_{jk}$
is Kronecker delta. Thus, any $d^{n}$-dimensional Hermitian matrix could be
represented as a real linear combination of ${\cal B}_{d}^{\otimes n}$.

###### Definition S1

Given a $d^{n}$-dimensional Hilbert space ${\cal H}_{d^{n}}$, for
$\mathbf{j}=\left(j_{1},j_{2}\cdots,j_{n}\right)\in\\{0,1,\cdots,$
$d^{2}-1\\}^{n}$, denote

$\sigma_{\mathbf{j}}\mathrel{\mathop{\mathchar
58\relax}}=\begin{cases}\sigma_{j_{1}}\otimes\sigma_{j_{2}}^{T}\otimes\sigma_{j_{3}}\otimes\cdots\otimes\sigma_{j_{d}},&\text{if
}d\text{ odd};\\\
\sigma_{j_{1}}^{T}\otimes\sigma_{j_{2}}\otimes\sigma_{j_{3}}^{T}\otimes\cdots\otimes\sigma_{j_{d}},&\text{if
}d\text{ even},\end{cases}$ (S5)

then

${\cal B}_{d,n}\mathrel{\mathop{\mathchar
58\relax}}=\left\\{\sigma_{\mathbf{j}}\,\middle|\,\mathbf{j}\in\left\\{0,1,\cdots,d^{2}-1\right\\}^{n}\right\\}$
(S6)

forms a group of orthonormal basis for ${\cal H}_{d^{n}}$ naturally.

###### Proposition S3

For any Hermitian $H\in{\cal H}_{d^{n}}$,

$H=\sum_{\mathbf{j}}H_{\mathbf{j}}\sigma_{\mathbf{j}},\text{ where each
}H_{\mathbf{j}}=\operatorname{Tr}\left[H\cdot\sigma_{\mathbf{j}}\right]\in\mathbb{R}.$
(S7)

###### Definition S2

For any Hermitian $H\in{\cal H}_{d^{n}}$, denote

$M_{H}\mathrel{\mathop{\mathchar
58\relax}}=\sum_{\mathbf{j}}H_{\mathbf{j}}\langle\mathbf{j}\rangle,$ (S8)

where

$\langle\mathbf{j}\rangle\mathrel{\mathop{\mathchar
58\relax}}=\begin{cases}\langle j_{1}|\otimes|j_{2}\rangle\otimes\langle
j_{3}|\otimes\cdots\otimes\langle j_{d}|,&\text{if }d\text{ odd};\\\
|j_{1}\rangle\otimes\langle
j_{2}|\otimes|j_{3}\rangle\otimes\cdots\otimes\langle j_{d}|,&\text{if
}d\text{ even},\end{cases}$ (S9)

###### Fact 1

Any state $\rho\in{\cal H}_{d}$, the Choi matrix of any virtual channel
$C_{\widetilde{{\cal N}}}$, the Choi matrix of identity channel and the Choi
matrix of any $1$-slot virtual comb $C_{\widetilde{\cal C}}$ could be
represented as

$\displaystyle\rho=\sum_{j}\rho_{j}\sigma_{j},$ $\displaystyle
M_{\rho}=\sum_{j}\rho_{j}\langle j|,$ (S10) $\displaystyle C_{\widetilde{{\cal
N}}}=\sum_{jk}\widetilde{{\cal N}}_{jk}\sigma_{j}^{T}\otimes\sigma_{k},$
$\displaystyle M_{\widetilde{{\cal N}}}=\sum_{jk}\widetilde{{\cal
N}}_{jk}|j\rangle\otimes\langle k|,$ (S11) $\displaystyle
C_{{\operatorname{id}}}=\sum_{j}\sigma_{j}^{T}\otimes\sigma_{j},$
$\displaystyle M_{{\operatorname{id}}}=I_{d^{2}},$ (S12) $\displaystyle
C_{\widetilde{\cal C}}=\sum_{klrs}\widetilde{\cal
C}_{klrs}\sigma_{k}^{T}\otimes\sigma_{l}\otimes\sigma_{r}^{T}\otimes\sigma_{s},$
$\displaystyle M_{\widetilde{\cal C}}=\sum_{klrs}\widetilde{\cal
C}_{klrs}|k\rangle\otimes\langle l|\otimes|r\rangle\otimes\langle s|,$ (S13)

where $M_{C_{*}}$ is abbreviated as $M_{*}$ when there is no ambiguity.

###### Fact 2

In the decomposition above, quantum processes could be represented as follows

$\displaystyle\widetilde{{\cal N}}(\rho)=\sum_{jk}\rho_{j}\widetilde{\cal
N}_{jk}\sigma_{k},$ $\displaystyle M_{\widetilde{{\cal
N}}(\rho)}=M_{\rho}\cdot M_{\widetilde{\cal N}},$ (S14) $\displaystyle
C_{\widetilde{{\cal N}}\circ\widetilde{{\cal
N}}^{\prime}}=\sum_{jkl}\widetilde{\cal N}^{\prime}_{jk}\widetilde{\cal
N}_{kl}\sigma_{j}^{T}\otimes\sigma_{l},$ $\displaystyle M_{\widetilde{{\cal
N}}\circ\widetilde{{\cal N}}^{\prime}}=M_{\widetilde{\cal N}^{\prime}}\cdot
M_{\widetilde{\cal N}},$ (S15) $\displaystyle C_{{\widetilde{\cal
C}}(\widetilde{{\cal N}})}=\sum_{klrs}\widetilde{\cal C}_{klrs}\widetilde{\cal
N}_{lr}\sigma_{k}^{T}\otimes\sigma_{s},$ $\displaystyle M_{{\widetilde{\cal
C}}(\widetilde{{\cal N}})}=\left(I_{d^{2}}\otimes M_{\widetilde{\cal
N}}^{T_{1}}\right)\cdot M_{\widetilde{\cal C}}^{T_{2}},$ (S16)

where

$M_{\widetilde{\cal N}}^{T_{1}}\mathrel{\mathop{\mathchar
58\relax}}=\sum_{jk}\widetilde{{\cal N}}_{jk}\langle j|\otimes\langle k|,\
M_{\widetilde{\cal C}}^{T_{2}}\mathrel{\mathop{\mathchar
58\relax}}=\sum_{klrs}\widetilde{\cal
C}_{klrs}|k\rangle\otimes|l\rangle\otimes|r\rangle\otimes\langle s|.$ (S17)

This fact can be directly checked by calculating

$\displaystyle\widetilde{{\cal N}}(\rho)$
$\displaystyle=\sum_{lr}\sum_{j^{\prime}}\rho_{j^{\prime}}\langle
l|\sigma_{j^{\prime}}|r\rangle\sum_{jk}\widetilde{\cal N}_{jk}\langle
l|\sigma_{j}^{T}|r\rangle\sigma_{k}=\sum_{j^{\prime}jk}\rho_{j^{\prime}}\widetilde{\cal
N}_{jk}\sigma_{k}\sum_{lr}\langle l|\sigma_{j^{\prime}}|r\rangle\langle
r|\sigma_{j}|l\rangle$ (S18)
$\displaystyle=\sum_{j^{\prime}jk}\rho_{j^{\prime}}\widetilde{\cal
N}_{jk}\sigma_{k}\operatorname{Tr}[\sigma_{j^{\prime}}\sigma_{j}]=\sum_{jk}\rho_{j}\widetilde{\cal
N}_{jk}\sigma_{k}.$ (S19)

Other equations could be obtained analogously. Based on these symbolic
expressions, we have the following statement as a direct corollary of Eq.
(S12) and Eq. (S15).

###### Corollary S4

For a channel $\widetilde{{\cal N}}$, it has inverse map $\widetilde{{\cal
N}}^{-1}$ if and only if $M_{\widetilde{{\cal N}}}$ is invertible, while

$M_{\widetilde{{\cal N}}^{-1}}=M_{\widetilde{{\cal N}}}^{-1}.$ (S20)

###### Lemma S5

For a given matrix $M_{\widetilde{{\cal N}}}\in\mathbb{R}^{d^{2}\times
d^{2}}$, $C_{\widetilde{{\cal N}}}$ is the Choi matrix of an HPTP map if and
only if $\widetilde{\cal N}_{j0}=\delta_{j0}$; for a given matrix
$M_{\widetilde{\cal C}}\in\mathbb{R}^{d^{4}\times d^{4}}$, $C_{\widetilde{\cal
C}}$ is the Choi matrix of a $1$-slot virtual comb if and only if

$\widetilde{\cal C}_{klr0}=\begin{cases}0,&\text{if }r\neq 0;\\\
\delta_{k0},&\text{if }l=r=0.\end{cases}$ (S21)

###### Proof.

By

$\forall\rho,\ \operatorname{Tr}[\rho]=\sqrt{d}\rho_{0},\
\operatorname{Tr}[\widetilde{{\cal N}}(\rho)]=\sum_{jk}\rho_{j}\widetilde{\cal
N}_{jk}\operatorname{Tr}[\sigma_{k}]=\sqrt{d}\sum_{j}\rho_{j}\widetilde{\cal
N}_{j0},$ (S22)

we find $\widetilde{{\cal N}}$ is TP if and only if $\widetilde{\cal
N}_{j0}=\delta_{j0}$. By Lemma S2, we have $C_{\widetilde{\cal C}}$ is the
Choi matrix of a $1$-slot virtual comb if and only if

$\operatorname{Tr}_{4}[C_{\widetilde{\cal
C}}]=\operatorname{Tr}_{34}[C_{\widetilde{\cal C}}\otimes I_{d}/d],\
\operatorname{Tr}_{234}[C_{\widetilde{\cal
C}}]={\operatorname{Tr}[C_{\widetilde{\cal C}}]}\cdot I_{d}/d,\
\operatorname{Tr}[C_{\widetilde{\cal C}}]=d^{2},$ (S23)

i.e.

$(r\neq 0\implies\widetilde{\cal C}_{klr0}=0)\wedge\widetilde{\cal
C}_{k000}=\delta_{k0}$ (S24)

$\sqcap$$\sqcup$

##  Appendix B Proof of Theorems

###  Supplementary Note 1 Reversing depolarizing channels

###### Theorem 1

For any $n\geq 1$, let ${\cal D}_{p_{1}},...,{\cal D}_{p_{n+1}}$ be $n+1$
$d$-dimensional depolarizing channels with distinct noise parameters
$p_{1},...,p_{n+1}\in[0,1)$. There exists an $n$-slot virtual comb
${\widetilde{\cal C}}$ satisfying

${\widetilde{\cal C}}({\cal D}_{p_{i}}^{\otimes n})={\cal
D}_{p_{i}}^{-1},\quad\forall\,i=1,...,n+1.$ (S25)

###### Proof.

For general $n$, we use a similar method to demonstrate the existence of a
virtual comb as the example for $n=1$ given in the main text. Let
$\mathbf{k}=(k_{1},k_{2},...,k_{n})\in\\{0,1\\}^{n}$ be a $n$-bit binary
string and $|\mathbf{k}|$ be the Hamming weight of it. We then denote ${\cal
D}_{\mathbf{k}}={\cal N}_{k_{1}}\otimes{\cal
N}_{k_{2}}\otimes\cdots\otimes{\cal N}_{k_{n}}$ where ${\cal
N}_{k_{i}}={\operatorname{id}}$ if $k_{i}=1$ and ${\cal N}_{k_{i}}={\cal D}$
if $k_{i}=0$. Suppose ${\widetilde{\cal C}}$ is a virtual comb that could do
exact inversion for $m$ distinct noise level, it is then sufficient to satisfy

${\widetilde{\cal C}}*{\cal D}_{p_{i}}^{\otimes
n}=\sum_{\mathbf{k}\in\\{0,1\\}^{N}}(1-p_{i})^{|\mathbf{k}|}p_{i}^{1-|\mathbf{k}|}{\widetilde{\cal
C}}*{\cal D}_{\mathbf{k}}=\frac{1}{1-p_{i}}{\operatorname{id}}_{{\cal P}{\cal
F}}-\frac{p_{i}}{1-p_{i}}{\cal D}_{{\cal P}{\cal F}},\;\;\forall
i=1,2,\cdots,m\,.$ (S26)

We denote ${\widetilde{\cal C}}*{\cal
D}_{\mathbf{k}}=\alpha_{\mathbf{k}}{\operatorname{id}}_{{\cal P}{\cal
F}}+(1-\alpha_{\mathbf{k}}){\cal D}_{{\cal P}{\cal F}}$ and
$\alpha_{i}=\sum_{|\mathbf{k}|=N-i}\alpha_{\mathbf{k}}$. Then we can
equivalently express Eq. (S26) as the following linear system

$\left\\{\begin{array}[]{c}\left(1-p_{1}\right)^{n}\alpha_{0}+\left(1-p_{1}\right)^{n-1}p_{1}\alpha_{1}+\cdots+p_{1}^{n}\alpha_{n}=\frac{1}{1-p_{1}}\\\
\left(1-p_{2}\right)^{n}\alpha_{0}+\left(1-p_{2}\right)^{n-1}p_{2}\alpha_{1}+\cdots+p_{2}^{n}\alpha_{n}=\frac{1}{1-p_{2}}\\\
\quad\quad\vdots\\\
\left(1-p_{m}\right)^{n}\alpha_{0}+\left(1-p_{m}\right)^{n-1}p_{m}\alpha_{1}+\cdots+p_{m}^{n}\alpha_{n}=\frac{1}{1-p_{m}}\end{array}\right.$
(S27)

The coefficient matrix of the linear system in Eq. (S27) can be written as

$A=\left(\begin{array}[]{cccc}(1-p_{1})^{n}&0&\ldots&0\\\
0&(1-p_{2})^{n}&\ldots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\ldots&(1-p_{m})^{n}\end{array}\right)\left(\begin{array}[]{cccc}1&\frac{p_{1}}{1-p_{1}}&\ldots&(\frac{p_{1}}{1-p_{1}})^{n}\\\
1&\frac{p_{2}}{1-p_{2}}&\ldots&(\frac{p_{2}}{1-p_{2}})^{n}\\\
\vdots&\vdots&\ddots&\vdots\\\
1&\frac{p_{m}}{1-p_{m}}&\ldots&(\frac{p_{m}}{1-p_{m}})^{n}\end{array}\right).$
(S28)

Notice that the right one is a Vandermonde matrix. When $m=n+1$, its
determinant can be expressed as

$\det(A)=\prod_{1\leq i\leq m}(1-p_{i})^{n}\prod_{1\leq i<j\leq
m}\left(\frac{p_{j}}{1-p_{j}}-\frac{p_{i}}{1-p_{i}}\right)$ (S29)

which indicates that it is invertible if and only if all $p_{i}$ are distinct.
Hence, we conclude that $\operatorname{Rank}A=\min\\{n+1,m\\}$. Now we
consider the augmented matrix of the linear system in Eq. (S27). We have

$(A|B)=\left(\begin{array}[]{ccccc}(1-p_{1})^{n}&(1-p_{1})^{n-1}p_{1}&\ldots&p_{1}^{n}&\frac{1}{1-p_{1}}\\\
(1-p_{2})^{n}&(1-p_{2})^{n-1}p_{2}&\ldots&p_{2}^{n}&\frac{1}{1-p_{1}}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
(1-p_{k})^{n}&(1-p_{k})^{n-1}p_{k}&\ldots&p_{k}^{n}&\frac{1}{1-p_{k}}\end{array}\right).$
(S30)

It is easy to verify that the determinant of $(A|B)$ is identical to the
following matrix

$\left(\begin{array}[]{ccccc}(1-p_{1})^{n+1}&(1-p_{1})^{n}&\ldots&(1-p_{1})&1\\\
(1-p_{2})^{n+1}&(1-p_{2})^{n}&\ldots&(1-p_{2})&1\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
(1-p_{k})^{n+1}&(1-p_{k})^{n}&\ldots&(1-p_{k})&1\end{array}\right)$ (S31)

which is also a Vandermonde matrix. Using a similar argument, we have
$\operatorname{Rank}(A|B)=\min\\{n+2,m\\}$. When $m=n+1$, it follows
$\operatorname{Rank}A=\operatorname{Rank}(A|B)$ which yields that the linear
system has a unique solution. Similar to Eq. (6), we can construct a virtual
comb according to the solution, which completes the proof.  $\sqcap$$\sqcup$

###### Proposition 2

For any $n\geq 1$, let ${\cal D}_{p_{1}},...,{\cal D}_{p_{n+1}}$ be $n+1$
$d$-dimensional depolarizing channels with distinct noise parameters
$p_{1},...,p_{n+1}\in[0,1)$. There does not exist an $n$-slot quantum comb
that can reverse ${\cal D}_{p_{i}}$ for each $i$, even probabilistically.

###### Proof.

For $n=1$, suppose there is a quantum comb ${\cal C}$ with a Choi operator $C$
that can probabilistically reverse an unknown depolarizing channel ${\cal
D}_{p}$. It follows

$\left\\{\begin{array}[]{c}C*|I_{d}\rangle\rangle\langle\langle I_{d}|_{{\cal
I}{\cal O}}=\alpha_{1}|I_{d}\rangle\rangle\langle\langle I_{d}|_{{\cal P}{\cal
F}}+\alpha_{2}(\frac{1}{d}I_{d}\otimes I_{d})_{{\cal P}{\cal F}}\\\
C*(\frac{1}{d}I_{d}\otimes I_{d})_{{\cal I}{\cal
O}}=\beta_{1}|I_{d}\rangle\rangle\langle\langle I_{d}|_{{\cal P}{\cal
F}}+\beta_{2}(\frac{1}{d}I_{d}\otimes I_{d})_{{\cal P}{\cal
F}}\end{array}\right.$ (S32)

where $\alpha_{1,2},\beta_{1,2}\geq 0,\alpha_{1}+\alpha_{2}\leq
1,\beta_{1}+\beta_{2}\leq 1$. At the same time, for $i=1,2$, we have

$\left\\{\begin{array}[]{c}(1-p_{i})\alpha_{1}+p_{i}\beta_{1}=\frac{q}{1-p_{i}}\\\
(1-p_{i})\alpha_{2}+p_{i}\beta_{2}=\frac{-p_{i}q}{1-p_{i}}\end{array}\right.$
(S33)

where $0<q\leq 1$. Notice that $1-p_{i}\geq 0,\alpha_{2}\geq 0,p_{i}\geq
0\,\beta_{2},\geq 0$ and $-p_{i}q/(1-p_{i})\leq 0$ which is a contradiction in
Eq. (S33). Thus, there is no probabilistic comb.

For $n\geq 2$, the proof is similar, and the key point is that in Eq. (S26) if
the virtual comb is replaced with a quantum comb or a probabilistic comb, the
left-hand side of the equation is always positive while the right-hand side
has negative eigenvalues.  $\sqcap$$\sqcup$

###### Theorem 5

Let $0\leq p_{1}<p_{2}\leq 1$, the minimum worst-case error of an approximate
channel inversion for a depolarizing channel ${\cal D}_{p}$ with
$p\in[p_{1},p_{2}]$ using an $n$-slot virtual comb is at most ${\cal
O}(n^{-1})$.

###### Proof.

Fix $n\geq 2$, by Theorem 1, we consider a virtual comb that holds
${\widetilde{C}}*J_{{\cal D}_{p_{i}}}^{\otimes n}=J_{{\cal D}_{p_{i}}}^{-1}$
for any $p_{1},p_{2},...,p_{n+1}$ where
$p_{i}=p_{1}+\frac{i-2}{n}(p_{2}-p_{1}),i\geq 3$. It follows

$\left\|J_{{\cal D}_{p}}*({\widetilde{C}}*J_{{\cal D}_{p}}^{\otimes
n})-|I\rangle\rangle\langle\langle
I|\right\|_{1}=\frac{3}{2}\left|1-(1-p)\cdot\left[(1-p)^{n}\alpha_{0}^{(n)}+(1-p)^{n-1}p\alpha_{1}^{(n)}+\cdots+p^{n}\alpha_{n}^{(n)}\right]\right|$

Denote
$f_{n}(p)=1-(1-p)\cdot\left[(1-p)^{n}\alpha_{0}^{(n)}+(1-p)^{n-1}p\alpha_{1}^{(n)}+\cdots+p^{n}\alpha_{n}^{(n)}\right]$
which is an univariate polynomial of degree $n+1$. Its root set is provided by
$\\{p_{i}\\}_{i=1}^{n+1}$. Noticing $f_{n}(0)=1-\alpha_{0}^{(n)}$, we can
rewrite $f_{n}(p)$ as

$f_{n}(p)=(-1)^{n+1}\left(1-\alpha_{0}^{(n)}\right)\cdot\prod_{i=1}^{n+1}\frac{p-p_{i}}{p_{i}}.$
(S34)

Consider the derivatives of this polynomial function at $p_{j}$. We have

$\frac{\mathrm{d}f_{n}}{\mathrm{d}p}\bigg{|}_{p=p_{i}}=(-1)^{n+1}\frac{1-\alpha_{0}^{(n)}}{p_{i}}\cdot\prod_{j\neq
i}^{n+1}\frac{p_{i}-p_{j}}{p_{j}}.$ (S35)

Recall that by Eq. (S27), we have
$\alpha_{0}^{(n)}=1-(-1)^{n+1}\prod_{i=1}^{n+1}\frac{p_{i}}{1-p_{i}}$. In the
following, we will show that

$\mathrm{abs}\left(\frac{\mathrm{d}f_{n}}{\mathrm{d}p}\bigg{|}_{p=p_{1}}\right)\leq\mathrm{abs}\left(\frac{\mathrm{d}f_{1}}{\mathrm{d}p}\bigg{|}_{p=p_{1}}\right),\;\mathrm{abs}\left(\frac{\mathrm{d}f_{n}}{\mathrm{d}p}\bigg{|}_{p=p_{k}}\right)\leq\mathrm{abs}\left(\frac{\mathrm{d}f_{n}}{\mathrm{d}p}\bigg{|}_{p=p_{1}}\right),\quad\forall
n,k\geq 2.$ (S36)

Firstly, we can calculate that

$\displaystyle\mathrm{abs}\left(\frac{\mathrm{d}f_{n}}{\mathrm{d}p}\bigg{|}_{p=p_{1}}\right)\bigg{/}\mathrm{abs}\left(\frac{\mathrm{d}f_{1}}{\mathrm{d}p}\bigg{|}_{p=p_{1}}\right)$
$\displaystyle=\frac{1-\alpha_{0}^{(n)}}{1-\alpha_{0}^{(1)}}\cdot\prod_{j=3}^{n+1}\frac{p_{j}-p_{1}}{p_{j}}$
(S37)
$\displaystyle=\prod_{i=3}^{n+1}\frac{p_{i}}{1-p_{i}}\cdot\prod_{j=3}^{n+1}\frac{p_{j}-p_{1}}{p_{j}}$
$\displaystyle=\prod_{j=3}^{n+1}\frac{p_{j}-p_{1}}{1-p_{j}}$
$\displaystyle\leq 1$

Here we note that $0\leq p_{1}<p_{2}\leq 1$ and
$p_{i+1}-p_{i}=p_{i+2}-p_{i+1}$ for any $i$. It holds that

$\frac{(p_{1}-p_{i})(p_{1}-p_{n+4-i})}{(1-p_{i})(1-p_{n+4-i})}\leq
1,\quad\forall i\geq 3,$ (S38)

which yields the inequality in Eq. (S37). Secondly, we have

$\mathrm{abs}\left(\frac{\mathrm{d}f_{n}}{\mathrm{d}p}\bigg{|}_{p=p_{k}}\right)\bigg{/}\mathrm{abs}\left(\frac{\mathrm{d}f_{n}}{\mathrm{d}p}\bigg{|}_{p=p_{1}}\right)=\bigg{|}\frac{\prod_{j\neq
k}(p_{k}-p_{j})}{\prod_{j\neq 1}(p_{1}-p_{j})}\bigg{|}\leq 1.$ (S39)

Therefore, for a given noise region $[p_{1},p_{2}]$, we denote
$c=\frac{\mathrm{d}f_{1}}{\mathrm{d}p}|_{p=p_{1}}$ and have

$f_{n}(p)\leq|c|\cdot\frac{p_{2}-p_{1}}{n}\,.$ (S40)

As shown in [Wat18] the worst-case diamond norm error can be bounded by the
entanglement error with a relation that

$\displaystyle\frac{1}{2}\left\|{\cal N}_{1}-{\cal
N}_{2}\right\|_{\diamond}\leq d\cdot\frac{1}{2}\left\|J_{{\cal
N}_{1}}-J_{{\cal N}_{2}}\right\|_{1}\,,$ (S41)

Eq. (S40) indicates the worst-case error is at most ${\cal O}(n^{-1})$.
$\sqcap$$\sqcup$

###  Supplementary Note 2 Reversing general channels

The proof of Theorem 4 is based on the Hermitian decomposition technique which
is introduced in Appendix A. Before proving the theorem, we will first prove
several lemmas and corollaries as follows. For simplicity, we label the
systems ${\cal P},{\cal I},{\cal O},{\cal F}$ as $1,2,3,4$, respectively.

###### Lemma S6

For a $1$-slot virtual comb ${\widetilde{\cal C}}$ and a channel ${\cal N}$,
${\widetilde{\cal C}}({\cal N})$ is the inverse map for channel ${\cal N}$, if
and only if

$\left(M_{\cal N}\otimes M_{{\cal N}}^{T_{1}}\right)\cdot M_{{\widetilde{\cal
C}}}^{T_{2}}=I_{d^{2}}.$ (S42)

###### Proof.

${\widetilde{\cal C}}*{\cal N}$ is the inverse map for channel ${\cal N}$ if
and only if $({\widetilde{\cal C}}*{\cal N})\circ{\cal N}$ is just identity
map. By (S12), (S15) and (S16), we have

$\displaystyle I_{d^{2}}=M_{{\operatorname{id}}}=M_{{\widetilde{\cal C}}({\cal
N})\circ{\cal N}}=M_{\cal N}\cdot M_{{\widetilde{\cal C}}({\cal N})}=M_{\cal
N}\cdot\left(\left(I_{d^{2}}\otimes M_{{\cal N}}^{T_{1}}\right)\cdot
M_{{\widetilde{\cal C}}}^{T_{2}}\right)=\left(M_{\cal N}\otimes M_{{\cal
N}}^{T_{1}}\right)\cdot M_{{\widetilde{\cal C}}}^{T_{2}}$ (S43)

$\sqcap$$\sqcup$

###### Corollary S7

For a $1$-slot virtual comb ${\widetilde{\cal C}}$ and several channels ${\cal
N}_{0},{\cal N}_{1},\cdots,{\cal N}_{m-1}$, each ${\widetilde{\cal C}}({\cal
N}_{j})$ is the inverse map for channel ${\cal N}_{j}$, if and only if

$\left(\sum_{j=0}^{m-1}|j\rangle\otimes M_{{\cal N}_{j}}\otimes M_{{\cal
N}_{j}}^{T_{1}}\right)\cdot M_{{\widetilde{\cal
C}}}^{T_{2}}=\sum_{j=0}^{m-1}|j\rangle\otimes I_{d^{2}}.$ (S44)

###### Lemma S8

For two different channels ${\cal N}_{0},{\cal N}_{1}$, if they both have
inverse map, then

$\operatorname{Rank}\left(\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal
N}_{j}}\otimes M_{{\cal N}_{j}}^{T_{1}}\right)=2d^{2}.$ (S45)

###### Proof.

Since such matrix is of dimension $2d^{2}\times d^{6}$, it is of full rank if
and only if it is row linearly independent, i.e.

$\sum_{k=0}^{d^{2}-1}\sum_{j=0}^{1}a_{kj}\langle
kj|\cdot\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal N}_{j}}\otimes M_{{\cal
N}_{j}}^{T_{1}}=\sum_{j=0}^{1}\sum_{k=0}^{d^{2}-1}a_{kj}\langle k|M_{{\cal
N}_{j}}\otimes M_{{\cal N}_{j}}^{T_{1}}=0\implies\forall\,k,j,\ a_{kj}=0.$
(S46)

Supposed that the left hands holds, considering $M_{{\cal N}_{0}}^{T_{1}}$ is
linear independent from $M_{{\cal N}_{1}}^{T_{1}}$, we derive that

$\forall\,j,\ \sum_{k=0}^{d^{2}-1}a_{kj}\langle k|M_{{\cal N}_{j}}=0.$ (S47)

Moreover, by each $M_{{\cal N}_{j}}$ invertible, we conclude that each
$a_{kj}$ vanishes, i.e. such matrix is of full rank.  $\sqcap$$\sqcup$

###### Corollary S9

For two different channels ${\cal N}_{0},{\cal N}_{1}$, if they both have
inverse maps, then there always exists $M_{\widetilde{\cal
C}^{\prime}}\in\mathbb{R}^{d^{6}\times d^{2}}$ satisfying

$\left(\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal N}_{j}}\otimes M_{{\cal
N}_{j}}^{T_{1}}\right)\cdot M_{\widetilde{\cal
C}^{\prime}}^{T_{2}}=\sum_{j=0}^{1}|j\rangle\otimes I_{d^{2}}.$ (S48)

###### Proof.

By Lemma S8, the rows of matrix $\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal
N}_{j}}\otimes M_{{\cal N}_{j}}^{T_{1}}$ are of full rank, so it has right
inverse $V\in\mathbb{R}^{d^{6}\times 2d^{2}}$, i.e.

$\left(\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal N}_{j}}\otimes M_{{\cal
N}_{j}}^{T_{1}}\right)\cdot V=I_{2d^{2}}.$ (S49)

Then let

$M_{\widetilde{\cal C}^{\prime}}^{T_{2}}\mathrel{\mathop{\mathchar
58\relax}}=V\cdot\left(\sum_{j=0}^{1}|j\rangle\otimes I_{d^{2}}\right),$ (S50)

and we find

$\left(\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal N}_{j}}\otimes M_{{\cal
N}_{j}}^{T_{1}}\right)\cdot M_{\widetilde{\cal
C}^{\prime}}^{T_{2}}=I_{2d^{2}}\cdot\left(\sum_{j=0}^{1}|j\rangle\otimes
I_{d^{2}}\right)=\sum_{j=0}^{1}|j\rangle\otimes I_{d^{2}}.$ (S51)

$\sqcap$$\sqcup$

###### Corollary S10

For two different channels ${\cal N}_{0},{\cal N}_{1}$, if they both have
inverse maps, then there always exists a virtual comb ${\widetilde{\cal C}}$
satisfying

$\left(\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal N}_{j}}\otimes M_{{\cal
N}_{j}}^{T_{1}}\right)\cdot M_{\widetilde{\cal
C}}^{T_{2}}=\sum_{j=0}^{1}|j\rangle\otimes I_{d^{2}}.$ (S52)

###### Proof.

By Corollary S9, there always exists $M_{{\widetilde{\cal
C}}^{\prime}}\in\mathbb{R}^{d^{6}\times d^{2}}$ satisfying

$\left(\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal N}_{j}}\otimes M_{{\cal
N}_{j}}^{T_{1}}\right)\cdot M_{{\widetilde{\cal
C}}^{\prime}}^{T_{2}}=\sum_{j=0}^{1}|j\rangle\otimes I_{d^{2}}.$ (S53)

Denote

$M_{\widetilde{\cal C}}^{T_{2}}\mathrel{\mathop{\mathchar
58\relax}}=M_{{\widetilde{\cal
C}}^{\prime}}^{T_{2}}\cdot(I_{d^{2}}-|0\rangle\\!\langle
0|)+|000\rangle\\!\langle 0|,$ (S54)

and we claim ${\widetilde{\cal C}}$ is a virtual comb satisfying (S52).
Firstly, we could check (S52) as following:

$\displaystyle\left(\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal N}_{j}}\otimes
M_{{\cal N}_{j}}^{T_{1}}\right)\cdot M_{{\widetilde{\cal C}}}^{T_{2}}$ (S55)
$\displaystyle=$ $\displaystyle\left(\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal
N}_{j}}\otimes M_{{\cal N}_{j}}^{T_{1}}\right)\cdot\left(M_{{\widetilde{\cal
C}}^{\prime}}^{T_{2}}\cdot(I_{d^{2}}-|0\rangle\\!\langle
0|)+|000\rangle\\!\langle 0|\right)$ (S56) $\displaystyle=$
$\displaystyle\sum_{j=0}^{1}|j\rangle\otimes
I_{d^{2}}\cdot(I_{d^{2}}-|0\rangle\\!\langle
0|)+\left(\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal N}_{j}}\otimes M_{{\cal
N}_{j}}^{T_{1}}\right)\cdot|000\rangle\\!\langle 0|$ (S57) $\displaystyle=$
$\displaystyle\sum_{j=0}^{1}|j\rangle\otimes(I_{d^{2}}-|0\rangle\\!\langle
0|)+\sum_{j=0}^{1}|j\rangle\otimes M_{{\cal N}_{j}}|0\rangle\otimes M_{{\cal
N}_{j}}^{T_{1}}|00\rangle\langle 0|$ (S58) $\displaystyle=$
$\displaystyle\sum_{j=0}^{1}|j\rangle\otimes(I_{d^{2}}-|0\rangle\\!\langle
0|)+\sum_{j=0}^{1}|j\rangle\otimes|0\rangle\otimes\langle 0|$ (S59)
$\displaystyle=$ $\displaystyle\sum_{j=0}^{1}|j\rangle\otimes I_{d^{2}},$
(S60)

where $M_{\cal N}|0\rangle=|0\rangle$, $M_{\cal N}^{T_{1}}|00\rangle=1$ comes
from ${\cal N}_{j0}=\delta_{j0}$ in Lemma S5. Since $M_{\widetilde{\cal
C}}^{T_{2}}|0\rangle=|000\rangle$, i.e.

${\widetilde{\cal C}}_{klr0}=\delta_{k0}\delta_{l0}\delta_{r0},$ (S61)

${\widetilde{\cal C}}$ always satisfies the condition for a virtual comb by
Lemma S5. As above all, ${\widetilde{\cal C}}$ is already a virtual comb
satisfying (S52) and we are done.  $\sqcap$$\sqcup$

###### Theorem 4

For any two invertible quantum channels ${\cal N}_{1}$, ${\cal N}_{2}$, there
exists a $1$-slot virtual comb ${\widetilde{\cal C}}$ satisfying

${\widetilde{\cal C}}({\cal N}_{i})={\cal N}_{i}^{-1},\quad\forall\,i=1,2.$
(S62)

###### Proof.

The argument can be directly derived from Corollary S7 and Corollary S10.
$\sqcap$$\sqcup$

###  Supplementary Note 3 Reversing unitary channels

###### Proposition 6

For any dimension $d$, there exists a $1$-slot virtual comb ${\widetilde{\cal
C}}$ that transforms any qudit-unitary channel ${\cal U}_{d}$ into its inverse
${\cal U}_{d}^{-1}$, i.e. ${\widetilde{\cal C}}({\cal
U}_{d})(\cdot)=U_{d}^{{\dagger}}(\cdot)U_{d}$.

###### Proof.

For simplicity, we label the systems ${\cal P},{\cal I},{\cal O},{\cal F}$ as
$1,2,3,4$, respectively. Let

$\displaystyle V_{0}$
$\displaystyle=\frac{1}{d^{2}-1}|I\rangle\rangle\langle\langle
I|^{T_{3}}_{13}\otimes|I\rangle\rangle\langle\langle
I|^{T_{4}}_{24}-\frac{1}{d^{2}-1}I_{13}\otimes|I\rangle\rangle\langle\langle
I|^{T_{4}}_{24}-\frac{1}{d^{2}-1}|I\rangle\rangle\langle\langle
I|^{T_{3}}_{13}\otimes I_{24}+\frac{1}{d^{2}-1}I_{1234},$ (S63) $\displaystyle
V_{1}$ $\displaystyle=-\frac{1}{d^{2}-1}|I\rangle\rangle\langle\langle
I|^{T_{3}}_{13}\otimes|I\rangle\rangle\langle\langle
I|^{T_{4}}_{24}-\frac{1}{d^{2}-1}I_{13}\otimes|I\rangle\rangle\langle\langle
I|^{T_{4}}_{24}+\frac{1}{d^{2}-1}|I\rangle\rangle\langle\langle
I|^{T_{3}}_{13}\otimes I_{24}+\frac{1}{d^{2}-1}I_{1234}.$ (S64)

After simple calculation, we could find $V_{0}$ and $V_{1}$ are both positive,
and it is straightforward to check that they are Choi operators of two quantum
combs ${\cal C}_{0},{\cal C}_{1}$, respectively. Then we have

$\displaystyle V$ $\displaystyle=\frac{d^{2}}{2}V_{0}-\frac{d^{2}-2}{2}V_{1}$
(S65) $\displaystyle=|I\rangle\rangle\langle\langle
I|^{T_{3}}_{13}\otimes|I\rangle\rangle\langle\langle
I|^{T_{4}}_{24}-\frac{1}{d^{2}-1}I_{13}\otimes\Phi^{T_{4}}_{24}-|I\rangle\rangle\langle\langle
I|^{T_{3}}_{13}\otimes I_{24}+\frac{1}{d^{2}-1}I_{1234}.$ (S66)

Denote $M_{0}=|I\rangle\rangle\langle\langle
I|^{T_{3}}_{13}\otimes|I\rangle\rangle\langle\langle
I|^{T_{4}}_{24},M_{1}=I_{13}\otimes|I\rangle\rangle\langle\langle
I|^{T_{4}}_{24},M_{2}=|I\rangle\rangle\langle\langle I|^{T_{3}}_{13}\otimes
I_{24}$ and $M_{3}=I_{1234}/d^{2}$. By calculation, we have

$M_{0}*|U\rangle\rangle\langle\langle
U|=|U^{\dagger}\rangle\rangle\langle\langle
U^{\dagger}|,M_{1}*|U\rangle\rangle\langle\langle U|=I_{{\cal P}{\cal
F}}/d,M_{2}*|U\rangle\rangle\langle\langle U|=I_{{\cal P}{\cal
F}}/d,M_{3}*|U\rangle\rangle\langle\langle U|=I_{{\cal P}{\cal F}}/d,$ (S67)

which follows

$V*|U\rangle\rangle\langle\langle U|=|U^{\dagger}\rangle\rangle\langle\langle
U^{\dagger}|-\frac{1}{d(d^{2}-1)}I_{{\cal P}{\cal F}}-\frac{1}{d}I_{{\cal
P}{\cal F}}+\frac{d^{2}}{d(d^{2}-1)}I_{{\cal P}{\cal
F}}=|U^{\dagger}\rangle\rangle\langle\langle U^{\dagger}|.$ (S68)

$\sqcap$$\sqcup$

###### Theorem 7

Let $F_{\rm opt}(d,n)$ be the optimal channel fidelity of reversing
$d$-dimensional unitary operations with an $n$-slot quantum comb and
$\nu(d,n)$ be the optimal sampling overhead for the $n$-slot virtual comb that
can exactly reverse a $d$-dimensional unitary operation. It satisfies

$\nu(d,n)=\frac{2}{F_{\rm opt}(d,n)}-1,\quad\forall d\geq 2,n\geq 1.$ (S69)

###### Proof.

First, we are going to show

$\nu(d,n)\geq\frac{2}{F_{\rm opt}(d,n)}-1.$ (S70)

Suppose $\\{\widehat{\eta},\widehat{{\cal C}}_{0},\widehat{{\cal C}}_{1}\\}$
is a feasible solution to SDP (19) where $\widehat{{\cal
C}}_{0},\widehat{{\cal C}}_{1}$ have Choi operators
$\widehat{C}_{0},\widehat{C}_{1}$, respectively. It follows

$(1+\widehat{\eta})\operatorname{Tr}[\widehat{C}_{0}\Omega]-\widehat{\eta}\operatorname{Tr}[\widehat{C}_{1}\Omega]=1.$
(S71)

Notice that $\widehat{\eta}\geq 0$ and
$\operatorname{Tr}[\widehat{C}_{1}\Omega]\geq 0$ will yield
$\operatorname{Tr}[\widehat{C}_{0}\Omega]\geq 1/(1+\widehat{\eta})$. Since
$\widehat{{\cal C}}_{0}$ is a quantum comb, it is a feasible solution to SDP
(22) which gives $F_{\rm opt}(d,n)\geq 1/(1+\widehat{\eta})$. Therefore, we
have $2\widehat{\eta}+1\geq 2/F_{\rm opt}(d,n)-1$ and $\nu(d,n)\geq 2/F_{\rm
opt}(d,n)-1$. Second, we shall prove that

$\nu(d,n)\leq\frac{2}{F_{\rm opt}(d,n)}-1.$ (S72)

Before that, we demonstrate that there always exists a quantum comb ${\cal
C}^{\prime}$ with a Choi operator $C^{\prime}$ such that
$\operatorname{Tr}[C^{\prime}\Omega]=0$ as follows. Consider a Choi operator
$C^{\prime}=V*W_{1}*W_{2}*\cdots*W_{n-1}$ where $V$ is as defined in Eq. (S64)

$\displaystyle V=$
$\displaystyle-\frac{1}{d^{2}-1}|I\rangle\rangle\langle\langle I|^{T_{{\cal
O}_{1}}}_{{\cal P}{\cal O}_{1}}\otimes|I\rangle\rangle\langle\langle
I|^{T_{{\cal F}_{1}}}_{{\cal I}_{1}{\cal F}_{1}}-\frac{1}{d^{2}-1}I_{{\cal
P}{\cal O}_{1}}\otimes|I\rangle\rangle\langle\langle I|^{T_{{\cal
F}_{1}}}_{{\cal I}_{1}{\cal F}_{1}}$ (S73)
$\displaystyle+\frac{1}{d^{2}-1}|I\rangle\rangle\langle\langle I|^{T_{{\cal
O}_{1}}}_{{\cal P}{\cal O}_{1}}\otimes I_{{\cal I}_{1}{\cal
F}_{1}}+\frac{1}{d^{2}-1}I_{{\cal P}{\cal I}_{1}{\cal O}_{1}{\cal F}_{1}},$

and $W_{k}=I_{{\cal F}_{k}{\cal O}_{k+1}}\otimes\Phi_{{\cal I}_{k+1}{\cal
F}_{k+1}},{\cal F}_{n}\mathrel{\mathop{\mathchar 58\relax}}={\cal F}$. We note
that $V$ is semidefinite positive and satisfies the linear constraints of a
quantum comb, and $W_{k}$ corresponds to a 1-slot comb which outputs an
identity channel for any input channel. It is straightforward to check that
for any input unitary channel ${\cal U}_{d}$

$\displaystyle\operatorname{Tr}\left[|U^{\dagger}\rangle\rangle\langle\langle
U^{\dagger}|\cdot(C^{\prime}*|U\rangle\rangle\langle\langle U|^{\otimes
n})\right]$
$\displaystyle=\operatorname{Tr}\Big{[}|U^{\dagger}\rangle\rangle\langle\langle
U^{\dagger}|\Big{(}V*|U\rangle\rangle\langle\langle
U|*\overbrace{|I\rangle\rangle\langle\langle
I|*\cdots*|I\rangle\rangle\langle\langle I|}^{n-1}\Big{)}\Big{]}$ (S74)
$\displaystyle=\operatorname{Tr}\Big{[}|U^{\dagger}\rangle\rangle\langle\langle
U^{\dagger}|(V*|U\rangle\rangle\langle\langle U|)\Big{]}$
$\displaystyle=0,\quad\forall U\in SU(d),$

which indicates $\operatorname{Tr}[C^{\prime}\Omega]=0$. Now suppose comb
$\widehat{{\cal C}}$ is a feasible solution to SDP (22) with a Choi operator
$\widehat{C}$. We denote $f=\operatorname{Tr}[\widehat{C}\Omega]$ and
construct a virtual comb $\widetilde{{\cal C}}^{\prime}$ with a Choi operator

$\widetilde{C}^{\prime}=\frac{1}{f}\widehat{C}-\frac{1-f}{f}C^{\prime}$ (S75)

We can see $\operatorname{Tr}[\widetilde{C}^{\prime}\Omega]=1$ and
$\widetilde{{\cal C}}^{\prime}$ is a feasible solution to SDP (19). Therefore,
we have $\nu(d,n)\leq 1/f+(1-f)/f=2/f-1$ and $\nu(d,n)\leq 2/F_{\rm
opt}(d,n)-1$. Combining Eq. (S70) and Eq. (S72), we conclude that

$\nu(d,n)=\frac{2}{F_{\rm opt}(d,n)}-1.$ (S76)

$\sqcap$$\sqcup$