# Information recoverability of noisy quantum states

Xuanqiang Zhao  Institute for Quantum Computing, Baidu Research, Beijing
100193, China  Benchi Zhao  Institute for Quantum Computing, Baidu Research,
Beijing 100193, China  Zihan Xia  Institute for Quantum Computing, Baidu
Research, Beijing 100193, China  Xin Wang<EMAIL_ADDRESS>Institute for
Quantum Computing, Baidu Research, Beijing 100193, China

###### Abstract

Extracting classical information from quantum systems is an essential step of
many quantum algorithms. However, this information could be corrupted as the
systems are prone to quantum noises, and its distortion under quantum dynamics
has not been adequately investigated. In this work, we introduce a systematic
framework to study how well we can retrieve information from noisy quantum
states. Given a noisy quantum channel, we fully characterize the range of
recoverable classical information. This condition allows a natural measure
quantifying the information recoverability of a channel. Moreover, we resolve
the minimum information retrieving cost, which, along with the corresponding
optimal protocol, is efficiently computable by semidefinite programming. As
applications, we establish the limits on the information retrieving cost for
practical quantum noises and employ the corresponding protocols to mitigate
errors in ground state energy estimation.

_Introduction.—_ In quantum mechanics, the dynamics of a closed quantum system
is described as a unitary evolution Griffiths and Schroeter (2018). However,
quantum systems are barely closed in practical as they unavoidably interacts
with the environment. Quantum channels, stemming from the unitary dynamics in
a larger Hilbert space, are considered as the proper mathematical formalism
depicting the evolution of general quantum systems Nielsen and Chuang (2010).
From the perspective of information processing, quantum channels represent the
quantum information manipulation processes, playing a key role in quantum
information and quantum computation Nielsen and Chuang (2010); Wilde (2017);
Watrous (2018); Bennett  _et al._ (2014); Wang and Wilde (2019); Smith and
Yard (2008); Wang  _et al._ (2019).

A central constituent of quantum computation is to extract classical
information from a quantum system. The expectation value of some chosen
observable, also known as shadow information, unravels many physical
properties of the quantum system, making estimating expectation values the
main goal of many quantum algorithms Nielsen and Chuang (2010); Cerezo  _et
al._ (2021), such as variational quantum eigensolver (VQE) Peruzzo  _et al._
(2014) and quantum approximate optimization algorithm (QAOA) Farhi and Harrow
(2016). The importance of expectation values has motivated the study of shadow
tomography and related problems Aaronson (2019); Aaronson and Rothblum (2019);
Huang  _et al._ (2020). However, inevitable noises modeled as quantum channels
can corrupt the shadow information as they undesirably change the state of the
quantum system, preventing us from estimating the expectation value
accurately.

It is natural to ask how a quantum channel ${\cal N}$ affects the information
stored in quantum states. The minimum fidelity Barnum  _et al._ (2000);
Bennett  _et al._ (1997); DiVincenzo  _et al._ (1998) of some initial state
$|\psi\rangle\\!\langle\psi|$ and the final state ${\cal
N}(|\psi\rangle\\!\langle\psi|)$ is the one we often use to answer this
question: $F_{\min}({\cal
N})\equiv\min_{|\psi\rangle}F(|\psi\rangle\\!\langle\psi|,{\cal
N}(|\psi\rangle\\!\langle\psi|))$. While this minimum fidelity may serve as a
proper measure for the preservation of quantum information, it is not
appropriate for quantifying how well a quantum channel preserves shadow
information encoded in a quantum state. Take the completely phase damping
channel ${\cal N}_{\rm PD}(\rho)=Z\rho Z$ as an example. While $F_{\min}({\cal
N}_{\rm PD})=0$, the expectation value of a diagonal observable (e.g.,
observable $Z$) is unaffected. Similarly, other fidelity-based measures such
as average fidelity and entanglement fidelity Schumacher (1996); Barnum  _et
al._ (2000) are not suitable to depict the shadow information preservation
either. Some other measures for information preservation are various channel
capacities, where each channel capacity quantifies a quantum channel’s utility
to transfer information for a certain purpose. For example, the classical
capacity Holevo (1973); Schumacher and Westmoreland (1997); Holevo (1998)
gives the highest rate at which classical information can be reliably
transmitted with an asymptotically vanishing error. However, these capacities
are derived in asymptotic settings with multiple uses of the channel, and thus
are not proper guides to practical tasks with finite quantum resources to some
extent. Naturally, the following key questions then arise:

  1. 1.

What is a proper way to quantify the level of shadow information preservation
or destruction by a quantum channel?

  2. 2.

How to quantify the cost of retrieving a certain piece of shadow information
given it is preserved?

To address these two questions in an operational way, we first introduce a
framework for retrieving shadow information from a noisy state. Both
practically relevant and theoretically interesting, this framework combines an
efficient way to manipulate quantum states and general quantum operations.
Note that similar protocols are employed in predicting properties of quantum
states Buscemi  _et al._ (2013); Huang  _et al._ (2020) and mitigating quantum
errors Temme  _et al._ (2017); Endo  _et al._ (2018); Takagi (2021); Jiang
_et al._ (2021); Piveteau  _et al._ (2021). In particular, we suppose that
multiple copies of a noisy state ${\cal N}(\rho)$ are available. For each copy
we apply a quantum channel randomly sampled from an ensemble of channels
$\\{{\cal D}_{j}\\}$ and then measure the observable of interest, as shown in
Fig. 1. We say that a quantum channel ${\cal N}$ preserves the classical
information inquired by an observable $O$ if we can recover this information,
that is: there exist a set of quantum channels $\\{{\cal D}_{j}\\}$ and a set
of real numbers $\\{c_{j}\\}$ such that

$\displaystyle\sum_{j}c_{j}\operatorname{Tr}[{\cal D}_{j}\circ{\cal
N}(\rho)O]=\operatorname{Tr}[\rho O].$ (1)

Within this framework, we give a necessary and sufficient condition for the
preservation of the desired shadow information in terms of a relation between
$O$ and ${\cal N}$ that should be satisfied. This condition motivates a
measure called shadow destructivity characterizing a quantum channel’s level
of destroying shadow information.

We also define a measure called retrieving cost to quantify the minimum cost
of recovering $\operatorname{Tr}[\rho O]$, which also quantifies how well the
channel preserves the shadow information queried by a specific observable.
This measure, along with the concrete retrieving protocol, is efficiently
computable via semidefinite programming Vandenberghe and Boyd (1996). We
analytically obtain the values of this measure along with the retrieving
protocols for generalized amplitude damping (GAD) channels and depolarizing
channels. Our retrieving costs set ultimate limits on the cost required for
shadow retrieving, and the corresponding protocols outperform existing
probabilistic error cancellation (PEC) methods Temme  _et al._ (2017); Endo
_et al._ (2018); Takagi (2021); Jiang  _et al._ (2021); Piveteau  _et al._
(2021). Specifically, we employ our method in tasks of estimating the ground
state energies of several molecules with VQE under the assumption that the
noise model of the entire circuit is known. The results show that the gap of
sampling overhead between our method and a conventional PEC method gets larger
as the size of the quantum system grows, implying potential applications of
our method in implementing near-term algorithms.

Figure 1: The framework for retrieving shadow information from noisy quantum
states. After independently applying channels ${\cal D}^{(i)}$ randomly
selected from an ensemble $\\{{\cal D}_{j}\\}$ to multiple copies of a noisy
state ${\cal N}(\rho)$, estimation of the desired information
$\operatorname{Tr}[\rho O]$ is obtained via making measurements with the
corresponding observable $O$ and post-processing the measurement results.

_Preliminaries.—_ Before introducing our results, we set the notation and
define several quantities that will be used throughout this paper. We use
symbols such as $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$ to denote finite-
dimensional Hilbert spaces associated with quantum systems $A$ and $B$,
respectively. We use $d_{A}$ to denote the dimension of the system $A$. The
set of linear operators acting on $A$ is denoted by ${\cal L}_{A}$, and the
set of Hermitian operators acting on $A$ is denoted by ${\cal L}^{\rm H}_{A}$.

In this work, we focus on linear maps having the same input and output
dimension. A linear map ${\cal N}_{A\to A^{\prime}}$ transforms linear
operators in ${\cal L}_{A}$ to linear operators in ${\cal L}_{A^{\prime}}$,
where ${\cal H}_{A^{\prime}}$ is isomorphic to ${\cal H}_{A}$. We call a
linear map ${\cal N}_{A\to A^{\prime}}$ a quantum channel if it is completely
positive and trace-preserving (CPTP). By saying ${\cal N}$ is completely
positive (CP), we mean ${\operatorname{id}}_{R}\otimes{\cal N}$ is a positive
map with a reference system $R$ of arbitrary dimension. By saying ${\cal N}$
is trace-preserving (TP), we mean $\operatorname{Tr}[{\cal
N}(X)]=\operatorname{Tr}[X]$ for all $X\in{\cal L}_{A}$. A linear map ${\cal
N}$ is called Hermitian-preserving (HP) if ${\cal N}(X)\in{\cal L}^{\rm
H}_{A^{\prime}}$ for all $X\in{\cal L}^{\rm H}_{A}$. For any linear map ${\cal
N}_{A\to A^{\prime}}$, we will frequently use its Choi-Jamiołkowski matrix,
which is defined as $J_{{\cal N}}\equiv\sum_{i,j=0}^{d_{A}-1}|i\rangle\langle
j|\otimes{\cal N}_{A\to A^{\prime}}(|i\rangle\langle j|)$, where
$\\{|i\rangle\\}_{i=0}^{d_{A}-1}$ is an orthonormal basis in ${\cal H}_{A}$.

_Necessary and sufficient condition for shadow information preservation.—_ We
study the preservation of shadow information by considering an operational
task: recovering the expectation value $\operatorname{Tr}[\rho O]$ of an
observable $O$ from multiple copies of a corrupted state ${\cal N}(\rho)$,
where ${\cal N}$ is the noisy channel of interest and $\rho$ is an unknown
state. A usual way Jiang  _et al._ (2021) is to simulate a Hermitian-
preserving and trace-preserving (HPTP) map ${\cal D}$, which we call a
retriever in this work, such that ${\cal D}\circ{\cal N}={\operatorname{id}}$,
where ${\operatorname{id}}$ is the identity map. While this approach is
sufficient for recovering the target information, its requirement on the
retriever ${\cal D}$ is generally not necessary as we are only concerned with
the expectation value of a specific observable. Hence, the only necessary
requirement for a retriever ${\cal D}$ is

$\displaystyle\operatorname{Tr}[{\cal D}\circ{\cal
N}(\rho)O]=\operatorname{Tr}[\rho O]$ (2)

for any state $\rho$ and a fixed observable $O$. Our framework extends the set
of potential retrievers from HPTP maps to Hermitian-preserving and trace-
scaling (HPTS) maps for that HPTS maps are physically simulatable in the way
prescribed by Eq. (1), as shown in Lemma 3. We say a linear map ${\cal N}$ is
trace-scaling (TS) if $\operatorname{Tr}_{A^{\prime}}[J_{\cal N}]=pI_{A}$ for
some real number $p$, and HPTP maps are special cases of HPTS maps when $p=1$.

Figure 2: Illustration of Theorem 2. Suppose a state $\rho$ is corrupted by a
channel ${\cal N}$. Then, a piece of shadow information is recoverable with
the help of a retriever ${\cal D}$ if and only if it is queried by an
observable lying in the brown area, which represents the observable space
evolved under the adjoint of ${\cal N}$. This necessary and sufficient
condition for shadow preservation connects channel corrupting state in
Schrödinger picture with the evolving of the observable space in Heisenberg
picture.

Here, given a quantum channel ${\cal N}$ and an observable $O$, we give the
only condition that a retriever ${\cal D}$ needs to satisfy so that Eq. (2)
holds for an arbitrary state:

$\displaystyle{\cal N}^{\dagger}\circ{\cal D}^{\dagger}(O)=O,$ (3)

where ${\cal N}^{\dagger}$ and ${\cal D}^{\dagger}$ are the adjoint maps of
${\cal N}$ and ${\cal D}$, respectively. This condition is a direct
implication of Lemma 1.

###### Lemma 1

Given an observable $O$, an HP map ${\cal M}$ satisfies
$\operatorname{Tr}[{\cal M}(\rho)O]=\operatorname{Tr}[\rho O]$ for any state
$\rho$ if and only if ${\cal M}^{\dagger}(O)=O$.

Now Lemma 1 sets the requirement that we should refer to when searching for a
retriever. We say a quantum channel ${\cal N}$ preserves the shadow
information queried by an observable $O$ if there exists a retriever ${\cal
D}$ satisfying Eq. (3). It is crucial to ask when does such a retriever exist,
that is: for what observables does the channel preserve their corresponding
shadow information? In Theorem 2, we establish a necessary and sufficient
condition for the preservation of the shadow information by introducing the
adjoint image of ${\cal L}^{\rm H}_{A^{\prime}}$ under the channel ${\cal
N}_{A\to A^{\prime}}$, which we define to be the image of ${\cal L}^{\rm
H}_{A^{\prime}}$ under ${\cal N}^{\dagger}_{A^{\prime}\to A}$ and is denoted
by ${\cal N}^{\dagger}({\cal L}^{\rm H}_{A^{\prime}})$. This theorem manifests
the ultimate limitation of a quantum channel on preserving the shadow
information queried by some observables.

###### Theorem 2

(Necessary and sufficient condition for information preservation). Given a
quantum channel ${\cal N}_{A\to A^{\prime}}$ and an observable $O$, there
exists an HPTS map ${\cal D}$ such that ${\cal M}\equiv{\cal D}\circ{\cal N}$
satisfies ${\cal M}^{\dagger}(O)=O$ if and only if $O\in{\cal
N}^{\dagger}({\cal L}^{\rm H}_{A^{\prime}})$.

This theorem, as illustrated in Fig. 2, implies that the channel ${\cal N}$
preserves the shadow information or, equivalently, the shadow information is
retrievable, if and only if the corresponding observable $O$ is in the adjoint
image of ${\cal L}^{\rm H}_{A^{\prime}}$ under ${\cal N}$. A physical
interpretation of this theorem can be given within the Heisenberg picture, in
which quantum states are constant while observables evolve with time Wilde
(2017). From this perspective, Theorem 2 is saying that
$\operatorname{Tr}[\rho O]$ can be recovered if and only if there is an
observable $Q$ evolving into $O$ under the backward dynamics prescribed by the
given ${\cal N}$.

