Information recoverability of noisy quantum states
Xuanqiang Zhao1,2 , Benchi Zhao1 , Zihan Xia1 , and Xin Wang1
1 Institute for Quantum Computing, Baidu Research, Beijing 100193, China
2 QICI Quantum Information and Computation Initiative, Department of Computer Science, The University of Hong Kong,arXiv:2203.04862v3 [quant-ph] 8 Apr 2023

Pokfulam Road, Hong Kong, China

Extracting classical information from quantum systems is an essential step of many
quantum algorithms. However, this information could be corrupted as the systems areprone 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 thecorresponding optimal protocol, is efficiently computable by semidefinite programming.
As applications, we establish the limits on the information retrieving cost for practicalquantum noises and employ the corresponding protocols to mitigate errors in groundstate energy estimation. Our work gives the first full characterization of information
recoverability of noisy quantum states from the recoverable range to the recovering
cost, revealing the ultimate limit of probabilistic error cancellation.

1 Introduction
1.1 BackgroundThe dynamics of a closed quantum system is described as a unitary evolution [1]. However,quantum systems are rarely closed in practice as they unavoidably interacts with the environment.
Quantum channels, stemming from the unitary dynamics in a larger Hilbert space, are consideredas the proper mathematical formalism depicting the evolution of general quantum systems [2].
Quantum channels represent the quantum information manipulation processes and are essential toquantum computation [2–8].
A central subroutine of quantum computation is to extract classical information from a quantum
system. The expectation value of some chosen observable, also known as shadow information,
characterizes physical properties of the quantum system, making estimating expectation values themain goal of many quantum algorithms [2, 9], such as variational quantum eigensolver (VQE) [10].
The importance of expectation values has motivated the study of shadow tomography and related
problems [11–13]. However, inevitable noises modeled as quantum channels can corrupt the shadow
information as they undesirably change the state of the quantum system, preventing us fromestimating the expectation value accurately.
It is natural to ask how a quantum channel N affects the information stored in quantum states.
The minimum fidelity [14–16] of some initial state |ψihψ| and the final state N (|ψihψ|) is the one
we often use to answer this question. But this method is not appropriate for quantifying how
well a quantum channel preserves shadow information. Take the completely phase damping channel NPD (ρ) = ZρZ as an example. While Fmin (NPD ) = 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 [14, 17] are not suitable to depict the shadow information
preservation either. Some other measures for information preservation are various channel capacities (e.g., classical capacity [18–20]), where each channel capacity quantifies a quantum channel’s
Xin Wang: wangxin73@baidu.com, https://www.xinwang.info/

Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

1

Figure 1: Framework for retrieving shadow information from noisy quantum states. After independently applying
D(i) randomly selected from {Dj } to multiple copies of N (ρ), estimation of the desired information Tr[ρO] isobtained via making measurements with the corresponding observable O and post-processing.

utility to transfer information for a certain purpose. However, these capacities are derived inasymptotic settings with multiple uses of the channel, and thus are not proper guides to practicaltasks with finite quantum resources to some extent. Naturally, the following key questions thenarise:
1. What is a proper way to quantify the level of shadow information preservation by aquantum channel?
2. How to quantify the cost of retrieving a certain piece of shadow information given
it is preserved?

1.2 Contributions
To address these two questions in an operational way, we 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 [13,21] and mitigating quantum errors [22–26]. In particular, we suppose that multiple copies of a noisy
state N (ρ) are available. For each copy we apply a quantum channel randomly sampled from anensemble of channels {Dj } and then measure the observable of interest, as shown in Fig. 1. We saythat a channel 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 {Dj } and a set of real numbers{cj } such thatX
cj Tr[Dj ◦ N (ρ)O] = Tr[ρO].
(1)j

We establish a necessary and sufficient condition for the preservation of the desired shadow information in terms of a relation between O and N that should be satisfied. This condition motivates ameasure called shadow destructivity characterizing a quantum channel’s level of destroying shadow
information.
We define a measure called retrieving cost to quantify the minimum cost of recovering Tr[ρO],
which also quantifies how well the channel preserves the shadow information queried by a specificobservable. This measure, along with the concrete retrieving protocol, is efficiently computablewith respect to the system dimension via semidefinite programming [27]. We analytically obtainthe values of this measure and 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 [22–26]. Specifically, we employ our method to estimate the groundstate energies of several molecules with VQE. 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.

Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

2

Figure 2: Illustration of Theorem 2. Suppose a state ρ is corrupted by a channel N . A piece of shadow
information is recoverable by the retriever 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 N . This result connects channel corrupting
state in Schrödinger picture with the evolving of the observable space in Heisenberg picture.

1.3 Preliminaries
Before introducing our results, we set the notations and define several quantities that will be usedthroughout this paper. We use symbols such as HA and HB to denote finite-dimensional Hilbert
spaces associated with systems A and B, respectively. We use dA to denote the dimension of thesystem A. The sets of linear and Hermitian operators acting on A are denoted by LA and LH
A,respectively.
In this work, we focus on linear maps having the same input and output dimension. A linear
map NA→A0 transforms linear operators in LA to linear operators in LA0 , where HA0 is isomorphic
to HA . We call a linear map NA→A0 a quantum channel if it is completely positive and tracepreserving (CPTP). By saying N is completely positive (CP), we mean idR ⊗ N is a positive
map with a reference system R of arbitrary dimension. By saying N is trace-preserving (TP), wemean Tr[N (X)] = Tr[X] for all X ∈ LA . A linear map N is called Hermitian-preserving (HP) if
H
N (X) ∈ LH
0 for all X ∈ LA . For any linear map NA→A0 , its Choi-Jamiołkowski matrix is given
PAdA −1dA −1
by JN ≡ i,j=0 |iihj| ⊗ NA→A0 (|iihj|), where {|ii}i=0
is an orthonormal basis in HA .

2 Main Results
2.1 A Necessary and Sufficient Condition
We study the preservation of shadow information by considering an operational task: recovering
the expectation value Tr[ρO] of an observable O from multiple copies of a corrupted state N (ρ),
where N is the noisy channel of interest and ρ is an unknown state. A usual way [25] is to simulatea Hermitian-preserving and trace-preserving (HPTP) map D, which we call a retriever in thiswork, such that D ◦ N = id, where id is the identity map. While this approach is sufficient forrecovering the target information, its requirement on the retriever 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 D isTr[D ◦ N (ρ)O] = Tr[ρO](2)

for any state ρ 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 6. We say alinear map N is trace-scaling (TS) if TrA0 [JN ] = pIA for some real number p, and HPTP maps
are special cases of HPTS maps when p = 1.
Here, given a quantum channel N and an observable O, we give the only condition that a
retriever D needs to satisfy so that Eq. (2) holds for an arbitrary state:N † ◦ D† (O) = O,

(3)

where N † and D† are the adjoint maps of N and D, respectively. This condition is a direct
implication of Lemma 1.
Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

3

Lemma 1 Given an observable O, an HP map M satisfies Tr[M(ρ)O] = Tr[ρO] for any state ρ
if and only if it holds that M† (O) = O.
Proof First, we assume that M† (O) = O is true. For M being HP, its adjoint map M† is also
HP (see Remark 1). Hence, Tr[M(ρ)O] = Tr[ρ(M† (O† ))† ] = Tr[ρM† (O)] for both O and M† (O)being Hermitian. Then, with our assumption, we have Tr[M(ρ)O] = Tr[ρM† (O)] = Tr[ρO].
For the other direction, given Tr[M(ρ)O] = Tr[ρO] for all states ρ, we immediately have
Tr[ρM† (O)] = Tr[ρO]. Suppose, for the sake of contradiction, that M† (O) 6= O. If we define∆O = M† (O) − O, then Tr[ρ∆O] = 0 for all ρ. However, this implies that ∆O = 0 since otherwise
we can choose a σ from the nonzero eigenspace of ∆O so that Tr[σ∆O] 6= 0. As ∆O = 0 contradicts
with the assumption that M† (O) 6= O, we conclude that Tr[ρM† (O)] = Tr[ρO] holds for all ρ only
if M† (O) = O.
Remark 1 A linear map N is Hermitian-preserving (HP) if and only if JN is Hermitian. The
adjoint of an HP map N is also HP. This can be seen by checking the Hermiticity of its Choi†
T †Tmatrix: JN† = (JN ) = JN = JN † for JN being Hermitian.
Lemma 1 sets the criterion that we should refer to when searching for a retriever. We say achannel N preserves the shadow information queried by an observable O if there exists a retriever D
satisfying Eq. (3). It is crucial to ask for what observables the channel preserves their corresponding
shadow information. In Theorem 2, we establish a necessary and sufficient condition for thepreservation of the shadow information by introducing the adjoint image of LH
A0 under the channel
†
under
N
and
is
denotedby N † (LH
NA→A0 , which we define to be the image of LH
A0 ).
A0
A0 →A
Theorem 2 (Necessary and sufficient condition for information preservation). Given a quantum
channel NA→A0 and an observable O, there exists an HPTS map D such that M ≡ D ◦ N satisfies
M† (O) = O if and only if O ∈ N † (LH
A0 ).
The proof for the necessity part is rather straightforward, while that for the sufficiency part
is nontrivial. To prove the “if” part, we denote by Q a Hermitian operator that evolves into theobservable O under the map N † , i.e., N † (Q) = O. Then, it is sufficient to construct an HPTS map
D such that D† (O) = Q. According to Lemma S1, we can instead construct an HP and unit-scaling
map D† , which guarantees that the map D is HPTS. By saying that D† is unit-scaling, we meanthat D† scales the identity operator. The main difficulty of this construction is to ensure that D† isunit-scaling. To overcome this difficulty, we split all the observables into three categories by theirrank and trace.
We first consider observables that do not have full rank and are not traceless, i.e., Tr[O] 6= 0.
For these observables, we exploit their kernel so that the constructed D† is unit-scaling. With somemanipulation, the other two cases can be reduced to this one. The detailed proof is given below.
Proof For the “only if” part, suppose such a map D exists for the given channel N and non-zero
observable O. Note that D† is also a Hermitian-preserving map since its Choi operator is Hermitian,as we have noted in Remark 1. Then, we can let Q = D† (O) so that N † (Q) = N † ◦ D† (O) =M† (O) = O. Hence, O ∈ N † (LHA0 ) if there exists an HPTS map D such that M ≡ D ◦ N satisfies
M† (O) = O.
For the “if” part, suppose O ∈ N † (LHA0 ), which means that there exists a Hermitian operator Q
such that N † (Q) = O. It is sufficient to construct an HPTS map D satisfying D† (O) = Q so thatN † (Q) = N † ◦ D† (O) = M† (O) = O. By Lemma S1, it is equivalent to construct a Hermitianpreserving and unit-scaling map D† satisfying the above requirement. Denoting the rank of theobservable O by k, the trace of O by t, and the dimension of the Hilbert space HA by d, we complete
the proof by constructing a Hermitian-preserving and unit-scaling map D† satisfying D† (O) = Q
in each of the following three cases.
• Case 1: k < d and t 6= 0. Let P be the projection on the support of O and P ⊥ be theprojection on the kernel of O. We can construct a map D† such thatD† (·) =k(I − Q)
Q
Tr[P · P ] +Tr[P ⊥ · P ⊥ ].
tt(d − k)Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

