Operational applications of the diamond norm andrelated measures in quantifying the non-physicalityof quantum maps
Bartosz Regula1 , Ryuji Takagi1 , and Mile Gu1,2,3
1 Nanyang Quantum Hub, School of Physical and Mathematical Sciences, Nanyang Technological University, 637371,

Singapore

arXiv:2102.07773v3 [quant-ph] 5 Aug 2021

2 Complexity Institute, Nanyang Technological University, 637371, Singapore
3 Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, 117543, Singapore

Although quantum channels underlie the dynamics of quantum states, maps which
are not physical channels — that is, not completely positive — can often be encounteredin settings such as entanglement detection, non-Markovian quantum dynamics, or error
mitigation. We introduce an operational approach to the quantitative study of the nonphysicality of linear maps based on different ways to approximate a given linear map
with quantum channels. Our first measure directly quantifies the cost of simulating
a given map using physically implementable quantum channels, shifting the difficultyin simulating unphysical dynamics onto the task of simulating linear combinations ofquantum states. Our second measure benchmarks the quantitative advantages thata non-completely-positive map can provide in discrimination-based quantum games.
Notably, we show that for any trace-preserving map, the quantities both reduce to afundamental distance measure: the diamond norm, thus endowing this norm with new
operational meanings in the characterisation of linear maps. We discuss applicationsof our results to structural physical approximations of positive maps, quantification of
non-Markovianity, and bounding the cost of error mitigation.

1 Introduction
It is one of the fundamental properties of quantum mechanics that the evolution of quantum states
is described by linear maps which are completely positive and trace preserving (CPTP), stemmingfrom the unitary dynamics enforced on a larger Hilbert space [1]. However, in several different
settings of practical importance, various applications of quantum dynamics which are not CPTP
can be encountered. This motivates the study of such transformations, and in particular a precise
understanding of how they can be compared with and approximated by physical quantum channels.
One important application of non-CPTP maps is in entanglement detection, where positive but
not completely positive maps can serve as entanglement witnesses [2]. A bipartite state ρ is entangled if and only if there exists a positive map Φ such that id ⊗ Φ(ρ) is no longer a positive operator,
and therefore such a map can reveal the correlations of ρ. This approach has constituted one of themost important ways of detecting entanglement [3, 4], but its experimental implementation encounters an obstacle: how to realise the action of an unphysical linear map in practice? This question
prompted the introduction of structural physical approximations (SPA) of non-CPTP maps [5],which aim to enable the physical evaluation of general maps by designing suitable approximationsin terms of quantum channels and using them to infer properties of the original map [6–8].
Another setting in which non-CPTP maps are encountered is that of non-Markovian quantum
dynamics or, generally, in the reduced dynamics of correlated systems. Specifically, when an
Bartosz Regula: bartosz.regula@gmail.com
Ryuji Takagi: ryuji.takagi@ntu.edu.sg
Mile Gu: mgu@quantumcomplexity.org

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

1

open quantum system shares some initial correlations with its environment, the evolution of thecomposite system-environment state can correspond to a non-CPTP map when looking only at the
dynamics of the reduced state of the system [9–12]. Although the physical interpretation of this isa matter of debate and alternative ways to understand such dynamics have been proposed [13–15],
it can nevertheless be useful to study such non-CPTP evolutions directly to gain an understandingof reduced dynamics of open quantum systems.
Even broader types of unphysical quantum dynamics can be found in the areas of quantum
error correction and error mitigation [16–18]. This is because, in a broad sense, both of thesesettings are concerned with the following problem: if an unknown system has undergone a noisy
evolution as ρ 7→ Θ(ρ), how can we reconstruct the original state as closely as possible, that is,
how to implement a map Φ such that Φ ◦ Θ(ρ) ≈ ρ? Such inverse operations typically cease to bevalid quantum channels, and so it becomes necessary to devise approaches to implement them inpractice with the use of physical operations.
In this work, we introduce a general quantitative framework for the characterisation of such
unphysical maps by approximating them with quantum channels. We then explicitly give theconsidered measures operational meaning by connecting them with the performance of practicaltasks, including the cost of simulating a given map with quantum channels. Notably, we showthat all of the considered measures reduce to the same quantity when the given linear map is trace
preserving: they all equal the diamond norm [19, 20], a fundamental computational tool that serves
as a measure of quantum channel distance and finds many uses in the practical characterisationof quantum processes [21]. This endows the diamond norm with new meanings in the operationaltasks that we consider, and furthermore allows a number of new connections to be established. On
the one hand, many known results in the quantification of the diamond norm can be carried overto the setting of our work, and on the other hand, we can use our characterisation to provide new
insight into the computation and applications of the diamond norm.
Our approach is based on the notion of robustness measures [22] — inspired by recent applications of such quantities in the study of general resource theories of channels [23–33], we use them toquantify the amount of noise needed to turn a given map into a quantum channel. Such measures
allow for several different generalisations to the setting of linear maps, motivating us to study
and compare these definitions. The robustness-based approaches can be understood as different
ways of designing optimal decompositions of linear maps in terms of quantum channels, and sothey generalise the standard structural physical approximations [5]. We express the measures assemidefinite programs and establish various relations and bounds between them.
We apply our first measure in the task of simulating the action of an unphysical map withvalid channels, accomplished by allowing the use of ancillary systems which can consists of linear
combinations of quantum states. Such an approach allows us to reduce the problem of simulating
the dynamics of quantum systems to the much simpler case of simulating the use of a non-positive
Hermitian operator. Assessing the difficulty of this procedure then reduces to quantifying how
much the given operator deviates from being a valid quantum state, and — employing the trace
norm as a natural quantifier of such ‘non-quantumness’ — we show that the optimal cost of
simulating a non-CPTP map in this way is given exactly by the value of the robustness measure.
Furthermore, answering the question of whether any unphysical map can provide measurable
operational advantages over quantum channels, we show this to be the case in the setting of
discrimination-based quantum games, establishing our second robustness measure as the exact
quantifier of this advantage.
Our results also generalise and shed light on the very recent findings of Ref. [33], which considered a similar framework for approximating trace-preserving maps using a robustness- andquasiprobability-based approach. In particular, we show that the measure considered in [33] isactually an alternative expression for the diamond norm of a map, rather than a new quantity.
The paper is structured as follows. In Sec. 2, we introduce the notions of robustness measuresand show how they can be applied to non-CPTP linear maps. We establish precise connections
with the diamond norm in Sec. 3. We then proceed to show that the robustness measures —and hence the diamond norm — play a crucial role in quantifying the cost of simulating linear
maps (Sec. 4) as well as in understanding the advantages a non-CPTP map could provide in inputoutput quantum games (Sec. 5). We proceed to establish a number of bounds for the measures inSec. 6. Finally, we discuss the applications of our approach, comparisons with other methods, andexplicitly show how the measures can be evaluated for some representative examples in Sec. 7.
Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

2

2 Robustness of non-CP maps
Let A and B denote two finite-dimensional quantum systems of dimension dA and dB , respectively.
We will use L(A) to denote the set of all linear operators, H(A) to denote the set of all Hermitian
operators, and D(A) to denote all density operators acting on the Hilbert space of system A. We
use hX, Y i = Tr(X † Y ) for the Hilbert-Schmidt inner product.
Among all linear maps from L(A) to L(B), we will be primarily concerned with Hermiticitypreserving maps H(A, B), which are defined as maps such that Φ(X) ∈ H(B) ∀X ∈ H(A). A
map is called positive if Φ(X) ≥ 0 ∀X ≥ 0 (w.r.t. the positive semidefinite cone), completely
positive (CP) if idA ⊗ Φ is positive, trace preserving if Tr Φ(X) = Tr X ∀X, and trace nonincreasing if Tr Φ(X) ≤ Tr X ∀X. To each map Φ ∈ P
H(A, B) we will associate the Choi operator
JΦ = (idA ⊗ Φ)[|ΩihΩ|] ∈ H(A ⊗ B) where |Ωi =i |iii. Importantly, a map is Hermiticitypreserving iff JΦ = JΦ† , CP iff JΦ ≥ 0, and trace preserving iff TrB JΦ = 1A (see e.g. [21]). Let
CPTNI(A, B) denote the set of completely positive and trace–non-increasing maps in H(A, B), andanalogously CPTP(A, B) the set of completely positive and trace-preserving maps. For simplicity
of notation, we will often simply write CPTP for CPTP(A, B) (and analogously for other sets)
when the spaces in consideration are not relevant.
In order to quantify how much a given map deviates from the set of CPTP maps, we will employ
the concept of robustness measures [22]. It will be insightful to first review how such measures
are defined for quantum states. Given a convex set of interest F ⊆ D, commonly chosen to be
the set of free states in a given resource theory, one asks: how much noise from a set N ⊆ D has
to be added to a state ρ in order to make it a free state? This has the intuitive interpretation of
measuring how robust the resources contained in the state ρ are with respect to noise from the set
N . Specifically, we writeρ + λω=: σ ∈ F, ω ∈ N .
(1)rN (ρ) := min λ1+λThe most common choices of the noise set N are: N = D, in which case we obtain the so-called
generalised robustness equivalently given bynorD (ρ) = min λ ρ ≤ (1 + λ)σ, σ ∈ F ,(2)and the choice N = F, which corresponds to the standard robustness rF . The latter quantity is
directly related to the so-called base norm kρk F of the set F, which can be alternatively understoodas an optimisation of quasiprobability distributions over the set F:
2rF (ρ) + 1 = kρk Fno:= min λ+ + λ− ρ + λ− σ− = λ+ σ+ , σ± ∈ F
(
)
X
X
= min
|λi | ρ =λ i σi , σ i ∈ F
i

(3)

i

where the third line is a simple consequence of the convexity of F. The definitions straightforwardly
extend to unnormalised operators X: defining
X + λωrN (X) := min λ=: σ ∈ F, ω ∈ N ,(4)
Tr X + λit is important to notice that the trace of X will come into play, and the base norm will equal
kXk F = 2rF (X) + Tr X.
The case of interest to us will be where the set of free states F contains all physical quantum
states, F = D, in which case the different notions of the robustness are equal and one has
2rD (X) + Tr X = kXk 1 ,(5)that is, the base norm is precisely the trace norm (Schatten 1-norm) k·k 1 .

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

3