Following Theorem 2, for a quantum channel ${\cal N}(\cdot)=\sum_{k}E_{k}\cdot
E_{k}^{\dagger}$, we define the dimension of ${\cal N}^{\dagger}({\cal L}^{\rm
H}_{A^{\prime}})$ as the channel ${\cal N}$’s effective shadow dimension
$d_{\rm s}({\cal N})$ that quantifies how much shadow information is preserved
by ${\cal N}$. The effective shadow dimension $d_{\rm s}({\cal N})$ is
efficiently computable by observing that the dimension of ${\cal
N}^{\dagger}({\cal L}^{\rm H}_{A^{\prime}})$ equals the matrix rank of
$M_{\cal N}\mathrel{\mathop{\mathchar 58\relax}}=\sum_{k}E_{k}\otimes E_{k}$,
as shown in the Supplemental Material.

Based on the effective shadow dimension, we define a measure called _shadow
destructivity_ :

$\displaystyle\zeta({\cal N})\equiv\log\frac{d^{2}}{d_{\rm s}({\cal N})},$ (4)

where $d$ is the dimension of the Hilbert space that the input linear
operators in ${\cal L}_{A}$ act on. The shadow destructivity quantifies a
quantum channel’s capacity to destruct shadow information and has some
meaningful properties, such as faithfulness, additivity, and data processing
inequality. Details of these properties can be found in the Supplemental
Material. Notably, the faithfulness of shadow destructivity offers a simple
invertibility criterion for quantum channels: $\zeta({\cal N})=0$ if and only
if ${\cal N}$ is invertible. This criterion can be easily checked with the
channels’ Kraus operators.

_Quantifying the cost of retrieving shadow information.—_ By saying that a
quantum channel preserves some shadow information, we mean this information
can be retrieved after a state is corrupted by this channel. Though the
effective shadow dimension of a quantum channel captures its overall
capability of preserving shadow information, a piece of shadow information
being preserved does not mean that retrieving it is cost-free, and different
pieces of information can have different retrieving cost. In the following
part, we derive a measure called retrieving cost from the number of copies of
the corrupted state required to estimate the desired shadow information within
an acceptable accuracy.

Note that the retriever ${\cal D}$ is an HPTS map but not necessarily CPTP,
i.e., not necessarily a quantum channel. While such a map ${\cal D}$ is not
physically implementable, we can simulate its action by decomposing it as a
linear combination of CPTP maps: ${\cal D}=\sum_{j}c_{j}{\cal D}_{j}$, and
utilizing Eq. (1). Indeed, as Lemma 3 implies, a linear map is physically
simulatable in this framework if and only if it is HPTS.

###### Lemma 3

A linear map ${\cal D}$ is HPTS if and only if it can be written as a linear
combination of quantum channels $\\{{\cal D}_{j}\\}$ with real numbers
$\\{c_{j}\\}$:

$\displaystyle{\cal D}=\sum_{j}c_{j}{\cal D}_{j}.$ (5)

Furthermore, for any HPTS map ${\cal D}$, there exist two quantum channels
${\cal D}_{1},{\cal D}_{2}$ with real numbers $c_{1},c_{2}$ such that

${\cal D}=c_{1}{\cal D}_{1}+c_{2}{\cal D}_{2}.$ (6)

Now let ${\cal D}$ be an HPTS map whose decomposition is $\sum_{j}c_{j}{\cal
D}_{j}$. With this decomposition, we can simulate its action on the
expectation value by the probabilistic sampling method prescribed by Eq. (1).
Specifically, in the $s$-th round of total S times of sampling, we first
sample a quantum channel ${\cal D}^{(s)}$ from $\\{{\cal D}_{j}\\}$ with
probabilities $\\{|c_{j}|/\gamma\\}$, where $\gamma=\sum_{j}|c_{j}|$, and
apply it to a copy of the corrupted state to obtain ${\cal D}^{(s)}\circ{\cal
N}(\rho)$. Then, we measure this state in the eigenbasis
$\\{|\psi_{j}\rangle\\!\langle\psi_{j}|\\}_{j}$ of the given observable
$O=\sum_{j}o_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|$, where $o_{j}\in[-1,1]$,
and obtain the measurement value $o^{(s)}$. After $S$ rounds of sampling, we
attain an estimation for the expectation value $\operatorname{Tr}[\rho O]$ as

$\displaystyle\xi=\frac{\gamma}{S}\sum_{s=1}^{S}{\rm sgn}(c^{(s)})o^{(s)},$
(7)

where ${\rm sgn}$ is the sign function. By the Hoeffding’s inequality
Hoeffding (1994), the number of rounds required to obtain the estimation
within an error $\varepsilon$ with a probability no less than $1-\delta$ is

$S=2\gamma^{2}\log(2/\delta)/\varepsilon^{2}.$ (8)

It can be seen that the required number of copies $S$ of the corrupted state
is directly related to $\gamma$, the sum of absolute values of all $c_{j}$.
Hence, $\gamma$ can be used to characterize the cost of simulating the HPTS
map ${\cal D}$. It is desirable to find a decomposition of ${\cal D}$ making
$\gamma$ as small as possible, and we denote the minimum possible value of
$\gamma$ as $\gamma_{\min}({\cal D})$. In Ref. Jiang  _et al._ (2021), the
authors define the logarithm of $\gamma_{\min}({\cal D})$ as the physical
implementability of an HPTP map ${\cal D}$.

Naturally, given a quantum channel ${\cal N}$, we define the _retrieving cost_
with respect to an observable $O$ to be

$\displaystyle\gamma_{O}({\cal N})=\min\\{\gamma_{\min}({\cal D})|{\cal
D}\text{ is HPTS},~{}{\cal N}^{\dagger}\circ{\cal D}^{\dagger}(O)=O\\},$ (9)

which is the $\gamma_{\min}({\cal D})$ minimized over all ${\cal D}$ that can
retrieve the shadow information queried by $O$ from the noisy channel ${\cal
N}$.

Notably, Lemma 3 states that any HPTS map can be decomposed as a linear
combination of two quantum channels (Eq. (6)), and we show in the Supplemental
Material that the minimum retrieving cost can be achieved by such a
decomposition. This is true because all channels with non-negative
coefficients can be grouped into a single channel with a non-negative
coefficient, and we can do the same thing for all channels with negative
coefficients. The existence of such an optimal decomposition with two CPTP
maps leads to an efficient way to compute this measure through a semidefinite
program (SDP) in terms of linear maps’ Choi-Jamiołkowski matrices:

$\displaystyle\gamma_{O}({\cal N})=\min$ $\displaystyle\;c_{1}+c_{2}$ (10a)
s.t. $\displaystyle\;J_{{\cal D}_{1}}\geq 0,\;J_{{\cal D}_{2}}\geq 0$ (10b)
$\displaystyle\;\operatorname{Tr}_{A^{\prime}_{o}}[J_{{\cal
D}_{1}}]=c_{1}I_{A^{\prime}_{i}}$ (10c)
$\displaystyle\;\operatorname{Tr}_{A^{\prime}_{o}}[J_{{\cal
D}_{2}}]=c_{2}I_{A^{\prime}_{i}}$ (10d) $\displaystyle\;J_{\cal D}\equiv
J_{{\cal D}_{1}}-J_{{\cal D}_{2}}$ (10e) $\displaystyle\;J_{\cal
M}\equiv\operatorname{Tr}_{A_{o}A^{\prime}_{i}}[(J_{{\cal N}}^{T}\otimes
I)(J_{I}\otimes J_{\cal D})]$ (10f)
$\displaystyle\;\operatorname{Tr}_{A^{\prime}_{o}}[(I_{A_{i}}\otimes
O_{A^{\prime}_{o}}^{T})J_{{\cal M}}^{T}]=O_{A_{i}}.$ (10g)

Eq. (10b) corresponds to the condition that ${\cal D}_{1}$ and ${\cal D}_{2}$
are CP, and Eq. (10c) and Eq. (10d) require them to be TP. Eq. (10g)
corresponds to the minimum requirement for a valid retriever as given in Eq.
(3). Systems of Choi-Jamiołkowski matrices appearing in this SDP are labelled
in Supplemental Material.

Note that we can establish an approximate version of Eq. (10) by relaxing the
requirement in Eq. (10g) such that
$\operatorname{Tr}_{A^{\prime}}[(I_{A}\otimes O_{A^{\prime}}^{T})J_{{\cal
M}}^{T}]$ is close to $O$ within a certain tolerance. This relaxation provides
a remedy to cases where a perfect retriever does not exist as well as a trade-
off between the retrieving cost and the estimation precision.

_Case study and applications in error mitigation.—_ To intuitively understand
effective shadow dimension and shadow destructivity, we study two non-
invertible channels as examples: ${\cal
N}_{1}(\cdot)=\frac{1}{2}I(\cdot)I+\frac{1}{2}X(\cdot)X$ and ${\cal
N}_{2}(\cdot)=\frac{1}{2}I(\cdot)I+\frac{1}{4}X(\cdot)X+\frac{1}{4}Y(\cdot)Y$.
For a quantum state $\rho=\begin{bmatrix}a&b+ci\\\ b-ci&1-a\end{bmatrix}$,
where $a,b,c$ are real numbers and $i\equiv\sqrt{-1}$, it can be easily
verified that ${\cal N}_{1}(\rho)=\begin{bmatrix}1/2&b\\\ b&1/2\end{bmatrix}$
and ${\cal N}_{2}(\rho)=\begin{bmatrix}1/2&(b+ci)/2\\\
(b-ci)/2&1/2\end{bmatrix}$. While both channels are non-invertible, it is
intuitive to see that channel ${\cal N}_{2}$ preserves more information than
channel ${\cal N}_{1}$ since the imaginary part of off-diagonal elements is
preserved. This intuition coincides with the effective shadow dimension of
these two channels, $d_{\rm s}({\cal N}_{2})=3>d_{\rm s}({\cal N}_{1})=2$,
which implies that ${\cal N}_{2}$ preserves one more shadow dimension than
${\cal N}_{1}$. The shadow destructivity of these channels, $\zeta({\cal
N}_{1})=\log(4/2)=1$ and $\zeta({\cal N}_{2})=\log(4/3)\approx 0.415$,
naturally has similar implications.

Now recall the retrieving cost, which quantifies the resources required to
recover a certain piece of shadow information. The corresponding optimal
retrieving protocol can be considered as a method to mitigate errors, endowing
the retrieving cost with a practical meaning in quantum error mitigation Temme
_et al._ (2017); Endo  _et al._ (2018); Takagi (2021); Jiang  _et al._ (2021);
Piveteau  _et al._ (2021); Bravyi  _et al._ (2020); Maciejewski  _et al._
(2020); Czarnik  _et al._ (2020); McClean  _et al._ (2020); Cai (2021a);
Bultrini  _et al._ (2021); Cai (2021b); Czarnik  _et al._ (2021); Piveteau
_et al._ (2021); Lostaglio and Ciani (2021); Takagi  _et al._ (2021); Koczor
(2021); Endo  _et al._ (2021); Wang  _et al._ (2021); Suzuki  _et al._ (2020).
In the following, we compare the retrieving cost between our proposed protocol
$\gamma_{\rm pro}$ and the conventional PEC method $\gamma_{\rm con}$ (see,
e.g., Temme  _et al._ (2017); Endo  _et al._ (2018); Takagi (2021); Jiang  _et
al._ (2021); Piveteau  _et al._ (2021)), with the assumption that the full
knowledge of the noise is accessible and the noise is modeled as a channel
just before the measurement.

As a concrete example, consider retrieving shadow information
$\operatorname{Tr}[\rho X]$ from a state $\rho$ corrupted by a GAD channel
Chirolli and Burkard (2008), where $X$ is the Pauli $X$ operator. The cost of
our method is $\gamma_{\rm pro}=\frac{1}{\sqrt{1-\epsilon}}$, while the cost
of the conventional method is $\gamma_{\rm
con}=\frac{|1-2p|\epsilon+1}{1-\epsilon}$ Jiang  _et al._ (2021), where
$\epsilon$ is the damping factor and $p$ is the temperature indicator
associated with the GAD channel. It is obvious to see that $\gamma_{\rm
pro}<\gamma_{\rm con}$ for any $0<\epsilon<1$, as shown in Fig. 3. Details of
the retrieving protocol can be found in Supplemental Material.

Figure 3: Comparison of the retrieving cost between our proposed protocol and
conventional PEC protocol in estimating expectation value
$\operatorname{Tr}[\rho O]$ from noisy state ${\cal N}(\rho)$. The observable
is $O=X$, and ${\cal N}$ is the GAD channel with coefficients $p\in[0,0.5]$
and $\epsilon\in[0,0.9]$.

_Overheads of mitigating noise in VQE.—_ VQE Peruzzo  _et al._ (2014) is a
promising near-term algorithm for estimating the ground state energy of a
quantum system (whose Hamiltonian is $H$). It aims to minimize the cost
function
$E=\operatorname{Tr}[|\psi(\bm{\theta})\rangle\\!\langle\psi(\bm{\theta})|H]$
by tuning parameters $\bm{\theta}$ in a parameterized quantum circuit used to
prepare the ansatz state $|\psi(\bm{\theta})\rangle$. In practice, the
Hamiltonian $H$ is decomposed into a linear combination of tensor products of
Pauli tensors $\\{O_{j}\\}$, i.e., $H=\sum_{j}h_{j}O_{j}$, where each $h_{j}$
is a real coefficient. The core subroutine of VQE is estimating the
expectation value of each term $\operatorname{Tr}[\rho O_{j}]$.

Here, we use Eq. (8) to estimate the numbers of sampling rounds required by
VQE to estimate the ground state energies of given molecules when there is
depolarizing noise Nielsen and Chuang (2010) on each qubit. The comparison
between our protocol and the conventional protocol Jiang  _et al._ (2021) are
shown in Table 1. Note that the retrieving cost of our proposed method is
$\gamma_{\rm pro}=\frac{1}{1-\epsilon}$ (see Supplemental Material), while the
convention method is $\gamma_{\rm
con}=\frac{1+(1-2/d^{2})\epsilon}{1-\epsilon}$, where $\epsilon$ is the noise
level, and $d$ is the dimension of the system. It is clear that the number of
sampling rounds of our method is smaller than that of the conventional method.
The retrieving protocols for depolarizing channels (and general mixed Pauli
channels) are shown in the Supplemental Material.