(4)4Clearly, D† is an HP map. Note thatQk(I − Q)
Tr[P OP ] +Tr[P ⊥ OP ⊥ ]tt(d − k)Q
= Tr[O]t=Q

D† (O) =

(5)
(6)
(7)

and
k(I − Q)
Q
Tr[P IP ] +Tr[P ⊥ IP ⊥ ]tt(d − k)k(I − Q)
Q
Tr[P ⊥ ]= Tr[P ] +tt(d − k)Q
k(I − Q)=·k+· (d − k)tt(d − k)k
= I,tD† (I) =

(8)
(9)
(10)
(11)

which implies that D† is also unit-scaling and D† (O) = Q.
• Case P
2: k < d and t = 0. Since t = 0, O has at least two distinct eigenvalues. Let
O = j λj |ψj ihψj | be the spectral decomposition of O, where each λj 6= 0. Define Õ ≡O − λ0 |ψ0 ihψ0 | and Q̃ ≡ Q + ∆Q, where ∆Q is a Hermitian operator that we will fix later.
Let k̃ denote the rank of Õ and t̃ the trace of Õ. Following the definition of Õ, we havek̃ = k − 1 and t̃ = −λ0 . As k̃ < d and t̃ 6= 0, we can construct a Hermitian-preserving andunit-scaling map
D† (·) =k̃(I − Q̃)Q̃
Tr[P̃ · P̃ ] +Tr[P̃ ⊥ · P̃ ⊥ ]t̃t̃(d − k̃)=−Q̃(k − 1)(I − Q̃)
Tr[P̃ ⊥ · P̃ ⊥ ],Tr[P̃ · P̃ ] −λ0λ0 (d − k + 1)

(12)
(13)

⊥
where P̃ denotes the projection on the support ofon the kernelPÕ and P̃ be the projectionof Õ. By the definition of Õ, we have P̃ OP̃ = j>0 λj |ψj ihψj | and P̃ ⊥ OP̃ ⊥ = λ0 |ψ0 ihψ0 |,and thus Tr[P̃ OP̃ ] = −λ0 and Tr[P̃ ⊥ OP̃ ⊥ ] = λ0 . Hence,Q̃(k − 1)(I − Q̃)· (−λ0 ) −· λ0λ0
λ0 (d − k + 1)
d
d
k−1
=
Q+
∆Q −
I.
d−k+1
d−k+1
d−k+1

D† (O) = −

(14)
(15)

†
Setting ∆Q = k−1
d (I − Q), we will have D (O) = Q.

• Case 3: k = d. We first consider the case where O = cI for some real coefficient c. As Q canbe any Hermitian operator satisfying N † (Q) = O, and we know that N † is unital, we can let
Q = O so that D† being the identity map id will complete the proof.
Now, consider the case where O 6= cI for any real
P coefficient c, which implies that O musthave at least two distinct eigenvalues. Let O = j λj |ψj ihψj | be the spectral decompositionof O, where each λj 6= 0 and λ0 is the smallest eigenvalue. Then, we define Õ ≡ O − λ0 I andQ̃ ≡ Q + ∆Q, where ∆Q is a Hermitian operator that we will fix later. Let k̃ denote the rankof Õ and t̃ the trace of Õ. Following the definition of Õ, we have k̃ < d and t̃ = t − d · λ0 > 0.
Hence, by Case 1, we can construct a Hermitian-preserving and unit-scaling map
D† (·) =Q̃k̃(I − Q̃)
Tr[P̃ · P̃ ] +Tr[P̃ ⊥ · P̃ ⊥ ]t̃t̃(d − k̃)

Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

(16)

5

=

Q̃
k̃(I − Q̃)
Tr[P̃ · P̃ ] +Tr[P̃ ⊥ · P̃ ⊥ ],t − d · λ0(t − d · λ0 )(d − k̃)(17)⊥where P̃ denotes the projection on the support of Õ andon theP P̃ be the projection
kernel of Õ. By the definition of Õ, we have P̃ OP̃ = λj 6=λ0 λj |ψj ihψj | and P̃ ⊥ OP̃ ⊥ =P⊥⊥
λj =λ0 λj |ψj ihψj |, and thus Tr[P̃ O P̃ ] = t − (d − k̃)λ0 and Tr[P̃ O P̃ ] = (d − k̃)λ0 . Hence,D† (O) =k̃(I − Q̃)Q̃· (t − (d − k̃)λ0 ) +· (d − k̃)λ0t − d · λ0(t − d · λ0 )(d − k̃)= Q + ∆Q +k̃ · λ0I.
t − d · λ0

(18)
(19)

k̃·λ0
Setting ∆Q = − t−d·λ
I results in D† (O) = Q.
0

Since any observable O can be categorized into one of the three cases above, we conclude thatgiven a quantum channel N , if O ∈ Image(N † ), then there exists a Hermitian-preserving andunit-scaling map D† such that D† (O) = Q for some Q satisfying N † (Q) = O. As the adjoint of a
Hermitian-preserving and unit-scaling map is HPTS, we can always find an HPTS retriever D sothat N † ◦ D† (O) = M† (O) = O given O ∈ N † (LH
A0 ).
As illustrated in Fig. 2, Theorem 2 implies that the channel N preserves the shadow informationor, equivalently, the shadow information is retrievable, if and only if the corresponding observable
O is in the adjoint image of LH
A0 under N . A physical interpretation of this theorem can be given
within the Heisenberg picture, where quantum states are constant while observables evolve withtime [3]. From this perspective, Theorem 2 is saying that Tr[ρO] can be recovered if and only ifthere is an observable Q evolving into O under the backward dynamics prescribed by the given
N . This theorem also manifests the ultimate limitation of a quantum channel on preserving the
shadow information queried by some observables.