Robustness of linear maps. A generalisation of these concepts to the case of linear maps canbe done in several different ways. Firstly, one has to note that it does not suffice to consider tracepreserving maps in the definitions of this measures. This follows since any linear combination of
CPTP maps necessarily satisfies that TrB JΦ ∝ 1, which means that Tr Φ(ρ) takes the same value
for any input state ρ. Therefore, any Hermiticity-preserving map whose reduced Choi matrix is
not proportional to the identity operator cannot be represented as λ+ Λ+ − λ− Λ− for CPTP Λ± .
To circumvent this, we will employ the set of completely positive and trace–non-increasing maps,
which can be understood as probabilistic implementations of quantum channels. Importantly,
robustness-based definitions which were all equal in the case of states might not be equal any more.
We therefore need to explicitly consider three different types of the robustness w.r.t. the sets CPTP
or CPTNI:Φ + λΛ
R(Φ) := min λ∈ CPTNI, Λ ∈ CPTNI ,
(6)
1+λ
n
o
R0 (Φ) := min λ | JΦ ≤ (1 + λ)JΛ , Λ ∈ CPTNI(7)no= min λ | JΦ ≤ (1 + λ)JΛ , Λ ∈ CPTP ,on(8)
R00 (Φ) := min λ Φ + λΛ ∈ CP, Λ ∈ CPTNIno= min λ Φ + λΛ ∈ CP, Λ ∈ CPTP ,as well as a generalised notion of a base norm with respect to the set of completely positive andtrace–non-increasing maps:nokΦk := min λ+ + λ− Φ = λ+ Λ+ − λ− Λ− , Λ± ∈ CPTNI .
(9)
In the expressions for R0 and R00 , we made use of the fact that one can, without loss of generality,
restrict the optimisation to CPTP maps; this follows since for any Λ ∈ CPTNI such that TrB JΛ ≤1A we can define the map Λ0 by JΛ0 = JΛ + dCB ⊗ 1B where C = 1A − TrB JΛ ≥ 0 which satisfies
Λ0 ∈ CPTP and achieves the same value of the objective function. We note that closely related
definitions were recently also considered in Ref. [33] for the case of trace-preserving maps.
All of the quantities above are well-defined and take a finite value for any map Φ ∈ H(A, B), as
we shall see explicitly by establishing general upper bounds in Sec. 6. The robustness R(Φ) can beseen to be an upper bound for all other quantities: any feasible decomposition of Φ in Eq. (6) gives
feasible solutions for Eq. (7), (8), and for the base norm in Eq. (9). It is a priori unclear whether
one can find general conditions under which the inequalities between the different measures aretight. We shall shortly see that equality indeed holds for all trace-preserving linear maps.
All of the introduced quantities can be computed as semidefinite programs, which follows since
the constraints for a map to be CPTNI (or CPTP) are linear matrix inequalities. This means thatthe measures can be evaluated efficiently (in the dimensions of the map) using numerical software.
The equivalent dual forms of the problems, which can also provide some insight into the differences
between the different definitions of the robustness measures, will be reported shortly in Sec. 6.

3 Relation with the diamond norm
For any Hermiticity-preserving map Φ, the diamond norm (completely bounded trace norm) isdefined as [19, 21]kΦk♦ = max kidA ⊗ Φ (ρ)k 1 ,(10)ρ∈D(A⊗A)

where, in a slight abuse of notation, we use D(A ⊗ A) to denote the states acting on a bipartite
Hilbert space composed of the space A and another space isomorphic thereto.
The diamond norm finds use as a fundamental measure of distance between quantum channels, mirroring the operational role of the trace distance in measuring distances between quantum
states [19, 21, 34, 35]. It is one of the most widely employed figures of merit in comparing quantum
channels and benchmarking channel manipulation protocols. Its quantification and characterisation is therefore crucial to an effective understanding of the properties of quantum processes. Close
Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

4connections between the diamond norm and the base norm in the space of quantum channels canbe inferred already from the operational similarity that the diamond norm bears to the trace norm,
the latter being the natural base norm in the space of quantum states. Here we aim to clarify
the details of such connections and to explicitly relate the diamond norm with the robustness
measures.
We will first introduce the following lemma, which establishes a useful formulation of the
diamond norm for Hermiticity-preserving maps. The result is closely related to a more generalapproach for generalised quantum channels considered previously by Jenčová [36], and can bealternatively deduced from Lem. 4 and Thm. 2 of [36].
Lemma 1. For any Hermiticity-preserving map Φ, it holds thatonkΦk♦ = min µ JΦ = M+ − M− , M± ≥ 0, TrB (M+ + M− ) ≤ µ1Aon= min µ JΦ = M+ − M− , M± ≥ 0, TrB (M+ + M− ) = µ1A .

(11)
(12)

0

Proof. Let kΦk♦ denote the quantity in (12). We first notice that the constraint TrB (M+ + M− ) =µ1A can be relaxed to TrB (M+ + M− ) ≤ µ1A without loss of generality. This follows since forany feasible M± s.t. TrB (M+ + M− ) + C = µ1 with C ≥ 0, one can define feasible solutions
000M±= M± + 2dCB ⊗ 1B which satisfy TrB (M++ M−) = µ1A and thus achieve the same optimalvalue. We thus haveno0kΦk♦ = min µ JΦ = M+ − M− , M± ≥ 0, TrB (M+ + M− ) ≤ µ1Ano(13)= min kTrB (M+ + M− )k ∞ JΦ = M+ − M− , M± ≥ 0 .
Taking the Lagrange dual of the above (see Appendix A) givesno0kΦk♦ = max hJΦ , W i − ρ ⊗ 1B ≤ W ≤ ρ ⊗ 1B , ρ ∈ D(A)no
= sup hJΦ , W i − ρ ⊗ 1B ≤ W ≤ ρ ⊗ 1B , ρ ∈ D>0 (A)
nD p
E
o
p
= sup
W, ρ ⊗ 1B JΦ ρ ⊗ 1B
ρ ∈ D>0 (A), −1A⊗B ≤ W ≤ 1A⊗B
p
p
= sup
ρ ⊗ 1 B JΦ ρ ⊗ 1 B
1

ρ∈D>0 (A)= max
ρ∈D(A)(14)p

ρ ⊗ 1 B JΦp

ρ ⊗ 1B,1

where in the second line, by continuity, we restricted our attention to the set of full-rank statesD
p>0 (A) without
p loss of generality, and in the third line we made the change of variables W 7→
ρ−1 ⊗ 1B W ρ−1 ⊗ 1B . The fact that this equals the diamond norm of Φ can be deduced fromthe results of Ref. [37] already; for completeness, we will show this explicitly. Recalling thatJΦ = (idA ⊗ Φ) |ΩihΩ| with |Ωi being the unnormalised maximally entangled state, and using thefact that Φ is only acting on one of the subsystems, we can writepp0kΦk♦ = max
ρ ⊗ 1B (idA ⊗ Φ) [|ΩihΩ|] ρ ⊗ 1B
ρ∈D(A)√= max k(idA ⊗ Φ) [ ρ ⊗ 1A |ΩihΩ|ρ∈D(A)=maxψ∈D(A⊗A)=

max
ρ∈D(A⊗A)√1

ρ ⊗ 1A ]k 1

kidA ⊗ Φ (ψ)k 1(15)

kidA ⊗ Φ (ρ)k 1= kΦk♦

√√where we used that any pure state ψ ∈ D(A ⊗ A) can be written asρ ⊗ 1A |ΩihΩ| ρ ⊗ 1A
for a suitable choice of ρ ∈ D(A), with |ψi constituting the canonical purification of ρ.
Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

5Compared with the semidefinite programs for the diamond norm of general linear maps originally derived in Refs. [37, 38], the form of the diamond norm presented in Lemma 1 alreadyconstitutes a major simplification — both at a conceptual level, allowing for a restatement of the
problem in terms of optimising over decompositions of the form JΦ = M+ − M− , and computationally, as the number of optimisation variables is reduced.
As an immediate consequence of the above result, we can use the characterisation of the diamondnorm in Eq. (11) to construct valid feasible solutions for the base norm and robustness measuresin Eqs. (6)–(9), and vice versa.
Corollary 2. For any Hermiticity-preserving map Φ, it holds that
2 kΦk♦ ≥ kΦk ≥ kΦk♦ ,
1kΦk♦ − 2 + λmin (TrB JΦ )kΦk♦ + 1 ≥ R0 (Φ) ≥
2

1
00
kΦk♦ ≥ R (Φ) ≥kΦk♦ − λmax (TrB JΦ ) ,2(16)

where λmin and λmax denote, respectively, the smallest and the largest eigenvalues.
Proof. Any decomposition for the diamond norm of the form JΦ = M+ −M− with TrB (M+ +M− ) ≤µ1A satisfies TrB M± ≤ µ1A , which provides valid feasible solutions to the norm k·k and therobustness measures. On the other hand, any decomposition for k·k of the form Φ = λ+ Λ+ − λ− Λ−with Λ± ∈ CPTNI gives a feasible decomposition for the diamond norm with TrB (λ+ JΛ+ +λ− JΛ− ) ≤(λ+ + λ− )1A . Similarly, any decomposition for R0 satisfying JΦ ≤ (1 + λ)JΛ gives a feasible
decomposition for k·k♦ of the form JΦ = (1 + λ)JΛ − M− where M− := (1 + λ)JΛ − JΦ . Using that
TrB [(1 + λ)JΛ + M− ] = TrB [2(1 + λ)JΛ − JΦ ]≤ [2(1 + λ) − λmin (TrB JΦ )] 1A ,(17)

we get the stated bound. The case of R00 follows analogously.
Equality between the different quantities can be shown for all trace-preserving maps, directly
relating the diamond norm with our considered measures.
Theorem 3. For any map Φ ∈ H(A, B) which is trace preserving or, more generally,
proportional to a trace-preserving map in the sense that TrB JΦ ∝ 1, it holds thatnokΦk♦ = kΦk = min µ+ + µ− JΦ = µ+ JΛ+ − µ− JΛ− , Λ± ∈ CPTP, µ± ∈ R+ . (18)
For trace-preserving maps Φ, it additionally holds that
R(Φ) = R0 (Φ) = R00 (Φ) =kΦk − 1kΦk♦ − 1
=
.
2
2

(19)

Proof. From the fact that TrB JΦ = t1A for some t ∈ R, it is easy to see that every decompositionof the form JΦ = M+ − M− , M± ≥ 0, TrB (M+ + M− ) = µ1A as in Lemma 1 has to satisfy
TrB M+ =

µ+t
1A ,
2

TrB M− =

µ−t
1A .
2

This implies that we can equivalently writenokΦk♦ = min µ+ + µ− JΦ = µ+ M+ − µ− M− , M± ≥ 0, TrB M+ = TrB M− = 1A

(20)

(21)

which is precisely Eq. (18). Notice then that any such decomposition gives a valid feasible solution
for kΦk , together with Cor. 2 yielding equality between the two norms.

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

6

When Φ is trace preserving (t = 1), we can writeonkΦk♦ = min µ+ + µ− JΦ = µ+ JΛ+ − µ− JΛ− , Λ± ∈ CPTPon= min 2µ+ − 1 JΦ = µ+ JΛ+ − µ− JΛ− , Λ± ∈ CPTPon= min 2µ− + 1 JΦ = µ+ JΛ+ − µ− JΛ− , Λ± ∈ CPTP .

(22)

The equality kΦk♦ = 2R0 (Φ) + 1 = 2R00 (Φ) + 1 then follows: on the one hand, any decomposition of
the form in Eq. (22) gives a feasible decomposition for R0 and R00 in Eqs. (7)–(8), and on the other
hand, any decomposition for the robustness measures is necessarily of the form in Eq. (22). Equality
with the robustness R(Φ) follows by noting again that any feasible decomposition in Eq. (22) givesa feasible decomposition for R(Φ), and on the other hand using the relation R(Φ) ≥ R0 (Φ) whichholds by definition.
Remark. The expression in Eq. (18) is valid also in the case of trace-annihilating maps (TrB JΦ = 0),
and thus the case of computing the distance kΛ − Λ0 k♦ between two quantum channels. A simplified
expression for this problem appeared previously in [37] and was explicitly expressed as a robustnesstype measure in [26].
We note that the quantity k·k , applied to trace-preserving maps, was recently considered inRefs. [33] and [39]. It was not noticed in these works that this is simply the diamond norm, andhence many results shown in [33] (e.g. the multiplicativity with respect to tensor product, unitaryinvariance, bounds with trace norm kJΦ k 1 , monotonicity under the action of superchannels, andsome explicit expressions) follow directly from known properties of the diamond norm [20, 37, 40,
41].
We will later see that this equivalence does not extend to maps which are not trace preserving(or proportional thereto), and indeed we can have kΦk = 2 kΦk♦ in the extreme case.