| Molecule
---|---
| H2 | HF | CO2
Proposed | $1.24\times 10^{5}$ | $7.84\times 10^{10}$ | $1.28\times 10^{13}$
Conventional | $1.60\times 10^{5}$ | $1.79\times 10^{11}$ | $1.21\times 10^{14}$
Table 1: Sampling times for estimating the ground state energies of three
different molecules under the depolarizing noise with a noise level
$\epsilon=0.1$. The precision parameters in Eq. (8) are set to
$\varepsilon=\delta=0.01$. For estimating the sampling times, each coefficient
$h_{j}$ of a Hamiltonian $H=\sum_{j}h_{j}O_{j}$ is assumed to be
$\max\\{|h_{j}|\\}$, and the term where $O_{j}$ is the identity operator is
excluded.

_Concluding remarks.—_ In this work, we establish two measures from an
operational perspective to quantify a quantum channel’s influence on shadow
information encoded in quantum states, answering the questions posed at the
beginning of this paper. Our work delivers a systematic framework of
quantifying the information preservativity and destructivity of a quantum
channel. Meanwhile it establishes an optimal way of extracting noiseless
classical information from noisy states, which could be useful for near-term
quantum information processing tasks.

For future work, it would be interesting to see how the techniques presented
in this work can be combined with quantum error correction Gottesman (2005);
Lidar and Brun (2013); Terhal (2015) or quantum error mitigation Koczor
(2021); Cai (2021b); Endo  _et al._ (2021); Wang  _et al._ (2021); Suzuki  _et
al._ (2020). We also expect that our ideas could be further applied to near-
term quantum tasks or applications on noisy quantum devices Preskill (2018).
Back to the problem of recovering classical information of noisy quantum
states, another interesting direction is to consider the case with no prior
information of the noisy channel.

_Acknowledgements.—_ X. Z. and B. Z. contributed equally to this work. Part of
this work was done when X. Z., B. Z., and Z. X. were research interns at Baidu
Research. We would like to thank Runyao Duan and Kun Wang for helpful
suggestions.

## References

  * Griffiths and Schroeter (2018) D. J. Griffiths and D. F. Schroeter,  _Introduction to quantum mechanics_ (Cambridge university press, 2018).
  * Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang,  _Quantum computation and quantum information_ (Cambridge university press, 2010).
  * Wilde (2017) M. M. Wilde,  _Quantum Information Theory_ (Cambridge University Press, Cambridge, 2017).
  * Watrous (2018) J. Watrous,  _The Theory of Quantum Information_ (Cambridge University Press, 2018).
  * Bennett  _et al._ (2014) C. H. Bennett, I. Devetak, A. W. Harrow, P. W. Shor, and A. Winter, IEEE Transactions on Information Theory 60, 2926 (2014).
  * Wang and Wilde (2019) X. Wang and M. M. Wilde, Physical Review Research 1, 033169 (2019), arXiv:1907.06306 .
  * Smith and Yard (2008) G. Smith and J. Yard, Science 321, 1812 (2008).
  * Wang  _et al._ (2019) X. Wang, M. M. Wilde, and Y. Su, New Journal of Physics 21, 103002 (2019), arXiv:1903.04483 .
  * Cerezo  _et al._ (2021) M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Nature Reviews Physics (2021), 10.1038/s42254-021-00348-9, arXiv:2012.09265 .
  * Peruzzo  _et al._ (2014) A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, Nature Communications 5, 4213 (2014), arXiv:1304.3061 .
  * Farhi and Harrow (2016) E. Farhi and A. W. Harrow, arXiv preprint arXiv:1602.07674 (2016).
  * Aaronson (2019) S. Aaronson, SIAM Journal on Computing 49, STOC18 (2019).
  * Aaronson and Rothblum (2019) S. Aaronson and G. N. Rothblum, in  _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ (2019) pp. 322–333.
  * Huang  _et al._ (2020) H.-Y. Huang, R. Kueng, and J. Preskill, Nature Physics 16, 1050 (2020).
  * Barnum  _et al._ (2000) H. Barnum, E. Knill, and M. Nielsen, IEEE Transactions on Information Theory 46, 1317 (2000).
  * Bennett  _et al._ (1997) C. H. Bennett, D. P. DiVincenzo, and J. A. Smolin, Physical Review Letters 78, 3217 (1997).
  * DiVincenzo  _et al._ (1998) D. P. DiVincenzo, P. W. Shor, and J. A. Smolin, Physical Review A 57, 830 (1998), arXiv:9706061 [quant-ph] .
  * Schumacher (1996) B. Schumacher, Physical Review A 54, 2614 (1996).
  * Holevo (1973) A. S. Holevo, Problemy Peredachi Informatsii 9, 3 (1973).
  * Schumacher and Westmoreland (1997) B. Schumacher and M. D. Westmoreland, Physical Review A 56, 131 (1997).
  * Holevo (1998) A. S. Holevo, IEEE Transactions on Information Theory 44, 269 (1998).
  * Buscemi  _et al._ (2013) F. Buscemi, M. Dall’Arno, M. Ozawa, and V. Vedral, arXiv:1312.4240 (2013), arXiv:1312.4240 .
  * Temme  _et al._ (2017) K. Temme, S. Bravyi, and J. M. Gambetta, Physical Review Letters 119, 180509 (2017), arXiv:1612.02058 .
  * Endo  _et al._ (2018) S. Endo, S. C. Benjamin, and Y. Li, Physical Review X 8, 031027 (2018), arXiv:1712.09271 .
  * Takagi (2021) R. Takagi, Physical Review Research 3, 033178 (2021), arXiv:2006.12509 .
  * Jiang  _et al._ (2021) J. Jiang, K. Wang, and X. Wang, Quantum 5, 600 (2021).
  * Piveteau  _et al._ (2021) C. Piveteau, D. Sutter, and S. Woerner, arXiv preprint arXiv:2101.09290 (2021), arXiv:2101.09290 .
  * Vandenberghe and Boyd (1996) L. Vandenberghe and S. Boyd, SIAM review 38, 49 (1996).
  * Hoeffding (1994) W. Hoeffding, in  _The Collected Works of Wassily Hoeffding_ (Springer, 1994) pp. 409–426.
  * Bravyi  _et al._ (2020) S. Bravyi, S. Sheldon, A. Kandala, D. C. Mckay, and J. M. Gambetta, arXiv:2006.14044 (2020), arXiv:2006.14044 .
  * Maciejewski  _et al._ (2020) F. B. Maciejewski, Z. Zimborás, and M. Oszmaniec, Quantum 4, 257 (2020), arXiv:1907.08518 .
  * Czarnik  _et al._ (2020) P. Czarnik, A. Arrasmith, P. J. Coles, and L. Cincio, arXiv:2005.10189 (2020), arXiv:2005.10189 .
  * McClean  _et al._ (2020) J. R. McClean, Z. Jiang, N. C. Rubin, R. Babbush, and H. Neven, Nature Communications 11, 636 (2020), arXiv:1903.05786 .
  * Cai (2021a) Z. Cai, npj Quantum Information 7 (2021a), 10.1038/s41534-021-00404-3, arXiv:2007.01265 .
  * Bultrini  _et al._ (2021) D. Bultrini, M. H. Gordon, P. Czarnik, A. Arrasmith, P. J. Coles, and L. Cincio, arXiv preprint arXiv:2107.13470 , 1 (2021), arXiv:2107.13470 .
  * Cai (2021b) Z. Cai, arXiv preprint arXiv:2110.05389 , 1 (2021b), arXiv:2110.05389 .
  * Czarnik  _et al._ (2021) P. Czarnik, A. Arrasmith, L. Cincio, and P. J. Coles, arXiv preprint arXiv:2102.06056 (2021), arXiv:2102.06056 .
  * Lostaglio and Ciani (2021) M. Lostaglio and A. Ciani, Physical Review Letters 127, 200506 (2021), arXiv:2103.07526 .
  * Takagi  _et al._ (2021) R. Takagi, S. Endo, S. Minagawa, and M. Gu, arXiv preprint arXiv:2109.04457 , 1 (2021), arXiv:2109.04457 .
  * Koczor (2021) B. Koczor, Physical Review X 11, 031057 (2021), arXiv:2011.05942 .
  * Endo  _et al._ (2021) S. Endo, Z. Cai, S. C. Benjamin, and X. Yuan, Journal of the Physical Society of Japan 90, 032001 (2021), arXiv:2011.01382 .
  * Wang  _et al._ (2021) K. Wang, Y.-A. Chen, and X. Wang, arXiv:2111.00691 (2021), arXiv:2111.00691 .
  * Suzuki  _et al._ (2020) Y. Suzuki, S. Endo, K. Fujii, and Y. Tokunaga, arXiv preprint arXiv:2010.03887 , 1 (2020), arXiv:2010.03887 .
  * Chirolli and Burkard (2008) L. Chirolli and G. Burkard, Advances in Physics 57, 225 (2008), arXiv:0809.4716 .
  * Gottesman (2005) D. Gottesman, arXiv:quant-ph/0507174 (2005), arXiv:0507174 [quant-ph] .
  * Lidar and Brun (2013) D. A. Lidar and T. A. Brun,  _Quantum error correction_ (Cambridge university press, 2013).
  * Terhal (2015) B. M. Terhal, Reviews of Modern Physics 87, 307 (2015), arXiv:arXiv:1302.3428v1 .
  * Preskill (2018) J. Preskill, Quantum 2, 79 (2018), arXiv:1801.00862 .
  * Khatri and Wilde (2020) S. Khatri and M. M. Wilde, arXiv preprint arXiv:2011.04672 (2020).
  * Axler (2015) S. Axler,  _Linear algebra done right_ , Vol. 2 (Springer, 2015).
  * Laub (2005) A. J. Laub,  _Matrix Analysis for Scientists and Engineers_ , Vol. 91 (SIAM, 2005).

Supplemental Material

##  I Proof of Lemma 1

###### Lemma 1

Given an observable $O$, an HP map ${\cal M}$ satisfies
$\operatorname{Tr}[{\cal M}(\rho)O]=\operatorname{Tr}[\rho O]$ for any state
$\rho$ if and only if ${\cal M}^{\dagger}(O)=O$.

###### Proof.

First, we assume that ${\cal M}^{\dagger}(O)=O$ is true. For ${\cal M}$ being
HP, its adjoint map ${\cal M}^{\dagger}$ is also HP (see Remark 1). Hence,
$\operatorname{Tr}[{\cal M}(\rho)O]=\operatorname{Tr}[\rho({\cal
M}^{\dagger}(O^{\dagger}))^{\dagger}]=\operatorname{Tr}[\rho{\cal
M}^{\dagger}(O)]$ for both $O$ and ${\cal M}^{\dagger}(O)$ being Hermitian.
Then, with our assumption, we have $\operatorname{Tr}[{\cal
M}(\rho)O]=\operatorname{Tr}[\rho{\cal M}^{\dagger}(O)]=\operatorname{Tr}[\rho
O]$.

For the other direction, given $\operatorname{Tr}[{\cal
M}(\rho)O]=\operatorname{Tr}[\rho O]$ for all states $\rho$, we immediately
have $\operatorname{Tr}[\rho{\cal M}^{\dagger}(O)]=\operatorname{Tr}[\rho O]$.
Suppose, for the sake of contradiction, that ${\cal M}^{\dagger}(O)\neq O$. If
we define $\Delta O={\cal M}^{\dagger}(O)-O$, then
$\operatorname{Tr}[\rho\Delta O]=0$ for all $\rho$. However, this implies that
$\Delta O=0$ since otherwise we can choose a $\sigma$ from the nonzero
eigenspace of $\Delta O$ so that $\operatorname{Tr}[\sigma\Delta O]\neq 0$. As
$\Delta O=0$ contradicts with the assumption that ${\cal M}^{\dagger}(O)\neq
O$, we conclude that $\operatorname{Tr}[\rho{\cal
M}^{\dagger}(O)]=\operatorname{Tr}[\rho O]$ holds for all $\rho$ only if
${\cal M}^{\dagger}(O)=O$.  $\sqcap$$\sqcup$

Remark 1 A linear map ${\cal N}$ is Hermitian-preserving (HP) if and only if
$J_{\cal N}$ is Hermitian. The adjoint of an HP map ${\cal N}$ is also HP.
This can be seen by checking the Hermiticity of its Choi matrix: $J_{{\cal
N}^{\dagger}}^{\dagger}=(J_{\cal N}^{T})^{\dagger}=J_{\cal N}^{T}=J_{{\cal
N}^{\dagger}}$ for $J_{\cal N}$ being Hermitian.

##  II Proof of Theorem 2

###### Lemma S1

The adjoint of a trace-scaling map is unit-scaling, and vice versa. By calling
a linear map ${\cal N}$ unit-scaling, we mean it scales the identity operator,
i.e., ${\cal N}(I)=pI$ for some real number $p$.

###### Proof.

Suppose that ${\cal N}$ is a trace-scaling map such that
$\operatorname{Tr}[{\cal N}(\cdot)]=p\operatorname{Tr}[\cdot]$ for some real
number $p$. If $p\neq 0$, we can define a TP map ${\cal M}\equiv{\cal N}/p$.
It is known that the adjoint of TP maps are unital Khatri and Wilde (2020),
which preserves the identity operator, and vice versa. Thus, ${\cal
M}^{\dagger}$, the adjoint of ${\cal M}$, is a unital map. Then, ${\cal
N}^{\dagger}=p{\cal M}^{\dagger}$, the adjoint of the trace-scaling map ${\cal
N}$, is a unit-scaling map. On the other hand, if $p=0$, then ${\cal
N}+{\operatorname{id}}$ is TP and thus ${\cal
N}^{\dagger}+{\operatorname{id}}$ is unital, making ${\cal N}^{\dagger}$ a
unit-scaling map. Hence, the adjoint of a trace-scaling map is unit-scaling.

Now suppose that ${\cal N}$ is a unit-scaling map such that ${\cal N}(I)=pI$
for some real number $p$. If $p\neq 0$, then ${\cal M}\equiv{\cal N}/p$ is a
unital map. Thus, we know its adjoint ${\cal M}^{\dagger}$ is TP, making
${\cal N}^{\dagger}=p{\cal M}^{\dagger}$ trace-scaling. On the other hand, if
$p=0$, then ${\cal N}+{\operatorname{id}}$ is unital and hence its adjoint
${\cal N}^{\dagger}+{\operatorname{id}}$ is TP, again making ${\cal
N}^{\dagger}$ trace-scaling. Hence, the adjoint of a unit-scaling map is
trace-scaling.  $\sqcap$$\sqcup$