2.2 Quantifying the Level of Shadow Information Preservation
Following Theorem 2, for a quantum channel NA→A0 , we define the dimension of N † (LHA0 ) as thechannel N ’s effective shadow dimension ds (N ), which quantifies how much shadow information ispreserved by N . To compute the effective shadow dimension, we note that the set of all Hermitian
operators LH
A0 can be viewed as a vector space over the field of real numbers, and the set of all
linear operators LA0 is a vector space over the field of complex numbers. Both vector spaces arewith dimension d2A0 , where dA0 = dim(HA0 ). Note that a basis for LH
A0 is also a basis for LA0 ,
†
0
))
=
dim(N
(L
)).
Then,
by
the
propertiesof the adjoint [28],which implies that dim(N † (LHA
A0
the image of N † is the space orthogonal to the null space of N . Hence, the dimension of N † (LHA0 )
is d2A0 − dim(null(N )) = dim(Image(N )), which equals the rank of a matrix of N as a linear map.
A matrixPof N as a linear map can be obtained from
Prepresentation. Given
P the channel’s Kraus
E
|ji
⊗
E
|ii
=
(
N (|iihj|) = k Ek |iihj|Ek† , we have vec(N (|iihj|)) =kk Ek ⊗ Ek )|jii, where
P k k
Ek is the complex conjugate of Ek . Hence, MN ≡ k Ek ⊗ Ek is a matrix representation of N asa linear map. The effective shadow dimension ds (N ) is efficiently computable with respect to thesystem dimension as the matrix rank of MN .
Based on the effective shadow dimension, we define a measure called shadow destructivity:
ζ(N ) ≡ log

d2,
ds (N )

(20)

where d is the dimension of the Hilbert space that the input linear operators in LA act on. The
shadow destructivity quantifies a quantum channel’s capability to destruct shadow informationand has some meaningful properties:
1. (Faithfulness) ζ(N ) = 0 if and only if all the shadow information is recoverable. In otherwords, ζ is strictly larger than 0 if and only if some shadow information is irreversibly lost.
Proposition 3 (Faithfulness of shadow destructivity). The shadow destructivity is faithfulin the sense that ζ(N ) ≥ 0 and it vanishes, i.e., ζ(N ) = 0, if and only if for each observableO, there exists a retriever D such that Tr[D ◦ N (ρ)O] = Tr[ρO] for every quantum state ρ.
Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

6

Proof First suppose ζ(N ) ≡ log(d2 /ds (N )) = 0, which is only true when ds (N ) = d2 andthus implying that N † is surjective, i.e., LH being the image of N † . In other words, theimage of N † consists of all observables. Then, according to Theorem 2 and Lemma 1, forevery observable O, there is a retriever D such that Tr[D ◦ N (ρ)O] = Tr[ρO] for every stateρ.
Now suppose that for every observable O, there is a retriever D such that Tr[D ◦ N (ρ)O] =Tr[ρO] for every state ρ. By Theorem 2, this implies that all observables are in the imageof N † . Since the image can only be a subspace of LH , we know that the image is LH
itself, whose dimension is d2 . Hence, ds (N ) ≡ dim(N † (LH )) = d2 , and we conclude that
ζ(N ) ≡ log(d2 /ds (N )) = 0.
We have shown that ζ(N ) = 0 if and only if all the shadow information is recoverable. In
addition, the shadow destructivity is non-negative by its definition. Therefore, the shadow
destructivity is faithful.

2. (Additivity) The global shadow destructivity equals the sum of the shadow destructivity of
local channels, that is, ζ(M ⊗ N ) = ζ(M) + ζ(N ) for two quantum channels M and N
acting on different subsystems.
Proposition 4 (Additivity of shadow destructivity). The shadow destructivity is additive
with respect to tensor product, i.e.,ζ(M ⊗ N ) = ζ(M) + ζ(N ),(21)

where MA→A0 and NB→B 0 are two quantum channels.
Proof We have showed that the effective shadow dimension of a channel equals the rankof the matrix of it as a linear map, that is: ds (M) = rank(MM ), ds (N ) = rank(MN ),and ds (M ⊗ N ) = rank(MM⊗N ). Hence, ζ(M ⊗ N ) ≡ log((dA dB )2 /ds (M ⊗ N )) =log(d2A d2B /rank(MM⊗N )). It is also known that [29]rank(MM⊗N )= rank(MM ⊗ MN ) = rank(MM )rank(MN ).

(22)

By this property, we haveζ(M ⊗ N ) = log(d2A d2B /(rank(MM )rank(MN )))= log(d2A /rank(MM )) + log(d2B /rank(MN ))= log(d2A /ds (M)) + log(d2B /ds (N )) = ζ(M) + ζ(N ).

(23)
(24)
(25)


3. (Data processing inequality) The shadow destructivity cannot increase when a quantum stateis sent through more channels, that is, ζ(N ◦ M) ≥ max(ζ(N ), ζ(M)). This property implies
that we can only lose shadow information by sending quantum states through quantum
channels.
Proposition 5 (Data processing inequality of shadow destructivity). For two quantum
channels M and N , it holds that ζ(N ◦ M) ≥ max(ζ(N ), ζ(M)).
Proof If we write the channels M and N in their matrix representations MM and MN , thethe matrix representation of the composite channel N ◦M is MN MM , which is known to havea rank rank(MN MM ) ≤ min(rank(MN ), rank(MM )). This is equivalent to ds (N ◦ M) ≤min(ds (N ), ds (M)), which implies ζ(N ◦ M) ≥ max(ζ(N ), ζ(M)).
As the shadow destructivity derived from Theorem 2 can be computed from the matrix rankof MN , Theorem 2 endows the matrix rank of MN an operational meaning in shadow information
recoverability, where a higher rank indicates that more shadow information is recoverable. It is
well known that a matrix is invertible if and only if it has full rank. Since full rank corresponds tothe total recoverability of shadow information, invertibility of a channel is equivalent to its total
shadow information recoverability.
Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

7

2.3 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 dimensionof 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 thedesired shadow information within an acceptable accuracy.
Note that the retriever D is an HPTS map but not necessarily CPTP, i.e., not necessarily aquantum channel. While such a map D is not physically implementable,
we can simulate its actionP
by decomposing it as a linear combination of CPTP maps: D = j cj Dj , and utilizing Eq. (1).
As Lemma 6 implies, a linear map is physically simulatable in this framework if and only if it is
HPTS.
Lemma 6 A linear map D is HPTS if and only if itPcan be written as a linear combination ofquantum channels {Dj } with real numbers {cj }: D = j cj Dj . Furthermore, for any HPTS map
D, there exist two quantum channels D1 , D2 with real numbers c1 , c2 such thatD = c1 D1 + c2 D2 .

(26)

Proof We first prove that a linear combinationPof quantum channelsPis HPTS. The Choi-Jamiołkowski
matrix of such a linear combination D =j cj Dj is JD =j cj JDj , where JDj ≥ 0 and
TrB [JDj ] = IA for each j. As a linear combination of Hermitian
operators P
is also Hermitian,P
D is Hermitian-preserving.P Also noting that TrB [JD ] =j cj TrB [JDj ] =j cj IA , we have
TrB [JD ] = cIA , where c = j cj . Hence, D is HPTS.
For the other direction, if a map D is HPTS, its Choi-Jamiołkowski matrix JD satisfies JD
being Hermitian and TrB [JD ] = cIA for some real coefficient c. If c 6= 0, D/c is an HPTP
map and there exist two CPTP maps D1 , D2 and two real numbers c1 ≥ 0, c2 ≤ 0 such that
D/c = c1 D1 + c2 D2 [25]. Then we have D = c · c1 D1 + c · c2 D2 . On the other hand, if c = 0, D + id
is an HPTP map and there still exist two CPTP maps D1 , D2 and two real numbers c1 ≥ 0, c2 ≤ 0such that D + id = c1 D1 + c2 D2 . Hence, D can be written as D = c1 D1 + (c2 − 1)D20 , where
D20 = c2 D2 /(c2 − 1) − id/(c2 − 1) is a quantum channel. P
Now let D be an HPTS map whose decomposition is j cj Dj . With this decomposition, we
can simulate its action on the expectation value by the probabilistic sampling method prescribedby Eq. (1). Specifically, in the s-th round of total S times of sampling,
we first sample a quantumP
channel D(s) from {Dj } with probabilities {|cj |/γ}, where γ = j |cj |, and apply it to a copy ofthe corrupted state to obtain P
D(s) ◦N (ρ). Then, we measure this state in the eigenbasis {|ψj ihψj |}jof the given observable O = j oj |ψj ihψj |, where oj ∈ [−1, 1], and obtain the measurement valueo(s) . After S rounds of sampling, we attain an estimation for the expectation value Tr[ρO] as
S

ξ=

γX
sgn(c(s) )o(s) .
S s=1

(27)

By the Hoeffding’s inequality [30], the number of rounds required to obtain the estimation within
an error ε with a probability no less than 1 − δ isS = 2γ 2 log(2/δ)/ε2 .

(28)

It can be seen that the required number of copies S of the corrupted state is directly related toγ, the sum of absolute values of all cj . Hence, γ can be used to characterize the cost of simulating
the HPTS map D. It is desirable to find a decomposition of D making γ as small as possible,
and we denote the minimum possible value of γ as γmin (D). In Ref. [25], the authors define thelogarithm of γmin (D) as the physical implementability of an HPTP map D.
Naturally, given a channel N , we define the retrieving cost with respect to an observable O tobeγO (N ) = min{γmin (D)|D is HPTS, N † ◦ D† (O) = O},
Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

(29)
8

which is the γmin (D) minimized over D that can retrieve the shadow information queried by O
from the noisy channel N .
Notably, Lemma 6 states that any HPTS map can be decomposed as a linear combination of
two quantum channels (Eq. (26)), 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, andwe 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 measurethrough a semidefinite program (SDP) in terms of linear maps’ Choi-Jamiołkowski matrices:γO (N ) = min c1 + c2

(30a)s.t. JD ≡ JD1 − JD2(30b)

JD1 ≥ 0, JD2 ≥ 0(30c)

TrA0o [JD1A0 A0 ] = c1 IA0i , TrA0o [JD2A0 A0 ] = c2 IA0i
i

o

i

(30d)

o

T
JMA A0 ≡ TrAo A0i [(JN
⊗ IAi A0o )(JidAi Ao ⊗ JDA0 A0 )]
A A0

(30e)

T
T
TrA0o [(IAi ⊗ OA
] = OAi ,
0 )JM
o
A A0

(30f)

i

o

o

i

i

i

o

o

where Jid is the Choi-Jamiołkowski matrix of an identity channel. Eq. (30c) corresponds to thecondition that D1 and D2 are CP, and Eq. (30d) requires them to be TP. Eq. (30f) corresponds
to the minimum requirement for a valid retriever as given in Eq. (3). Note that we can establish
approximate versions of Eq. (30) by relaxing the requirement in Eq. (30f) such that TrA0o [(IAi ⊗T
T
OA] is close to O within a certain tolerance. This relaxation provides a remedy to cases0 )JMoAi A0owhere a perfect retriever does not exist as well as a trade-off between the retrieving cost and theestimation precision.

2.4 Case Study and Applications in Error Mitigation
To intuitively understand effective shadow dimension and shadow destructivity, we study two nonI(·)I + 12 X(·)X and N2 (·) = 12 I(·)I + 14 X(·)X + 14 Y (·)Y .
invertible channels as examples:N1 (·) = 12√ab + ciFor a quantum state ρ =, where a, b, c are real numbers and i ≡ −1, it canb −
ci 1 − a 


1/2
b
1/2
(b + ci)/2
be easily verified that N1 (ρ) =and N2 (ρ) =. While bothb
1/2
(b − ci)/2
1/2
channels are non-invertible, it is intuitive to see that channel N2 preserves more information thanchannel N1 since the imaginary part of off-diagonal elements is preserved. This intuition coincides
with the effective shadow dimension of these two channels, ds (N2 ) = 3 > ds (N1 ) = 2, which
implies that N2 preserves one more shadow dimension than N1 . The shadow destructivity of thesechannels, ζ(N1 ) = log(4/2) = 1 and ζ(N2 ) = log(4/3) ≈ 0.415, has similar implications.
Now recall the retrieving cost, which quantifies the resources required to recover a certain pieceof shadow information. The corresponding optimal retrieving protocol can be considered as amethod to mitigate errors, endowing the retrieving cost with a practical meaning in quantum error
mitigation [22–26, 26, 31–44].
In error mitigation, PEC methods are promising to suppress noises in quantum circuits run on
near-term quantum computers and return us unbiased estimation of expectation values [22–25].
Briefly speaking, the idea of PEC is to decompose the inverse (HPTP) of a noisy
Pchannel N into alinear combination of physically implementable channels (CPTP), i.e., N −1 = j aj Aj , with realP
coefficients aj and CPTP maps Aj , where j aj = 1. The inverse map N −1 is implemented byP|aj |sampling the channels Aj according to a probability distribution p(j) = γcon
, where γcon = j |aj |.
In this way, the unbiased estimation of the expectation value of an observable O with respect to astate ρ is obtained by manipulating multiple copies of the noisy state N (ρ):X
γconp(j) Tr[Aj ◦ N (ρ)O] = Tr[N −1 ◦ N (ρ)O] = Tr[ρO].
(31)
jAccepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

9

Figure 3: Comparison of the retrieving cost between our proposed protocol and conventional PEC protocol inestimating expectation value Tr[ρO] from noisy state N (ρ). The observable is O = X, and N is the GAD
channel with coefficients p ∈ [0, 0.5] and  ∈ [0, 0.9].

The quantity γcon is known as the overhead (also called retrieving cost in the setting of our work)
because it captures how many copies of the noisy state are needed to ensure the estimation within
the acceptable precision. Therefore, γcon is usually used to evaluate the efficiency of an error
mitigation protocol.
Our proposed method can be considered as an approach to mitigating errors, where the retrieving cost corresponds to the overhead of an error mitigation protocol. For a given noisy channel N
and an observable O of interest, the SDP in Eq. (30) can give us a retriever D and its decomposition D = c1 D1 + c2 D2 with the optimized retrieving cost γpro = |c1 | + |c2 |. The expectation of theestimation made by our method is


|c2 |
|c1 |
γpro
Tr[D1 ◦ N (ρ)O] +Tr[D2 ◦ N (ρ)O] = Tr[D ◦ N (ρ)O]
(32)
γpro
γpro
= Tr[ρN † ◦ D† (O)](33)

= Tr[ρO].

(34)

Note that in our method, the retriever D is not necessarily the inverse of the noisy channel, i.e.,D=
6 N −1 .
In the following, we compare the retrieving cost between our proposed protocol γpro and theconventional PEC method γcon (see, e.g., [22–26]), with the assumption that full knowledge ofthe noise is accessible and the noise is modeled as a channel just before the measurement.
As a concrete example, consider retrieving shadow information Tr[ρX] from a state ρ corrupted
1
by a GAD channel [45], where X is the Pauli X operator. The cost of our method is γpro = √1−,while the cost of the conventional method is γcon = |1−2p|+1[25], where  is the damping factor1−and p is the temperature indicator associated with the GAD channel. It is obvious to see thatγpro < γcon for any 0 <  < 1, as shown in Fig. 3. Detailed protocols are provided in the
Supplemental Material.
Now we apply our protocol to ground state energy estimation with VQE. VQE [10] is a promisingnear-term algorithm for estimating the ground state energy of a Hamiltonian H. It aims tominimize the cost function E = Tr[|ψ(θ)ihψ(θ)|H] by tuning parameters θ in a parameterized
quantum circuit used to prepare the ansatz state |ψ(θ)i. In practice,PH is decomposed into alinear combination of tensor products of Pauli tensors {Oj }, i.e., H = j hj Oj , where each hj isa real coefficient. The core subroutine of VQE is estimating the expectation value of each term
Tr[ρOj ].
We use Eq. (28) to estimate the numbers of sampling rounds required by VQE to estimate theground state energies of given molecules when there is depolarizing noise [2] on each qubit. Table 1
shows the Comparison between our protocol and the conventional protocol [25]. The retrieving1
cost of our proposed method is γpro = 1−(see Supplemental Material), while the conventional
Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

10

2

)
method is γcon = 1+(1−2/d, where  is the noise level, and d is the dimension of the system. It is1−clear that the number of sampling rounds of our method is smaller than that of the conventional
method.

Molecule
H2

HF

CO2

Proposed

1.24 × 105

7.84 × 1010

1.28 × 1013

Conventional

1.60 × 105

1.79 × 1011

1.21 × 1014

Table 1: Sampling times for estimating the ground state energies of three different molecules under the depolarizing noise with a noise level  = 0.1. The precision parameters in Eq.
P (28) are set to ε = δ = 0.01. For
estimating the sampling times, each coefficient hj of a Hamiltonian H = j hj Oj is assumed to be max{|hj |},and the term where Oj is the identity operator is excluded.

Besides the advantage of having a lower cost, our method has a larger range of applicability.
The conventional method implements the retriever as the inverse of the noisy channel. In contrast,
it only works for the cases where the noise is invertible. However, our method, employing anobservable-adaptive strategy, also works for some cases where the noise is non-invertible. As longas the observable of interest is in the image of the noise’s adjoint map, our method can provide an
optimal protocol for recovering the corresponding shadow information.

3 Conclusions
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. 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.
While the shadow destructivity and the retrieving cost capture different aspects of shadow
information recoverability, a single unified measure that captures both aspects may be worth further
studies. For future work, it would be interesting to see how the techniques presented in this work
can be combined with quantum error correction [46–48] or quantum error mitigation [37, 41–44].
We also expect that our ideas could be applied to near-term quantum tasks or applications on
noisy quantum devices [49].

Acknowledgements
X. Z. and B. Z. contributed equally to this work. We would like to thank Chenghong Zhu forhelpful discussions. We would also like to thank the referees for their helpful comments, which
greatly improved the readability of the manuscript. Part of this work was done when X. Z., B. Z.,
and Z. X. were research interns at Baidu Research.

References[1] David J Griffiths and Darrell F Schroeter. Introduction to quantum mechanics. Cambridge
University Press, 2018. ISBN 1108100341. DOI: 10.1017/9781316995433.
[2] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information.
Cambridge University Press, 2010. ISBN 9781107002173. DOI: 10.1017/CBO9780511976667.
[3] Mark M Wilde. Quantum Information Theory. Cambridge University Press, Cambridge, 2017.
ISBN 9781316809976. DOI: 10.1017/9781316809976. URL http://ebooks.cambridge.org/
ref/id/CBO9781316809976.
Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

11

[4] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018.
ISBN 9781107180567. DOI: 10.1017/9781316848142.
[5] C H Bennett, I Devetak, A W Harrow, P W Shor, and A Winter. The Quantum Reverse Shannon Theorem and Resource Tradeoffs for Simulating Quantum Channels. IEEE Transactions
on Information Theory, 60(5):2926–2959, 2014. DOI: 10.1109/TIT.2014.2309968.
[6] Xin Wang and Mark M. Wilde. Resource theory of asymmetric distinguishability forquantum channels.
Physical Review Research, 1(3):033169, dec 2019.
ISSN 26431564. DOI: 10.1103/PhysRevResearch.1.033169. URL https://link.aps.org/doi/10.
1103/PhysRevResearch.1.033169.
[7] Graeme Smith and Jon Yard. Quantum communication with zero-capacity channels. Science,
321(5897):1812–1815, 2008.
[8] Xin Wang, Mark M Wilde, and Yuan Su. Quantifying the magic of quantum channels.
New Journal of Physics, 21(10):103002, oct 2019. ISSN 1367-2630. DOI: 10.1088/13672630/ab451d. URL https://iopscience.iop.org/article/10.1088/1367-2630/ab451d.
[9] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke
Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J.
Coles. Variational quantum algorithms. Nature Reviews Physics, aug 2021. ISSN
2522-5820. DOI: 10.1038/s42254-021-00348-9. URL https://www.nature.com/articles/
s42254-021-00348-9.
[10] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J.
Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5(1):4213, dec 2014. ISSN 2041-1723.
DOI: 10.1038/ncomms5213. URL http://www.nature.com/articles/ncomms5213.
[11] Scott Aaronson. Shadow tomography of quantum states. SIAM Journal on Computing, 49(5):STOC18–368, 2019. DOI: 10.1145/3188745.3188802.
[12] Scott Aaronson and Guy N Rothblum. Gentle measurement of quantum states and differential privacy. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory ofComputing, pages 322–333, 2019. DOI: 10.1145/3313276.3316378.
[13] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020. DOI:
10.1038/s41567-020-0932-7.
[14] Howard Barnum, Emanuel Knill, and M.A. Nielsen. On quantum fidelities and channel capacities. IEEE Transactions on Information Theory, 46(4):1317–1329, jul 2000. ISSN 00189448.
DOI: 10.1109/18.850671. URL http://ieeexplore.ieee.org/document/850671/.
[15] Charles H Bennett, David P DiVincenzo, and John A Smolin. Capacities of Quantum Erasure Channels. Physical Review Letters, 78(16):3217–3220, apr 1997. ISSN 0031-9007. DOI:
10.1103/PhysRevLett.78.3217. URL https://link.aps.org/doi/10.1103/PhysRevLett.
78.3217.
[16] David P. DiVincenzo, Peter W. Shor, and John A. Smolin. Quantum-channel capacity ofvery noisy channels. Physical Review A, 57(2):830–839, feb 1998. ISSN 1050-2947. DOI:
10.1103/PhysRevA.57.830. URL https://link.aps.org/doi/10.1103/PhysRevA.57.830.
[17] Benjamin Schumacher. Sending entanglement through noisy quantum channels. PhysicalReview A, 54(4):2614, 1996. DOI: 10.1103/PhysRevA.54.2614.
[18] Alexander Semenovich Holevo. Bounds for the quantity of information transmitted by aquantum communication channel. Problemy Peredachi Informatsii, 9(3):3–11, 1973. URL
http://mi.mathnet.ru/eng/ppi903.
[19] Benjamin Schumacher and Michael D Westmoreland. Sending classical information via noisy
quantum channels. Physical Review A, 56(1):131, 1997. DOI: 10.1103/PhysRevA.56.131.
[20] Alexander S Holevo. The capacity of the quantum channel with general signal states. IEEE
Transactions on Information Theory, 44(1):269–273, 1998. DOI: 10.1109/18.651037.
[21] Francesco Buscemi, Michele Dall’Arno, Masanao Ozawa, and Vlatko Vedral. Direct observation of any two-point quantum correlation function. arXiv:1312.4240, dec 2013. URL
http://arxiv.org/abs/1312.4240.
[22] Kristan Temme, Sergey Bravyi, and Jay M. Gambetta. Error Mitigation for ShortDepth Quantum Circuits. Physical Review Letters, 119(18):180509, nov 2017. ISSN 0031-

Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

129007. DOI: 10.1103/PhysRevLett.119.180509. URL https://link.aps.org/doi/10.1103/
PhysRevLett.119.180509.
[23] Suguru Endo, Simon C. Benjamin, and Ying Li. Practical Quantum Error Mitigation for
Near-Future Applications. Physical Review X, 8(3):031027, jul 2018. ISSN 2160-3308. DOI:
10.1103/PhysRevX.8.031027. URL https://doi.org/10.1103/PhysRevX.8.031027https://link.aps.org/doi/10.1103/PhysRevX.8.031027.
[24] Ryuji Takagi.
Optimal resource cost for error mitigation.
Physical Review
Research, 3(3):033178, aug 2021.
ISSN 2643-1564.
DOI: 10.1103/PhysRevResearch.3.033178. URL http://arxiv.org/abs/2006.12509https://link.aps.org/doi/10.
1103/PhysRevResearch.3.033178.
[25] Jiaqing Jiang, Kun Wang, and Xin Wang. Physical Implementability of Linear Maps and Its
Application in Error Mitigation. Quantum, 5:600, December 2021. ISSN 2521-327X. DOI:
10.22331/q-2021-12-07-600. URL https://doi.org/10.22331/q-2021-12-07-600.
[26] Christophe Piveteau, David Sutter, and Stefan Woerner. Quasiprobability decompositions
with reduced sampling overhead. arXiv preprint arXiv:2101.09290, jan 2021. URL http://arxiv.org/abs/2101.09290.
[27] Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM review, 38(1):49–95, 1996.
[28] Sheldon Axler. Linear algebra done right, volume 2. Springer, 2015.
[29] Alan J Laub. Matrix Analysis for Scientists and Engineers, volume 91. SIAM, 2005.
[30] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The
Collected Works of Wassily Hoeffding, pages 409–426. Springer, 1994. DOI: 10.1007/978-14612-0865-5_26.
[31] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay, and Jay M. Gambetta.
Mitigating measurement errors in multi-qubit experiments. arXiv:2006.14044, jun 2020. URL
http://arxiv.org/abs/2006.14044.
[32] Filip B. Maciejewski, Zoltán Zimborás, and Michał Oszmaniec. Mitigation of readout noisein near-term quantum devices by classical post-processing based on detector tomography.
Quantum, 4:257, apr 2020. ISSN 2521-327X. DOI: 10.22331/q-2020-04-24-257. URL http://
arxiv.org/abs/1907.08518https://quantum-journal.org/papers/q-2020-04-24-257/.
[33] Piotr Czarnik, Andrew Arrasmith, Patrick J Coles, and Lukasz Cincio. Error mitigation with
Clifford quantum-circuit data. arXiv:2005.10189, may 2020. URL http://arxiv.org/abs/
2005.10189.
[34] Jarrod R. McClean, Zhang Jiang, Nicholas C. Rubin, Ryan Babbush, and Hartmut Neven.
Decoding quantum errors with subspace expansions. Nature Communications, 11(1):636, dec
2020. ISSN 2041-1723. DOI: 10.1038/s41467-020-14341-w. URL http://arxiv.org/abs/
1903.05786http://www.nature.com/articles/s41467-020-14341-w.
[35] Zhenyu Cai. Multi-exponential error extrapolation and combining error mitigation techniques for NISQ applications. npj Quantum Information, 7(1), 2021. ISSN 20566387. DOI:
10.1038/s41534-021-00404-3. URL http://dx.doi.org/10.1038/s41534-021-00404-3.
[36] Daniel Bultrini, Max Hunter Gordon, Piotr Czarnik, Andrew Arrasmith, Patrick J. Coles,
and Lukasz Cincio. Unifying and benchmarking state-of-the-art quantum error mitigation
techniques. arXiv preprint arXiv:2107.13470, pages 1–13, 2021. URL http://arxiv.org/
abs/2107.13470.
[37] Zhenyu Cai. A Practical Framework for Quantum Error Mitigation. arXiv preprint
arXiv:2110.05389, pages 1–15, oct 2021. URL http://arxiv.org/abs/2110.05389.
[38] Piotr Czarnik, Andrew Arrasmith, Lukasz Cincio, and Patrick J. Coles. Qubit-efficient
exponential suppression of errors. arXiv preprint arXiv:2102.06056, 2021. URL http://arxiv.org/abs/2102.06056.
[39] Matteo Lostaglio and Alessandro Ciani. Error Mitigation and Quantum-Assisted Simulation in the Error Corrected Regime. Physical Review Letters, 127(20):200506, nov 2021.
ISSN 0031-9007. DOI: 10.1103/PhysRevLett.127.200506. URL http://arxiv.org/abs/
2103.07526https://link.aps.org/doi/10.1103/PhysRevLett.127.200506.
[40] Ryuji Takagi, Suguru Endo, Shintaro Minagawa, and Mile Gu. Fundamental limits of quantum
error mitigation. arXiv preprint arXiv:2109.04457, pages 1–20, sep 2021. URL http://arxiv.
org/abs/2109.04457.

Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

13

[41] Bálint Koczor. Exponential Error Suppression for Near-Term Quantum Devices. Physical Review X, 11(3):031057, sep 2021.
ISSN 2160-3308.
DOI: 10.1103/PhysRevX.11.031057. URL http://arxiv.org/abs/2011.05942http://dx.doi.org/10.1103/
PhysRevX.11.031057https://link.aps.org/doi/10.1103/PhysRevX.11.031057.
[42] Suguru Endo, Zhenyu Cai, Simon C Benjamin, and Xiao Yuan. Hybrid Quantum-ClassicalAlgorithms and Quantum Error Mitigation. Journal of the Physical Society of Japan, 90(3):032001, mar 2021. ISSN 0031-9015. DOI: 10.7566/JPSJ.90.032001. URL http://arxiv.org/
abs/2011.01382https://journals.jps.jp/doi/10.7566/JPSJ.90.032001.
[43] Kun Wang, Yu-Ao Chen, and Xin Wang. Mitigating Quantum Errors via Truncated Neumann
Series. arXiv:2111.00691, nov 2021. URL http://arxiv.org/abs/2111.00691.
[44] Yasunari Suzuki, Suguru Endo, Keisuke Fujii, and Yuuki Tokunaga. Quantum error mitigation
for fault-tolerant quantum computing. arXiv preprint arXiv:2010.03887, pages 1–33, 2020.
URL http://arxiv.org/abs/2010.03887.
[45] Luca Chirolli and Guido Burkard. Decoherence in solid-state qubits. Advances in Physics,
57(3):225–285, may 2008. ISSN 0001-8732. DOI: 10.1080/00018730802218067. URL http://www.tandfonline.com/doi/abs/10.1080/00018730802218067.
[46] Daniel Gottesman. Quantum Error Correction and Fault-Tolerance. arXiv:quant-ph/0507174,
jul 2005. URL http://arxiv.org/abs/quant-ph/0507174.
[47] Daniel A Lidar and Todd A Brun. Quantum error correction. Cambridge University Press,2013. ISBN 0521897874.
[48] Barbara M. Terhal. Quantum error correction for quantum memories. Reviews of Modern
Physics, 87(2):307–346, apr 2015. ISSN 0034-6861. DOI: 10.1103/RevModPhys.87.307. URL
http://link.aps.org/doi/10.1103/RevModPhys.87.307.
[49] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2:79, aug 2018.
ISSN 2521-327X. DOI: 10.22331/q-2018-08-06-79. URL https://quantum-journal.org/
papers/q-2018-08-06-79/.
[50] Sumeet Khatri and Mark M Wilde. Principles of quantum communication theory: A modern
approach. arXiv preprint arXiv:2011.04672, 2020.

Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

14

Supplemental Material for
Information Recoverability of Noisy Quantum States

1 Adjoint of a Trace-scaling Map
Lemma S1 The adjoint of a trace-scaling map is unit-scaling, and vice versa. By calling a linear
map N unit-scaling, we mean it scales the identity operator, i.e., N (I) = pI for some real numberp.
Proof Suppose that N is a trace-scaling map such that Tr[N (·)] = p Tr[·] for some real number
p. If p 6= 0, we can define a TP map M ≡ N /p. It is known that the adjoint of TP maps areunital [50], which preserves the identity operator, and vice versa. Thus, M† , the adjoint of M, is a
unital map. Then, N † = pM† , the adjoint of the trace-scaling map N , is a unit-scaling map. On
the other hand, if p = 0, then N + id is TP and thus N † + id is unital, making N † a unit-scaling
map. Hence, the adjoint of a trace-scaling map is unit-scaling.
Now suppose that N is a unit-scaling map such that N (I) = pI for some real number p. If
p 6= 0, then M ≡ N /p is a unital map. Thus, we know its adjoint M† is TP, making N † = pM†
trace-scaling. On the other hand, if p = 0, then N + id is unital and hence its adjoint N † + id is
TP, again making N † trace-scaling. Hence, the adjoint of a unit-scaling map is trace-scaling. 

2 Retrieving Cost
Recall that, given a quantum channel N , the shadow retrieving cost with respect to an observable
O is defined asγO (N ) = min{γmin (D)|D is HPTS, N † ◦ D† (O) = O},(S1)

where γmin (D) is the minimum cost for simulating 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. [25], and the proof here is similar.
Proposition S2 For any HPTS map D,γmin (D) = min |c1 | + |c2 | D = c1 D1 + c2 D2 ; D1 , D2 are CPTP; c1 , c2 ∈ R .

(S2)

Proof Lemma 6 implies that γmin (D) is finite as D can be decomposed into a linear combinationPT
0 0of two CPTP maps. Suppose γmin (D) is achieved by D =j=1 cj Dj , where T ≥ 3 so thatPTγmin (D) = j=1 |c0j |. Then, it is always possible to construct two
1 , D2 so that D =P CPTP maps DP
c1 D1 + c2 D2 and |c1 | + |c2 | = γmin (D). In particular, let c1 = j:c0 ≥0 c0j , D1 = j:c0 ≥0 c0j /c1 · Dj0 ,jjPP
c2 = j:c0 <0 c0j , and D2 = j:c0 <0 c0j /c2 · Dj0 . One can check that D1 and D2 are CPTP and
j
j
PT
PT
c1 D1 + c2 D2 = j=1 c0j Dj0 . Thus, this decomposition of D is valid. Plus, |c1 | + |c2 | = j=1 |c0j |,ensuring that this decomposition achieves γmin (D).


2.1 Dual SDP for Retrieving Cost
For a quantum channel NA→A0 , the primal SDP characterization of its retrieving cost with respect
to an observable O isγO (N ) = min c1 + c2

(S3a)s.t. JD ≡ JD1 − JD2(S3b)

JD1 ≥ 0, JD2 ≥ 0(S3c)

TrA0o [JD1A0 A0 ] = c1 IA0i , TrA0o [JD2A0 A0 ] = c2 IA0i
i

o

i

(S3d)

o

T
JMA A0 ≡ TrAo A0i [(JN
⊗ IAi A0o )(JidAi Ao ⊗ JDA0 A0 )]
A A0
i

o

o

i

Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

i

(S3e)

o

15

T
T
TrA0o [(IAi ⊗ OA
] = OAi .
0 )JM
o
A A0
i

(S3f)

o

The Lagrange function isL(JD1 , JD2 , c1 , c2 , M, N, K) = c1 + c2 + hM, TrA0o [JD1 ] − c1 IA0i i + hN, TrA0o [JD2 ] − c2 IA0i i
TT+ hK, TrA0o [(IAi ⊗ OA0 )JM ] − Oio(S4)

= c1 (1 − Tr[M ]) + c2 (1 − Tr[N ]) + hM ⊗ I, JD1 i
T
T+ hN ⊗ I, JD2 i − Tr[KO] + hK, TrA0o [(IAi ⊗ OA0 )JM ]io(S5)where M , N , K are the dual variables. The last term can be expanded as
T
T
T
T
hKAi , TrA0o [(IAi ⊗ OA]]0 )JM ]i = Tr[KAi TrA0 [(IAi ⊗ OA0 )JM
o
o
o
A A0
i

(S6)

o

T
T
]
= Tr[(KAi ⊗ OA
0 )JM
o
A A0

(S7)

T
= Tr[(KA⊗ OA0o )JMA A0 ]
i

(S8)

i

i

o

o

T
T
= Tr[(KA⊗ OA0o ) TrAo A0i [(JN
⊗ IAi A0o )(JidAi Ao ⊗ JDA0 A0 )]]
i
A A0
o

i

i

o

(S9)
T
T
= Tr[(KA⊗ JN⊗ OA0o )(JidAi Ao ⊗ JDA0 A0 )]
i
Ao A0
o

(S10)

i

i

T
T
= Tr[(KA⊗ JN⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )(IAi Ao ⊗ JDA0 A0 )]
i
A A0
o

i

i

o

(S11)
T
T
= Tr[TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )]JDA0 A0 ]
i
Ao A0
o
i