4 Quantifying simulation cost
Since the quantum dynamics which can be realised in practice are restricted to completely positive
maps, a relevant question then becomes: how can one simulate the action of a non-CPTP map on
a quantum state when only CPTP maps are available to us?
A similar question was recently asked in Ref. [33], where the authors applied quasiprobability
sampling methods [17, 30, 42] to the desired operation Φ. We take a different approach here andinstead allow for the use of an ancillary system X, which can be an affine combination of quantum
states, in order to simulate the action of the map Φ as a CPTP map Λ acting jointly on the input
quantum state and the ancilla X. The “non-physicality” of the given map Φ is then pushed into
the system X, allowing for the overall transformation Λ to be a valid quantum channel.
The motivation for this approach is that the task of simulating the action of the non-CPTP
map Φ is effectively replaced with the simulation of a unit-trace Hermitian operator X, which
could be significantly easier to realise in practice, especially since we will see that the dimensionof the ancilla can be taken to be arbitrarily small. Standard quasiprobability-based approaches
such as the ones employed in [17, 30, 33] aim to estimate the expectation value Tr[Φ(ρ)A], whereΦ is a non-CPTP map and A an observable, by decomposing the given map as Φ = λi Λi withλi ∈ R and Λi ∈ CPTP (or CPTNI). The expectation value Tr[Φ(ρ)A] is then estimated byevaluating Tr[Λi (ρ)A] and appropriately sampling from the output distributions with probabilities
determined by the coefficients λi [17, 42]. In practice, this means that we have to repeatedly
realise each operation Λi , which requires the implementation of a different quantum circuit foreach operation. Consider, on the other hand, a situation in which the dynamics is fixed as somemap Λ ∈ CPTNI, and we only need to vary the input states. This can be achieved by writing
Φ(·) = Λ(·P ⊗ X), where we can write any Hermitian operator in a quasiprobability representationas X = i µi ρi . The task of sampling from the output distribution is then reduced to feeding in
the different states ρi into the circuit which realises the fixed operation Λ, thus greatly simplifying
the implementation.
As mentioned in Sec. 2, a natural quantifier of how much a given operator X ∈ H(A) with
Tr(X) = 1 deviates from the set of all quantum states is the trace norm kXk 1 . Indeed, thisAccepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

7quantity can be given an explicit interpretation in terms of the optimal cost of a quasiprobabilitybased estimation of the expectation value of X [42]. We then define the simulation cost of a map
as the minimal amount of such “non-physicality” of X needed to simulate the action of the map:on(23)
S(Φ) := min kXk 1 Λ(· ⊗ X) = Φ(·), Tr(X) = 1, Λ ∈ CPTNI .
We then have the following.
Theorem 4. For any map Φ ∈ H(A, B), it holds that
S(Φ) = 2R(Φ) + 1.

(24)

In the case of a trace-preserving Φ, we have in particular that
S(Φ) = kΦk♦(25)

and an optimal Λ for the simulation can be chosen to satisfy Λ ∈ CPTP.
Proof. Let Λ± ∈ CPTNI(A, B) be maps that achieve an optimal decomposition for Φ such that
Φ = (1+R(Φ))Λ+ −R(Φ)Λ− . Now, consider a non-positive Hermitian operator X = µ+ ω+ −µ− ω− ∈H(A0 ) where ω± are orthogonal quantum states and Tr[X] = µ+ − µ− = 1. We do not impose any
additional conditions on the size of the ancillary system A0 , meaning that its Hilbert space can bechosen to be an arbitrary space of dimension at least 2. Defining the projector onto the positive partof X as P+ , we then consider the map defined by the action on a basis |i1 ihj1 | ⊗ |i2 ihj2 | ∈ L(A ⊗ A0 )as follows:





P+
P+
Λ(|i1 ihj1 | ⊗ |i2 ihj2 |) := Tr|i2 ihj2 | Φ(|i1 ihj1 |) + Tr 1 −|i2 ihj2 | Λ− (|i1 ihj1 |)
µ+
µ+


P+
|i2 ihj2 | Λ+ (|i1 ihj1 |)(26)= (1 + R(Φ)) Tr
µ+



P+
+ Tr 1 − (1 + R(Φ))|i2 ihj2 | Λ− (|i1 ihj1 |)µ+It is easy to check that Λ(ρ ⊗ X) = Φ(ρ). Now, we will show that as long as the conditionP+ρ ≤ 1 ∀ρ(27)
(1 + R(Φ)) Trµ+is satisfied, then Λ is also CPTNI. This can be seen by observing first that (27) gives
0 ≤ P̃ := (1 + R(Φ))

P+
≤ 1,
µ+

(28)

which implies that P̃ is a valid POVM element. Note that we can rewrite (26) asΛ==Λ+ ⊗ TP̃ + Λ− ⊗ T1−P̃(1 ⊗ TP̃ )(Λ+ ⊗ 1) + (1 ⊗ T1−P̃ )(Λ− ⊗ 1)

(29)
(30)

where TP (·) := Tr [P ·]. Since Λ+ , Λ− , and TP̃ , T1−P̃ are all completely positive, Λ is also completely
positive. Since (27) is always satisfied whenµ+ ≥ 1 + R(Φ),(31)

an operator X with kXk 1 = µ+ + µ− = 1 + 2R(Φ) achieves the desired implementation.
The converse part can be proven by extending an argument in Ref. [23] to our setting. Supposea non-quantum resource X = µ+ ω+ − µ− ω− and CPTNI map Λ realise the simulation of Φ, i.e.
Φ(·) = Λ (· ⊗ X). Also, define Λ+ (·) := Λ(· ⊗ ω+ ). Then, by linearity of Λ, we getΛ+ (·)==11
Λ(· ⊗ X) +Λ(· ⊗ µ− ω− )
µ+
µ+
1
µ−
Φ(·) +
Λ(· ⊗ ω− ).
µ+µ+Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

(32)
(33)

8

Since Λ+ and Λ− := Λ(· ⊗ ω− ) are CPTNI maps, this is a valid linear decomposition of Φ into two
CPTNI maps, providing an upper bound for its robustness as R(Φ) ≤ µ− = µ+ − 1. This gives thedesired lower bound for the simulation cost as µ+ + µ− ≥ 1 + 2R(Φ).
An interesting quantitative equivalence emerges between our approach and the method ofRef. [33]. In that work, the authors showed that the minimal overhead required to employ
quasiprobability-based simulation techniques [17, 42] to estimate Tr[Φ(ρ)A] for a trace-preserving
map Φ scales with the norm kΦk (see also the discussion in Sec. 7.2). Since we know from Thm. 3that
2R(Φ) + 1 = kΦk = kΦk♦(34)
holds for any trace-preserving map, the quantitative cost of the simulation scheme is actually thesame as our method, despite the seemingly different approaches employed. In fact, our Thm. 4shows that it is sufficient to consider decompositions of Φ asΦ(·) = µ+ Λ(· ⊗ ω+ ) − µ− Λ(· ⊗ ω− )(35)

where Λ and X = µ+ ω+ − µ− ω− are as constructed in our protocol. This means that, despite
the significant practical simplification obtained by fixing the dynamics of the simulator as Λ andoptimising over the quasiprobability representations of X instead, our simulation method does not
sacrifice any performance, and the optimal sampling overhead cost of the more direct approach of[33] cannot be any better.
We note that Theorem 4 gives a general way of reducing the task of simulating the actionof a linear map Φ to simulating an affine combination of states in the form of the operator X.
This could provide methods for the simulation of dynamics even beyond quasiprobability-based
approaches like the one discussed above, although the specifics of this will depend on the given
simulation method.
State injection and resource simulation. The setting considered here is closely related tostate injection methods which generalise quantum teleportation [43] and find use e.g. in the resource
theories of entanglement [44–48], stabiliser-state quantum computation [49, 50], and coherence [23,51]. In such tasks, a resourceful state φ (such as a maximally entangled singlet) is used to simulate
the action of an arbitrary quantum channel Θ as Θ(·) = Γ(· ⊗ φ), where now Γ is a free operation(such as a protocol consisting of local operations and classical communication only). In this sense,
our result can be thought of as the cost of channel simulation in the resource theory of “nonphysicality” beyond quantum mechanics, with the operator X acting as a resource. There aremany potential ways to interpret such a result: for instance, unit-trace Hermitian operators which
are not necessarily positive semidefinite have found use as so-called pseudo-states in [52], where
they were used to study correlations beyond quantum mechanics, and as so-called pseudo-density
matrices in [53], where they were used to put spatial and temporal correlations on equal footing.
Being able to use a Hermitian system X could then be interpreted as having access to such extended
sets of correlations. We leave a precise investigation of the connections between the operationalsetting employed here and resource theories of correlations for future work.
Amortised simulation. A related setting that we can consider is that of amortised simulation[23, 54], in which the non-quantum resource X is not consumed completely, but instead we canrecover some of it in the form of another resource Y which can be reused. Precisely, we define


kXk 1
SA (Φ) = minΛ(· ⊗ X) = Φ(·) ⊗ Y, Tr(X) = Tr(Y ) = 1, Λ ∈ CPTNI .
(36)
kY k 1
Clearly, SA (Φ) ≤ S(Φ) as we can just take X to be optimal for S and Y to be the trivial system
1. One could expect amortisation to lead to a strictly smaller cost of simulating a given map.
However, we can show that this is not the case — amortisation cannot improve the simulation costof any trace-preserving map.

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

9

Corollary 5. For any trace-preserving map Φ ∈ H(A, B), it holds that
SA (Φ) = S(Φ) = kΦk♦ .

(37)

Proof. Let Λ be the optimal map such that Λ(· ⊗ X) = Φ(·) ⊗ Y with SA (Φ) = kXk 1 / kY k 1 .
Noting that this can be alternatively understood as a simulation protocol for the trace-preserving
map Φ(·) ⊗ Y , Thm. 4 tells us that any such protocol satisfies
kXk 1 ≥ S (Φ(·) ⊗ Y )= kΦ(·) ⊗ Y k♦
= kΦk♦ kY k 1(38)= S(Φ) kY k 1
where we used the multiplicativity of the diamond norm and the fact that kY k♦ = kY k 1 where wetreat Y as a preparation channel with a trivial input space. From this we have that SA (Φ) ≥ S(Φ),
which concludes the proof.

5 Quantifying advantages in quantum games
The study of general linear maps in a resource-theoretic setting motivates the question: is there awell-defined operational task in which having access to any non-CPTP map could provide practicaladvantages over all quantum channels?
In order to give an instance of such a task, we consider the setting of input-output games,
inspired by the work of Ref. [55] and studied in the context of dynamical quantum resourcesin [27, 28]. The setting is as follows: Alice prepares a state chosen randomly from the ensemble{pi , σi }i and sends the state through the map Φ ∈ H(A, B) to Bob, who then measures with a
POVM {Mj }j . The players are then awarded a score based on a reward function characterised by
the coefficients {wij }i,j ∈ R, and their goal is to maximise the average payoff given byX
P (Φ, {pi , σi }, {Mj }, {wij }) =wij pi hMj , Φ(σi )i
(39)
i,j

by a suitable choice of the states and measurements. The tuple G = ({pi , σi }, {Mj }, {wij }) thendefines the input-output game G.
We stress that, although the payoff P (Φ, G) might lose its physical meaning as a discrimination
task when Φ is an arbitrary linear map, already for a positive trace-preserving map Φ we havethat every output Φ(σi ) is indeed a valid density matrix and thus the measurement at the output
constitutes a well-defined state discrimination task.
We are then interested in quantifying the best possible advantage that a given map Φ could
provide over CPTP maps. Such an optimisation is unbounded without any further constraints, so
we will consider games for which any completely positive map Γ achieves a non-negative payoff
value — this can always be ensured by suitably shifting the payoff function for a given game. We
then have the following.
Theorem 6. For any map Φ ∈ H(A, B), it holds that
supG