###### Theorem 2

(Necessary and sufficient condition for information preservation). Given a
quantum channel ${\cal N}_{A\to A^{\prime}}$ and an observable $O$, there
exists an HPTS map ${\cal D}$ such that ${\cal M}\equiv{\cal D}\circ{\cal N}$
satisfies ${\cal M}^{\dagger}(O)=O$ if and only if $O\in{\cal
N}^{\dagger}({\cal L}^{\rm H}_{A^{\prime}})$.

###### Proof.

For the “only if” part, suppose such a map ${\cal D}$ exists for the given
channel ${\cal N}$ and non-zero observable $O$. Note that ${\cal D}^{\dagger}$
is also a Hermitian-preserving map since its Choi operator is Hermitian, as we
have noted in Remark 1. Then, we can let $Q={\cal D}^{\dagger}(O)$ so that
${\cal N}^{\dagger}(Q)={\cal N}^{\dagger}\circ{\cal D}^{\dagger}(O)={\cal
M}^{\dagger}(O)=O$. Hence, $O\in{\cal N}^{\dagger}({\cal L}^{\rm
H}_{A^{\prime}})$ if there exists an HPTS map such that ${\cal M}\equiv{\cal
D}\circ{\cal N}$ satisfies ${\cal M}^{\dagger}(O)=O$.

For the “if” part, suppose $O\in{\cal N}^{\dagger}({\cal L}^{\rm
H}_{A^{\prime}})$, which means that there exists a Hermitian operator $Q$ such
that ${\cal N}^{\dagger}(Q)=O$. It is sufficient to construct an HPTS map
${\cal D}$ satisfying ${\cal D}^{\dagger}(O)=Q$ so that ${\cal
N}^{\dagger}(Q)={\cal N}^{\dagger}\circ{\cal D}^{\dagger}(O)={\cal
M}^{\dagger}(O)=O$. By Lemma S1, it is equivalent to construct an Hermitian-
preserving and unit-scaling map ${\cal D}^{\dagger}$ satisfying the above
requirement. Denoting the rank of the observable $O$ by $k$, the trace of $O$
by $t$, and the dimension of the Hilbert space ${\cal H}_{A}$ by $d$, we
complete the proof by constructing an Hermitian-preserving and unit-scaling
map ${\cal D}^{\dagger}$ satisfying ${\cal D}^{\dagger}(O)=Q$ in each of the
following three cases.

  * •

Case 1: $k<d$ and $t\neq 0$. Let $P$ be the projection on the support of $O$
and $P^{\perp}$ be the projection on the kernel of $O$. We can construct a map
${\cal D}^{\dagger}$ such that

$\displaystyle{\cal D}^{\dagger}(\cdot)=\frac{Q}{t}\operatorname{Tr}[P\cdot
P]+\frac{k(I-Q)}{t(d-k)}\operatorname{Tr}[P^{\perp}\cdot P^{\perp}].$ (S1)

Clearly, ${\cal D}^{\dagger}$ is an HP map. Note that

$\displaystyle{\cal D}^{\dagger}(O)$
$\displaystyle=\frac{Q}{t}\operatorname{Tr}[POP]+\frac{k(I-Q)}{t(d-k)}\operatorname{Tr}[P^{\perp}OP^{\perp}]$
(S2) $\displaystyle=\frac{Q}{t}\operatorname{Tr}[O]$ (S3) $\displaystyle=Q$
(S4)

and

$\displaystyle{\cal D}^{\dagger}(I)$
$\displaystyle=\frac{Q}{t}\operatorname{Tr}[PIP]+\frac{k(I-Q)}{t(d-k)}\operatorname{Tr}[P^{\perp}IP^{\perp}]$
(S5)
$\displaystyle=\frac{Q}{t}\operatorname{Tr}[P]+\frac{k(I-Q)}{t(d-k)}\operatorname{Tr}[P^{\perp}]$
(S6) $\displaystyle=\frac{Q}{t}\cdot k+\frac{k(I-Q)}{t(d-k)}\cdot(d-k)$ (S7)
$\displaystyle=\frac{k}{t}Q+\frac{k}{t}(I-Q)$ (S8)
$\displaystyle=\frac{k}{t}I,$ (S9)

which implies that ${\cal D}^{\dagger}$ is also unit-scaling and ${\cal
D}^{\dagger}(O)=Q$.

  * •

Case 2: $k<d$ and $t=0$. Since $t=0$, $O$ has at least two distinct
eigenvalues. Let $O=\sum_{j}\lambda_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|$ be
the spectral decomposition of $O$, where each $\lambda_{j}\neq 0$. Define
$\tilde{O}\equiv O-\lambda_{0}|\psi_{0}\rangle\\!\langle\psi_{0}|$ and
$\tilde{Q}\equiv Q+\Delta Q$, where $\Delta Q$ is an Hermitian operator that
we will fix later. Let $\tilde{r}$ denote the rank of $\tilde{O}$ and
$\tilde{t}$ the trace of $\tilde{O}$. Following the definition of $\tilde{O}$,
we have $\tilde{k}=k-1$ and $\tilde{t}=-\lambda_{0}$. As $\tilde{k}<d$ and
$\tilde{t}\neq 0$, we can construct an Hermitian-preserving and unit-scaling
map

$\displaystyle{\cal D}^{\dagger}(\cdot)$
$\displaystyle=\frac{\tilde{Q}}{\tilde{t}}\operatorname{Tr}[\tilde{P}\cdot\tilde{P}]+\frac{\tilde{k}(I-\tilde{Q})}{\tilde{t}(d-\tilde{k})}\operatorname{Tr}[\tilde{P}^{\perp}\cdot\tilde{P}^{\perp}]$
(S10)
$\displaystyle=-\frac{\tilde{Q}}{\lambda_{0}}\operatorname{Tr}[\tilde{P}\cdot\tilde{P}]-\frac{(k-1)(I-\tilde{Q})}{\lambda_{0}(d-k+1)}\operatorname{Tr}[\tilde{P}^{\perp}\cdot\tilde{P}^{\perp}],$
(S11)

where $\tilde{P}$ denotes the projection on the support of $\tilde{O}$ and
$\tilde{P}^{\perp}$ be the projection on the kernel of $\tilde{O}$. By the
definition of $\tilde{O}$, we have
$\tilde{P}O\tilde{P}=\sum_{j>0}\lambda_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|$
and
$\tilde{P}^{\perp}O\tilde{P}^{\perp}=\lambda_{0}|\psi_{0}\rangle\\!\langle\psi_{0}|$,
and thus $\operatorname{Tr}[\tilde{P}O\tilde{P}]=-\lambda_{0}$ and
$\operatorname{Tr}[\tilde{P}^{\perp}O\tilde{P}^{\perp}]=\lambda_{0}$. Hence,

$\displaystyle{\cal D}^{\dagger}(O)$
$\displaystyle=-\frac{\tilde{Q}}{\lambda_{0}}\cdot(-\lambda_{0})-\frac{(k-1)(I-\tilde{Q})}{\lambda_{0}(d-k+1)}\cdot\lambda_{0}$
(S12) $\displaystyle=\tilde{Q}-\frac{k-1}{d-k+1}(I-\tilde{Q})$ (S13)
$\displaystyle=\frac{d}{d-k+1}\tilde{Q}-\frac{k-1}{d-k+1}I$ (S14)
$\displaystyle=\frac{d}{d-k+1}Q+\frac{d}{d-k+1}\Delta Q-\frac{k-1}{d-k+1}I.$
(S15)

Setting $\Delta Q=\frac{k-1}{d}(I-Q)$, we will have ${\cal D}^{\dagger}(O)=Q$.

  * •

Case 3: $k=d$. We first consider the case where $O=cI$ for some real
coefficient $c$. As $Q$ can be any Hermitian operator satisfying ${\cal
N}^{\dagger}(Q)=O$, and we know that ${\cal N}^{\dagger}$ is unital, we can
let $Q=O$ so that ${\cal D}^{\dagger}$ being the identity map
${\operatorname{id}}$ will complete the proof.

Now, consider the case where $O\neq cI$ for any real coefficient $c$, which
implies that $O$ must have at least two distinct eigenvalues. Let
$O=\sum_{j}\lambda_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|$ be the spectral
decomposition of $O$, where each $\lambda_{j}\neq 0$ and $\lambda_{0}$ is the
smallest eigenvalue. Then, we define $\tilde{O}\equiv O-\lambda_{0}I$ and
$\tilde{Q}\equiv Q+\Delta Q$, where $\Delta Q$ is an Hermitian operator that
we will fix later. Let $\tilde{r}$ denote the rank of $\tilde{O}$ and
$\tilde{t}$ the trace of $\tilde{O}$. Following the definition of $\tilde{O}$,
we have $\tilde{k}<d$ and $\tilde{t}=t-d\cdot\lambda_{0}>0$. Hence, by Case 1,
we can construct an Hermitian-preserving and unit-scaling map

$\displaystyle{\cal D}^{\dagger}(\cdot)$
$\displaystyle=\frac{\tilde{Q}}{\tilde{t}}\operatorname{Tr}[\tilde{P}\cdot\tilde{P}]+\frac{\tilde{k}(I-\tilde{Q})}{\tilde{t}(d-\tilde{k})}\operatorname{Tr}[\tilde{P}^{\perp}\cdot\tilde{P}^{\perp}]$
(S16)
$\displaystyle=\frac{\tilde{Q}}{t-d\cdot\lambda_{0}}\operatorname{Tr}[\tilde{P}\cdot\tilde{P}]+\frac{\tilde{k}(I-\tilde{Q})}{(t-d\cdot\lambda_{0})(d-\tilde{k})}\operatorname{Tr}[\tilde{P}^{\perp}\cdot\tilde{P}^{\perp}],$
(S17)

where $\tilde{P}$ denotes the projection on the support of $\tilde{O}$ and
$\tilde{P}^{\perp}$ be the projection on the kernel of $\tilde{O}$. By the
definition of $\tilde{O}$, we have
$\tilde{P}O\tilde{P}=\sum_{\lambda_{j}\neq\lambda_{0}}\lambda_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|$
and
$\tilde{P}^{\perp}O\tilde{P}^{\perp}=\sum_{\lambda_{j}=\lambda_{0}}\lambda_{j}|\psi_{j}\rangle\\!\langle\psi_{j}|$,
and thus $\operatorname{Tr}[\tilde{P}O\tilde{P}]=t-(d-\tilde{k})\lambda_{0}$
and
$\operatorname{Tr}[\tilde{P}^{\perp}O\tilde{P}^{\perp}]=(d-\tilde{k})\lambda_{0}$.
Hence,

$\displaystyle{\cal D}^{\dagger}(O)$
$\displaystyle=\frac{\tilde{Q}}{t-d\cdot\lambda_{0}}\cdot(t-(d-\tilde{k})\lambda_{0})+\frac{\tilde{k}(I-\tilde{Q})}{(t-d\cdot\lambda_{0})(d-\tilde{k})}\cdot(d-\tilde{k})\lambda_{0}$
(S18)
$\displaystyle=\frac{t-d\cdot\lambda_{0}+\tilde{k}\cdot\lambda_{0}}{t-d\cdot\lambda_{0}}\tilde{Q}+\frac{\tilde{k}\cdot\lambda_{0}}{t-d\cdot\lambda_{0}}(I-\tilde{Q})$
(S19)
$\displaystyle=\tilde{Q}+\frac{\tilde{k}\cdot\lambda_{0}}{t-d\cdot\lambda_{0}}I$
(S20) $\displaystyle=Q+\Delta
Q+\frac{\tilde{k}\cdot\lambda_{0}}{t-d\cdot\lambda_{0}}I.$ (S21)

Setting $\Delta Q=-\frac{\tilde{k}\cdot\lambda_{0}}{t-d\cdot\lambda_{0}}I$
results in ${\cal D}^{\dagger}(O)=Q$.

Since any observable $O$ can be categorized into one of the three cases above,
we conclude that given a quantum channel ${\cal N}$, if $O\in{\rm Range({\cal
N}^{\dagger})}$, then there exists an Hermitian-preserving and unit-scaling
map ${\cal D}^{\dagger}$ such that ${\cal D}^{\dagger}(O)=Q$ for some $Q$
satisfying ${\cal N}^{\dagger}(Q)=O$. As the adjoint of an Hermitian-
preserving and unit-scaling map is HPTS, we can always find an HPTS retriever
${\cal D}$ so that ${\cal N}^{\dagger}\circ{\cal D}^{\dagger}(O)={\cal
M}^{\dagger}(O)=O$ given $O\in{\cal N}^{\dagger}({\cal L}^{\rm
H}_{A^{\prime}})$.  $\sqcap$$\sqcup$

##  III Proof of Lemma 3

###### Lemma 3

A linear map ${\cal D}$ is HPTS if and only if it can be written as a linear
combination of quantum channels $\\{{\cal D}_{j}\\}$ with real numbers
$\\{c_{j}\\}$:

$\displaystyle{\cal D}=\sum_{j}c_{j}{\cal D}_{j}.$ (S22)

Furthermore, for any HPTS map ${\cal D}$, there exist two quantum channels
${\cal D}_{1},{\cal D}_{2}$ with real numbers $c_{1},c_{2}$ such that

${\cal D}=c_{1}{\cal D}_{1}+c_{2}{\cal D}_{2}.$ (S23)

###### Proof.

We first prove that a linear combination of quantum channels is HPTS. The
Choi-Jamiołkowski matrix of such a linear combination ${\cal
D}=\sum_{j}c_{j}{\cal D}_{j}$ is $J_{\cal D}=\sum_{j}c_{j}J_{{\cal D}_{j}}$,
where $J_{{\cal D}_{j}}\geq 0$ and $\operatorname{Tr}_{B}[J_{{\cal
D}_{j}}]=I_{A}$ for each $j$. As a linear combination of Hermitian operators
is also Hermitian, ${\cal D}$ is Hermitian-preserving. Also noting that
$\operatorname{Tr}_{B}[J_{\cal D}]=\sum_{j}c_{j}\operatorname{Tr}_{B}[J_{{\cal
D}_{j}}]=\sum_{j}c_{j}I_{A}$, we have $\operatorname{Tr}_{B}[J_{\cal
D}]=cI_{A}$, where $c=\sum_{j}c_{j}$. Hence, ${\cal D}$ is HPTS.