i

(S12)
T
T
= hTrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )], JD1A0 A0 i
i
Ao A0
o
i

i

T
T
− hTrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )], JD2A0 A0 i
i
A A0
o

i

i

o

(S13)
Thus, the Lagrange function can be expressed as
L(JD1 , JD2 , c1 , c2 , M, N, K) = c1 (1 − Tr[M ]) + c2 (1 − Tr[N ]) − Tr[KO]TT+ hM ⊗ I + TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )], JD1 i
i
A A0
o

i

T
T
+ hN ⊗ I − TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )], JD2 i
i
A A0
o

i

(S14)
The corresponding Lagrange dual function isg(M, N, K) =inf

JD1 ≥0,JD2 ≥0

L(JD1 , JD2 , M, N, K)(S15)

For JD1 ≥ 0 and JD2 ≥ 0, it must hold that Tr[M ] ≤ 1, Tr[N ] ≤ 1,
T
T
MA0i ⊗ IA0o + TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] ≥ 0, and
i
A A0

(S16)

T
T
NA0i ⊗ IA0o − TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] ≥ 0.
i
A A0

(S17)

o

o

i

i

Thus, we arrive at the following dual SDP:γO (N ) = max − Tr[KO](S18a)

s.t. Tr[M ] ≤ 1, Tr[N ] ≤ 1(S18b)