P (Φ, G)
= R0 (Φ) + 1
maxΛ∈CPTP P (Λ, G)(40)

where the maximisation is over all input-output games G such that P (Γ, G) ≥ 0 ∀Γ ∈ CP.
In the case of a trace-preserving Φ, we have in particular that
supGkΦk♦ + 1
P (Φ, G)=,maxΛ∈CPTP P (Λ, G)
2(41)

and it suffices to optimise over games such that P (Λ, G) ≥ 0 ∀Λ ∈ CPTP.

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

10

Proof. Any Φ can be written as Φ = (1 + R0 (Φ))Λ − Γ where Λ ∈ CPTP, Γ ∈ CP. On the one
hand, we then have for any G that
P (Φ, G) = (1 + R0 (Φ)) P (Λ, G) − P (Γ, G)≤ (1 + R0 (Φ)) P (Λ, G)(42)≤ (1 + R0 (Φ)) max P (Λ, G)
Λ∈CPTP

where the first inequality follows since P (Γ, G) ≥ 0 ∀Γ ∈ CP, which shows that the left-hand side ofEq. (40) is upper-bounded by the right-hand side. By Thm. 3, in the case of a trace preserving
map Φ we can equivalently write Φ = (1 + R0 (Φ))Λ+ − R0 (Φ)Λ− where Λ± ∈ CPTP, so one only
needs to consider games such that P (Λ, G) ≥ 0 ∀Λ ∈ CPTP.
On the other hand, by strong Lagrange duality (see App. A) we can writenoR0 (Φ) + 1 = max hW, JΦ i 0 ≤ W ≤ ρ ⊗ 1B , ρ ∈ D(A) .
(43)
We can then make the following observations. Firstly, since the set of separable states
Pnin D(A ⊗ B)
has a non-empty interior [56], any Hermitian operator X can be written as X = i=1 xi σi ⊗ ηifor some σi ∈ P
D(A), ηi ∈ D(B), xi ∈ R, and n ∈ N. Then, choose the optimal W in Eq. (43) andnwrite W TA = i=1 xi σi ⊗ ηi , where TA denotes the partial transpose. Defining the set {Mi }n+1
i=1P
Pnby Mi := ηi /
η
for
i
≤
n
and
M
=
1
−
M
,
we
have
that
j
n+1
i
j
i=1
∞

W =

X

pi wi σiT ⊗ Mi

(44)

i

where pi = 1/n for i ≤ n and pn+1 = 0, and the coefficients wi are defined by wi = xi n
By the Choi-Jamiołkowski isomorphism and the linearity of Φ, we then have for Φ thatX
hW, JΦ i =pi wi hMi , Φ(σi )i = P (Φ, G 0 )

P

j ηj

∞

.

(45)

i

with G 0 defined by the above choices of {pi , σi }, {Mi }, and {wi }. Noticing that W ≥ 0 ⇒ P (Γ, G 0 ) ≥0 ∀Γ ∈ CP, this finally gives
supG

P (Φ, G 0 )P (Φ, G)≥maxΛ∈CPTP P (Λ, G)
maxΛ∈CPTP P (Λ, G 0 )
R0 (Φ) + 1≥
maxΛ∈CPTP R0 (Λ) + 1= R0 (Φ) + 1(46)

where the second inequality follows since P (Φ, G 0 ) = hW, JΦ i = R0 (Φ) + 1 holds by assumption
while P (Λ, G 0 ) = hW, JΛ i ≤ R0 (Λ) + 1 holds for any map Λ by definition, and the last equality
follows since R0 (Λ) = 0 for any Λ ∈ CPTP.

6 General bounds
Useful bounds for the measures can be obtained by relating them with norms or quantities computed at the level of the Choi operator JΦ , avoiding an optimisation over all CPTNI or CPTP
maps. For instance, the following relation with the trace norm generalises known bounds for the
diamond norm [41, 57] (see also [33]).
Proposition 7. For any Hermiticity-preserving map Φ ∈ H(A, B), decompose JΦ into its

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

11

positive and negative parts as JΦ = JΦ+ − JΦ− with JΦ± ≥ 0. Then
1
kJΦ k 1 ,
dA



1
1
Tr JΦ+ − 1,
Tr JΦ− ,max Tr JΦ+ − 1, Tr JΦ− ≥ R(Φ) ≥ max
dA
dA
1
Tr JΦ+ − 1,
Tr JΦ+ − 1 ≥ R0 (Φ) ≥dA
1
Tr JΦ− .
Tr JΦ− ≥ R00 (Φ) ≥dAkJΦ k 1 ≥ kΦk ≥Proof. Consider k·k first. Using the expressiononkJΦ k 1 = min µ+ + µ− JΦ = µ+ ω+ − µ− ω− , ω± ∈ D(A ⊗ B)

(47)

(48)

we see that any such decomposition provides a feasible solution for kΦk , since ω± constitutevalid Choi operators of maps Ω± ∈ CPTNI(A, B). The first inequality thus follows. The second
inequality is a consequence of the bound kΦk ≥ kΦk♦ from Cor. 2 and the fact that d1A kJΦ k 1
is known to lower bound the diamond norm (see e.g. [41, 57]). It can also be explicitly seen bynoting that any decomposition of the form JΦ = λ+ JΛ+ − λ− JΛ− with Λ± ∈ CPTNI can provide a
decomposition for the trace norm by rescaling each JΛ± by its trace; specifically,kJΦ k 1 ≤ λ+ Tr JΛ+ + λ− Tr JΛ− ,(49)and using the fact that Tr JΛ± ≤ dA JΛ± ∞ ≤ dA gives the desired bound.
The case of
R0 , R00 follows nanalogously, where we now
n the robustness measuresoo use the fact thatTr X+ = min µ X ≤ µρ, ρ ∈ D and Tr X− = min µ X + µρ ≥ 0, ρ ∈ D for any Hermitian
X. For the robustness R, take λ to be the greater of Tr JΦ+ − 1 and Tr JΦ− , and writeJΦ + λJΦ−JΦ+= (1 + λ)
.
λ
1+λ

(50)

J

Since each Φλ± ∈ CPTNI, this provides a valid feasible solution for R. On the other hand,R(Φ) ≥ max{R0 (Φ), R00 (Φ)} by definition, from which the lower bound follows.
Both the upper and the lower bounds in Prop. 7 can be tight, as was shown already for the
diamond norm [40]. However, better upper bounds can be obtained as follows.
Proposition 8. For any Hermiticity-preserving map Φ ∈ H(A, B), it holds thatkΦk♦ ≤ λmax (TrB [JΦ+ + JΦ− ]),kΦk ≤ λmax (TrB JΦ+ ) + λmax (TrB JΦ− ),R(Φ) ≤ max λmax (TrB JΦ+ ) − 1, λmax (TrB JΦ− ) ,

(51)

0

R (Φ) ≤ λmax (TrB JΦ+ ) − 1,
R00 (Φ) ≤ λmax (TrB JΦ− ).
We note that the bound for the diamond norm, which we stated above for completeness, appeared previously in [41].
Proof. The bounds for k·k♦ , k·k , R0 and R00 follow simply by using JΦ = JΦ+ − JΦ− as feasible
solutions in the definitions.
For the robustness R, take λ to be the greater of λmax (TrB JΦ+ ) − 1 and λmax (TrB JΦ− ), and
write
JΦ−
JΦ+
(52)
JΦ + λ= (1 + λ).
λ1+λSince this is a feasible solution for R, we get R(Φ) ≤ λ.
Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

12

As for lower bounds, we will first need to establish dual expressions for the considered measures.
The following Proposition is an application of standard convex duality arguments, and we include
details in Appendix A for completeness.
Proposition 9. For any Φ ∈ H(A, B), the following dual expressions hold.
onkΦk♦ = max hJΦ , W i − ρ ⊗ 1B ≤ W ≤ ρ ⊗ 1B , ρ ∈ D(A)onkΦk = max hJΦ , W i − ρ ⊗ 1B ≤ W ≤ σ ⊗ 1B , ρ, σ ∈ D(A)on
R(Φ) = max hJΦ , W i − Tr Y − X ⊗ 1B ≤ W ≤ Y ⊗ 1B , X, Y ≥ 0, Tr(X + Y ) = 1onR0 (Φ) = max hJΦ , W i − 1 0 ≤ W ≤ ρ ⊗ 1B , ρ ∈ D(A)on
R00 (Φ) = max hJΦ , W − ρ ⊗ 1B i 0 ≤ W ≤ ρ ⊗ 1B , ρ ∈ D(A)on= max hJΦ , W i − Tr Φ(ρ) 0 ≤ W ≤ ρ ⊗ 1B , ρ ∈ D(A) .
(53)
We can then obtain lower bounds by employing the dual optimisation problems. The bound forthe diamond norm is well known [20], but we find it is insightful to rederive it using this approach1 .
Proposition 10. For any Φ ∈ H(A, B) and any input state ρ ∈ D(A), let Φ(ρ)± denotethe positive/negative part of the output operator Φ(ρ). ThennokΦk ≥ kΦk♦ ≥ max kΦ(ρ)k 1 ρ ∈ D(A)≥ kTrB JΦ k ∞nkΦk ≥ max Tr Φ(ρ)− + Tr Φ(σ)+ρ, σ ∈ D(A)o≥ λmax [(TrB JΦ )+ ] + λmax [(TrB JΦ )− ]noR(Φ) ≥ max Tr Φ(X)− + Tr Φ(Y )+ − Tr Y X, Y ≥ 0, Tr(X + Y ) = 1no≥ max λmax [(TrB JΦ )+ ] − 1, λmax [(TrB JΦ )− ]noR0 (Φ) ≥ max Tr Φ(ρ)+ − 1 ρ ∈ D(A)(54)

≥ λmax [(TrB JΦ )+ ] − 1noR00 (Φ) ≥ max Tr Φ(ρ)− ρ ∈ D(A)≥ λmax [(TrB JΦ )− ].

Proof. Consider the diamond norm first. The main idea is to restrict the optimisation in the dual
expression of k·k♦ in (53) to operators of the form W = ρ ⊗ Z for some operator Z. Then we havenokΦk♦ ≥ max hJΦ , ρ ⊗ Zi − 1B ≤ Z ≤ 1B , ρ ∈ D(A)no= max Φ(ρT ), Z
− 1B ≤ Z ≤ 1B , ρ ∈ D(A)
n
o
= max
Φ(ρT ) 1
ρ ∈ D(A) ,(55)

where the second line follows by the Choi-Jamiołkowski isomorphism. Taking Z ∈ {1, −1}, we get
1 We remark the curious fact that, despite the apparent similarity, the bound for the diamond norm in Prop. 10 is

not the induced Schatten norm k·k 1→1 , as the latter requires an optimisation over non-Hermitian input operatorseven when the map Φ is Hermiticity-preserving [20].

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

13

the lower boundnkΦk♦ ≥ max ± hTrB JΦ , ρiρ ∈ D(A)o(56)= kTrB JΦ k ∞ .
In the case of k·k , we use feasible solutions of the form W = ρ ⊗ Z + σ ⊗ V with −1 ≤ Z ≤ 0
and n0 ≤ V ≤ 1 to obtaino the stated bound analogously — the crucial observation being thatmax hA, Bi 0 ≤ B ≤ 1 = Tr A+ for any Hermitian A. The other measures follow in the sameway.
Note the similarity between the eigenvalue-based lower bounds of Prop. 10 and the upperbounds of Prop. 8: the upper bounds consider the eigenvalues after decomposing JΦ as JΦ+ − JΦ− ,while the lower bounds use the positive and negative parts of TrB JΦ .
An immediate consequence is that for any completely positive map Φ, it holds thatkΦk = kΦk♦ = kTrB JΦ k ∞(57)