For the other direction, if a map ${\cal D}$ is HPTS, its Choi-Jamiołkowski
matrix $J_{\cal D}$ satisfies $J_{\cal D}$ being Hermitian and
$\operatorname{Tr}_{B}[J_{\cal D}]=cI_{A}$ for some real coefficient $c$. If
$c\neq 0$, ${\cal D}/c$ is an HPTP map and there exist two CPTP maps ${\cal
D}_{1},{\cal D}_{2}$ and two real numbers $c_{1}\geq 0,c_{2}\leq 0$ such that
${\cal D}/c=c_{1}{\cal D}_{1}+c_{2}{\cal D}_{2}$ Jiang  _et al._ (2021). Then
we have ${\cal D}=c\cdot c_{1}{\cal D}_{1}+c\cdot c_{2}{\cal D}_{2}$. On the
other hand, if $c=0$, ${\cal D}+{\operatorname{id}}$ is an HPTP map and there
still exist two CPTP maps ${\cal D}_{1},{\cal D}_{2}$ and two real numbers
$c_{1}\geq 0,c_{2}\leq 0$ such that ${\cal D}+{\operatorname{id}}=c_{1}{\cal
D}_{1}+c_{2}{\cal D}_{2}$. Hence, ${\cal D}$ can be written as ${\cal
D}=c_{1}{\cal D}_{1}+(c_{2}-1){\cal D}_{2}^{\prime}$, where ${\cal
D}_{2}^{\prime}=c_{2}{\cal D}_{2}/(c_{2}-1)-{\operatorname{id}}/(c_{2}-1)$ is
a quantum channel.  $\sqcap$$\sqcup$

##  IV Effective shadow dimension and shadow destructivity

###  IV.1 Computing effective shadow dimension

Recall that the effective shadow dimension of a quantum channel ${\cal
N}_{A\to A^{\prime}}$ is defined as

$\displaystyle d_{\rm s}\equiv\dim({\cal N}^{\dagger}({\cal L}^{\rm
H}_{A^{\prime}})).$ (S24)

The set of all Hermitian operators ${\cal L}^{\rm H}_{A^{\prime}}$ can be
viewed as a vector space over the field of real numbers, and the set of all
linear operators ${\cal L}_{A^{\prime}}$ is a vector space over the field of
complex numbers. Both vector spaces are with dimension $d_{A^{\prime}}^{2}$,
where $d_{A^{\prime}}=\dim({\cal H}_{A^{\prime}})$. Note that a basis for
${\cal L}^{\rm H}_{A^{\prime}}$ is also a basis for ${\cal L}_{A^{\prime}}$,
which implies that $\dim({\cal N}^{\dagger}({\cal L}^{\rm
H}_{A^{\prime}}))=\dim({\cal N}^{\dagger}({\cal L}_{A^{\prime}}))$. Then, by
the properties of the adjoint Axler (2015), the image of ${\cal N}^{\dagger}$
is the space orthogonal to the null space of ${\cal N}$. Hence, the dimension
of ${\cal N}^{\dagger}({\cal L}^{\rm H}_{A^{\prime}})$ is
$d_{A^{\prime}}^{2}-\dim({\rm null}({\cal N}))=\dim({\rm range}({\cal N}))$,
which equals the rank of a matrix of ${\cal N}$ as a linear map.

A matrix of ${\cal N}$ as a linear map can be obtained from the channel’s
Kraus representation. Given ${\cal N}(|i\rangle\\!\langle
j|)=\sum_{k}E_{k}|i\rangle\\!\langle j|E_{k}^{\dagger}$, we have ${\rm
vec}({\cal N}(|i\rangle\\!\langle j|))=\sum_{k}E_{k}|i\rangle\otimes
E_{k}|j\rangle=(\sum_{k}E_{k}\otimes E_{k})|ij\rangle$. Hence,
$\sum_{k}E_{k}\otimes E_{k}$ is a matrix representation of ${\cal N}$ as a
linear map, and the rank of this matrix gives $d_{\rm s}({\cal N})$.

###  IV.2 Properties of shadow destructivity

The shadow destructivity of a channel ${\cal N}$ is defined as

$\displaystyle\zeta({\cal N})\equiv\log\frac{d^{2}}{d_{\rm s}({\cal N})},$
(S25)

where $d$ is the dimension of the Hilbert space that the input linear
operators act on. The shadow destructivity has some meaningful properties:

  1. 1.

(_Faithfulness_) $\zeta({\cal N})=0$ if and only if ${\cal N}$ is invertible,
in which case no information is lost. For a non-invertible quantum channel,
$\zeta$ is strictly larger than $0$. This property offers a simple
invertibility criterion for quantum channels, which can be easily checked with
the channels’ Kraus operators.

  2. 2.

(_Additivity_) $\zeta({\cal M}\otimes{\cal N})=\zeta({\cal M})+\zeta({\cal
N})$ for two quantum channels ${\cal M}$ and ${\cal N}$.

  3. 3.

(_Data processing inequality_) $\zeta({\cal N}\circ{\cal
M})\geq\max(\zeta({\cal N}),\zeta({\cal M}))$. This property implies that we
can only lose shadow information by sending quantum states through quantum
channels.

In the following, we prove these three properties.

###### Proposition S2

(Faithfulness of shadow destructivity). The shadow destructivity is faithful
so that $\zeta({\cal N})=0$ if and only if the quantum channel ${\cal N}$ is
invertible.

###### Proof.

First suppose $\zeta({\cal N})\equiv\log(d^{2}/d_{\rm s}({\cal N}))=0$, which
is only true when $d_{\rm s}({\cal N})=d^{2}$ and thus implying that ${\cal
N}$ is surjective. Since the image of ${\cal N}$ has the same dimension as its
domain, we know that ${\cal N}$ is injective. As ${\cal N}$ is both surjective
and injective, we conclude that ${\cal N}$ is invertible.

Now suppose ${\cal N}$ is invertible, which is the same to say ${\cal N}$ is
both surjective and injective. For ${\cal N}$ being surjective, the dimension
of its image is $\delta^{2}$, making its shadow destructivity $\zeta({\cal
N})\equiv\log(d^{2}/d_{\rm s}({\cal N}))=0$.  $\sqcap$$\sqcup$

###### Proposition S3

(Additivity of shadow destructivity). The shadow destructivity is additive
with respect to tensor product, i.e.,

$\displaystyle\zeta({\cal M}\otimes{\cal N})=\zeta({\cal M})+\zeta({\cal N}),$
(S26)

where ${\cal M}_{A\to A^{\prime}}$ and ${\cal N}_{B\to B^{\prime}}$ are two
quantum channels.

###### Proof.

We have showed that the effective shadow dimension of a channel equals the
rank of the matrix of it as a linear map, that is: $d_{\rm s}({\cal M})={\rm
rank}({\cal M})$, $d_{\rm s}({\cal N})={\rm rank}({\cal N})$, and $d_{\rm
s}({\cal M}\otimes{\cal N})={\rm rank}({\cal M}\otimes{\cal N})$. Hence,
$\zeta({\cal M}\otimes{\cal N})\equiv\log((d_{A}d_{B})^{2}/d_{\rm s}({\cal
M}\otimes{\cal N}))=\log(d_{A}^{2}d_{B}^{2}/{\rm rank}({\cal M}\otimes{\cal
N}))$. It is also known that ${\rm rank}({\cal M}\otimes{\cal N})={\rm
rank}({\cal M}){\rm rank}({\cal N})$ Laub (2005). By this property, we have
$\zeta({\cal M}\otimes{\cal N})=\log(d_{A}^{2}d_{B}^{2}/({\rm rank}({\cal
M}){\rm rank}({\cal N})))=\log(d_{A}^{2}/{\rm rank}({\cal
M}))+\log(d_{B}^{2}/{\rm rank}({\cal N}))=\log(d_{A}^{2}/d_{\rm s}({\cal
M}))+\log(d_{B}^{2}/d_{\rm s}({\cal N}))=\zeta({\cal M})+\zeta({\cal N})$.
$\sqcap$$\sqcup$

###### Proposition S4

(Data processing inequality of shadow destructivity). For two quantum channels
${\cal M}$ and ${\cal N}$, it holds that $\zeta({\cal N}\circ{\cal
M})\geq\max(\zeta({\cal N}),\zeta({\cal M}))$.

###### Proof.

For the composite channel ${\cal N}\circ{\cal M}$, we can treat ${\cal N}$ as
a linear map from the image of ${\cal M}$ to ${\cal L}$. As the dimension of
the image of ${\cal M}$ is $d^{2}-\dim({\rm null}({\cal M}))$, we have
$\dim({\rm range}({\cal N}\circ{\cal M}))\leq d^{2}-\dim({\rm null}({\cal
M}))$ by the fundamental theorem of linear maps Axler (2015). This inequality
implies that $d_{\rm s}({\cal N}\circ{\cal M})\leq d_{\rm s}({\cal M})$, which
is equivalent to $\zeta({\cal N}\circ{\cal M})\geq\zeta({\cal M})$. Also,
$d_{\rm s}({\cal N}\circ{\cal M})\leq d_{\rm s}({\cal N})$ as the image of
${\cal M}$ is a subspace of ${\cal L}$, implying that $\zeta({\cal
N}\circ{\cal M})\geq\zeta({\cal N})$.  $\sqcap$$\sqcup$

##  V Retrieving Cost

Recall that, given a quantum channel ${\cal N}$, the shadow retrieving cost
with respect to an observable $O$ is defined as

$\displaystyle\gamma_{O}({\cal N})=\min\\{\gamma_{\min}({\cal D})|{\cal
D}\text{ is HPTS},~{}{\cal N}^{\dagger}\circ{\cal D}^{\dagger}(O)=O\\},$ (S27)

where $\gamma_{\min}({\cal D})$ is the minimum cost for simulating ${\cal D}$.
Here, we give a proof that the minimum cost of simulating an HPTS map can be
achieved by a decomposition with two CPTP maps. The same thing has been proved
for HPTP maps in Ref. Jiang  _et al._ (2021), and the proof here is similar.

###### Proposition S5

$\displaystyle\gamma_{\min}({\cal D})=\min\big{\\{}|c_{1}|+|c_{2}|\big{|}{\cal
D}=c_{1}{\cal D}_{1}+c_{2}{\cal D}_{2};{\cal D}_{1},{\cal D}_{2}\text{ are
CPTP}\big{\\}}$ (S28)

###### Proof.

Lemma 3 implies that $\gamma_{\min}({\cal D})$ is finite as ${\cal D}$ can be
decomposed into a linear combination of two CPTP maps. Suppose
$\gamma_{\min}({\cal D})$ is achieved by

$\displaystyle{\cal D}=\sum_{j=1}^{T}c^{\prime}_{j}{\cal D}^{\prime}_{j},$
(S29)

where $T\geq 3$ so that $\gamma_{\min}({\cal
D})=\sum_{j=1}^{T}|c^{\prime}_{j}|$. Then, it is always possible to construct
two CPTP maps ${\cal D}_{1},{\cal D}_{2}$ so that ${\cal D}=c_{1}{\cal
D}_{1}+c_{2}{\cal D}_{2}$ and $|c_{1}|+|c_{2}|=\gamma_{\min}({\cal D})$.

In particular, let $c_{1}=\sum_{j\mathrel{\mathop{\mathchar
58\relax}}c^{\prime}_{j}\geq 0}c^{\prime}_{j}$, ${\cal
D}_{1}=\sum_{j\mathrel{\mathop{\mathchar 58\relax}}c^{\prime}_{j}\geq
0}c^{\prime}_{j}/c_{1}\cdot{\cal D}^{\prime}_{j}$,
$c_{2}=\sum_{j\mathrel{\mathop{\mathchar
58\relax}}c^{\prime}_{j}<0}c^{\prime}_{j}$, and ${\cal
D}_{2}=\sum_{j\mathrel{\mathop{\mathchar
58\relax}}c^{\prime}_{j}<0}c^{\prime}_{j}/c_{2}\cdot{\cal D}^{\prime}_{j}$.
One can check that ${\cal D}_{1}$ and ${\cal D}_{2}$ are CPTP and $c_{1}{\cal
D}_{1}+c_{2}{\cal D}_{2}=\sum_{j=1}^{T}c^{\prime}_{j}{\cal D}^{\prime}_{j}$.
Thus, this decomposition of ${\cal D}$ is valid. Plus,
$|c_{1}|+|c_{2}|=\sum_{j=1}^{T}|c^{\prime}_{j}|$, ensuring that this
decomposition achieves $\gamma_{\min}({\cal D})$.  $\sqcap$$\sqcup$

###  V.1 Dual SDP for Retrieving Cost