T
T
MA0i ⊗ IA0o + TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] ≥ 0i
Ao A0(S18c)T
T
NA0i ⊗ IA0o − TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] ≥ 0.
i
A A0

(S18d)ioiAccepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

16

3 Retrieving Cost for GAD channel
A GAD channel can be used to describe the energy dissipation to the environment at finite temperature [45]. 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:



√ 
√
√
1 √0
0

E0 = p, E1 = p
,
(S19)
0 0
0
1−

 √


p
p
0 0
1− 0
,
(S20)
E2 = 1 − p, E3 = 1 − p √ 001
where  is the damping factor and p is the indicator of the temperature of theP3environment. A
quantum state ρ after going through the GAD channel is given by NGAD (ρ) = i=0 Ei ρEi† . Notethat the amplitude damping channel is a special case of the GAD channel when p = 1. A single
ρ00 ρ01
qubit state ρ =after going through the GAD channel isρ10 ρ11
√
1 − ρ01(1 − )ρ√00 + p(ρ00 + ρ11 )
0
,
(S21)
ρ = NGAD (ρ) =1 − ρ10
ρ11 + ρ00 − p(ρ00 + ρ11 )where  and p are noise parameters.
Proposition S3 Given an observable O ∈ {X, Y } and a GAD channel N , the minimum cost γ
1
to retrieve the information Tr[ρO] is γO (N ) = √1−, and the corresponding retriever D can be
written in the form of a Choi matrix
JD = c1 JD1 + c2 JD2 ,where c1 = −c2 = 2√11− , JD1 = 12 OT ⊗ O + 21 I ⊗ I, and JD2 = − 12 OT ⊗ O + 12 I ⊗ I.
1
Proof First, we are going to prove γO (N ) ≤ √1−using SDP (S3). We show that the retriever D
1above is a feasible solution with a cost of √1− . So to be specific, we haveD ◦ N (ρ) = D(ρ0 )