since the operators JΦ and TrB JΦ are both positive semidefinite. However, the lower bounds allow
us to show explicitly that the equality kΦk = kΦk♦ is no longer true for maps which are neither
CP nor trace preserving, and in fact the extreme disparity of kΦk = 2 kΦk♦ (cf. Cor. 2) can beachieved. Consider for instance the case whenΦ(·) = h0| · |0i |0ih0| − h1| · |1i |1ih1| .

(58)

Decomposing JΦ = |0ih0| ⊗ |0ih0| − |1ih1| ⊗ |1ih1| into its positive and negative parts, the boundof Prop. 8 gives kΦk♦ ≤ 1. However, the best upper bound we get for kΦk is 2, and it is indeed
tight: we have Φ(|0ih0|) = |0ih0| and Φ(|1ih1|) = − |1ih1|, and so Prop. 10 gives kΦk ≥ 2. A
similar argument can be used to show that R(Φ) = 1, which in particular implies that 2R(Φ) + 1 >kΦk > kΦk♦ .
All of the bounds that we established in this section can be tight, as we shall demonstrate inwhat follows.

7 Applications and examples
7.1 Positive maps and structural physical approximation
Positive maps constitute a fundamental way to detect and characterise quantum entanglement [2–4].
One of the most studied approaches to implementing such maps in practice is the structural physicalapproximation (SPA) [5, 6], which aims to approximate a given positive map Φ with a physicalquantum channel by considering decompositions of the form Φ + ςD, where D is the completely
depolarising channel, JD = 1/dB . Such approximations have found use in both understanding theproperties of positive maps [7, 58], as well as in realising them in experiments [6, 8, 59].
Intuitively, the robustness measures can then be understood as different approaches to defining
an optimised SPA to the map Φ, by allowing channels other than the depolarising map to be usedin the decomposition (cf. [33]). We will now discuss the similarities and differences between theapproaches by studying two representative examples of positive maps.
Transposition map. Consider first the transposition map T ∈ H(A, A). Letting SPA(T ) denotethe minimal amount ς needed for (T +ςD)/(1+ς) to be a quantum channel, it can be easily verified
that SPA(T ) = dA . However, by making a more suitable choice of a channel in the optimisation, ourrobustness measures construct an approximation as (T + λΛ)/(1 + λ) where λ = 12 (dA − 1) alreadysuffices to ensure that this is a valid physical channel. From this we see that R(T ) = 12 (dA − 1)and hence kT k = dA . Quantitatively, the advantage gained by allowing arbitrary channels in suchdecompositions can therefore be significant.
To understand why a better approximation can be obtained, let us take a closer look at the
optimal decomposition for this map. Our generalised approach can take into consideration the factthat the Choi operator of the transposition map, JT (the swap operator), already has a non-trivial
positive part, which means that there is no need to act on that part of the space. More specifically,
Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

14

1 − JTa better approximation is obtained simply by defining the map JΛ =∈ CPTP and mixing
dA − 1as
2dA − 1
1(59)
T+Λ ∈ CPTP.
JT + (dA − 1)JΛ ≥ 0 ⇒2
dA + 1
dA + 1
Structurally, this is not too different from the SPA — the only maps involved in the combination
are the depolarising channel and the transposition map itself, even if the optimal approximation is
not simply a convex mixture of the two. Indeed, we could define an optimised structural physicalapproximation which allows for such decompositions to be used:




0
0 λmax (JΦ )1 − JΦ0≥0
SPA (Φ) := min ς JΦ + ς
λmax (JΦ )dB − 1(60)
dB λmax (JΦ ) − 1= − λmin (JΦ ),λmax (JΦ ) − λmin (JΦ )with the expression valid for any map such that λmin (JΦ ) < λmax (JΦ ) 6= d−1
B . This can be used togive a general bound to the robustness measures.
Proposition 11. For any trace-preserving map Φ ∈ H(A, B) such that Φ 6= D, it holds
that
R(Φ) ≤ SPA0 (Φ) ≤ SPA(Φ).
(61)
In the case of the transpose, it holds that SPA0 (T ) = R(T ) = 12 (dA − 1), so we know thatan optimal approximation of the transposition map can be realised with only the depolarisingchannel, as long as one considers the optimised approach of Eq. (60). However, this is not the casefor general maps, and the advantages offered by the generalised robustness approach can provide
new insight into optimal approximations of maps, as we shall see in the following.
Choi map. The Choi map C ∈ H(A, A) with dA = 3 is an example of an indecomposable positive
map, and is defined by [60]
X11 + X22−X12
−X13
X22 + X33
−X23 
C(X) :=  −X21
(62)
−X31
−X32
X33 + X11
where Xij denote the matrix elements of X in a chosen basis. A numerical evaluation shows thatthe optimal decompositions for C give SPA(C) = 32 and SPA0 (C) = 23 . With the robustness, animproved choice can be obtained by choosing Λ = id and mixing as JC + 16 Jid ≥ 0, yielding R(C) = 16 .
Consequently, mixing with more general maps can not only provide quantitative improvements, butalso identify ways of implementing non-CPTP maps which are impossible to find with the standard
structural physical approximations.
An interesting difference between the SPA- and robustness-based approaches is that the optimal
SPA of the Choi map is a measure-and-prepare (entanglement-breaking) channel [7], while the map
obtained in the robustness-based approach is not (as can be verified with the PPT criterion). Since
measure-and-prepare channels enjoy an easy implementation in practical settings, it would be aninteresting extension of our approach to consider the extent of a quantitative advantage that canbe maintained while requiring that the optimal CPTP approximation be entanglement breaking.
We also note that another approach to realising positive maps was studied in Ref. [61] by using
multiple copies of the input state, where a related SPA-based approximation was also considered.
An extension of the methods of our work to this framework could provide additional insight into
the implementability of positive maps.

7.2 Inverse quantum channels
A fundamentally important case of a non-CPTP map encountered in many settings is the inverse
linear map of a bijective quantum channel, that is, a map such that Λ−1 ◦ Λ = Λ ◦ Λ−1 = id.2 Note
2 We note that in many cases it suffices to consider only left or right inverses, but we assume two-sided invertibility
for simplicity.

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

15

that such an inverse is not guaranteed to exist for a general channel, and even when it does, it will
not form a valid quantum channel unless Λ is a unitary map. However, many important cases ofquantum dynamics are indeed invertible, allowing us to study their inverses in the formalism of
our work.
Non-Markovianity. One setting in which channel inverses play a role is the study of nonMarkovianity. Among the different ways to define Markovian evolution, a common way is to saythat a time-dependent evolution governed by the channel Λt,0 is Markovian if it behaves as aphysical map over any time interval [t, t + δt]. Mathematically, any Λt,0 satisfying this condition issaid to be CP-divisible [62–64], which can be formalised by the statement that for all times t ands ≤ t we can write
Λt,0 = Ξt,s ◦ Λs,0
where the propagator Ξt,s is a CPTP map. For more general channels, the decomposition Λt,0 =Ξt,s ◦ Λs,0 results in some Ξt,s that is non-CPTP, indicating that Markovian dynamics break down
after some time point s.
Observe that, provided Λt,0 is invertible for all t, we can take Ξt,s = Λt,0 ◦ Λ−1s,0 . Therefore, thenon-physicality of Λt,0 ◦ Λ−1servesasanindicatorofnon-Markovianity,and— since this map
s,0−1
is trace preserving for any trace-preserving Λ — the diamond norm Λt,0 ◦ Λs,0 ♦ can be used
as a quantitative measure of non-Markovianity over the time-interval [t, s]. This is similar to theoriginal approach of Ref. [62] where a quantifier based on the trace norm of the Choi operator was
employed — the advantage of our definition is the ability to interpret this quantity operationally.
Specifically, we observe that quantum mechanics is ultimately a Markovian theory: if we had
knowledge of all relevant objects, then all quantum dynamics could be described by Markovian
unitary dynamics. That is, any information from the past that is relevant to the future must passthrough the present, and hence the optimal prediction of future observational statistics ultimately
depends only on the the present state of reality. Non-Markovianity is an artefact of not tracking all
relevant information in the present. In our context, this arises as our mathematical characterisationof the candidate channel, Λs,0 , does not track the state of the environment. The operational
relevance of Λt,0 ◦ Λ−1s,0 ♦ then becomes more evident. Notably, in Sec. 4 we presented a systematic
X. Here, we maymeans of simulating any unphysical map Ξt,s by introducing an ancillary system
Pthink of this as building a Markovian model for Ξt,s by introducing X = i µi ρi as an “artificial
environment”. The feeding in of different states ρi depending on X then represents a means
in which non-Markovian behaviour on the system is realised. While this construction does not
immediately look physical (as it allows affine mixtures of quantum states), it can be simulated bya classical computer with sufficient resource overhead. The resource costs of doing so — kΞt,s k♦ —thus represents a bound on the information processing capabilities of the environment that enablesaid non-Markovian behaviour to emerge.
There are multiple approaches for extending this to a time-independent measure of non-Markovianityof Λ. One could, for example, take the supremum of the measure Λt,0 ◦ Λ−1s,0 ♦ over all t and s.
This would then characterise how much extra information processing we need beyond tracking thestate of the system at time s to simulate dynamics overZ the time-interval [s, t]. We may also follow∞

an approach based on Ref. [62] and define I♦ (Λ) :=g♦,t (Λ) dt, where g♦,t can be understood0

as the right-hand derivative of the diamond norm of the dynamics at time t:
g♦,t (Λ) := lim+
ε→0−1
Λt+ε,0 ◦ Λ−1t,0 ♦ − Λt,0 ◦ Λt,0 ♦ε= lim+
ε→0

Λt+ε,0 ◦ Λ−1t,0 ♦ − 1
ε

.

(63)

I♦ (Λ) therefore represents the total amount of non-Markovianity in this evolution. A suitablenormalisation of this quantity can allow for the comparison of the strength of non-Markovianity indifferent settings [62, 64]. We leave a careful consideration of these possibilities to future work.
Error mitigation. Another application for the study of channel inverses is error mitigation.
This setting considers the scenario where one is tasked with computing expectation values of
the type Tr[U(ρ)A] for an input state ρ, ideal gate U, and observable A, while operations arefollowed by a noise channel Θ. A leading approach to this problem, called probabilistic error
Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

16