For a quantum channel ${\cal N}_{A\to A^{\prime}}$, the primal SDP
characterization of its retrieving cost with respect to an observable $O$ is
$\displaystyle\gamma_{O}({\cal N})=\min$ $\displaystyle\;c_{1}+c_{2}$ (S30a)
s.t. $\displaystyle\;J_{\cal D}\equiv J_{{\cal D}_{1}}-J_{{\cal D}_{2}}$
(S30b) $\displaystyle\;J_{{\cal D}_{1}}\geq 0,\;J_{{\cal D}_{2}}\geq 0$ (S30c)
$\displaystyle\;\operatorname{Tr}_{A_{o}^{\prime}}[J_{{\cal
D}_{1{A^{\prime}_{i}A^{\prime}_{o}}}}]=c_{1}I_{A^{\prime}_{i}},\;\operatorname{Tr}_{A^{\prime}_{o}}[J_{{\cal
D}_{2{A^{\prime}_{i}A^{\prime}_{o}}}}]=c_{2}I_{A^{\prime}_{i}}$ (S30d)
$\displaystyle\;J_{{\cal
M}_{A_{i}A^{\prime}_{o}}}\equiv\operatorname{Tr}_{A_{o}A^{\prime}_{i}}[(J_{{\cal
N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
I_{A_{i}A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes J_{{\cal
D}_{A^{\prime}_{i}A^{\prime}_{o}}})]$ (S30e)
$\displaystyle\;\operatorname{Tr}_{A^{\prime}_{o}}[(I_{A_{i}}\otimes
O_{A^{\prime}_{o}}^{T})J_{{\cal M}_{A_{i}A^{\prime}_{o}}}^{T}]=O_{A_{i}}.$
(S30f)

The Lagrange function is

$\displaystyle L(J_{{\cal D}_{1}},J_{{\cal D}_{2}},c_{1},c_{2},M,N,K)$
$\displaystyle=c_{1}+c_{2}+\langle
M,\operatorname{Tr}_{A^{\prime}_{o}}[J_{{\cal
D}_{1}}]-c_{1}I_{A^{\prime}_{i}}\rangle+\langle
N,\operatorname{Tr}_{A^{\prime}_{o}}[J_{{\cal
D}_{2}}]-c_{2}I_{A^{\prime}_{i}}\rangle$ $\displaystyle~{}\quad+\langle
K,\operatorname{Tr}_{A^{\prime}_{o}}[(I_{A_{i}}\otimes
O_{A^{\prime}_{o}}^{T})J_{{\cal M}}^{T}]-O\rangle$ (S31)
$\displaystyle=c_{1}(1-\operatorname{Tr}[M])+c_{2}(1-\operatorname{Tr}[N])+\langle
M\otimes I,J_{{\cal D}_{1}}\rangle$ $\displaystyle~{}\quad+\langle N\otimes
I,J_{{\cal D}_{2}}\rangle-\operatorname{Tr}[KO]+\langle
K,\operatorname{Tr}_{A^{\prime}_{o}}[(I_{A_{i}}\otimes
O_{A^{\prime}_{o}}^{T})J_{{\cal M}}^{T}]\rangle$ (S32)

where $M$, $N$, $K$ are the dual variables. The last term can be expanded as

$\displaystyle\langle
K_{A_{i}},\operatorname{Tr}_{A^{\prime}_{o}}[(I_{A_{i}}\otimes
O_{A^{\prime}_{o}}^{T})J_{{\cal M}}^{T}]\rangle$
$\displaystyle=\operatorname{Tr}[K_{A_{i}}\operatorname{Tr}_{A^{\prime}_{o}}[(I_{A_{i}}\otimes
O_{A^{\prime}_{o}}^{T})J_{{\cal M}_{A_{i}A^{\prime}_{o}}}^{T}]]$ (S33)
$\displaystyle=\operatorname{Tr}[(K_{A_{i}}\otimes
O_{A^{\prime}_{o}}^{T})J_{{\cal M}_{A_{i}A^{\prime}_{o}}}^{T}]$ (S34)
$\displaystyle=\operatorname{Tr}[(K_{A_{i}}^{T}\otimes
O_{A^{\prime}_{o}})J_{{\cal M}_{A_{i}A^{\prime}_{o}}}]$ (S35)
$\displaystyle=\operatorname{Tr}[(K_{A_{i}}^{T}\otimes
O_{A^{\prime}_{o}})\operatorname{Tr}_{A_{o}A^{\prime}_{i}}[(J_{{\cal
N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
I_{A_{i}A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes J_{{\cal
D}_{A^{\prime}_{i}A^{\prime}_{o}}})]]$ (S36)
$\displaystyle=\operatorname{Tr}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes J_{{\cal
D}_{A^{\prime}_{i}A^{\prime}_{o}}})]$ (S37)
$\displaystyle=\operatorname{Tr}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{A^{\prime}_{i}A^{\prime}_{o}})(I_{A_{i}A_{o}}\otimes J_{{\cal
D}_{A^{\prime}_{i}A^{\prime}_{o}}})]$ (S38)
$\displaystyle=\operatorname{Tr}[\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes
J_{{\cal N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{A^{\prime}_{i}A^{\prime}_{o}})]J_{{\cal
D}_{A^{\prime}_{i}A^{\prime}_{o}}}]$ (S39)
$\displaystyle=\langle\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes
J_{{\cal N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{A^{\prime}_{i}A^{\prime}_{o}})],J_{{\cal
D}_{1A^{\prime}_{i}A^{\prime}_{o}}}\rangle$
$\displaystyle~{}\quad-\langle\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes
J_{{\cal N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{A^{\prime}_{i}A^{\prime}_{o}})],J_{{\cal
D}_{2A^{\prime}_{i}A^{\prime}_{o}}}\rangle$ (S40)

Thus, the Lagrange function can be expressed as

$\displaystyle L(J_{{\cal D}_{1}},J_{{\cal D}_{2}},c_{1},c_{2},M,N,K)$
$\displaystyle=c_{1}(1-\operatorname{Tr}[M])+c_{2}(1-\operatorname{Tr}[N])-\operatorname{Tr}[KO]$
$\displaystyle~{}\quad+\langle M\otimes
I+\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{A^{\prime}_{i}A^{\prime}_{o}})],J_{{\cal D}_{1}}\rangle$
$\displaystyle~{}\quad+\langle N\otimes
I-\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{A^{\prime}_{i}A^{\prime}_{o}})],J_{{\cal D}_{2}}\rangle$ (S41)

The corresponding Lagrange dual function is

$\displaystyle g(M,N,K)=\inf_{J_{{\cal D}_{1}}\geq 0,J_{{\cal D}_{2}}\geq
0}L(J_{{\cal D}_{1}},J_{{\cal D}_{2}},M,N,K)$ (S42)

For $J_{{\cal D}_{1}}\geq 0$ and $J_{{\cal D}_{2}}\geq 0$, it must hold that
$\operatorname{Tr}[M]\leq 1,\operatorname{Tr}[N]\leq 1$,

$\displaystyle M_{A^{\prime}_{i}}\otimes
I_{A^{\prime}_{o}}+\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes
J_{{\cal N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{A^{\prime}_{i}A^{\prime}_{o}})]$ $\displaystyle\geq 0,\text{ and}$ (S43)
$\displaystyle N_{A^{\prime}_{i}}\otimes
I_{A^{\prime}_{o}}-\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes
J_{{\cal N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{A^{\prime}_{i}A^{\prime}_{o}})]$ $\displaystyle\geq 0.$ (S44)

Thus, we arrive at the following dual SDP:

$\displaystyle\gamma_{O}({\cal N})=\max$
$\displaystyle\;-\operatorname{Tr}[KO]$ (S45a) s.t.
$\displaystyle\;\operatorname{Tr}[M]\leq 1,\;\operatorname{Tr}[N]\leq 1$
(S45b) $\displaystyle\;M_{A^{\prime}_{i}}\otimes
I_{A^{\prime}_{o}}+\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes
J_{{\cal N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{A^{\prime}_{i}A^{\prime}_{o}})]\geq 0$ (S45c)
$\displaystyle\;N_{A^{\prime}_{i}}\otimes
I_{A^{\prime}_{o}}-\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes
J_{{\cal N}_{A_{o}A^{\prime}_{i}}}^{T}\otimes
O_{A^{\prime}_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{A^{\prime}_{i}A^{\prime}_{o}})]\geq 0.$ (S45d)

##  VI Retrieving Cost for GAD channel

A generalized amplitude damping (GAD) channel can be used to describe the
energy dissipation to the environment at finite temperature Chirolli and
Burkard (2008). It is one of the realistic sources of noise in superconducting
quantum computing. For single-qubit cases, a GAD channel can be characterized
by the following Kraus operators:

$\displaystyle E_{0}=\sqrt{p}\left(\begin{array}[]{cc}1&0\\\
0&\sqrt{1-\epsilon}\end{array}\right)$
$\displaystyle,E_{1}=\sqrt{p}\left(\begin{array}[]{cc}0&\sqrt{\epsilon}\\\
0&0\end{array}\right),$ (S50) $\displaystyle
E_{2}=\sqrt{1-p}\left(\begin{array}[]{cc}\sqrt{1-\epsilon}&0\\\
0&1\end{array}\right)$
$\displaystyle,E_{3}=\sqrt{1-p}\left(\begin{array}[]{cc}0&0\\\
\sqrt{\epsilon}&0\end{array}\right),$ (S55)

where $\epsilon$ is the damping factor and $p$ is the indicator of the
temperature of the environment. A quantum state $\rho$ after going through the
GAD channel is given by ${\cal N}_{\rm GAD}(\rho)=\sum_{i=0}^{3}E_{i}\rho
E_{i}^{\dagger}$. Note that the amplitude damping channel is a special case of
the GAD channel when $p=1$. A single qubit state
$\rho=\begin{bmatrix}\rho_{00}&\rho_{01}\\\ \rho_{10}&\rho_{11}\end{bmatrix}$
after going through the GAD channel is

$\displaystyle\rho^{\prime}={\cal N}_{\rm GAD}(\rho)$
$\displaystyle=\left(\begin{array}[]{cc}(1-\epsilon)\rho_{00}+p\epsilon(\rho_{00}+\rho_{11})&\sqrt{1-\epsilon}\rho_{01}\\\
\sqrt{1-\epsilon}\rho_{10}&\rho_{11}+\epsilon\rho_{00}-p\epsilon(\rho_{00}+\rho_{11})\end{array}\right),$
(S58)

where $\epsilon$ and $p$ are noise parameters.

###### Proposition S6

Given an observable $O\in\\{X,Y\\}$ and a GAD channel ${\cal N}$, the minimum
cost $\gamma$ to retrieve the information $\operatorname{Tr}[\rho O]$ is
$\gamma_{O}({\cal N})=\frac{1}{\sqrt{1-\epsilon}}$, and the corresponding
retriever ${\cal D}$ can be written in the form of a Choi matrix

$J_{{\cal D}}=c_{1}J_{{\cal D}_{1}}+c_{2}J_{{\cal D}_{2}},$

where $c_{1}=-c_{2}=\frac{1}{2\sqrt{1-\epsilon}}$,
$J_{\mathcal{D}_{1}}=\frac{1}{2}O^{T}\otimes O+\frac{1}{2}I\otimes I$, and
$J_{\mathcal{D}_{2}}=-\frac{1}{2}O^{T}\otimes O+\frac{1}{2}I\otimes I$.

###### Proof.

First, we are going to prove $\gamma_{O}({\cal
N})\leq\frac{1}{\sqrt{1-\epsilon}}$ using SDP (S30). We show that the
retriever ${\cal D}$ above is a feasible solution with a cost of
$\frac{1}{\sqrt{1-\epsilon}}$. So be specific, we have

$\displaystyle{\cal D}\circ{\cal N}(\rho)$ $\displaystyle={\cal
D}(\rho^{\prime})$ (S59) $\displaystyle=\operatorname{Tr}_{A}[(\rho^{\prime
T}\otimes I)\cdot J_{{\cal D}}]$ (S60)
$\displaystyle=\frac{1}{2\sqrt{1-\epsilon}}\operatorname{Tr}_{A}[(\rho^{\prime
T}\otimes I)(O^{T}\otimes O)]$ (S61)
$\displaystyle=\frac{1}{2\sqrt{1-\epsilon}}\operatorname{Tr}_{A}[\rho^{\prime
T}O^{T}\otimes IO]$ (S62)
$\displaystyle=\frac{1}{2\sqrt{1-\epsilon}}O\operatorname{Tr}[\rho^{\prime}O].$
(S63)

This means that

$\displaystyle\operatorname{Tr}[{\cal D}\circ{\cal N}(\rho)O]$
$\displaystyle=\frac{1}{2\sqrt{1-\epsilon}}\operatorname{Tr}[O^{2}]\operatorname{Tr}[\rho^{\prime}O]$
(S64)
$\displaystyle=\frac{1}{\sqrt{1-\epsilon}}\operatorname{Tr}[\rho^{\prime}O]$
(S65) $\displaystyle=\operatorname{Tr}[O\rho],$ (S66)

where the second equality follows from the fact that $O^{2}=I$ for
$O\in\\{X,Y\\}$. Here, we have proven that the retriever ${\cal D}$ is a
feasible solution to retrieve information with cost
$\frac{1}{\sqrt{1-\epsilon}}$, implying that $\gamma_{O}({\cal
N})\leq|c_{1}|+|c_{2}|=\frac{1}{\sqrt{1-\epsilon}}$.

Second, we use the dual SDP (S45) to show the cost $\gamma_{O}({\cal
N})\geq\frac{1}{\sqrt{1-\epsilon}}$. We show that $\\{M,N,K\\}$ is a feasible
solution to the dual problem, where $M=N=\frac{I}{2}$ and
$K=-\frac{1}{2\sqrt{1-\epsilon}}O$. To be specific, we have

$\displaystyle\operatorname{Tr}_{A_{i}A_{o}}[(K^{T}_{A_{i}}\otimes
J^{T}_{{\cal N}_{A_{o}B_{i}}}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$
$\displaystyle=\operatorname{Tr}_{A_{i}A_{o}}[(-\frac{1}{2\sqrt{1-\epsilon}}O\otimes\sum_{i,j}|j\rangle\langle
i|\otimes{\cal N}^{T}(|i\rangle\langle j|)\otimes
O)(\sum_{m,n}|m\rangle\langle n|\otimes|m\rangle\langle n|\otimes I\otimes
I)]$ (S67)
$\displaystyle=-\frac{1}{2\sqrt{1-\epsilon}}\operatorname{Tr}_{A_{i}A_{o}}[\sum_{i,j,m,n}O|m\rangle\langle
n|\otimes|j\rangle\langle i|m\rangle\langle n|\otimes{\cal
N}^{T}(|i\rangle\langle j|)\otimes O]$ (S68)
$\displaystyle=-\frac{1}{2\sqrt{1-\epsilon}}\sum_{i,j,n}\operatorname{Tr}_{A_{i}A_{o}}[O|i\rangle\langle
n|\otimes|j\rangle\langle n|\otimes{\cal N}^{T}(|i\rangle\langle j|)\otimes
O]$ (S69)
$\displaystyle=-\frac{1}{2\sqrt{1-\epsilon}}\sum_{i,j,n}\operatorname{Tr}[O|i\rangle\langle
n|]\operatorname{Tr}[|j\rangle\langle n|]{\cal N}^{T}(|i\rangle\langle
j|)\otimes O$ (S70)
$\displaystyle=-\frac{1}{2\sqrt{1-\epsilon}}\sum_{i,j}O_{ji}{\cal
N}^{T}(|i\rangle\langle j|)\otimes O,$ (S71)

where $O_{ji}\equiv\langle j|O|i\rangle$. Since $O\in\\{X,Y\\}$ only has non-
zero elements on the anti-diagonal, we have

$\displaystyle\operatorname{Tr}_{A_{i}A_{o}}[(K^{T}_{A_{i}}\otimes
J^{T}_{{\cal N}_{A_{o}B_{i}}}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=-\frac{1}{2\sqrt{1-\epsilon}}(O_{10}{\cal
N}^{T}(|0\rangle\langle 1|)+O_{01}{\cal N}^{T}(|1\rangle\langle 0|))\otimes O$
(S72)
$\displaystyle=-\frac{\sqrt{1-\epsilon}}{2\sqrt{1-\epsilon}}(O_{10}|1\rangle\\!\langle
0|+O_{01}|0\rangle\\!\langle 1|)\otimes O$ (S73)
$\displaystyle=-\frac{1}{2}O\otimes O,$ (S74)

where the second equality follows from Eq. (S58). This means that

$\displaystyle M_{B_{i}}\otimes
I_{B_{o}}+\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}B_{i}}}^{T}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=\frac{1}{2}I\otimes I-\frac{1}{2}O\otimes
O\geq 0,$ (S75) $\displaystyle N_{B_{i}}\otimes
I_{B_{o}}-\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}B_{i}}}^{T}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=\frac{1}{2}I\otimes I+\frac{1}{2}O\otimes
O\geq 0.$ (S76)