(S22)
0T

= TrA [(ρ ⊗ I) · JD ]1
TrA [(ρ0T ⊗ I)(OT ⊗ O)]
= √
2 1−
1
= √
TrA [ρ0T OT ⊗ IO]
2 1−
1
= √
O Tr[ρ0 O].
2 1−

(S23)
(S24)
(S25)
(S26)

This means that1
Tr[D ◦ N (ρ)O] = √Tr[O2 ] Tr[ρ0 O]
2 1−
1
=√
Tr[ρ0 O]1−= Tr[Oρ],

(S27)
(S28)
(S29)

where the second equality follows from the fact that O2 = I for O ∈ {X, Y }, and the third equality
can be verified with direct calculation using Eq. (S21). Here, we have proven that the retriever D is1
1
a feasible solution to retrieve information with cost √1−
, implying that γO (N ) ≤ |c1 |+|c2 | = √1−.
1Second, we use the dual SDP (S18) to show the cost γO (N ) ≥ √1− . We show that {M, N, K}
is a feasible solution to the dual problem, where M = N = I2 and K = − 2√11− O. To be specific,
we have
T
T
TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )]
i
A A0
o

i

Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

17

X
X
1
O⊗
|jihi| ⊗ N T (|iihj|) ⊗ O)(|mihn| ⊗ |mihn| ⊗ I ⊗ I)]= TrAi Ao [(− √
2 1−
m,n
i,j
X
1
TrAi Ao [O|mihn| ⊗ |jihi|mihn| ⊗ N T (|iihj|) ⊗ O]
=− √
2 1−
i,j,m,nX
1=− √TrAi Ao [O|iihn| ⊗ |jihn| ⊗ N T (|iihj|) ⊗ O]
2 1 −  i,j,nX
1=− √Tr[O|iihn|] Tr[|jihn|]N T (|iihj|) ⊗ O
2 1 −  i,j,n
X
1
Oji N T (|iihj|) ⊗ O,=− √2 1 −  i,j

(S30)
(S31)
(S32)
(S33)
(S34)

where Oji ≡ hj|O|ii. Since O ∈ {X, Y } only has non-zero elements on the anti-diagonal, we have
T
T
⊗ JN
TrAi Ao [(KA⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )]
i
A A0
o

i

1
(O10 N T (|0ih1|) + O01 N T (|1ih0|)) ⊗ O
=− √
2 1−
√
1−
(O10 |1ih0| + O01 |0ih1|) ⊗ O
=− √
2 1−
1
= − O ⊗ O,
2

(S35)
(S36)
(S37)

where the second equality follows from Eq. (S21). This means that
1
1
I ⊗ I − O ⊗ O ≥ 0,
2
2
1
1
T
T
NA0i ⊗ IA0o − TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] = I ⊗ I + O ⊗ O ≥ 0.
i
Ao A0
2
2
i

T
T
MA0i ⊗ IA0o + TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] =
i
A A0
o