cancellation [17, 65], is to counteract the noise with the inverse map Θ−1 , so that Tr[U(ρ)A] =Tr[Θ◦Θ−1 ◦ U(ρ)A]. By decomposing Θ−1 into a quasiprobability distribution over a convex subsetof channels P = {Λi } such that Λi ◦ U would be implementable on a (fictitious) noiseless device,
standard quasiprobability sampling arguments allows us to construct an unbiased estimator for
Tr[U(ρ)A] using only operations implementable on a noisy device. The optimal overhead cost ofsuch a procedure scales as γP (Θ)2 , where [17, 30]
(
)
X
X
−1
γP (Θ) = min|λi | Θ =λi Λi , Λi ∈ P
(64)
i
i
n
o
−1
= min λ+ + λ− Θ = λ+ Λ+ − λ− Λ− , Λ± ∈ P .
The specific choice of P can be made depending on not only the physical setting in consideration,
but also on one’s precise motivations. On the one hand, a set with a finite number of operations(e.g., Clifford gates) turns Eq. (64) into a linear program [17, 65], making the overhead cost easily
computable while sacrificing the expressibility of devices. On the other hand, choosing a larger set
with an infinite number of implementable operations takes into account a larger expressibility [30],but makes the computation of Eq. (64) hard in general. Here, to accommodate computability andexpressibility at the same time, we take another approach considered in Ref. [33, 66]: we choose
P to be all physical quantum channels. We notice that the norm k·k provides the cost of error
mitigation in this setting as γCPTP (Θ) = Θ−1  = Θ−1 ♦ , which can be efficiently computed bysemidefinite programming. Although this choice of P might seem too permissive, the lower boundobtained through this approach can actually match known achievability results (upper bounds) [33],showing new optimality results and even improving on the specialised characterisation of Ref. [30]in some cases. Of note is the fact that, since any inverse map Θ−1 of a quantum channel Θ istrace preserving, our Thm. 3 shows a new application of the diamond norm in bounding the costof error mitigation: it always holds that γP (Θ) ≥ Θ−1 ♦ , regardless of the choice of P.
In some cases — such as when experiencing the leakage or loss of some qubits during computation — the noisy evolution can actually correspond to a map which is not trace preserving.
Although many previous approaches did not take this into consideration, our methods explicitly extend to such maps, allowing one to understand the simulation of non-trace-preserving linear maps
through Thm. 4. Related settings which our methods can characterise include the so-called linear
quantum error correction [67], which aims to correct errors of systems undergoing general, nonCPTP dynamics Θ, as well as error mitigation for non-Markovian noise [68], where the mitigation
cost can be related to a measure of non-Markovianity. In such cases, our approach can thus help
understand the implementation of not only the inverse maps, but also the dynamics themselves.
7.2.1

Computing the measures

To showcase the application of our methods and evaluate the measures for some representative
examples, we will consider the inverse maps of several fundamental types of noisy quantum evolutions: depolarising, amplitude damping, dephasing, and qubit leakage channels. The expressions
for the first two appeared in Ref. [33], which we rederive using the methods and results of thiswork. We also find for the first three that the optimal decomposition into Λ± for the norm kΘ−1 k(Eq. (9)), can be taken as convex mixtures of unitaries and state preparations. Thus, kΘ−1 k also
serves as the optimal cost γP (Θ−1 ) with a smaller set P as considered in Ref. [30], indicating thatthe capability to implement all CPTNI maps does not provide any advantage over that of implementing unitaries and state preparations only. Note that the inverses of trace-preserving maps aretrace preserving, and so in such cases the equality kΦk = kΦk♦ = 2R(Φ) + 1 holds by Thm. 3,
which means that it will suffice to evaluate any one of the measures.
Depolarising noise. The depolarising channel, given by Dp (X) := (1 − p)X + p Tr X d1A for somep1
X − 1−p
Tr X d1A . This gives
noise parameter p ∈ [0, 1), has the inverse Dp−1 (X) = 1−p1p|ΩihΩ| −1A⊗A .
1−p(1 − p)dA(65)

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

17

JDp−1 =

Importantly, one can notice that TrB JDp−1+

and TrB JDp−1−

are proportional to identity. As first

noticed in [40, 41], this means that the lower bound d1A JDp−1hibound λmax TrB JDp−1 + JDp−1
of Prop. 83 . We thus getof Prop. 7 matches the upper1−+

Dp−1  =Dp−1 ♦ =

1
J −1
dA Dp


1 + 1 − 2d−2
p
A
=
.
1−p
1

(66)

PdA −1pi Zi XZi† ,Dephasing noise. The generalised dephasing channel [69] is defined by ∆p (X) := i=0
where p = (p0 , . . . , pdA −1 ) is a chosen set of noise parameters pi ≥ 0, and Zi refers to the qudit
clock operators
dX
A −1
Zi =
ω ij |jihj|
(67)
j=0

in some basis {|ii}, with ω being a primitive dA th root of unity. In the case of dA = 2, this recovers
the usual qubit dephasing channel ∆p (X) = (1 − p)X + pZXZ † . One can notice that the actionof this channel can be represented by ∆p (X) = X S where denotes the element-wise matrix
product (Schur/Hadamard product), and(S)jk =dX
A −1

pi ω ij (ω ik )∗ =

i=0

dX
A −1

pi ω i(j−k)

j, k = 0, . . . dA − 1

(68)

i=0

in the same basis {|ii}. Provided that the coefficients of S are non-zero (that is, ∆p does not act
as a completely dephasing channel on any subspace), the map is invertible as ∆−1S
p (X) = Xwith S defined by
1(S)jk =
j, k = 0, . . . dA − 1.
(69)
(S)jk
We will now show that ∆−1= ∆−1= d1A J∆−1
p
p

♦
p

1

= d1A S1.

is a consequence of Thm. 3; note here that we do not actually
The equality ∆−1
= ∆−1
p
p
♦

P
need to impose that ∆p be trace preserving (i.e., that i pi = 1), since both ∆p and ∆−1
p arealways proportional to a trace-preserving map by construction.
To show the equality ∆−1= d1A S 1 , consider the decomposition of S as S = S + − S − .
pCrucially, since S is a circulant matrix, so is S, and hence it can be diagonalised by the Fouriertransform matrix (F )jk = √1d ω jk [70, 2.2.P10]. Each eigenvector of S is therefore of the form
A

dA −1
1 X
|sm i = √ω im |ii ,dA i=0(70)

ensuring in particular that all diagonal elements of each density matrix |sm ihsm | are equal. Thisentails that S + and S − both have constant diagonals. Define now the maps
Λ± (X) := X

(71)

S±.

Since S ± ≥ 0, each such map is completely positive [71, Thm. 3.7], and clearly Λ0± := Λ± dA / Tr(S ± )is trace preserving as we have just seen that (S ± )ii = (S ± )jj ∀i, j. Thus we have a decompositionas
Tr S − 0
Tr S + 0(72)
Λ+ −Λ− , Λ0± ∈ CPTP,
∆−1
p =
dA
dA
PdA −1from which we get the bound ∆−1≤ d1A S 1 . On the other hand, let |ψi = √1dpi=0 |iiAand use Prop. 10 to get
∆−1
≥ ∆−1
p
p (|ψihψ|) 1 =
3 In fact, kΦk = 1 kJ k if and only if Tr
B
Φ 1
♦
dA

1
S
dA

1

.

(73)

JΦ+ + JΦ− ∝ 1 [40, 41].

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

18

Finally, the equality J∆−1
p

= S
1

1

is obtained by noticing that J∆−1=pPi,j (S)ij |iiihjj| which

has the same eigenvalues as S.
The eigenvalues of S can be readily obtained due to the fact that it is a circulant matrix [70,2.2.P10], allowing for a straightforward computation of the trace norm S 1 and altogether giving
=
∆−1
p
♦

dA −1 dX
A −1
1 X
dA m=0 j=0

dX
A −1

!−1
pi ω

j(i−m)

.

(74)

i=0

For the qubit dephasing channel with p ∈ [0, 12 ), we recover
=
∆−1
p
♦

1
2



1
1
1−2p

1 
1−2p

1

=
1

1
.
1 − 2p(75)

Since each eigenvector |sm i for S in (70) corresponds to the application of Zm , Λ0± in (72) are
realised as probabilistic applications of the generalised phase unitaries.
Amplitude damping noise. The qubit amplitude
damping channel Aγ (·) = A0 · A†0 + A1 · A†1√√
is defined by the Kraus operators A0 := |0ih0| + 1 − γ |1ih1| and A1 := γ |0ih1|. Using the factthatγ
1Aγ (|1ih1|) −|0ih0||1ih1| =
1−γ
1−γ
(76)
γ
1
Aγ (|1ih1|) −Aγ (|0ih0|),
=
1−γ
1−γ
we haveA−1
γ (|1ih1|) =1
γ|1ih1| −|0ih0| .
1−γ
1−γ

(77)

Proposition 10 thus gives
A−1
= A−1
≥ A−1
γ
γ
γ (|1ih1|) 1

♦
=

1+γ
.
1−γ

(78)

A matching upper bound can be obtained by explicitly computing JA−1
(see e.g. [17, 30]) andγ
using the upper bound in Prop. 8.
The above shows a rather general method of obtaining lower bounds for linear maps which are
inverses of other linear maps, without having to explicitly compute the full inverse map. Indeed, thiscan be extended to maps which only approximately invert a given channel — useful, for instance,
when dealing with non-invertible maps, or when aiming to reduce the cost of implementing a given
map by only requiring that it approximately mitigates the error.
e ∈ H(B, A) be such that Φe ◦ Φ(ρ) − ρ ≤ ε for
Proposition 12. Let Φ ∈ H(A, B) and Φ1all ρ ∈ D(A). Thennoe ≥ max kZk (1 − ε) Φ(Z) ∈ D(B)
Φ
1
♦
n
o
e ≥ max Tr Z− + Tr Q+ − ε(kZk + kQk ) Φ(Z), Φ(Q) ∈ D(B)
Φ
1
1

n
e ≥ max Tr Z− + Tr Q+ − Tr Φ(Q) − ε(kZk + kQk ) Φ(Z), Φ(Q) ≥ 0,
R(Φ)
1
1
(79)
Tr Φ(Z + Q) = 1noe ≥ max Tr Z+ − 1 − ε kZk
R0 (Φ)
Φ(Z) ∈ D(B)1noe ≥ max Tr Z− − ε kZk
R00 (Φ)
Φ(Z)
∈
D(B)
.
1

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

19

Proof. We use Prop. 10 to get thatonee ≥ maxσ ∈ D(B) ∩ ran(Φ)
Φ(σ)
Φ
1
♦
o
n
e ◦ Φ(Z)
Φ(Z)
∈
D(B)
= max
Φ
1
o
n
e ◦ Φ(Z)Φ(Z) ∈ D(B)≥ max kZk 1 − Z − Φ1on≥ max kZk 1 (1 − ε) Φ(Z) ∈ D(B) .

(80)

The third line follows by the triangle inequality, and the last line is a consequence of the assumptione ◦ Φ(ρ) − ρ ≤ ε for all ρ ∈ D(A), since we can write any Z = µ+ ρ+ − µ− ρ− for somethat Φ
1e ◦ Φ(Z) − Z
ρ± ∈ D(A) to get Φ≤ ε(µ+ + µ− ) ≤ ε kZk . The case of the other measures is1

1

analogous: using the variational form of the function Tr Z+ (and similarly Tr Z− ) we can obtainnDEoe + = maxe ◦ Φ(Z), W
Tr Φ(σ)Φ
0≤W ≤1nDEoe ◦ Φ(Z), W= max hZ, W i − Z − Φ
0≤W ≤1(81)noe≥ max hZ, W i − Z − Φ ◦ Φ(Z) 1 kW k ∞ 0 ≤ W ≤ 1≥ Tr Z+ − ε kZk 1
where we used the Cauchy-Schwarz inequality. Using these bounds in Prop. 10 yields the statedresult.
√Leakage error. Consider the qubit leakage error Lp (·) = Lp ·L†p where Lp := |0ih0|+ 1 − p |1ih1|.
This represents a situation where the excited state is lost with probability 1 − p, and this stochastic
nature is reflected to the fact that Lp is not trace preserving. The inverse of the leakage error is−1−1
given by L−1
p (·) = Lp · Lp . Since this is a completely positive map, Eq. (57) gives
L−1
= L−1
= TrB JL−1
p
p

♦
p

∞

=

1
.
1−p

Note that the inverse can be realised as




1
1
1
1
p
√
√
1
+
Π|1ih1|
L−1
=
id
−
−
1
Z+
p
2
2
1−p
1−p
1−p

(82)

(83)

where Z(·) := Z · Z with Z = |0ih0| − |1ih1| being the Pauli Z matrix, and Π|1ih1| (·) := |1ih1| · |1ih1|
being the projection onto the state |1i.