Thus, $\\{M,N,K\\}$ is a feasible solution to the dual SDP (S45), which means
that $\gamma_{O}({\cal
N})\geq-\operatorname{Tr}[KO]=\frac{1}{\sqrt{1-\epsilon}}$. Combining this
with the primal part, we conclude that $\gamma_{O}({\cal
N})=\frac{1}{\sqrt{1-\epsilon}}$ for $O\in\\{X,Y\\}$ and ${\cal N}$ being a
single-qubit GAD channel.  $\sqcap$$\sqcup$

From the proof, we also know that the above retriever ${\cal D}$ is optimal.
Moreover, since the Choi matrices of ${\cal D}_{1}$ and ${\cal D}_{2}$ are
given already, it is trivial to derive the corresponding Kraus operators,
which are $E_{{\cal
D}_{1}}=\left\\{\sqrt{\frac{1}{2}}E_{i}\middle|E_{i}\in\\{I,X,Y,Z\\},E_{i}O=OE_{i}\right\\}$
and $E_{{\cal
D}_{2}}=\left\\{\sqrt{\frac{1}{2}}E_{i}\middle|E_{i}\in\\{I,X,Y,Z\\},E_{i}O=-OE_{i}\right\\}$.

###### Proposition S7

Given an observable $O=Z$ and a GAD channel ${\cal N}$, the minimum cost
$\gamma_{O}({\cal N})$ to retrieve the information $\operatorname{Tr}[\rho O]$
is $\gamma_{O}({\cal N})=\frac{|1-2p|\epsilon+1}{1-\epsilon}$, and the
corresponding retriever ${\cal D}$ can be written in the form of a Choi matrix

$J_{{\cal D}}=c_{1}J_{{\cal D}_{1}}+c_{2}J_{{\cal D}_{1}},$

where $c_{1}=-c_{2}=\frac{|1-2p|\epsilon+1}{2(1-\epsilon)}$, and

$\displaystyle J_{{\cal D}_{1}}$
$\displaystyle=\frac{1}{2(|1-2p|\epsilon+1)}Z\otimes
Z+\frac{\epsilon(1-2p)\epsilon}{2(|1-2p|\epsilon+1)}I\otimes
Z+\frac{1}{2}I\otimes I$ (S77) $\displaystyle J_{{\cal D}_{2}}$
$\displaystyle=-\frac{1}{2(|1-2p|\epsilon+1)}Z\otimes
Z-\frac{\epsilon(1-2p)}{2(|1-2p|\epsilon+1)}I\otimes Z+\frac{1}{2}I\otimes I.$
(S78)

###### Proof.

First, we are going to prove $\gamma_{O}({\cal
N})\leq\frac{|1-2p|\epsilon+1}{(1-\epsilon)}$ by showing that the retriever
${\cal D}$ is a feasible solution to the SDP (S30). To be specific, we have

$\displaystyle{\cal D}\circ{\cal N}(\rho)$ $\displaystyle={\cal
D}(\rho^{\prime})$ (S79) $\displaystyle=\operatorname{Tr}_{A}[(\rho^{\prime
T}\otimes I)\cdot J_{{\cal D}}]$ (S80)
$\displaystyle=\operatorname{Tr}_{A}\left[(\rho^{\prime T}\otimes
I)\cdot\frac{|1-2p|\epsilon+1}{2(1-\epsilon)}\left(\frac{1}{|1-2p|\epsilon+1}Z\otimes
Z+\frac{\epsilon(1-2p)}{|1-2p|\epsilon+1}I\otimes Z\right)\right]$ (S81)
$\displaystyle=\frac{1}{2(1-\epsilon)}Z\operatorname{Tr}[\rho^{\prime}Z]+\frac{\epsilon(1-2p)}{2(1-\epsilon)}Z\operatorname{Tr}[\rho^{\prime}].$
(S82)

Therefore, we further have

$\displaystyle\operatorname{Tr}[Z{\cal D}\circ{\cal N}(\rho)]$
$\displaystyle=\frac{1}{2(1-\epsilon)}\operatorname{Tr}[Z^{2}]\operatorname{Tr}[\rho^{\prime}Z]+\frac{\epsilon(1-2p)}{2(1-\epsilon)}\operatorname{Tr}[Z^{2}]\operatorname{Tr}[\rho^{\prime}]$
(S83)
$\displaystyle=\frac{1}{(1-\epsilon)}((1-\epsilon)\rho_{00}+p\epsilon(\rho_{00}+\rho_{11})-\rho_{11}-\epsilon\rho_{00}+p\epsilon(\rho_{00}+\rho_{11})+\epsilon(1-2p)(\rho_{00}+\rho_{11}))$
(S84) $\displaystyle=\rho_{00}-\rho_{11}$ (S85)
$\displaystyle=\operatorname{Tr}[Z\rho],$ (S86)

where the second equality follows from Eq. (S58) and the fact that $Z^{2}=I$.
Hence, the retriever ${\cal D}$ is a feasible solution to retrieve
information, implying that $\gamma_{O}({\cal
N})\leq|c_{1}|+|c_{2}|=\frac{|1-2p|\epsilon+1}{1-\epsilon}$.

Second, we use the dual SDP (S45) to show the cost $\gamma_{O}({\cal
N})\geq\frac{|1-2p|\epsilon+1}{1-\epsilon}$. To prove this, we are going to
split into several cases: $0\leq p<\frac{1}{2}$, $p=\frac{1}{2}$, and
$\frac{1}{2}<p\leq 1$. First note that

$\displaystyle\operatorname{Tr}_{A_{i}A_{o}}[(K^{T}_{A_{i}}\otimes
J^{T}_{{\cal N}_{A_{o}B_{i}}}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$
$\displaystyle=\operatorname{Tr}_{A_{i}A_{o}}[(K^{T}\otimes\sum\limits_{i,j}|j\rangle\langle
i|\otimes{\cal N}^{T}(|i\rangle\langle j|)\otimes
Z)(\sum\limits_{m,n}|m\rangle\langle n|\otimes|m\rangle\langle n|\otimes
I\otimes I)]$ (S87)
$\displaystyle=\operatorname{Tr}_{A_{i}A_{o}}[\sum\limits_{i,j,m,n}K^{T}|m\rangle\langle
n|\otimes|j\rangle\\!\langle i|m\rangle\langle n|\otimes{\cal
N}^{T}(|i\rangle\langle j|)\otimes Z]$ (S88)
$\displaystyle=\sum\limits_{i,j,n}\operatorname{Tr}[K^{T}|i\rangle\langle
n|]\operatorname{Tr}[|j\rangle\langle n|]{\cal N}^{T}(|i\rangle\langle
j|)\otimes Z$ (S89)
$\displaystyle=\sum\limits_{i,j}\operatorname{Tr}[K^{T}|i\rangle\langle
j|]{\cal N}^{T}(|i\rangle\langle j|)\otimes Z.$ (S90)

  * •

When $0\leq p<\frac{1}{2}$, we set the dual variables $\\{M,N,K\\}$ as
$M=N=|0\rangle\langle
0|,K=-\frac{1}{2}I+\frac{2p\epsilon-1-\epsilon}{2(1-\epsilon)}Z$ and prove
that they form a feasible solution to the dual SDP.

$\displaystyle\operatorname{Tr}_{A_{i}A_{o}}[(K^{T}_{A_{i}}\otimes
J^{T}_{{\cal N}_{A_{o}B_{i}}}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$
$\displaystyle=\sum_{i,j}\left(-\frac{1}{2}\operatorname{Tr}[|i\rangle\langle
j|]+\frac{2p\epsilon-1-\epsilon}{2(1-\epsilon)}\operatorname{Tr}[Z|i\rangle\langle
j|]\right){\cal N}^{T}(|i\rangle\langle j|)\otimes Z$ (S91)
$\displaystyle=\sum_{i}\left(-\frac{1}{2}+(-1)^{i}\frac{2p\epsilon-1-\epsilon}{2(1-\epsilon)}\right){\cal
N}^{T}(|i\rangle\langle i|)\otimes Z$ (S92)
$\displaystyle=\left(\frac{p\epsilon-1}{1-\epsilon}{\cal
N}^{T}(|0\rangle\langle 0|)+\frac{\epsilon-p\epsilon}{1-\epsilon}{\cal
N}^{T}(|1\rangle\langle 1|)\right)\otimes Z$ (S93)
$\displaystyle=-|0\rangle\langle 0|\otimes Z$ (S94)
$\displaystyle=-|00\rangle\langle 00|+|01\rangle\langle 01|.$ (S95)

Therefore,

$\displaystyle M_{B_{i}}\otimes
I_{B_{o}}+\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}B_{i}}}^{T}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=2|01\rangle\langle 01|\geq 0$ (S96)
$\displaystyle N_{B_{i}}\otimes
I_{B_{o}}-\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}B_{i}}}^{T}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=2|00\rangle\langle 00|\geq 0.$ (S97)

  * •

When $p=\frac{1}{2}$, we set the dual variables $\\{M,N,K\\}$ as
$M=N=\frac{1}{2}I,K=-\frac{1}{2(1-\epsilon)}Z$ and prove that they form a
feasible solution to the dual SDP.

$\displaystyle\operatorname{Tr}_{A_{i}A_{o}}[(K^{T}_{A_{i}}\otimes
J^{T}_{{\cal N}_{A_{o}B_{i}}}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$
$\displaystyle=\sum_{i,j}\operatorname{Tr}\left[-\frac{1}{2(1-\epsilon)}Z|i\rangle\langle
j|\right]{\cal N}^{T}(|i\rangle\langle j|)\otimes Z$ (S98)
$\displaystyle=-\frac{1}{2(1-\epsilon)}({\cal N}^{T}(|0\rangle\langle
0|)-{\cal N}^{T}(|1\rangle\langle 1|))\otimes Z$ (S99)
$\displaystyle=-\frac{1}{2}Z\otimes Z.$ (S100)

Therefore,

$\displaystyle M_{B_{i}}\otimes
I_{B_{o}}+\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}B_{i}}}^{T}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=\frac{1}{2}I\otimes I-\frac{1}{2}Z\otimes
Z\geq 0,$ (S101) $\displaystyle N_{B_{i}}\otimes
I_{B_{o}}-\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}B_{i}}}^{T}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=\frac{1}{2}I\otimes I+\frac{1}{2}Z\otimes
Z\geq 0.$ (S102)

  * •

When $\frac{1}{2}<p\leq 1$, we set the dual variables $\\{M,N,K\\}$ as
$M=N=|1\rangle\langle
1|,K=\frac{1}{2}I+\frac{\epsilon-2p\epsilon-1}{2(1-\epsilon)}$ and prove that
they form a feasible solution to the dual SDP.

$\displaystyle\operatorname{Tr}_{A_{i}A_{o}}[(K^{T}_{A_{i}}\otimes
J^{T}_{{\cal N}_{A_{o}B_{i}}}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$
$\displaystyle=\sum_{i,j}\left(\frac{1}{2}\operatorname{Tr}[|i\rangle\langle
j|]+\frac{\epsilon-2p\epsilon-1}{2(1-\epsilon)}\operatorname{Tr}[Z|i\rangle\langle
j|]\right){\cal N}^{T}(|i\rangle\langle j|)\otimes Z$ (S103)
$\displaystyle=\sum_{i}\left(\frac{1}{2}+(-1)^{i}\frac{\epsilon-2p\epsilon-1}{2(1-\epsilon)}\right){\cal
N}^{T}(|i\rangle\langle i|)\otimes Z$ (S104)
$\displaystyle=\left(\frac{-p\epsilon}{1-\epsilon}{\cal
N}^{T}(|0\rangle\langle 0|)+\frac{p\epsilon+1-\epsilon}{1-\epsilon}{\cal
N}^{T}(|1\rangle\langle 1|)\right)\otimes Z$ (S105)
$\displaystyle=|1\rangle\langle 1|\otimes Z$ (S106)
$\displaystyle=|10\rangle\langle 10|-|11\rangle\langle 11|.$ (S107)

Therefore,

$\displaystyle M_{B_{i}}\otimes
I_{B_{o}}+\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}B_{i}}}^{T}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=2|10\rangle\langle 10|\geq 0,$ (S108)
$\displaystyle N_{B_{i}}\otimes
I_{B_{o}}-\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}B_{i}}}^{T}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=2|11\rangle\langle 11|\geq 0.$ (S109)

Hence, we conclude that under different $p$ values, the corresponding
solutions $\\{M,N,K\\}$ are all feasible. It can be easily verified that
$-\operatorname{Tr}[KO]=\frac{|1-2p|\epsilon+1}{1-\epsilon}$ for all these
cases, which implies that the inequality $\gamma_{O}({\cal
N})\geq\frac{|1-2p|\epsilon+1}{1-\epsilon}$ always holds. Combining it with
the primal part, we have $\gamma_{O}({\cal
N})=\frac{|1-2p|\epsilon+1}{1-\epsilon}$.  $\sqcap$$\sqcup$

From the proof, we also know that the above retriever ${\cal D}$ is optimal.
Moreover, since the Choi matrix has been given, the corresponding Kraus
operators of the retriever can be easily derived.

  * •

When $0\leq p<\frac{1}{2}$, the Kraus operators for ${\cal D}_{1}$ and ${\cal
D}_{2}$ are $E_{{\cal D}_{1}}=\\{\alpha|1\rangle\langle 1|,|0\rangle\langle
0|,\beta|0\rangle\langle 1|\\}$ and $E_{{\cal D}_{2}}=\\{|1\rangle\langle
0|,\alpha|0\rangle\langle 1|,\beta|0\rangle\langle 1|\\}$, where
$\alpha=\sqrt{\frac{1}{1+\epsilon|1-2p|}}$ and
$\beta=\sqrt{\frac{\epsilon|1-2p|}{1+\epsilon|1-2p|}}$.

  * •