(S38)

i

(S39)

Thus, {M, N, K} is a feasible solution to the dual SDP (S18), which means that γO (N ) ≥1
1− Tr[KO] = √1−. Combining this with the primal part, we conclude that γO (N ) = √1−forO ∈ {X, Y } and N being a single-qubit GAD channel.
From the proof, we also know that the above retriever D is optimal. Moreover, since the Choi
matrices of D1 andD2 are given already, it is trivial to oderive the corresponding
Kraus operators,
nq
nq

o
1
1
which are ED1 =2 Ei Ei ∈ {I, X, Y, Z}, Ei O = OEi and ED2 =2 Ei Ei ∈ {I, X, Y, Z}, Ei O = −OEi .
It is interesting to note that there is a connection between the retrieving
 cost and the spectral
O00 O01
properties of the noisy channel and the observable of interest. Let O =be a singleO10 O11
qubit observable. Then,
†
NGAD
(O) =

3
X
i=0

Ei† OEi =√
O00 − (11 − O01√ − p)(O00 − O11 ).
1 − O10
O11 + p(O00 − O11 )

(S40)

√
†
†
For O ∈ X, Y , we have NGAD
(O) = 1 − O and hence Tr[NGAD (ρ)O] = Tr[ρNGAD(O)] =√
1 −  Tr[ρO]. Thus, we need a retrievertoscalestheexpectation
value
back,
and
such
a
retriever√corresponds to a retrieving cost of 1/ 1 − , which aligns with the above proposition. The same
phenomena are observed for the mixed Pauli noises with Pauli observables (see Proposition S5).
Proposition S4 Given an observable O = Z and a GAD channel N , the minimum cost γO (N )to retrieve the information Tr[ρO] is γO (N ) = |1−2p|+1, and the corresponding retriever D can be1−written in the form of a Choi matrix
JD = c1 JD1 + c2 JD1 ,Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

18

where c1 = −c2 = |1−2p|+12(1−) , and(1 − 2p)1
1
Z ⊗Z +I ⊗Z + I ⊗I
2(|1 − 2p| + 1)
2(|1 − 2p| + 1)
21
(1 − 2p)1
JD2 = −Z ⊗Z −I ⊗ Z + I ⊗ I.
2(|1 − 2p| + 1)
2(|1 − 2p| + 1)
2

JD1 =

(S41)
(S42)

Proof First, we are going to prove γO (N ) ≤ |1−2p|+1
by showing that the retriever D is a feasible(1−)
solution to the SDP (S3). To be specific, we haveD ◦ N (ρ) = D(ρ0 )

(S43)
0T

= TrA [(ρ ⊗ I) · JD ]1(1 − 2p)
|1 − 2p| + 1
0T
Z ⊗Z +I ⊗Z= TrA (ρ ⊗ I) ·2(1 − )|1 − 2p| + 1|1 − 2p| + 1
1
(1 − 2p)=
Z Tr[ρ0 Z] +Z Tr[ρ0 ].
2(1 − )2(1 − )

(S44)
(S45)
(S46)

Therefore, we further have1(1 − 2p)
Tr[Z 2 ] Tr[ρ0 Z] +Tr[Z 2 ] Tr[ρ0 ]2(1 − )2(1 − )1=((1 − )ρ00 + p(ρ00 + ρ11 ) − ρ11 − ρ00
(1 − )+ p(ρ00 + ρ11 ) + (1 − 2p)(ρ00 + ρ11 ))Tr[ZD ◦ N (ρ)] =

(S47)

(S48)

= ρ00 − ρ11(S49)= Tr[Zρ],(S50)

where the second equality follows from Eq. (S21) and the fact that Z 2 = I. Hence, the retriever.
D is a feasible solution to retrieve information, implying that γO (N ) ≤ |c1 | + |c2 | = |1−2p|+1
1−Second, we use the dual SDP (S18) to show the cost γO (N ) ≥ |1−2p|+1. To prove this, we are
1−
1
1
1
going to split into several cases: 0 ≤ p < 2 , p = 2 , and 2 < p ≤ 1. First note that
T
T
TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )]
i
Ao A0
i
X
X
= TrAi Ao [(K T ⊗|jihi| ⊗ N T (|iihj|) ⊗ Z)(|mihn| ⊗ |mihn| ⊗ I ⊗ I)]i,j= TrAi Ao [

X

(S51)

m,n

K T |mihn| ⊗ |jihi|mihn| ⊗ N T (|iihj|) ⊗ Z]

(S52)

i,j,m,n=X

Tr[K T |iihn|] Tr[|jihn|]N T (|iihj|) ⊗ Z(S53)

Tr[K T |iihj|]N T (|iihj|) ⊗ Z.

(S54)

i,j,n

=

X
i,j

• When 0 ≤ p < 21 , we set the dual variables {M, N, K} as M = N = |0ih0|, K = − 12 I +2p−1−2(1−) Z and prove that they form a feasible solution to the dual SDP.
T
T
TrAi Ao [(KA⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )]
⊗ JN
i
Ao A0
i

X 1
2p − 1 − =− Tr[|iihj|] +Tr[Z|iihj|] N T (|iihj|) ⊗ Z
22(1 − )
i,j


X
1
2p − 1 − 
N T (|iihi|) ⊗ Z=− + (−1)i
2
2(1
−
)
i

Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

(S55)
(S56)

19


=


p − 1 T − p T
N (|0ih0|) +N (|1ih1|) ⊗ Z
1−
1−

(S57)

= −|0ih0| ⊗ Z(S58)= −|00ih00| + |01ih01|.

(S59)

Therefore,
T
T⊗ JN
MA0i ⊗ IA0o + TrAi Ao [(KA⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] = 2|01ih01| ≥ 0
i
A A0

(S60)

T
T
⊗ JN
NA0i ⊗ IA0o − TrAi Ao [(KA⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] = 2|00ih00| ≥ 0.
i
A A0

(S61)

o

o

i

i

1
• When p = 21 , we set the dual variables {M, N, K} as M = N = 12 I, K = − 2(1−)Z and provethat they form a feasible solution to the dual SDP.
T
T
TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )]
i
Ao A0
i


X
1
Z|iihj| N T (|iihj|) ⊗ Z
=
Tr −
2(1
−
)
i,j

1
(N T (|0ih0|) − N T (|1ih1|)) ⊗ Z
2(1 − )1= − Z ⊗ Z.
2

=−

(S62)
(S63)
(S64)

Therefore,
1
1
I ⊗ I − Z ⊗ Z ≥ 0,
2
2
i
(S65)
1
1
T
T
NA0i ⊗ IA0o − TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] = I ⊗ I + Z ⊗ Z ≥ 0.
i
Ao A0
2
2
i
(S66)

T
T
MA0i ⊗ IA0o + TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] =
i
A A0
o

• When 21 < p ≤ 1, we set the dual variables {M, N, K} as M = N = |1ih1|, K = 12 I + −2p−12(1−)and prove that they form a feasible solution to the dual SDP.
T
T
TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )]
i
Ao A0
i


X 1
 − 2p − 1
Tr[|iihj|] +Tr[Z|iihj|] N T (|iihj|) ⊗ Z
=
2
2(1
−
)
i,j

X 1
i  − 2p − 1=+ (−1)N T (|iihi|) ⊗ Z
2
2(1
−
)
i


−p T
p + 1 −  T=
N (|0ih0|) +N (|1ih1|) ⊗ Z
1−
1−

(S67)
(S68)
(S69)

= |1ih1| ⊗ Z(S70)= |10ih10| − |11ih11|.