8 Discussion
We introduced a comprehensive quantitative approach to the study of non-completely-positive linear maps, focusing in particular on the task of approximating and simulating them with valid
quantum channels. To this end, we considered several quantifiers which generalise measures employed in the study of quantum resources — namely, variants of the robustness and base norm
measures. We showed that they satisfy very close relations with the diamond norm, and in particular are exactly equal to it for any trace-preserving linear map. Since such trace-preserving
maps are the most commonly encountered examples of dynamics beyond physical quantum channels, this allowed us to establish fruitful interrelations between the quantities, and discover new
applications of the fundamentally important quantity that is the diamond norm. We developedin particular two operational connections. Firstly, we introduced a method of simulating generallinear maps with quantum channels, shifting the difficulty of realising non-quantum dynamics onto
the structurally simpler task of implementing linear combinations of quantum states. We showedthat our robustness measure exactly quantifies the cost of realising such schemes in terms of therequired state-based resources. Secondly, we showed that another variant of the robustness finds
Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

20

use as an exact quantifier of the performance advantage that a general linear map can enable overquantum channels in a class of state discrimination games. We introduced a number of usefulbounds and explicitly employed them to demonstrate the computability of the measures for some
representative examples. Finally, we showed how our measures can find use in the quantitative
characterisation of several practically relevant settings, namely, structural approximations of positive maps, non-Markovianity quantification, and tightly bounding the cost of probabilistic error
mitigation.
Although we focused on the application of our framework to Hermiticity-preserving maps, wenote that more general linear maps can be treated in a similar way. The simplest way to approach this is to decompose any linear map Φ into its Hermiticity-preserving and skew-Hermiticitypreserving parts, that is, write Φ = ΦH + iΦSH where the constituent maps are defined through1(JΦ −JΦ† ). The maps ΦH and ΦSH are then explicitly HermiticityJΦH := 12 (JΦ +JΦ† ) and JΦSH := 2i
preserving, and our arguments can be applied to them directly. A similar approach was employedin [72] to decompose the two-point quantum correlator T : L(A) → L(A ⊗ A), defined as the mapsatisfying Tr[T (ρ)(A ⊗ B)] = Tr[AρB] for all A, B. Indeed, one can show that the decompositions
constructed in [72] are also optimal for the robustness-based quantities.
We also note that the diamond norm has been applied as a measure of specific properties ofquantum channels, such as their ability to detect coherence [73]. Connections between our methods
and such approaches could be fruitful to explore.
A major outstanding issue is to understand how the framework of this work can be extended
to non-linear maps, which could allow for the characterisation and more efficient approximation ofimportant unphysical dynamics such as quantum cloners. This question was already asked in theearliest works concerned with approximating non-CPTP maps with quantum channels [5], but it
still remains a considerable challenge to devise approaches which could apply to general non-linear
transformations.

Acknowledgments
We acknowledge fruitful discussions with Joonwoo Bae, Francesco Buscemi, Ludovico Lami, Varun
Narasimhachar, Jayne Thompson, and Xiao Yuan. This research is supported by the National
Research Foundation (NRF), Singapore, under its NRFF Fellow program (Award No. NRFNRFF2016-02), the National Research Foundation and Agence Nationale de la Recherche joint
Project No. NRF2017-NRFANR004 VanQuTe, the Singapore Ministry of Education Tier 1 Grant
RG162/19 (S) and grant No. FQXi-RFP-IPW-1903 from the Foundational Questions Instituteand Fetzer Franklin Fund (a donor advised fund of Silicon Valley Community Foundation). B.R. is
supported by the Presidential Postdoctoral Fellowship from Nanyang Technological University, Singapore. Any opinions, findings and conclusions or recommendations expressed in this material arethose of the author(s) and do not reflect the views of National Research Foundation, Singapore.

References[1] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information.
Cambridge University Press, New York, 2010. ISBN 978-1-107-00217-3.
[2] Michał Horodecki, Paweł Horodecki, and Ryszard Horodecki. Separability of mixed states:
Necessary and sufficient conditions. Physics Letters A, 223:1–8, 1996. ISSN 0375-9601. DOI:
10.1016/S0375-9601(96)00706-2.
[3] Otfried Gühne and Géza Tóth. Entanglement detection. Phys. Rep., 474:1–75, 2009. ISSN
0370-1573. DOI: 10.1016/j.physrep.2009.02.004.
[4] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum
entanglement. Rev. Mod. Phys., 81:865–942, 2009. DOI: 10.1103/RevModPhys.81.865.
[5] Paweł Horodecki. From limits of quantum operations to multicopy entanglement witnesses and state-spectrum estimation. Phys. Rev. A, 68:052101, 2003. DOI: 10.1103/PhysRevA.68.052101.
[6] Paweł Horodecki and Artur Ekert. Method for Direct Detection of Quantum Entanglement.
Phys. Rev. Lett., 89:127902, 2002. DOI: 10.1103/PhysRevLett.89.127902.

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

21

[7] J. K. Korbicz, M. L. Almeida, J. Bae, M. Lewenstein, and A. Acín. Structural approximations
to positive maps and entanglement-breaking channels. Phys. Rev. A, 78:062105, 2008. DOI:
10.1103/PhysRevA.78.062105.
[8] Joonwoo Bae. Designing quantum information processing via structural physical approximation. Rep. Prog. Phys., 80:104001, 2017. ISSN 0034-4885. DOI: 10.1088/1361-6633/aa7d45.
[9] Philip Pechukas. Reduced Dynamics Need Not Be Completely Positive. Phys. Rev. Lett., 73:
1060–1062, 1994. DOI: 10.1103/PhysRevLett.73.1060.
[10] Anil Shaji and E. C. G. Sudarshan. Who’s afraid of not completely positive maps? Physics
Letters A, 341:48–54, 2005. ISSN 0375-9601. DOI: 10.1016/j.physleta.2005.04.029.
[11] César A. Rodríguez-Rosario, Kavan Modi, Aik-meng Kuah, Anil Shaji, and E. C. G. Sudarshan. Completely positive maps and classical correlations. J. Phys. A: Math. Theor., 41:205301, 2008. ISSN 1751-8121. DOI: 10.1088/1751-8113/41/20/205301.
[12] Hilary A. Carteret, Daniel R. Terno, and Karol Życzkowski. Dynamics beyond completely
positive maps: Some properties and applications. Phys. Rev. A, 77:042113, 2008. DOI:
10.1103/PhysRevA.77.042113.
[13] Robert Alicki. Comment on “Reduced Dynamics Need Not Be Completely Positive”. Phys.
Rev. Lett., 75:3020–3020, 1995. DOI: 10.1103/PhysRevLett.75.3020.
[14] Kavan Modi. Operational approach to open dynamics and quantifying initial correlations. Sci.
Rep., 2:581, 2012. ISSN 2045-2322. DOI: 10.1038/srep00581.
[15] David Schmid, Katja Ried, and Robert W. Spekkens. Why initial system-environment correlations do not imply the failure of complete positivity: A causal perspective. Phys. Rev. A,
100:022112, 2019. DOI: 10.1103/PhysRevA.100.022112.
[16] P.W. Shor. Fault-tolerant quantum computation. In Proceedings of 37th Conference on Foundations of Computer Science, pages 56–65, 1996. DOI: 10.1109/SFCS.1996.548464.
[17] Kristan Temme, Sergey Bravyi, and Jay M. Gambetta. Error Mitigation for ShortDepth Quantum Circuits. Phys. Rev. Lett., 119:180509, 2017. DOI: 10.1103/PhysRevLett.119.180509.
[18] Ying Li and Simon C. Benjamin. Efficient Variational Quantum Simulator Incorporating
Active Error Minimization. Phys. Rev. X, 7:021050, 2017. DOI: 10.1103/PhysRevX.7.021050.
[19] A. Y. Kitaev. Quantum computations: Algorithms and error correction. Russ. Math. Surv.,
52:1191–1249, 1997. DOI: 10.1070/RM1997v052n06ABEH002155.
[20] John Watrous. Notes on super-operator norms induced by Schatten norms. arXiv:quantph/0411077, 2004. URL http://arxiv.org/abs/quant-ph/0411077.
[21] John Watrous. The Theory of Quantum Information. Cambridge University Press, Cambridge,
2018. ISBN 978-1-107-18056-7.
[22] Guifré Vidal and Rolf Tarrach. Robustness of entanglement. Phys. Rev. A, 59:141–155, 1999.
DOI: 10.1103/PhysRevA.59.141.
[23] María García Díaz, Kun Fang, Xin Wang, Matteo Rosati, Michalis Skotiniotis, John Calsamiglia, and Andreas Winter. Using and reusing coherence to realize quantum processes.
Quantum, 2:100, 2018. DOI: 10.22331/q-2018-10-19-100.
[24] Ryuji Takagi and Bartosz Regula. General Resource Theories in Quantum Mechanics andBeyond: Operational Characterization via Discrimination Tasks. Phys. Rev. X, 9:031053,
2019. DOI: 10.1103/PhysRevX.9.031053.
[25] Zi-Wen Liu and Andreas Winter. Resource theories of quantum channels and the universal
role of resource erasure. arXiv:1904.04201, 2019. URL http://arxiv.org/abs/1904.04201.
[26] Gilad Gour and Andreas Winter. How to Quantify a Dynamical Quantum Resource. Phys.
Rev. Lett., 123:150401, 2019. DOI: 10.1103/PhysRevLett.123.150401.
[27] Roope Uola, Tristan Kraft, and Alastair A. Abbott. Quantification of quantum dynamics with
input-output games. Phys. Rev. A, 101:052306, 2020. DOI: 10.1103/PhysRevA.101.052306.
[28] Xiao Yuan, Yunchao Liu, Qi Zhao, Bartosz Regula, Jayne Thompson, and Mile Gu. Universal
and operational benchmarking of quantum memories. npj Quantum Inf., 7:108, 2021. ISSN
2056-6387. DOI: 10.1038/s41534-021-00444-9.
[29] Ryuji Takagi, Kun Wang, and Masahito Hayashi. Application of the Resource Theory of Channels to Communication Scenarios. Phys. Rev. Lett., 124:120502, 2020. DOI: 10.1103/PhysRevLett.124.120502.
[30] Ryuji Takagi. Optimal resource cost for error mitigation. arXiv:2006.12509, 2020. URL
http://arxiv.org/abs/2006.12509.
Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

22