When $\frac{1}{2}\leq p\leq 1$, the Kraus operators for ${\cal D}_{1}$ and
${\cal D}_{2}$ are $E_{{\cal D}_{1}}=\\{|1\rangle\langle
1|,\alpha|0\rangle\langle 0|,\beta|1\rangle\langle 0|\\}$ and $E_{{\cal
D}_{2}}=\\{|0\rangle\langle 1|,\alpha|1\rangle\langle 1|,\beta|1\rangle\langle
1|\\}$, where $\alpha=\sqrt{\frac{1}{1+\epsilon|1-2p|}}$ and
$\beta=\sqrt{\frac{\epsilon|1-2p|}{1+\epsilon|1-2p|}}$.

##  VII Retrieving Cost for Mixed Pauli Channel

The mixed Pauli channel is a common noise model in quantum computers. For
single-qubit cases, a quantum state corrupted by mixed Pauli becomes

${\cal N}_{\rm Pauli}(\rho)=p_{i}\rho+p_{x}X\rho X+p_{y}Y\rho Y+p_{z}Z\rho Z,$
(S110)

where $p_{i},p_{x},p_{y},p_{z}$ are the corresponding probabilities with
$p_{i}+p_{x}+p_{y}+p_{z}=1$ and $0\leq p\leq 1$ for each
$p\in\\{p_{i},p_{x},p_{y},p_{z}\\}$. For general $n$-qubit cases, the noisy
state is

${\cal N}_{\rm Pauli}(\rho)=\sum_{\sigma}p_{\sigma}\sigma\rho\sigma,$ (S111)

where the sum is over all the $n$-qubit Pauli operators $\\{\sigma\\}$, and
$\\{p_{\sigma}\\}$ are the corresponding probabilities with
$\sum_{\sigma}p_{\sigma}=1$ and $0\leq p_{\sigma}\leq 1$. Note that the
depolarizing channel is a special case of the mixed Pauli channels, where
$p_{x}=p_{y}=p_{z}$.

###### Proposition S8

Given an $n$-qubit observable $O=\bigotimes_{i=1}^{n}\sigma_{i}$, where
$\sigma_{i}\in\\{X,Y,Z,I\\}$, and a mixed Pauli channel ${\cal N}$. The
minimum cost $\gamma_{O}({\cal N})$ to retrieve the information
$\operatorname{Tr}[\rho O]$ is $\gamma_{O}({\cal
N})=\frac{1}{\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}}}$,
and the corresponding retriever ${\cal D}$ can be written in the form of a
Choi matrix $J_{{\cal D}}=c_{1}J_{{\cal D}_{1}}+c_{2}J_{{\cal D}_{1}}$, where
$J_{{\cal D}_{1}}=\frac{1}{2^{n}}I^{\otimes 2n}+\frac{1}{2^{n}}(O^{T}\otimes
O),J_{{\cal D}_{2}}=\frac{1}{2^{n}}I^{\otimes 2n}-\frac{1}{2^{n}}(O^{T}\otimes
O)$ and
$c_{1}=-c_{2}=\frac{1}{2(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}})}$.
The $\\{\sigma^{+}\\}$ are all the Pauli operators that commute with the
observable, i.e., $\sigma^{+}\in P_{n},[\sigma^{+},O]=0$, and correspondingly
$\sigma^{-}\in P_{n},\\{\sigma^{-},O\\}=0$.

###### Proof.

First, we are going to prove $\gamma_{O}({\cal
N})\leq\frac{1}{\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}}}$.
We prove this by utilizing SDP (S30) and showing that the retriever ${\cal D}$
is a feasible solution.

For an arbitrary state $\rho$, after the mixed Pauli channel, it becomes
$\rho^{\prime}={\cal
N}(\rho)=\sum_{\sigma^{+}}p_{\sigma^{+}}\sigma^{+}\rho\sigma^{+}+\sum_{\sigma^{-}}p_{\sigma^{-}}\sigma^{-}\rho\sigma^{-}$.
Then, we have

$\displaystyle{\cal D}\circ{\cal N}(\rho)$ $\displaystyle={\cal
D}(\rho^{\prime})$ (S112) $\displaystyle=\operatorname{Tr}_{A}[(\rho^{\prime
T}\otimes I)\cdot J_{{\cal D}}^{O}]$ (S113)
$\displaystyle=\frac{1}{2^{n}\cdot(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}})}\operatorname{Tr}_{A}[(\rho^{\prime
T}\otimes I)\cdot(O^{T}\otimes O)]$ (S114)
$\displaystyle=\frac{1}{2^{n}\cdot(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}})}\operatorname{Tr}_{A}[\rho^{\prime
T}O^{T}\otimes IO]$ (S115)
$\displaystyle=\frac{1}{2^{n}\cdot(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}})}O\operatorname{Tr}[\rho^{\prime
T}O^{T}]$ (S116)

Since the transpose is linear, we have $\operatorname{Tr}[\rho^{\prime
T}O^{T}]=\operatorname{Tr}[(\rho^{\prime}O)^{T}]=\operatorname{Tr}[\rho^{\prime}O]$.
Therefore,

$\displaystyle{\cal D}\circ{\cal N}(\rho)$
$\displaystyle=\frac{1}{2^{n}\cdot(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}})}O\operatorname{Tr}[\rho^{\prime}O]$
(S118)
$\displaystyle=\frac{1}{2^{n}\cdot(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}})}O\operatorname{Tr}\left[\left(\sum_{\sigma^{+}}p_{\sigma^{+}}\sigma^{+}\rho\sigma^{+}+\sum_{\sigma^{-}}p_{\sigma^{-}}\sigma^{-}\rho\sigma^{-}\right)O\right]$
(S119)
$\displaystyle=\frac{1}{2^{n}\cdot(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}})}O\operatorname{Tr}\left[\left(\sum_{\sigma^{+}}p_{\sigma^{+}}\sigma^{+}\rho
O\sigma^{+}-\sum_{\sigma^{-}}p_{\sigma^{-}}\sigma^{-}\rho
O\sigma^{-}\right)\right]$ (S120)
$\displaystyle=\frac{1}{2^{n}\cdot(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}})}O\operatorname{Tr}\left[\left(\sum_{\sigma^{+}}p_{\sigma^{+}}\rho
O\sigma^{+}\sigma^{+}-\sum_{\sigma^{-}}p_{\sigma^{-}}\rho
O\sigma^{-}\sigma^{-}\right)\right]$ (S121)
$\displaystyle=\frac{1}{2^{n}\cdot(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}})}O\operatorname{Tr}\left[\left(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}}\right)\rho
O\right]$ (S122) $\displaystyle=\frac{1}{2^{n}}O\operatorname{Tr}[\rho O],$
(S123)

where the third equality follows from the commutative properties of
$\\{\sigma_{+}\\}$ and $\\{\sigma_{-}\\}$ with respect to the observable, the
fourth equality follows from the cyclic property of trace, and the fifth
equality follows from the identities that
$\sigma^{+}\sigma^{+}=\sigma^{-}\sigma^{-}=I^{\otimes n}$. Then, it is easy to
check that

$\displaystyle\operatorname{Tr}[O{\cal D}\circ{\cal N}(\rho)]$
$\displaystyle=\frac{1}{2^{n}}\operatorname{Tr}[O^{2}]\operatorname{Tr}[\rho
O]$ (S124) $\displaystyle=\frac{1}{2^{n}}\operatorname{Tr}[I^{\otimes
n}]\operatorname{Tr}[\rho O]$ (S125) $\displaystyle=\operatorname{Tr}[\rho
O],$ (S126)

which means that the retriever ${\cal D}$ is a feasible protocol, and thus we
have $\gamma_{O}({\cal
N})\leq|c_{1}|+|c_{2}|=\frac{1}{\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}}}$.

Second, we use the dual SDP (S45) to show that $\gamma_{O}({\cal
N})\geq\frac{1}{\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}}}$.
We set the dual variables as $M=N=\frac{1}{2^{n}}I,K=qO$, where $n$ is the
number of qubits and
$q\equiv-\frac{1}{2^{n}(\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}})}$.
We will show the variables $\\{M,N,K\\}$ is a feasible solution to the dual
problem.

$\displaystyle\operatorname{Tr}_{A_{i}A_{o}}[(K^{T}_{A_{i}}\otimes
J^{T}_{{\cal N}_{A_{o}B_{i}}}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$
$\displaystyle=\operatorname{Tr}_{A_{i}A_{o}}\left[\left(qO^{T}\otimes\sum_{i,j}|j\rangle\langle
i|\otimes\sum_{\sigma}p_{\sigma}\sigma^{T}|j\rangle\langle i|\sigma^{T}\otimes
O\right)\left(\sum_{m,n}|m\rangle\langle n|\otimes|m\rangle\langle n|\otimes
I\otimes I\right)\right]$ (S127)
$\displaystyle=\operatorname{Tr}_{A_{i}A_{o}}\left[\sum_{i,j,m,n}\sum_{\sigma}qO^{T}|m\rangle\langle
n|\otimes|j\rangle\langle i|m\rangle\langle n|\otimes
p_{\sigma}\sigma^{T}|j\rangle\langle i|\sigma^{T}\otimes O\right]$ (S128)
$\displaystyle=\sum_{i,j,n}\sum_{\sigma}qp_{\sigma}\operatorname{Tr}[O^{T}|i\rangle\langle
n|\otimes|j\rangle\langle n|]\sigma^{T}|j\rangle\langle i|\sigma^{T}\otimes O$
(S129)
$\displaystyle=\sum_{i,j,n}\sum_{\sigma}qp_{\sigma}\operatorname{Tr}[O^{T}|i\rangle\langle
n|]\operatorname{Tr}[|j\rangle\langle n|]\sigma^{T}|j\rangle\langle
i|\sigma^{T}\otimes O$ (S130)
$\displaystyle=\sum_{i,j}\sum_{\sigma}qp_{\sigma}O^{T}_{ji}\sigma^{T}|j\rangle\langle
i|\sigma^{T}\otimes O$ (S131)
$\displaystyle=\sum_{\sigma}qp_{\sigma}\sigma^{T}O^{T}\sigma^{T}\otimes O$
(S132) $\displaystyle=q\left(\sum_{\sigma^{+}}p_{\sigma^{+}}O^{T}\otimes
O-\sum_{\sigma^{-}}p_{\sigma^{-}}O^{T}\otimes O\right)$ (S133)
$\displaystyle=-\frac{1}{2^{n}}O^{T}\otimes O,$ (S134)

where $O^{T}_{ji}\equiv\langle j|O^{T}|i\rangle$. This implies that

$\displaystyle M_{B_{i}}\otimes
I_{B_{o}}+\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}B_{i}}}^{T}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=\frac{1}{2^{2n}}I\otimes
I-\frac{1}{2^{n}}O^{T}\otimes O\geq 0,$ (S135) $\displaystyle N_{B_{i}}\otimes
I_{B_{o}}-\operatorname{Tr}_{A_{i}A_{o}}[(K_{A_{i}}^{T}\otimes J_{{\cal
N}_{A_{o}B_{i}}}^{T}\otimes O_{B_{o}})(J_{I_{A_{i}A_{o}}}\otimes
I_{B_{i}B_{o}})]$ $\displaystyle=\frac{1}{2^{2n}}I\otimes
I+\frac{1}{2^{n}}O^{T}\otimes O\geq 0,$ (S136)

which means that $\\{M,N,K\\}$ is a feasible solution to the dual SDP (S45).
Therefore, we have $\gamma_{O}({\cal
N})\geq-\operatorname{Tr}[KO]=\frac{1}{\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}}}$.
Combining this with the primal part, we conclude that $\gamma_{O}({\cal
N})=\frac{1}{\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}}}$.
$\sqcap$$\sqcup$

From the proof, we also know that the above retriever ${\cal D}$ is optimal.
Moreover, from the given Choi matrix, one could derive that the corresponding
Kraus operators of ${\cal D}_{1}$ and ${\cal D}_{2}$ are $E_{{\cal
D}_{1}}=\left\\{\sqrt{\frac{1}{2^{2n-1}}}E_{i}\middle|E_{i}\in\\{I,X,Y,Z\\}^{\otimes
n},E_{i}O=OE_{i}\right\\}$ and $E_{{\cal
D}_{2}}=\left\\{\sqrt{\frac{1}{2^{2n-1}}}E_{i}\middle|E_{i}\in\\{I,X,Y,Z\\}^{\otimes
n},E_{i}O=-OE_{i}\right\\}$.

Note that the depolarizing channel is a special case of the mixed Pauli
channels, where all noise coefficients are the same. For the single-qubit
case, the depolarizing channel is ${\cal N}_{\rm
depo}(\rho)=(1-\epsilon)\rho+\epsilon\frac{I}{2}$, which is equivalent to Eq.
(S110) by setting $p_{x}=p_{y}=p_{z}=\frac{\epsilon}{4}$ and
$p_{i}=1-p_{x}-p_{y}-p_{z}=1-\frac{3\epsilon}{4}$. The $n$-qubit depolarizing
channel is ${\cal N}_{n-{\rm
depo}}(\rho)=(1-\epsilon)\rho+\epsilon\frac{I}{2^{n}}$, by setting the
parameters in Eq. (S111) as $p_{\sigma}=\frac{\epsilon}{4^{n}}$ and
$p_{I}=1-\sum_{\sigma}p_{\sigma}=1-\epsilon\frac{4^{n}-1}{4^{n}}$, where
$\\{\sigma\\}$ are the $n$-qubit Pauli operators excluding $I^{\otimes n}$,
and $\\{p_{\sigma}\\}$ are the corresponding probabilities. It is obvious that
$I^{\otimes n}$ commutes with any observable, i.e., $I\in\sigma^{+}$. Since
the rest probabilities are identical, we have
$\sum_{\sigma^{+}}p_{\sigma^{+}}-\sum_{\sigma^{-}}p_{\sigma^{-}}=1-\epsilon$,
which means that the retrieving cost for depolarizing channel is
$\gamma_{O}({\cal N}_{n-{\rm depo}})=\frac{1}{1-\epsilon}$ for $O$ being an
$n$-qubit Pauli operator.