(S71)

Therefore,
TT
MA0i ⊗ IA0o + TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] = 2|10ih10| ≥ 0,
i
A A0

(S72)

T
T
NA0i ⊗ IA0o − TrAi Ao [(KA⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] = 2|11ih11| ≥ 0.
⊗ JN
i
A A0

(S73)

o

o

i

i

Hence, we conclude that under different p values, the corresponding solutions {M, N, K} arefor all these cases, which implies
all feasible. It can be easily verified that − Tr[KO] = |1−2p|+1
1−
Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

20

that the inequality γO (N ) ≥ |1−2p|+1
always holds. Combining it with the primal part, we have1−.
γO (N ) = |1−2p|+1
1−
From the proof, we also know that the above retriever D is optimal. Moreover, since the Choi
matrix has been given, the corresponding Kraus operators of the retriever can be easily derived.
• When 0 ≤ p < 12 , the Kraus operators for D1 and D2 are ED1 = {α|1ih1|, |0ih0|, β|0ih1|} andqq
|1−2p|1
ED2 = {|1ih0|, α|0ih1|, β|0ih1|}, where α = 1+|1−2p|
and β = 1+|1−2p|.
• When 12 ≤ p ≤ 1, the Kraus operators for D1 and D2 are ED1 = {|1ih1|, α|0ih0|, β|1ih0|} andqq
|1−2p|1
ED2 = {|0ih1|, α|1ih1|, β|1ih1|}, where α = 1+|1−2p|
and β = 1+|1−2p|.

4 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
NPauli (ρ) = pi ρ + px XρX + py Y ρY + pz ZρZ,

(S74)

where pi , px , py , pz are the corresponding probabilities with pi + px + py + pz = 1 and 0 ≤ p ≤ 1
for each p ∈ {pi , px , py , pz }. For general n-qubit cases, the noisy state isX
NPauli (ρ) =pσ σρσ,(S75)
σwhere the sumPis over all the n-qubit Pauli operators {σ}, and {pσ } are the corresponding probabilities with σ pσ = 1 and 0 ≤ pσ ≤ 1. Note that the depolarizing channel is a special case of
the mixed Pauli channels, where px = py = pz .
Nn
Proposition S5 Given an n-qubit observable O = i=1 σi , where σi ∈ {X, Y, Z, I}, and a mixed
Pauli channel N . The minimum cost γO (N ) to retrieve the information Tr[ρO] is γO (N ) =1PP, and the corresponding retriever D can be written in the form of a Choi matrix
p −
p
σ+

σ+

σ−

σ−

JD = c1 JD1 + c2 JD1 , where JD1 = 21n I ⊗2n + 21n (OT ⊗ O), JD2 = 21n I ⊗2n − 21n (OT ⊗ O) and
c1 = −c2 = 2(P p 1−P p ) . The {σ + } are all the Pauli operators that commute with the
σ+

σ+

σ−

σ−

observable, i.e., σ + ∈ Pn , [σ + , O] = 0, and correspondingly σ − ∈ Pn , {σ − , O} = 0.
Proof First, we are going to prove γO (N ) ≤ P

1P

p +−
σ+ σ

σ−

pσ −

. We prove this by utilizing

SDP (S3) and showing that the retriever D is a feasible solution.
Pstate ρ, after the mixed Pauli channel, it becomes ρ0 = N (ρ) = σ+ pσ+ σ + ρσ + +P For an arbitrary−−σ − pσ − σ ρσ . Then, we haveD ◦ N (ρ) = D(ρ0 )= TrA [(ρ

(S76)
0T

O
⊗ I) · JD]

1
PP
TrA [(ρ0T ⊗ I) · (OT ⊗ O)]
2n · ( σ+ pσ+ − σ− pσ− )
1
P
= n P
TrA [ρ0T OT ⊗ IO]
2 · ( σ+ pσ+ − σ− pσ− )
1
P
= n P
O Tr[ρ0T OT ]2 · ( σ+ pσ+ − σ− pσ− )
=

(S77)
(S78)
(S79)
(S80)
(S81)

Since the transpose is linear, we have Tr[ρ0T OT ] = Tr[(ρ0 O)T ] = Tr[ρ0 O]. Therefore,
D ◦ N (ρ) =2n · (Pσ+

1
PO Tr[ρ0 O]
pσ + − σ − pσ − )Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

(S82)

21

=

=

=

=
=

"

1
2n · (

P

σ + pσ + −P

σ − pσ − )P

σ + pσ + −P

σ − pσ − )P

σ + pσ + −P

σ − pσ − )P

pσ+ σ ρσ +X−

pσ− σ ρσ

−

O
!#

X

O Tr

O Tr

σ + pσ + −P

σ − pσ − )++pσ+ σ ρOσ −

X

σ+

σ−

X

X

−

pσ− σ ρOσ

−

(S84)
!#

pσ+ ρOσ + σ + −pσ− ρOσ − σ −
#

!
X
σ+

(S85)

σ−

σ+

O Tr

(S83)

σ−

σ+

"

1
2n · (+"

1
2n · (

O Tr

+

"

1
2n · (

! #
X

pσ+ −

X

ρO

pσ −

(S86)

σ−

1
O Tr[ρO],
2n

(S87)

where the third equality follows from the commutative properties of {σ+ } and {σ− } with respect tothe observable, the fourth equality follows from the cyclic property of trace, and the fifth equality
follows from the identities that σ + σ + = σ − σ − = I ⊗n . Then, it is easy to check that
1
Tr[O2 ] Tr[ρO]2n1= n Tr[I ⊗n ] Tr[ρO]2= Tr[ρO],

Tr[OD ◦ N (ρ)] =

(S88)
(S89)
(S90)

which means that the retriever D is a feasible protocol, and thus we have γO (N ) ≤ |c1 | + |c2 | =
1P
P
.
σ+

pσ + −σ−pσ −Second, we use the dual SDP (S18) to show that γO (N ) ≥ P

1P

p +−
σ+ σ

σ−

pσ −

.

We setthe dual variables as M = N = 21n I, K = qO, where n is the number of qubits and q ≡− 2n (P p 1−P p ) . We will show the variables {M, N, K} is a feasible solution to the dualσ+σ+

problem.

σ−

σ−

T
T
TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )]
i
Ao A0
i


!
X
X
X
pσ σ T |jihi|σ T ⊗ O|mihn| ⊗ |mihn| ⊗ I ⊗ I  (S91)|jihi| ⊗= TrAi Ao qOT ⊗
σ

i,j

m,n


= TrAi Ao X X

qOT |mihn| ⊗ |jihi|mihn| ⊗ pσ σ T |jihi|σ T ⊗ O(S92)

i,j,m,n σ=XX

qpσ Tr[OT |iihn| ⊗ |jihn|]σ T |jihi|σ T ⊗ O(S93)

qpσ Tr[OT |iihn|] Tr[|jihn|]σ T |jihi|σ T ⊗ O

(S94)

T T
qpσ Oji
σ |jihi|σ T ⊗ O(S95)

i,j,n σ=XX
i,j,n σ

=
=

XX
i,j

σ

X

qpσ σ T OT σ T ⊗ O

(S96)

σ

!
=q

X

T

pσ + O ⊗ O −

σ+

X

T

pσ − O ⊗ O

(S97)

σ−

1
= − n OT ⊗ O,
2

Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

(S98)

22

T
where Oji≡ hj|OT |ii. This implies that

1
1
I ⊗ I − n OT ⊗ O ≥ 0,
22n
2
(S99)
1
1
T
T
NA0i ⊗ IA0o − TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] = 2n I ⊗ I + n OT ⊗ O ≥ 0,
i
Ao A0
2
2
i
(S100)

T
T
MA0i ⊗ IA0o + TrAi Ao [(KA⊗ JN
⊗ OA0o )(JidAi Ao ⊗ IA0i A0o )] =
i
A A0
o

i

which means that {M, N, K} is a feasible solution to the dual SDP (S18). Therefore, we haveγO (N ) ≥ − Tr[KO] = P p −1 P p . Combining this with the primal part, we conclude thatσ+γO (N ) = P
σ

σ+

σ−

1P
.
+ pσ + −− pσ −σ−σ

From the proof, we also know that the above retriever D is optimal. Moreover, from the given
Choi matrix, one could derive that the corresponding Kraus operators of D1 and D2 are(r)
1
Ei Ei ∈ {I, X, Y, Z}⊗n , Ei O = OEi
ED1 =
22n−1
and

(r
ED2 =

1
22n−1

)
⊗n

Ei Ei ∈ {I, X, Y, Z}, Ei O = −OEi.

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 Ndepo (ρ) = (1−)ρ+ I2 , which is equivalent to Eq. (S74) by setting px = py = pz = 4 and pi = 1 − px − py − pz = 1 − 3
4 .
I
The n-qubit depolarizing channel is Nn−depo (ρ) = (1 − )ρ +  2n , by setting the parametersPnin Eq. (S75) as pσ = 4n and pI = 1 − σ pσ = 1 −  4 4−1
n , where {σ} are the n-qubit Pauli
operators excluding I ⊗n , and {pσ } are the corresponding probabilities. It is obvious that I ⊗n+commutes
withP
P any observable, i.e., I ∈ σ . Since the rest probabilities are identical, we haveσ + pσ + −σ − pσ − = 1 − , which means that the retrieving cost for depolarizing channel is1
for O being an n-qubit Pauli operator.
γO (Nn−depo ) = 1−Accepted in Quantum 2023-04-03, click title to verify. Published under CC-BY 4.0.

23