[31] Bartosz Regula and Ryuji Takagi. Fundamental limitations on distillation of quantum channel
resources. Nat. Commun., 12:4411, 2021. ISSN 2041-1723. DOI: 10.1038/s41467-021-24699-0.
[32] Bartosz Regula and Ryuji Takagi. One-Shot Manipulation of Dynamical Quantum Resources.
Phys. Rev. Lett., 127:060402, 2021. DOI: 10.1103/PhysRevLett.127.060402.
[33] Jiaqing Jiang, Kun Wang, and Xin Wang. Physical Implementability of Quantum Maps and
Its Application in Error Mitigation. arXiv:2012.10959, 2020. URL http://arxiv.org/abs/
2012.10959.
[34] M. F. Sacchi. Optimal discrimination of quantum operations. Phys. Rev. A, 71:062340, 2005.
DOI: 10.1103/PhysRevA.71.062340.
[35] Alexei Gilchrist, Nathan K. Langford, and Michael A. Nielsen. Distance measures to compare real and ideal quantum processes. Phys. Rev. A, 71:062310, 2005. DOI: 10.1103/PhysRevA.71.062310.
[36] A. Jenčová. Base norms and discrimination of generalized quantum channels. J. Math. Phys.,
55:022201, 2014. ISSN 0022-2488. DOI: 10.1063/1.4863715.
[37] John Watrous. Semidefinite programs for completely bounded norms. Theory Comput., 5:
217–238, 2009. ISSN 1557-2862. DOI: 10.4086/toc.2009.v005a011.
[38] John Watrous. Simpler semidefinite programs for completely bounded norms. Chicago J.
Theor. Comp. Sci., 19:1–19, 2013. DOI: 10.4086/cjtcs.2013.008.
[39] Christophe Piveteau, David Sutter, and Stefan Woerner. Quasiprobability decompositions
with reduced sampling overhead. arXiv:2101.09290, 2021. URL http://arxiv.org/abs/
2101.09290.
[40] U. Michel, M. Kliesch, R. Kueng, and D. Gross. Comments on “Improving Compressed
Sensing With the Diamond Norm”–Saturation of the Norm Inequalities Between Diamondand Nuclear Norm. IEEE Trans. Inf. Theory, 64:7443–7445, 2018. ISSN 1557-9654. DOI:
10.1109/TIT.2018.2861887.
[41] Ion Nechita, Zbigniew Puchała, Łukasz Pawela, and Karol Życzkowski. Almost all quantum channels are equidistant. J. Math. Phys., 59:052201, 2018. ISSN 0022-2488. DOI:
10.1063/1.5019322.
[42] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities. Phys. Rev. Lett., 115:070501, 2015. DOI:
10.1103/PhysRevLett.115.070501.
[43] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, andWilliam K. Wootters. Teleporting an unknown quantum state via dual classical andEinstein-Podolsky-Rosen channels. Phys. Rev. Lett., 70:1895–1899, 1993. DOI: 10.1103/PhysRevLett.70.1895.
[44] Mario Berta, Fernando G. S. L. Brandão, Matthias Christandl, and Stephanie Wehner. Entanglement Cost of Quantum Channels. IEEE Trans. Inf. Theory, 59:6779–6795, 2013. ISSN
1557-9654. DOI: 10.1109/TIT.2013.2268533.
[45] Stefano Pirandola, Riccardo Laurenza, Carlo Ottaviani, and Leonardo Banchi. Fundamental
limits of repeaterless quantum communications. Nat. Commun., 8:15043, 2017. ISSN 20411723. DOI: 10.1038/ncomms15043.
[46] Mark M. Wilde. Entanglement cost and quantum channel simulation. Phys. Rev. A, 98:
042338, 2018. ISSN 2469-9926, 2469-9934. DOI: 10.1103/PhysRevA.98.042338.
[47] Gilad Gour and Carlo Maria Scandolo. Entanglement of a bipartite channel. Phys. Rev. A,
103:062422, Jun 2021. DOI: 10.1103/PhysRevA.103.062422. URL https://link.aps.org/
doi/10.1103/PhysRevA.103.062422.
[48] Stefan Bäuml, Siddhartha Das, Xin Wang, and Mark M. Wilde. Resource theory of entanglement for bipartite quantum channels. arXiv:1907.04181, 2019. URL http://arxiv.org/
abs/1907.04181.
[49] Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal quantum
computation using teleportation and single-qubit operations. Nature, 402:390–393, 1999. ISSN
1476-4687. DOI: 10.1038/46503.
[50] James R. Seddon and Earl T. Campbell. Quantifying magic for multi-qubit operations.
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 475:
20190251, 2019. DOI: 10.1098/rspa.2019.0251.

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

23

[51] Khaled Ben Dana, María García Díaz, Mohamed Mejatty, and Andreas Winter. Resource
theory of coherence: Beyond states. Phys. Rev. A, 95:062327, 2017. DOI: 10.1103/PhysRevA.95.062327.
[52] Joshua Geller and Marco Piani. Quantifying non-classical and beyond-quantum correlationsin the unified operator formalism. J. Phys. A: Math. Theor., 47:424030, 2014. ISSN 1751-8121.
DOI: 10.1088/1751-8113/47/42/424030.
[53] Joseph F. Fitzsimons, Jonathan A. Jones, and Vlatko Vedral. Quantum correlations which
imply causation. Sci. Rep., 5:18281, 2015. ISSN 2045-2322. DOI: 10.1038/srep18281.
[54] Eneet Kaur and Mark M. Wilde. Amortized entanglement of a quantum channel and approximately teleportation-simulable channels. J. Phys. A: Math. Theor., 51:035303, 2017. ISSN
1751-8121. DOI: 10.1088/1751-8121/aa9da7.
[55] Denis Rosset, Francesco Buscemi, and Yeong-Cherng Liang. Resource Theory of Quantum
Memories and Their Faithful Verification with Minimal Assumptions. Phys. Rev. X, 8:021033,
2018. DOI: 10.1103/PhysRevX.8.021033.
[56] Karol Życzkowski, Paweł Horodecki, Anna Sanpera, and Maciej Lewenstein. Volume of theset of separable states. Phys. Rev. A, 58:883–892, 1998. DOI: 10.1103/PhysRevA.58.883.
[57] M. Kliesch, R. Kueng, J. Eisert, and D. Gross. Improving Compressed Sensing With the
Diamond Norm. IEEE Trans. Inf. Theory, 62:7445–7463, 2016. ISSN 1557-9654. DOI:
10.1109/TIT.2016.2606500.
[58] Fred Shultz. The structural physical approximation conjecture. J. Math. Phys., 57:015218,
2015. ISSN 0022-2488. DOI: 10.1063/1.4938226.
[59] Hyang-Tag Lim, Yong-Su Kim, Young-Sik Ra, Joonwoo Bae, and Yoon-Ho Kim. Experimental
Realization of an Approximate Partial Transpose for Photonic Two-Qubit Systems. Phys. Rev.
Lett., 107:160401, 2011. DOI: 10.1103/PhysRevLett.107.160401.
[60] Man-Duen Choi. Some assorted inequalities for positive linear maps on C*-algebras. J. Oper.
Theory, 4:271–285, 1980. ISSN 0379-4024. URL https://www.jstor.org/stable/24714007.
[61] Qingxiuxiong Dong, Marco Túlio Quintino, Akihito Soeda, and Mio Murao. Implementing
positive maps with multiple copies of an input state. Phys. Rev. A, 99:052352, 2019. DOI:
10.1103/PhysRevA.99.052352.
[62] Ángel Rivas, Susana F. Huelga, and Martin B. Plenio. Entanglement and Non-Markovianityof Quantum Evolutions.
Phys. Rev. Lett., 105:050403, 2010.
DOI: 10.1103/PhysRevLett.105.050403.
[63] Dariusz Chruściński and Sabrina Maniscalco. Degree of Non-Markovianity of Quantum Evolution. Phys. Rev. Lett., 112:120404, 2014. DOI: 10.1103/PhysRevLett.112.120404.
[64] Ángel Rivas, Susana F. Huelga, and Martin B. Plenio. Quantum non-Markovianity: Characterization, quantification and detection. Rep. Prog. Phys., 77:094001, 2014. ISSN 0034-4885.
DOI: 10.1088/0034-4885/77/9/094001.
[65] Suguru Endo, Simon C. Benjamin, and Ying Li. Practical Quantum Error Mitigation for
Near-Future Applications. Phys. Rev. X, 8:031027, 2018. DOI: 10.1103/PhysRevX.8.031027.
[66] Y. Xiong, D. Chandra, S. X. Ng, and L. Hanzo. Sampling overhead analysis of quantum
error mitigation: Uncoded vs. coded systems. IEEE Access, 8:228967–228991, 2020. DOI:
10.1109/ACCESS.2020.3045016.
[67] Alireza Shabani and Daniel A. Lidar. Maps for general open quantum systems and a theoryof linear quantum error correction. Phys. Rev. A, 80:012309, 2009. DOI: 10.1103/PhysRevA.80.012309.
[68] Hideaki Hakoshima, Yuichiro Matsuzaki, and Suguru Endo. Relationship between costs forquantum error mitigation and non-Markovian measures. Phys. Rev. A, 103:012611, Jan 2021.
DOI: 10.1103/PhysRevA.103.012611. URL https://link.aps.org/doi/10.1103/PhysRevA.
103.012611.
[69] I. Devetak and P. W. Shor. The Capacity of a Quantum Channel for Simultaneous Transmission of Classical and Quantum Information. Commun. Math. Phys., 256:287–303, 2005. ISSN
1432-0916. DOI: 10.1007/s00220-005-1317-6.
[70] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2012.
ISBN 978-0-521-83940-2.
[71] Vern Paulsen. Completely Bounded Maps and Operator Algebras. Cambridge University Press,
2002. ISBN 978-0-521-81669-4.

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

24

[72] Francesco Buscemi, Michele Dall’Arno, Masanao Ozawa, and Vlatko Vedral. Direct observation of any two-point quantum correlation function. arXiv:1312.4240, 2013. URL
http://arxiv.org/abs/1312.4240.
[73] Thomas Theurer, Dario Egloff, Lijian Zhang, and Martin B. Plenio. Quantifying Operations
with an Application to Coherence. Phys. Rev. Lett., 122:190405, 2019. DOI: 10.1103/PhysRevLett.122.190405.
[74] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press,
New York, 2004. ISBN 978-0-521-83378-3.
[75] J. P. Ponstein. Approaches to the Theory of Optimization. Cambridge University Press, 2004.
ISBN 978-0-521-60491-8.

A Dual forms
Here we derive the dual expressions of the measures, as stated in Prop. 9. The derivation follows
standard arguments in convex optimisation [74, 75] (see also [24, App. B]). Let us explicitly consider
the case of the diamond norm. As our starting point, we will take the primal optimisation problem
as in Lem. 1:on(84)kΦk♦,p = min µ JΦ = M+ − M− , M± ≥ 0, TrB (M+ + M− ) ≤ µ1A .
The Lagrangian of this problem is given byL(µ, M+ , M− ; W, P, Q, R) = µ − hM+ − M− − JΦ , W i − hM+ , P i − hM− , Qi
− hµ1A − TrB (M+ + M− ), Ri(85)= µ(1 − Tr R) + hM+ , −W − P + R ⊗ 1B i
+ hM− , W − Q + R ⊗ 1B i + hJΦ , W i

where W, P, Q ∈ H(A ⊗ B), R ∈ H(A) are Lagrange multipliers, and we used that hS, TrB T i =hS ⊗ 1B , T i holds for any S ∈ H(A), T ∈ H(A ⊗ B). The dual problem is then defined askΦk♦,d :=

sup

inf

µ∈R
W ∈H
P,Q,R≥0 M+ ,M− ∈H

(
=

sup
W ∈H
P,Q,R≥0

L(µ, M+ , M− ; W, P, Q, R)

if Tr R = 1 and W + P = R ⊗ 1B and W − Q = −R ⊗ 1B
otherwiseoW ≥ −R ⊗ 1, W ≤ R ⊗ 1, R ≥ 0, Tr R = 1 ,hJΦ , W i−∞n= sup hJΦ , W i(86)with the supremum achieved since the feasible set is compact. A strictly feasible solution, that is, afeasible solution for which the inequality constraints are strict, can be constructed by decomposingJΦ = JΦ+ − JΦ− and defining M± := JΦ± + ε1A⊗B with µ suitably large. By Slater’s theorem(see e.g. [75]), the existence of a strictly feasible solution ensures that kΦk♦,p = kΦk♦,d .
The dual forms of the other measures are obtained in full analogy with the derivation above.
The crucial observation is that an optimisation of the formnokΦk = min λ+ + λ− Φ = λ+ Λ+ − λ− Λ− , Λ± ∈ CPTNI(87)
can be rewritten asnkΦk = min λ+ + λ−JΦ = M+ − M− , M± ≥ 0, TrB M± ≤ λ± 1A

o

(88)

which allows us to follow the same approach.

Accepted in Quantum 2021-07-30, click title to verify. Published under CC-BY 4.0.

25