# Inevitability of knowing less than nothing

Gilad Gour  Department of Mathematics and Statistics, Institute for Quantum
Science and Technology, University of Calgary, Alberta, Canada T2N 1N4  Mark
M. Wilde  School of Electrical and Computer Engineering, Cornell University,
Ithaca, New York 14850, USA  Sarah Brandsen  Department of Physics, Duke
University, Durham, North Carolina 27708, USA  Isabelle Jianing Geng
Department of Mathematics and Statistics, Institute for Quantum Science and
Technology, University of Calgary, Alberta, Canada T2N 1N4

###### Abstract

A colloquial interpretation of entropy is that it is the knowledge gained upon
learning the outcome of a random experiment. Conditional entropy is then
interpreted as the knowledge gained upon learning the outcome of one random
experiment after learning the outcome of another, possibly statistically
dependent, random experiment. In the classical world, entropy and conditional
entropy take on non-negative values, consistent with the intuition that one
has regarding the aforementioned interpretations. However, for certain
entangled states, one obtains negative values when evaluating commonly
accepted and information-theoretically justified formulas for the quantum
conditional entropy, leading to the confounding conclusion that one can know
less than nothing in the quantum world. Here, we introduce a physically
motivated framework for defining quantum conditional entropy, based on two
simple postulates inspired by the second law of thermodynamics (non-decrease
of entropy) and extensivity of entropy, and we argue that all plausible
definitions of quantum conditional entropy should respect these two
postulates. We then prove that all plausible quantum conditional entropies
take on negative values for certain entangled states, so that it is inevitable
that one can know less than nothing in the quantum world. All of our arguments
are based on constructions of physical processes that respect the first
postulate, the one inspired by the second law of thermodynamics.

quantum conditional entropy

††preprint:

LABEL:FirstPage1 LABEL:LastPage#110

###### Contents

  1. I Introduction
    1. I.1 Summary of results
    2. I.2 Notation
  2. II Uncertainty and entropy
    1. II.1 Uncertainty measures
    2. II.2 Entropy
  3. III Conditional uncertainty and entropy
    1. III.1 Conditional uncertainty measures
    2. III.2 Conditional entropy
  4. IV Main result: Inevitability of negative quantum conditional entropy
  5. V Conditional entropy from relative entropy
  6. VI Conclusion
  7. A Proofs of properties of entropy
  8. B Choi matrix formulations
    1. B.1 Choi matrix formulation of conditional unitality
    2. B.2 Choi matrix formulation of locally balanced channels
  9. C Quantum conditional majorization reduces to classical conditional majorization
  10. D Proofs of properties of quantum conditional entropy
  11. E A subclass of conditional entropies
    1. E.1 Proof of Theorem 4
    2. E.2 Proof of Theorem 1
  12. F Proof of Theorem 2
    1. F.1 Conditional min-entropy is a conditional entropy
  13. G Example of non-negative weakly additive monotonic function

##  I Introduction

Quantum information science is famously known for having features that are not
present in classical information science. Among these, perhaps the feature
that distinguishes it the most from the classical case is that our knowledge
of the state of two particles can be greater than our knowledge of the
individual states of the particles. Indeed, for an Einstein–Podolsky–Rosen
(EPR) state $|\Phi^{(2)}\rangle\coloneqq(|00\rangle+|11\rangle)/\sqrt{2}$
epr1935 , said to be entangled, our knowledge of the joint state of the two
particles is complete. However, the state of an individual particle is
described by an unbiased probabilistic ensemble (i.e., $|0\rangle$ or
$|1\rangle$ with equal probability), and we thus have incomplete knowledge of
the state of an individual particle S35 .

Given this peculiar situation, one of the earliest puzzles in quantum
information science was to devise a quantum generalization of the concept of
conditional entropy. In the classical case, conditional entropy is meant to
capture the uncertainty about the state of one particle given access to a
second particle that is potentially statistically dependent on the first S48 .
If there is no statistical dependence whatsoever, then the conditional entropy
reduces to the usual entropy. However, if there is dependence, then there is a
reduction in the uncertainty of the first particle when given access to the
second. When generalizing the definition of conditional entropy in a
straightforward way to the quantum case (by means of this reduction), one
finds that quantum conditional entropy is negative when evaluated for the EPR
state mentioned above CA97 . Since conditional entropy is never negative in
classical information science, this situation represents a radical departure
from the classical case and has been popularly described as “knowing less than
nothing” T05 .

In quantum information theory H17 ; W17 ; Watrous2018 ; H19book ; KW20book ,
the traditional approach to resolving such puzzles is to devise a physically
meaningful task for which an information quantity is an optimal rate for
accomplishing the task. For the case of quantum conditional entropy, this
approach was successfully applied and led to the introduction of the quantum
state merging protocol Horodecki2005 ; Horodecki:2007:107 . In this protocol,
the goal is for one party $A$ to use entanglement and classical communication
to transfer her share $A$ of a joint state to another party $B$. If the
conditional entropy $H(A|B)$ is non-negative, then the protocol consumes
entanglement to accomplish the task, at a rate given by $H(A|B)$ EPR states
per copy of the original state. Whereas, if the conditional entropy $H(A|B)$
is negative, then the protocol generates entanglement at a rate of $H(A|B)$
EPR states per copy of the original state, while transferring $A$ to $B$. This
protocol inspired further developments regarding conditional entropy in the
context of the uncertainty principle BCCRR10  and thermodynamics Rio2011a , in
which its negativity plays an essential role.

Although these works brought great insight to the peculiar situation mentioned
above, they mainly focus on a particular definition of the conditional
entropy, based on the formula from CA97 . It is also well known that there are
an infinite number of ways to define quantum conditional entropy, with
particular examples being the conditional min-entropy Renner2005 , conditional
max-entropy KRS09 , conditional Rényi entropies TCR09 ; MDSFT13 ; TBH13 , and
those based more broadly on generalized divergences (see, e.g., KW20book ).
Several of these alternate definitions have physical meanings as well KRS09 ;
HT16 . However, all of these definitions are based on particular mathematical
formulas for quantum conditional entropy that hitherto have not been derived
on the basis of simple physical principles. As such, the aforementioned
contributions do not address the question of why any plausible quantum
conditional entropy can be negative when defining it in the most general way
possible, which is consistent with some simple physical principles.

###  I.1 Summary of results

In this paper, it is our aim to address this pressing foundational question,
and we do so by introducing a physically motivated framework for defining
quantum conditional entropy, based on two simple postulates. The two
postulates are related to the second law of thermodynamics and the extensivity
of entropy, widely accepted in scenarios of physical interest. This novel
framework is essentially the simplest way of defining any plausible quantum
conditional entropy, and one of our main conclusions is that any such quantum
conditional entropy must take on a negative value when evaluated for the EPR
state. Following the popular terminology introduced in T05 , we can summarize
this finding as the “inevitability of knowing less than nothing” in the
quantum world. As such, our approach answers the aforementioned question,
i.e., why the quantum conditional entropy can be negative. We additionally
note here that this finding is in stark contrast to the conclusion, also
presented here, that any plausible unconditional quantum entropy takes on a
non-negative value for all quantum states (here quantum entropy is defined by
a similar physically motivated framework that generalizes the classical case
in GT2021 ).

As additional findings, we show that all plausible quantum conditional
entropies cannot be smaller than the quantum conditional min-entropy, thus
justifying once and for all the name of the latter quantity as the smallest
plausible quantum conditional entropy. We also establish a logical equivalence
between the non-negativity of all quantum conditional entropies and the well
known reduction criterion HH99  from entanglement theory. As a corollary, it
follows that all separable states have non-negative quantum conditional
entropy.

In what follows, we present details of our claims. We first generalize the
classical entropy framework from GT2021  in order to define quantum entropy,
and then we introduce our framework for defining quantum conditional entropy.
After that, we indicate several properties of quantum conditional entropy that
follow from the two postulates, before giving arguments for our main results.
All arguments for our main results are based on constructions of physical
processes that respect the first aforementioned postulate for quantum
conditional entropy. The only background needed to understand the rest of our
paper is basic knowledge of density operators and quantum channels (physical
processes), available in various textbooks on quantum information H17 ; W17 ;
Watrous2018 ; H19book ; KW20book .

###  I.2 Notation

Throughout our paper, we employ standard notation used in quantum information
H17 ; W17 ; Watrous2018 ; H19book ; KW20book . We use symbols like $\rho$,
$\sigma$, $\omega$ to refer to quantum states (density operators) and
$\mathfrak{D}(A)$ to denote the set of density operators acting on a Hilbert
space $A$. We also identify a quantum system $A$ with its corresponding
Hilbert space $A$. Let $\mathbf{u}_{A}\coloneqq I_{A}/|A|$ denote the uniform
state of a system $A$, where $I_{A}$ is the identity operator acting on $A$
and $|A|$ denotes the dimension of $A$. We use system labels to denote
bipartite states as $\rho_{AB},\sigma_{AB},\omega_{AB}\in\mathfrak{D}(AB)$,
and $\rho_{A}=\operatorname{Tr}_{B}[\rho_{AB}]$ denotes the marginal state
after performing a partial trace over system $B$. A quantum channel
$\mathcal{N}_{A\to B}$ is a completely positive and trace-preserving map that
takes an input system $A$ to an output system $B$. If the input and output
systems are the same, then we simply write $\mathcal{N}_{A}$. A particular
kind of quantum channel is an isometric channel, typically denoted by
$\mathcal{U}_{A\to B}$ or $\mathcal{V}_{A\to B}$, and is realized as
$\mathcal{U}_{A\to B}(\cdot)=U_{A\to B}(\cdot)(U_{A\to B})^{\dagger}$, where
$U_{A\to B}$ an isometry (i.e., it satisfies $(U_{A\to B})^{\dagger}U_{A\to
B}=I_{A}$).

##  II Uncertainty and entropy

###  II.1 Uncertainty measures

Let us first define what it means for a function to be an uncertainty measure,
following the approach of GT2021  for the classical case. What we expect for
any measure of uncertainty is that it does not decrease under the action of a
mixing operation. Thus, we demand that an uncertainty measure is a function
that is monotone with respect to a set of mixing operations, similar to how
one variant of the second law of thermodynamics states that the entropy of an
isolated system left to spontaneous evolution does not decrease. This approach
is also consistent with that taken in quantum resource theories when defining
resource monotones Chitambar_2019 , in turn inspired by the second law of
thermodynamics.

In the classical case of finite and discrete probability distributions, such a
mixing operation is described by a random relabeling of values. For example,
for a six-sided die described by a probability distribution, one can randomly
relabel or permute the numbers on the faces of the die to realize a mixing
operation, and the outcome of the die toss becomes more difficult to guess
(and intuitively, more uncertain). Furthermore, the odds of winning a game of
chance are lower after performing a mixing operation BGG22 , providing a
precise way of measuring uncertainty.

Under such mixing operations, the uniform distribution remains invariant.
Furthermore, our intuition is that the uniform distribution should take the
largest value of an uncertainty measure for all probability distributions of
the same size, given that it is an unbiased distribution with equally likely
outcomes and thus the unique distribution for which it is the most difficult
to guess which outcome will occur (more generally, for which one is the least
likely to win a game of chance BGG22 ). Given everything stated above, one
thus defines a function to be an uncertainty measure in the classical case if
it is not equal to the zero function (i.e., a function that trivially takes
all inputs to the value zero) and if it does not decrease under the action of
a mixing operation GT2021 .

In order to generalize this notion to the quantum case, the key previously
stated property that we use to define a mixing operation is the preservation
of the uniform state $\mathbf{u}$. In this way, it is guaranteed that a mixing
operation does not increase the value of an uncertainty measure for the
uniform state; rather, it remains constant. Indeed, such a state is already
intuitively maximally uncertain, as argued above, and so it cannot be any more
uncertain, among all states of a fixed dimension. At the very least, the
mixing operations we consider for defining an uncertainty measure should be
quantum channels because all physical processes are described by quantum
channels. The additional property of preserving the uniform state thus
constrains the mixing operations to be unital channels (i.e., channels that
preserve the identity operator). Formally, recall that a channel
$\mathcal{N}_{A}$ is unital if $\mathcal{N}_{A}(I_{A})=I_{A}$, or
equivalently, if $\mathcal{N}_{A}(\mathbf{u}_{A})=\mathbf{u}_{A}$ H17 ; W17 ;
Watrous2018 ; H19book ; KW20book . We thus define a function of quantum states
to be an uncertainty measure if it is not equal to the zero function and if it
does not decrease under the action of a unital channel $\mathcal{N}_{A}$,
i.e.,

$f(\mathcal{N}_{A}(\rho_{A}))\geq f(\rho_{A})$ (1)

for every state $\rho_{A}$ and unital channel $\mathcal{N}_{A}$.

A state $\rho_{A}$ majorizes another state $\sigma_{A}$, denoted by
$\rho_{A}\succ\sigma_{A}$, if the following inequalities hold for all
$k\in\\{1,\ldots,|A|\\}$:

$\sum_{i=1}^{k}\lambda_{i}^{\downarrow}(\rho_{A})\geq\sum_{i=1}^{k}\lambda_{i}^{\downarrow}(\sigma_{A}),$
(2)

where $\lambda_{i}^{\downarrow}(\omega_{A})$ denotes the components of the
vector of eigenvalues of a density operator $\omega_{A}$ sorted in decreasing
order. It is well known that $\rho_{A}$ majorizes $\sigma_{A}$ if and only if
there exists a unital channel $\mathcal{N}_{A}$ such that
$\sigma_{A}=\mathcal{N}_{A}(\rho_{A})$ U71 ; U72 ; U73  (see also
(Watrous2018, , Theorem 4.32)). Thus, our definition of an uncertainty measure
$f$ implies that $f$ reverses the majorization pre-order, i.e.,

$\rho_{A}\succ\sigma_{A}\Rightarrow f(\rho_{A})\leq f(\sigma_{A}).$ (3)

It is ideal and natural to generalize the definition of an uncertainty measure
just slightly in order to compare the uncertainties of states of different
dimensions. Suppose that we have a state $\rho_{A}$ with an uncertainty value
given by $f(\rho_{A})$ for some uncertainty measure $f$. Now consider the
density matrix $\rho_{A^{\prime}}\coloneqq\rho_{A}\oplus{\bf 0}$, where ${\bf
0}$ denotes the zero square matrix, so that $\rho_{A^{\prime}}$ represents an
embedding of $\rho_{A}$ into a larger system $A^{\prime}$. There is no reason
that the uncertainty measure should change at all under this embedding,
because, intuitively, the extra matrix entries corresponding to ${\bf 0}$
neither increase nor decrease uncertainty. Indeed, when flipping a die on a
table, one could add an extra degree of freedom corresponding to whether the
table is upside down or right side up, and under normal circumstances, the
table will never be upside down, so that the uncertainty of the die toss will
be unaffected by this embedding. As such, we impose the additional constraint
that the uncertainty measure $f$ satisfies the equality
$f(\rho_{A})=f(\rho_{A^{\prime}})$ for every state $\rho_{A}$ and every
embedding into a larger system $A^{\prime}$.

In this spirit, we now generalize the standard definition of majorization for
quantum states from U71 ; U72 ; U73  (see also Watrous2018 ). Given two states
$\rho_{A}$ and $\sigma_{A^{\prime}}$, we say that $\rho_{A}$ majorizes
$\sigma_{A^{\prime}}$, and write

$\rho_{A}\succ\sigma_{A^{\prime}}$ (4)

if either $|A^{\prime}|\geq|A|$, there exists an isometric channel
$\mathcal{V}_{A\to A^{\prime}}$, and a unital channel $\mathcal{N}_{A}$, such
that

$\displaystyle\sigma_{A^{\prime}}=(\mathcal{V}_{A\to
A^{\prime}}\circ\mathcal{N}_{A})(\rho_{A})\;,$ (5)

or $|A|\geq|A^{\prime}|$, there exists an isometric channel
$\mathcal{U}_{A^{\prime}\to A}$, and a unital channel $\mathcal{N}_{A}$, such
that

$\displaystyle\mathcal{U}_{A^{\prime}\to
A}\left(\sigma_{A^{\prime}}\right)=\mathcal{N}_{A}(\rho_{A}).$ (6)

The isometric channels introduced in the definition of majorization above
enable us to compare states of different dimensions, as desired. Also, note
that majorization between two probability vectors of the same dimension can be
extended to vectors of different dimensions in this way (it is a standard
approach to add zero components to the vector with the smaller dimension so
that the resulting vectors have equal dimension). As discussed in the previous
paragraph, such an extension is motivated by the fact that uncertainty
measures should not change under embeddings.

In conclusion, our final definition of an uncertainty measure is a function
$f$ that is not equal to the zero function and reverses the majorization pre-
order from (4); i.e., for all states $\rho_{A}$ and $\sigma_{A^{\prime}}$,

$\rho_{A}\succ\sigma_{A^{\prime}}\Rightarrow f(\rho_{A})\leq
f(\sigma_{A^{\prime}}).$ (7)

###  II.2 Entropy

Following the approach of GT2021  for the classical case, an uncertainty
measure is not necessarily an entropy. To be an entropy, we also require that
the uncertainty measure possess an extensivity or additivity property. That
is, $f$ is an entropy if it is an uncertainty measure and it is additive on
tensor-product states; i.e., for all states $\rho_{A}$ and
$\sigma_{A^{\prime}}$,

$f(\rho_{A}\otimes\sigma_{A^{\prime}})=f(\rho_{A})+f(\sigma_{A^{\prime}}).$
(8)

The additivity postulate of entropy is motivated by the basic expectation that
the disorder of isolated, non-interacting systems should be the sum of the
individual disorders. Indeed, if two physical systems are separate from each
other, not having interacted in any way whatsoever previously, we expect that
the disorder characterizing the overall system should simply be the sum of the
individual disorders (i.e., there would not be a meaningful alternative way of
quantifying the overall disorder in this scenario).

The motivation for additivity of entropy is also related to the second law of
thermodynamics, in particular, the Clausius and Kelvin–Planck statements. In
those statements, cyclic processes are considered, in which a system of
interest undergoes a thermodynamic transition, while all other systems,
including the environment, heat baths, etc., all return to their original
state. In recent developments, using a quantum information-theoretic approach
to small-scale thermodynamics BHNOW15 , these cyclic processes were identified
as catalytic processes. That is, consider a thermodynamical evolution of a
physical system $A$, in a state $\rho_{A}$, to a physical system $A^{\prime}$
in a state $\sigma_{A^{\prime}}$. The thermal machine that corresponds to this
transition includes all the other systems (e.g., heat baths, environment,
etc.) that can be represented with an additional system $M$ in a state
$\tau_{M}$. Therefore, for cyclic processes, the thermodynamical transition
takes the form

$\rho_{A}\otimes\tau_{M}\to\sigma_{A^{\prime}}\otimes\tau_{M}\;.$ (9)

In this context, the second law not only states that the entropy of system $A$
is no greater than that of system $A^{\prime}$, but also that this property
holds if and only if the entropy of the joint state $\rho_{A}\otimes\tau_{M}$
increases (or remains unchanged) in such a thermodynamic cyclic process that
returns $\tau_{M}$ intact. Clearly, if the entropy is measured with an
additive function (under tensor products) then the entropy of $\rho_{A}$ is
never greater than that of $\sigma_{A^{\prime}}$ if and only if the same
relation holds between $\rho_{A}\otimes\tau_{M}$ and
$\sigma_{A^{\prime}}\otimes\tau_{M}$. Thus, the second law of thermodynamics
also motivates the additivity postulate for entropy.

With all of this reasoning in place, we now provide a formal definition of
entropy: a function

$\mathbf{H}:\bigcup_{A}\mathfrak{D}(A)\rightarrow\mathbb{R}$ (10)

is a quantum entropy if it is not equal to the zero function and satisfies the
following two postulates for all systems $A$ and $A^{\prime}$ and states
$\rho_{A}$ and $\sigma_{A^{\prime}}$:

  1. 1.

Monotonicity:

$\rho_{A}\succ\sigma_{A^{\prime}}\quad\Rightarrow\quad\mathbf{H}(\rho_{A})\leq\mathbf{H}(\sigma_{A^{\prime}}).$
(11)

  2. 2.

Additivity:

$\mathbf{H}(\rho_{A}\otimes\sigma_{A^{\prime}})=\mathbf{H}(\rho_{A})+\mathbf{H}(\sigma_{A^{\prime}}).$
(12)

As stated previously, the requirement that an entropy not be equal to the zero
function is to avoid a trivial situation in which the entropy of every state
takes on the value zero.

By employing the two basic postulates of entropy and the same reasoning given
in (GT2021, , Lemma 3), some important properties follow (see Appendix A for
proofs). The entropy of every state $\rho$ is non-negative, i.e.,
$\mathbf{H}(\rho)\geq 0$, and it is equal to zero for every pure state
$|\psi\rangle\\!\langle\psi|$, i.e.,
$\mathbf{H}(|\psi\rangle\\!\langle\psi|)=0$. For every state $\sigma$ of a
fixed dimension $d$, the entropy does not exceed the entropy of the uniform
state of dimension $d$, i.e.,
$\mathbf{H}(\mathbf{u}^{(d)})\geq\mathbf{H}(\sigma)$. Finally, the entropy of
the uniform state of dimension two is strictly positive, i.e.,
$\mathbf{H}(\mathbf{u}^{(2)})>0$. This allows for setting the normalization of
entropy to be in units of bits, such that $\mathbf{H}(\mathbf{u}^{(2)})=1$,
and henceforth, we thus set the normalization of entropy in this way. It then
follows that $\mathbf{H}(\mathbf{u}^{(d)})=\log_{2}d$.

##  III Conditional uncertainty and entropy

###  III.1 Conditional uncertainty measures

Our goal now is to define what it means for a function of a bipartite state
$\rho_{AB}$ to be a measure of conditional uncertainty. Inspired by the
criterion of monotonicity under mixing operations in the previous case of
unconditional uncertainty, we are interested in identifying a criterion for a
bipartite channel $\mathcal{N}_{AB\to A^{\prime}B^{\prime}}$ to be a
conditional mixing operation. For the unconditional case, we ultimately stated
that a quantum channel is a mixing operation if it preserves the uniform
state, and this choice led to identifying unital channels as the mixing
operations that define an uncertainty measure. The reason for this, as
previously stated, is that the uniform state is the least informative state,
it thus gives the least likelihood of winning a game of chance, and should
thus be a state of maximal uncertainty (for which a mixing operation cannot
increase uncertainty).

For the setting of conditional uncertainty, it remains the case that the
uniform state $\mathbf{u}_{AB}=\mathbf{u}_{A}\otimes\mathbf{u}_{B}$ is the
least informative state, for reasons similar to those given before. However,
for conditional uncertainty, we are interested in the uncertainty of system
$A$ in the presence of system $B$. That is, the system $B$ can be used as an
aid or side information to help win a game of chance performed on the system
$A$. With this in mind, a state of the form $\mathbf{u}_{A}\otimes\rho_{B}$ is
still least informative, with $\rho_{B}$ an arbitrary state, because the
system $B$ is independent of system $A$ and thus cannot help at all in winning
a game of chance performed on $A$. At the same time, the state of system $A$
is still uniform and thus the least informative. As such, we identify the set
of states having the form $\mathbf{u}_{A}\otimes\rho_{B}$, where $\rho_{B}$ is
an arbitrary state of system $B$, as being the set of states with maximum
conditional uncertainty.

Thus, we have argued that one requirement for a function to be a measure of
conditional uncertainty is that it should not decrease under the action of a
bipartite channel that preserves the set of states with maximum conditional
uncertainty. We call such channels conditionally unital channels because they
generalize unital channels. Formally, a bipartite channel
$\mathcal{N}_{AB\rightarrow{AB^{\prime}}}$ is a conditionally unital channel
if for every $\rho_{B}\in\mathfrak{D}(B)$, there exists a state
$\sigma_{B^{\prime}}\in\mathfrak{D}(B^{\prime})$ such that

$\displaystyle\mathcal{N}_{AB\rightarrow{AB^{\prime}}}(\mathbf{u}_{A}\otimes\rho_{B})=\mathbf{u}_{A}\otimes\sigma_{B^{\prime}}.$
(13)

See Appendix B.1 for an equivalent formulation of this condition in terms of
the Choi matrix of $\mathcal{N}_{AB\rightarrow{AB^{\prime}}}$. We note here
that conditionally unital channels were independently defined in our companion
paper BGWG21  and in Vempati2022unitaloperations . See also (Renner2005, ,
Lemma 3.1.12) for an implicit definition of sub-conditionally-unital channels.

In the setting of conditional uncertainty, it is important to consider a
further constraint on the class of transformations allowed. Intuitively,
conditional uncertainty measures the uncertainty of system $A$ when one is
given access to system $B$. Evidently, by allowing transformations in which
information can leak from system $A$ to system $B$, Bob could gain information
that could decrease the uncertainty associated with system $A$. Thus, it is
natural to assume that channels that do not decrease conditional uncertainty
do not allow for communication or signaling from Alice to Bob. This
requirement is also motivated from a cryptographic perspective, in which
conditional uncertainty measures the amount of uncertainty that an
eavesdropper has about another system that is intended to be secure PR22
(with respect to our system labeling, the eavesdropper would have system $B$
and the secure system would be $A$). With this motivation in mind, let us
recall the definition of $A\not\to B$ semi-causal channels Beckman_2001 . A
bipartite channel $\mathcal{N}_{AB\rightarrow AB^{\prime}}$ is $A\not\to
B^{\prime}$ semi-causal if for every channel $\mathcal{M}_{A}$

$\displaystyle\mathcal{N}_{AB\rightarrow
B^{\prime}}\circ\mathcal{M}_{A}=\mathcal{N}_{AB\rightarrow B^{\prime}},$ (14)

where

$\mathcal{N}_{AB\rightarrow
B^{\prime}}\coloneqq\operatorname{Tr}_{A}\circ\mathcal{N}_{AB\rightarrow
AB^{\prime}}.$ (15)

See Figure 1 for a depiction of the semi-causality requirement.

\begin{overpic}[scale={0.5}]{figures/semicausal}
\put(20.0,44.0){$\mathcal{M}$} \put(59.0,30.0){$\mathcal{N}$}
\put(183.0,30.0){$\mathcal{N}$} \end{overpic} Figure 1: Depiction of the
definition of a semi-causal channel $\mathcal{N}$, where the black square
represents the discarding channel.

The authors of ESW02  proved that every semi-causal channel can be written as
a local channel on $B$ that feeds an output (corresponding to a quantum system
$R$) into a channel acting only on $A$ and $R$. See also Piani_2006  and
Figure 2 for a visual depiction. As such, for these channels, information can
only flow from $B$ to $A$, and it never leaks from $A$ to $B$. Formally, if
$\mathcal{N}_{AB\rightarrow AB^{\prime}}$ is an $A\not\to B^{\prime}$ semi-
causal channel, then there exists a quantum system $R$, a quantum channel
$\mathcal{E}_{AR\rightarrow A}$, and an isometric channel
$\mathcal{F}_{B\rightarrow RB^{\prime}}$ such that

$\mathcal{N}_{AB\rightarrow AB^{\prime}}=\mathcal{E}_{RA\rightarrow
A}\circ\mathcal{F}_{B\rightarrow RB^{\prime}}\;.$ (16)

\begin{overpic}[scale={0.6}]{figures/semicausalfig2}
\put(62.0,80.0){$\mathcal{N}_{AB\to AB^{\prime}}$}
\put(43.0,22.0){$\mathcal{F}$} \put(112.0,55.0){$\mathcal{E}$}
\put(67.0,32.0){$R$} \put(8.0,25.0){$B$} \put(8.0,65.0){$A$}
\put(147.0,62.0){$A$} \put(147.0,20.0){$B^{\prime}$} \end{overpic} Figure 2:
Eq. (16) asserts that a semi-causal bipartite channel
$\mathcal{N}_{AB\rightarrow AB^{\prime}}$ can be implemented in the depicted
fashion.

We use the term locally balanced to describe a channel $\mathcal{N}_{AB\to
AB^{\prime}}$ that is both conditionally unital and $A\not\to B^{\prime}$
semi-causal. We use this term because the properties of such a channel are
invariant under the exchange of the $A$ input and $A$ output systems. This is
most readily observed using the formalism of Choi matrices and we discuss it
further in Appendix B.2. Importantly, we use locally balanced channels to
define measures of conditional uncertainty.

Generalizing how unital channels define the majorization pre-order on quantum
states, we now define a conditional majorization pre-order on bipartite
quantum states, based on locally balanced channels. Given two bipartite states
$\rho_{AB}$ and $\sigma_{A^{\prime}B^{\prime}}$, we say that $\rho_{AB}$
conditionally majorizes $\sigma_{A^{\prime}B^{\prime}}$ with respect to system
$A$, and write

$\rho_{AB}\succ_{A}\sigma_{A^{\prime}B^{\prime}}$ (17)

if either $|A^{\prime}|\geq|A|$, there exists an isometric channel
$\mathcal{V}_{A\to A^{\prime}}$, and a locally balanced channel
$\mathcal{N}_{AB\rightarrow AB^{\prime}}$, such that

$\displaystyle\sigma_{A^{\prime}B^{\prime}}=\mathcal{V}_{A\to
A^{\prime}}\circ\mathcal{N}_{AB\rightarrow AB^{\prime}}(\rho_{AB})\;,$ (18)

or $|A|\geq|A^{\prime}|$, there exists an isometric channel
$\mathcal{U}_{A^{\prime}\to A}$, and a locally balanced channel
$\mathcal{N}_{AB\rightarrow AB^{\prime}}$, such that

$\displaystyle\mathcal{U}_{A^{\prime}\to
A}\left(\sigma_{A^{\prime}B^{\prime}}\right)=\mathcal{N}_{AB\rightarrow
AB^{\prime}}(\rho_{AB}).$ (19)

The isometric channels introduced in the definition above enable us to compare
bipartite states of different dimensions, as was the case before with the
generalized definition of majorization in (4)–(6). We note here that
conditional majorization, as defined here, reduces to classical conditional
majorization, as defined in GGHKLV18 , when the the states involved are
classical (see Appendix C for a proof).

We define a function $f$ to be a conditional uncertainty measure if it is not
equal to the zero function and if it reverses the conditional majorization
pre-order, i.e.,

$\rho_{AB}\succ_{A}\sigma_{A^{\prime}B^{\prime}}\quad\Rightarrow\quad
f(\rho_{AB})\leq f(\sigma_{A^{\prime}B^{\prime}}).$ (20)

###  III.2 Conditional entropy

Having defined measures of conditional uncertainty, we now follow the approach
from before and define a function to be a conditional entropy if it is not
only a conditional uncertainty measure but also additive on tensor-product
states. Our motivation for the additivity postulate is the same as before.
Formally, a function

$\mathbf{H}:\bigcup_{A,B}\mathfrak{D}(AB)\rightarrow\mathbb{R}$ (21)

is a quantum conditional entropy if it is not equal to the zero function and
satisfies the following postulates for all systems $A$, $B$, $A^{\prime}$,
$B^{\prime}$ and states $\rho_{AB}$ and $\sigma_{A^{\prime}B^{\prime}}$:

  1. 1.

Monotonicity:

$\rho_{AB}\succ_{A}\sigma_{A^{\prime}B^{\prime}}\quad\Rightarrow\quad\mathbf{H}(A|B)_{\rho}\leq\mathbf{H}(A^{\prime}|B^{\prime})_{\sigma}.$
(22)

  2. 2.

Additivity:

$\mathbf{H}(AA^{\prime}|BB^{\prime})_{\rho\otimes\sigma}=\mathbf{H}(A|B)_{\rho}+\mathbf{H}(A^{\prime}|B^{\prime})_{\sigma}.$
(23)

As indicated in the definition, a conditional entropy $\mathbf{H}$ is defined
for all density matrices in all finite dimensions. As a very special case, if
$\rho\in\mathfrak{D}(AB)$ and $B$ is a trivial system for which $|B|=1$, then
we write

$\mathbf{H}(A|B)_{\rho}=\mathbf{H}(A)_{\rho}\;,$ (24)

where $\mathbf{H}(A)_{\rho}$ is an entropy, as defined before.

Here we state some basic properties of quantum conditional entropy before
presenting our main result in the next section (see Appendix D for proofs).
First, conditional entropy reduces to entropy when evaluated on a tensor-
product state. That is, for every product state $\omega_{A}\otimes\tau_{B}$,
the following equality holds:

$\mathbf{H}(A|B)_{\omega\otimes\tau}=\mathbf{H}(A)_{\omega}.$ (25)

Next, conditional entropy is invariant under the action of local isometric
channels. That is, for a bipartite state $\rho_{AB}$ and isometric channels
$\mathcal{U}_{A\to A^{\prime}}$ and $\mathcal{V}_{B\to B^{\prime}}$,

$\mathbf{H}(A|B)_{\rho}=\mathbf{H}(A^{\prime}|B^{\prime})_{\omega},$ (26)

where $\omega_{AB^{\prime}}\coloneqq(\mathcal{U}_{A\to
A^{\prime}}\otimes\mathcal{V}_{B\to B^{\prime}})(\rho_{AB})$. Finally,
consider the product state $\mathbf{u}^{(2)}_{A}\otimes\rho_{B}$. Similar to
what we found previously for unconditional entropy, the following inequality
holds

$\mathbf{H}(A|B)_{\mathbf{u}^{(2)}\otimes\rho}=\mathbf{H}(A)_{\mathbf{u}^{(2)}}>0.$
(27)

This strict inequality allows us to set a normalization factor for conditional
entropy. To be consistent with the normalization convention for unconditional
entropy, we set $\mathbf{H}(A|B)_{\mathbf{u}^{(2)}\otimes\rho}=1$, which in
turn implies that

$\mathbf{H}(A|B)_{\mathbf{u}^{(d)}\otimes\rho}=\log_{2}d,$ (28)

where the state being evaluated is $\mathbf{u}^{(d)}_{A}\otimes\rho_{B}$.

##  IV Main result: Inevitability of negative quantum conditional entropy

We now have almost everything set up to state our main result. Before doing
so, let us define the conditional min-entropy Renner2005  of a bipartite state
$\rho_{AB}$ as

$H_{\min}(A|B)_{\rho}\coloneqq-\inf_{\lambda\geq
0}\log_{2}\\{\lambda:\rho_{AB}\leq\lambda I_{A}\otimes\rho_{B}\\},$ (29)

The conditional min-entropy is indeed a conditional entropy according to
(22)–(23) (see Appendix F.1 for a proof). This quantity was previously given
the name conditional min-entropy because it is known to be the least among all
Rényi conditional entropies Renner2005 ; TCR09 ; MDSFT13 . As part of our main
result, we strengthen this observation by proving that all plausible quantum
conditional entropies are not smaller than the conditional min-entropy; that
is, the conditional min-entropy is the least plausible.

The following theorem (proved in Appendix E.2) states that every plausible
quantum conditional entropy is bounded from below by the conditional min-
entropy and also that this lower bound is saturated for the maximally
entangled state. As a consequence, every plausible conditional entropy takes
on a negative value for the maximally entangled state.

###### Theorem 1

Let $\mathbf{H}$ be a quantum conditional entropy, as defined in (21)–(23).
Then, for every state $\rho_{AB}$,

$\mathbf{H}(A|B)_{\rho}\geq H_{\min}(A|B)_{\rho}.$ (30)

Equality is attained in (30) if $\rho_{AB}$ is equal to a maximally entangled
state $\Phi^{(k)}_{A^{\prime}B^{\prime}}$ by the action of local isometric
channels. Thus,

$\mathbf{H}(A|B)_{\Phi^{(k)}}=-\log_{2}k$ (31)

for every conditional entropy $\mathbf{H}$.

The following statement is a direct consequence of Theorem 1, indicating that
every plausible conditional entropy being non-negative is equivalent to the
reduction criterion HH99 , well known in entanglement theory. Thus, Corollary
1 provides a direct link between every conditional entropy (including the
conditional min-entropy) and the reduction criterion.

###### Corollary 1

Let $\rho_{AB}$ be a bipartite state. Then, the following are equivalent:

  1. 1.

For every conditional entropy $\mathbf{H}$,

$\mathbf{H}(A|B)_{\rho}\geq 0.$ (32)

  2. 2.

The reduction criterion holds: $I_{A}\otimes\rho_{B}\geq\rho_{AB}$.

The proof of Corollary 1 is immediate from Theorem 1. Indeed, if the first
condition holds, then the inequality $H_{\min}(A|B)_{\rho}\geq 0$ holds in
particular (since $H_{\min}(A|B)_{\rho}$ is a conditional entropy), and the
second condition is then a consequence of the definition in (29). Now suppose
that the second condition holds. This then means that there exists
$\lambda\leq 1$ such that $\rho_{AB}\leq\lambda I_{A}\otimes\rho_{B}$.
According to the definition in (29), it follows that $H_{\min}(A|B)_{\rho}\geq
0$ and then Theorem 1 implies the first condition.

Suppose that a state $\rho_{AB}$ is separable W89 , meaning that it can be
written as a probabilistic mixture of product states (i.e.,
$\rho_{AB}=\sum_{x}p(x)\sigma^{x}_{A}\otimes\tau^{x}_{B}$ for some probability
distribution $\\{p(x)\\}_{x}$ and sets $\\{\sigma^{x}_{A}\\}_{x}$ and
$\\{\tau^{x}_{B}\\}_{x}$ of states). Then it follows that the second condition
in Corollary 1 holds HH99 , so that every conditional entropy is non-negative
for all separable states.

Although all plausible conditional entropies are non-negative on all separable
states, this does not mean that the conditional entropies are only non-
negative on separable states. In fact, some entangled states have non-negative
conditional entropy on _all_ choices of conditional entropy functions. In
light of this, Corollary 1 is helpful because it provides a simple sufficient
criterion for a bipartite state to have non-negative quantum conditional
entropy.

In Appendix E, we discuss a subclass of conditional entropies and report
results that are similar to those given in Theorem 1 and Corollary 1. The
difference is that the lower bound in (30) is expressed in terms of a
different definition of conditional min-entropy and the equivalent condition
in Corollary 1 becomes a variation of the reduction criterion, rather than the
reduction criterion itself.

##  V Conditional entropy from relative entropy

In this section, we prove that one can construct a quantum conditional entropy
from a quantum relative entropy, based on two simple postulates that define a
quantum relative entropy GT2021 ; GT20 . Before giving this construction, let
us first recall the definition of a quantum relative entropy GT2021 ; GT20 .
Formally, a function

$\mathbf{D}:\bigcup_{A}\\{\mathfrak{D}(A)\times\mathfrak{D}(A)\\}\rightarrow\mathbb{R}_{+}\cup\\{\infty\\}$
(33)

is a quantum relative entropy if it is not equal to the zero function and
satisfies the following postulates for all systems $A$ and $B$, all states
$\rho_{A}$, $\sigma_{A}$, $\omega_{B}$, $\tau_{B}$, and every channel
$\mathcal{N}_{A\to B}$:

  1. 1.

Monotonicity:

$\mathbf{D}(\rho_{A}\|\sigma_{A})\geq\mathbf{D}(\mathcal{N}_{A\to
B}(\rho_{A})\|\mathcal{N}_{A\to B}(\sigma_{A})).$ (34)

  2. 2.

Additivity:

$\mathbf{D}(\rho_{A}\otimes\omega_{B}\|\sigma_{A}\otimes\tau_{B})=\mathbf{D}(\rho_{A}\|\sigma_{A})+\mathbf{D}(\omega_{B}\|\tau_{B}).$
(35)

Now we state our final result (see Appendix F for a proof):

###### Theorem 2

Let $\mathbf{D}$ be a quantum relative entropy. Then the function

$\mathrm{log}_{2}|A|-\mathbf{D}(\rho_{AB}\|\mathbf{u}_{A}\otimes\rho_{B})$
(36)

is a quantum conditional entropy.

Suitable relative entropies include the Umegaki (standard) U62 ,
Belavkin–Staszewski Belavkin1982 , Petz–Rényi P85 ; P86 , sandwiched Rényi
MDSFT13 ; WWY14 , $\alpha$-$z$ AD15 , and geometric Rényi M13 ; Matsumoto2018
relative entropies, for which we point to KW20book  for a summary. The
construction in (36), for generating a conditional entropy from a relative
entropy, has been known for some time, but the difference with our result here
is that we prove, starting from the simple postulates for relative entropy in
(33)–(35), that the function in (36) satisfies the two simple postulates for
conditional entropy in (21)–(23).

##  VI Conclusion

In summary, we have established a physically motivated, minimal framework for
defining conditional entropies, based on two simple postulates (non-decrease
under locally balanced channels and additivity on tensor-product states). We
then explored the consequences of these postulates, which include reduction to
entropy for tensor-product states, invariance under local isometric channels,
a lower bound in terms of the conditional min-entropy, and taking on a
negative value for the maximally entangled state. We consider the latter
property to be the most profound result of this work, and all of our arguments
rely on constructing physical processes that respect the first postulate of
non-decrease under locally balanced channels.

One may wonder if it might be possible to replace the additivity postulate of
conditional entropy with a weaker criterion. For example, suppose we replace
the additivity postulate (23) with a weaker postulate of the form

$\mathbf{H}(A^{n}|B^{n})_{\rho^{\otimes
n}}=n\mathbf{H}(A|B)_{\rho}\quad\forall n\in\mathbb{N}.$ (37)

In Appendix G we show that there exist examples of functions that satisfy both
the monotonicity postulate and the above weak additivity, but take a non-
negative value on _all_ states. Therefore, the negativity of conditional-
entropies (as defined in this paper) on the maximally entangled state is
closely related to the (strong) additivity postulate (23).

Every relative entropy $\mathbf{D}$, can be used as in (36) to define a
conditional entropy. One can also attempt to define another type of
conditional entropy of the form

$\log_{2}|A|-\min_{\sigma\in\mathfrak{D}(B)}\mathbf{D}(\rho_{AB}\|\mathbf{u}_{A}\otimes\sigma_{B})\;.$
(38)

While the function above behaves monotonically under conditional unital
channels, and therefore satisfies the monotonicity postulate (22) it is not
clear if this function is additive under tensor products. It is known to be
additive if $\mathbf{D}$ is taken to be the Petz Rényi relative entropy (SW13,
, Lemma 3) or the sandwiched Rényi relative entropy Bei13 , but it is not
known if it is additive in general.

From its definition, the set of all conditional entropies is convex. Hence,
not every conditional entropy has to take the form of dimension minus
divergence. For example, if $\mathbf{D}$ is one of the quantum Rényi relative
entropies then every convex combination of the functions (36) and (38) is also
a conditional entropy. It is an interesting open problem if there exists
conditional entropies that cannot be expressed in terms of divergences.
Another interesting open problem is whether or not all quantum conditional
entropies are upper bounded by the conditional max-entropy. We leave these
open problems to future investigations.

###### Acknowledgements.

The authors thank Henry Pfister for helpful discussions. GG and IG acknowledge
support from the Natural Sciences and Engineering Research Council of Canada
(NSERC). SB acknowledges support from the National Science Foundation (NSF)
under Grant Nos. 1908730 and 1910571. MMW acknowledges support from the NSF
under Grant No. 1907615. Any opinions, findings, conclusions, and
recommendations expressed in this material are those of the authors and do not
necessarily reflect the views of these sponsors.

## References

  * (1) Albert Einstein, Boris Podolsky, and Nathan Rosen.  Can quantum-mechanical description of physical reality be considered complete?  Physical Review, 47:777–780, 1935.
  * (2) Erwin Schrödinger.  Discussion of probability relations between separated systems.  Proceedings of the Cambridge Philosophical Society, 31:555–563, 1935.
  * (3) Claude E. Shannon.  A mathematical theory of communication.  The Bell System Technical Journal, 27(3):379–423, 1948.
  * (4) Nicolas J. Cerf and Christoph Adami.  Negative entropy and information in quantum mechanics.  Physical Review Letters, 79(26):5194–5197, December 1997.
  * (5) Ian Turner.  Scientist knows less than nothing.  Bristol Evening Post, August 2005.  Screenshot available at https://twitter.com/markwilde/status/1558125303569846278.
  * (6) Masahito Hayashi.  Quantum Information Theory: Mathematical Foundation.  Springer, second edition, 2017.
  * (7) Mark M. Wilde.  Quantum Information Theory.  Cambridge University Press, second edition, 2017.  arXiv:1106.1445.
  * (8) John Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.
  * (9) Alexander S. Holevo.  Quantum Systems, Channels, Information: A Mathematical Introduction.  Walter de Gruyter, second edition, 2019.
  * (10) Sumeet Khatri and Mark M. Wilde.  Principles of Quantum Communication Theory: A Modern Approach.  November 2020.  arXiv:2011.04672v1.
  * (11) Michał Horodecki, Jonathan Oppenheim, and Andreas Winter.  Partial quantum information.  Nature, 436(7051):673–676, August 2005.
  * (12) Michal Horodecki, Jonathan Oppenheim, and Andreas Winter.  Quantum state merging and negative information.  Communications in Mathematical Physics, 269(1):107–136, January 2007.  arXiv:quant-ph/0512247.
  * (13) Mario Berta, Matthias Christandl, Roger Colbeck, Joseph M. Renes, and Renato Renner.  The uncertainty principle in the presence of quantum memory.  Nature Physics, 6:659–662, 2010.  arXiv:0909.0950.
  * (14) Lídia del Rio, Johan Åberg, Renato Renner, Oscar Dahlsten, and Vlatko Vedral.  The thermodynamic meaning of negative entropy.  Nature, 474(7349):61–63, 2011.
  * (15) Renato Renner.  Security of Quantum Key Distribution.  PhD thesis, ETH Zurich, September 2005.  arXiv:quant-ph/0512258.
  * (16) Robert Koenig, Renato Renner, and Christian Schaffner.  The operational meaning of min- and max-entropy.  IEEE Transactions on Information Theory, 55(9):4337–4347, September 2009.  arXiv:0807.1338.
  * (17) Marco Tomamichel, Roger Colbeck, and Renato Renner.  A fully quantum asymptotic equipartition property.  IEEE Transactions on Information Theory, 55(12):5840–5847, December 2009.  arXiv:0811.1221.
  * (18) Martin Müller-Lennert, Frédéric Dupuis, Oleg Szehr, Serge Fehr, and Marco Tomamichel.  On quantum Rényi entropies: a new generalization and some properties.  Journal of Mathematical Physics, 54(12):122203, December 2013.  arXiv:1306.3142.
  * (19) Marco Tomamichel, Mario Berta, and Masahito Hayashi.  Relating different quantum generalizations of the conditional Rényi entropy.  Journal of Mathematical Physics, 55(8):082206, August 2014.  arXiv:1311.3887.
  * (20) Masahito Hayashi and Marco Tomamichel.  Correlation detection and an operational interpretation of the rényi mutual information.  Journal of Mathematical Physics, 57(10):102201, October 2016.
  * (21) Gilad Gour and Marco Tomamichel.  Entropy and relative entropy from information-theoretic principles.  IEEE Transactions on Information Theory, 67(10):6313–6327, 2021\.
  * (22) Michał Horodecki and Paweł Horodecki.  Reduction criterion of separability and limits for a class of distillation protocols.  Physical Review A, 59(6):4206–4216, June 1999.
  * (23) Eric Chitambar and Gilad Gour.  Quantum resource theories.  Reviews of Modern Physics, 91(2):025001, April 2019.
  * (24) Sarah Brandsen, Isabelle Jianing Geng, and Gilad Gour.  What is entropy? a perspective from games of chance.  Physical Review E, 105(2):024117, February 2022.
  * (25) Armin Uhlmann.  Sätze über dichtematrizen.  Wissenschaftliche Zeitschrift der Karl-Marx-Universitat Leipzig. Mathematisch-naturwissenschaftliche Reihe, 20(4/5):633–653, 1971.
  * (26) Armin Uhlmann.  Endlich-dimensionale dichtematrizen i.  Wissenschaftliche Zeitschrift der Karl-Marx-Universitat Leipzig. Mathematisch-naturwissenschaft-liche Reihe, 21(4):421–452, 1972.
  * (27) Armin Uhlmann.  Endlich-dimensionale dichtematrizen ii.  Wissenschaftliche Zeitschrift der Karl-Marx-Universitat Leipzig Mathematisch-naturwissenschaft-liche Reihe, 22(2):139–177, 1973.
  * (28) Fernando G. S. L. Brandão, Michal Horodecki, Nelly Ng, Jonathan Oppenheim, and Stephanie Wehner.  The second laws of quantum thermodynamics.  Proceedings of the National Academy of Sciences, 112(11):3275–3279, March 2015.  arXiv:1305.5278.
  * (29) Sarah Brandsen, Isabelle J. Geng, Mark M. Wilde, and Gilad Gour.  Quantum conditional entropy from information-theoretic principles.  October 2021.  arXiv:2110.15330.
  * (30) Mahathi Vempati, Saumya Shah, Nirman Ganguly, and Indranil Chakrabarty.  A-unital Operations and Quantum Conditional Entropy.  Quantum, 6:641, February 2022.
  * (31) Christopher Portmann and Renato Renner.  Security in quantum cryptography.  Reviews of Modern Physics, 94(2):025008, June 2022.
  * (32) David Beckman, Daniel Gottesman, Michael A. Nielsen, and John Preskill.  Causal and localizable quantum operations.  Physical Review A, 64(5):052309, October 2001.
  * (33) T. Eggeling, D. Schlingemann, and Reinhard F. Werner.  Semicausal operations are semilocalizable.  Europhysics Letters, 57(6):782–788, March 2002.  arXiv:quant-ph/0104027.
  * (34) Marco Piani, Michal Horodecki, Pawel Horodecki, and Ryszard Horodecki.  Properties of quantum nonsignaling boxes.  Physical Review A, 74(1):012305, July 2006.
  * (35) Gilad Gour, A. Grudka, M. Horodecki, W. Klobus, J. Lodyga, and V. Narasimhachar.  The conditional uncertainty principle.  Physical Review A, 97:042130, 2018.
  * (36) Reinhard F. Werner.  Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model.  Physical Review A, 40(8):4277–4281, October 1989.
  * (37) Gilad Gour and Marco Tomamichel.  Optimal extensions of resource measures and their applications.  Physical Review A, 102(6):062401, December 2020.
  * (38) Hisaharu Umegaki.  Conditional expectations in an operator algebra IV (entropy and information).  Kodai Mathematical Seminar Reports, 14(2):59–85, 1962.
  * (39) V. P. Belavkin and P. Staszewski.  C*-algebraic generalization of relative entropy and entropy.  Annales de l’I.H.P. Physique théorique, 37(1):51–58, 1982.
  * (40) Dénes Petz.  Quasi-entropies for States of a von Neumann Algebra.  Publications of the Research Institute for Mathematical Sciences, 21(4):787–800, 1985.
  * (41) Dénes Petz.  Quasi-entropies for finite quantum systems.  Reports in Mathematical Physics, 23:57–65, 1986.
  * (42) Mark M. Wilde, Andreas Winter, and Dong Yang.  Strong converse for the classical capacity of entanglement-breaking and Hadamard channels via a sandwiched Rényi relative entropy.  Communications in Mathematical Physics, 331(2):593–622, October 2014.  arXiv:1306.1586.
  * (43) Koenraad M. R. Audenaert and Nilanjana Datta.  $\alpha$-$z$-Rényi relative entropies.  Journal of Mathematical Physics, 56(2):022202, February 2015.
  * (44) Keiji Matsumoto.  A new quantum version of $f$-divergence.  2013\.  arXiv:1311.4722.
  * (45) Keiji Matsumoto.  A new quantum version of f-divergence.  In Masanao Ozawa, Jeremy Butterfield, Hans Halvorson, Miklós Rédei, Yuichiro Kitajima, and Francesco Buscemi, editors, Reality and Measurement in Algebraic Quantum Theory, volume 261, pages 229–273, Singapore, 2018. Springer Singapore.  Series Title: Springer Proceedings in Mathematics & Statistics.
  * (46) Naresh Sharma and Naqueeb Ahmad Warsi.  Fundamental bound on the reliability of quantum information transmission.  Phys. Rev. Lett., 110:080501, Feb 2013.
  * (47) Salman Beigi.  Sandwiched Rényi divergence satisfies data processing inequality.  Journal of Mathematical Physics, 54:122202, December 2013.
  * (48) Xin Wang.  Semidefinite optimization for quantum information.  PhD thesis, University of Technology Sydney, Centre for Quantum Software and Information, Faculty of Engineering and Information Technology, July 2018.  http://hdl.handle.net/10453/127996.
  * (49) Gilad Gour.  Comparison of quantum channels by superchannels.  IEEE Transactions on Information Theory, 65(9):5880–5904, 2019\.
  * (50) Robert Salzmann, Nilanjana Datta, Gilad Gour, Xin Wang, and Mark M. Wilde.  Symmetric distinguishability as a quantum resource.  New Journal of Physics, 23:083016, August 2021.  arXiv:2102.12512.
  * (51) Robert Konig and Renato Renner.  Sampling of min-entropy relative to quantum knowledge.  IEEE Transactions on Information Theory, 57(7):4760–4787, July 2011\.
  * (52) Gilad Gour.  Resources of the Quantum World (Volume 1).  2023\.
  * (53) Nilanjana Datta.  Min- and max-relative entropies and a new entanglement monotone.  IEEE Transactions on Information Theory, 55(6):2816–2826, June 2009\.  arXiv:0803.2770.

##  Appendix A Proofs of properties of entropy

Let us employ the postulates in (10)–(12) to derive some basic properties of
every entropy. The proofs given here are similar to those given for the
classical case in [21, Lemma 3]. First, let us recall an often overlooked
fact, that the number 1 is a trivial quantum state of dimension one. Indeed,
the underlying Hilbert space is of dimension one, so that the only possible
density “operator” for this space is the number 1. We now prove that the
entropy of this state is equal to zero. Since, by assumption, the entropy is
not equal to the zero function, there exists a state $\rho$ such that
$\mathbf{H}(\rho)\neq 0$. Then consider that

$\mathbf{H}(\rho)=\mathbf{H}(\rho\otimes
1)=\mathbf{H}(\rho)+\mathbf{H}(1)\quad\Rightarrow\quad\mathbf{H}(1)=0.$ (39)

The first equality follows as a trivial assertion, because $\rho=\rho\otimes
1$. The next equality is a consequence of the additivity postulate. The
conclusion that $\mathbf{H}(1)=0$ then follows because $\mathbf{H}(\rho)\neq
0$.

It follows that the entropy of every pure state $|\psi\rangle\\!\langle\psi|$
is equal to zero, as a consequence of (39). Indeed, the state vector
$|\psi\rangle$ is an isometry from the trivial Hilbert space of dimension one
to the Hilbert space that contains $|\psi\rangle$. As such, it follows that
$1\succ|\psi\rangle\\!\langle\psi|$ and $1\prec|\psi\rangle\\!\langle\psi|$
according to the definitions in (4)–(6) and (10)–(12). So we conclude that

$\mathbf{H}(|\psi\rangle\\!\langle\psi|)=0$ (40)

for every pure state $|\psi\rangle\\!\langle\psi|$.

Next we conclude that the entropy of every state is non-negative. This follows
because there exists a unital channel taking a pure state
$|\psi\rangle\\!\langle\psi|$ to an arbitrary state $\rho$, so that
$|\psi\rangle\\!\langle\psi|\succ\rho$. Indeed, let
$\rho=\sum_{x}p_{x}|\psi_{x}\rangle\\!\langle\psi_{x}|$ be a pure state
decomposition of $\rho$. Let $U_{x}$ be a unitary that transforms
$|\psi\rangle$ to $|\psi_{x}\rangle$. Thus,
$(\cdot)\to\sum_{x}p_{x}U_{x}(\cdot)U_{x}^{\dagger}$ is a unital channel that
transforms $|\psi\rangle\\!\langle\psi|$ to $\rho$. By applying (11) and (40),
we conclude that

$\mathbf{H}(\rho)\geq 0$ (41)

for every state $\rho$.

For a fixed dimension $d$, the uniform state $\mathbf{u}^{(d)}=I/d$ is the
state of maximal entropy, which follows from (11) and because every state
$\rho$ can be taken to $\mathbf{u}^{(d)}$ by means of the unital channel
$(\cdot)\to\operatorname{Tr}[(\cdot)]\mathbf{u}^{(d)}$. Thus,

$\mathbf{H}(\mathbf{u}^{(d)})\geq\mathbf{H}(\rho)$ (42)

for every state $\rho$ of dimension $d$.

Let us prove that $\mathbf{H}(\mathbf{u}^{(2)})>0$. By the inequality in (41)
and the assumption that entropy is not equal to the zero function, there
exists a state $\rho$ of some dimension $d$ such that $\mathbf{H}(\rho)>0$. By
applying (42), we conclude that
$\mathbf{H}(\mathbf{u}^{(d)})\geq\mathbf{H}(\rho)$. By taking $n$ sufficiently
large (i.e., such that $2^{n}>d$), we conclude that
$\mathbf{u}^{(d)}\succ(\mathbf{u}^{(2)})^{\otimes n}$, which implies that
$\mathbf{H}((\mathbf{u}^{(2)})^{\otimes n})>\mathbf{H}(\mathbf{u}^{(d)})$.
Finally, by applying the additivity postulate, we conclude that
$n\mathbf{H}(\mathbf{u}^{(2)})=\mathbf{H}((\mathbf{u}^{(2)})^{\otimes n})$.
Combining all inequalities, we conclude that $\mathbf{H}(\mathbf{u}^{(2)})>0$.

After establishing the normalization convention that
$\mathbf{H}(\mathbf{u}^{(2)})=1$, the proof that
$\mathbf{H}(\mathbf{u}^{(d)})=\log_{2}d$ is the same as that given in the
proof of [21, Lemma 3].

##  Appendix B Choi matrix formulations

In this appendix, we provide Choi matrix formulations of conditionally unital
channels and locally balanced channels. These formulations are useful
conceptually and also for numerical optimization if one wishes to use semi-
definite programming to optimize over these sets of channels. See [8, 48, 10]
for examples and discussions of semi-definite programming in quantum
information.

Before giving these formulations, let us first recall the definition of the
Choi matrix. The Choi matrix $J^{\mathcal{M}}_{CD}$ of a linear map
$\mathcal{M}_{C\rightarrow D}$ is defined by its action on the maximally
entangled operator, as follows:

$\displaystyle J^{\mathcal{M}}_{CD}=\sum_{i,j=1}^{|C|}|i\rangle\\!\langle
j|\otimes\mathcal{M}(|i\rangle\\!\langle j|).$ (43)

In general, the matrix $J^{\mathcal{M}}_{CD}$ is the Choi matrix of a trace-
preserving map if and only if

$\operatorname{Tr}_{D}[J^{\mathcal{M}}_{CD}]=I_{C},$ (44)

and it is the Choi matrix of a completely positive map if and only if

$J^{\mathcal{M}}_{CD}\geq 0.$ (45)

Thus, $J^{\mathcal{M}}_{CD}$ is the Choi matrix of a quantum channel if and
only if (44) and (45) both hold.

###  B.1 Choi matrix formulation of conditional unitality

Here we prove that a conditionally unital channel has an equivalent
formulation in terms of its Choi matrix. We then see that a channel being
conditionally unital represents a semi-definite constraint on its Choi matrix,
which is convenient for optimizing over such channels using semi-definite
programming.

###### Lemma 1

A channel $\mathcal{N}_{AB\rightarrow\tilde{A}B^{\prime}}$ is conditionally
unital if and only if its Choi matrix
$J^{\mathcal{N}}_{AB\tilde{A}B^{\prime}}$ satisfies

$J^{\mathcal{N}}_{B\tilde{A}B^{\prime}}=J^{\mathcal{N}}_{BB^{\prime}}\otimes\mathbf{u}_{\tilde{A}},$
(46)

where

$\displaystyle J^{\mathcal{N}}_{B\tilde{A}B^{\prime}}$
$\displaystyle\coloneqq\operatorname{Tr}_{A}[J^{\mathcal{N}}_{AB\tilde{A}B^{\prime}}],$
(47) $\displaystyle J^{\mathcal{N}}_{BB^{\prime}}$
$\displaystyle\coloneqq\operatorname{Tr}_{A\tilde{A}}[J^{\mathcal{N}}_{AB\tilde{A}B^{\prime}}],$
(48)

are marginals of $J^{\mathcal{N}}_{AB\tilde{A}B^{\prime}}$ and we employ this
kind of shorthand in what follows.

Proof. We begin by proving that the channel
$\mathcal{N}_{AB\rightarrow\tilde{A}B^{\prime}}$ is conditionally unital if
its Choi matrix has the form in (46). To this end, let
$\rho_{B}\in\mathfrak{D}(B)$ and consider that

$\displaystyle\mathcal{N}\left(\mathbf{u}_{A}\otimes\rho_{B}\right)$
$\displaystyle=\operatorname{Tr}_{AB}\\!\left[J^{\mathcal{N}}_{AB\tilde{A}B^{\prime}}\left(\mathbf{u}_{A}\otimes\left(\rho_{B}\right)^{T}\otimes
I_{\tilde{A}B^{\prime}}\right)\right]$ (49)
$\displaystyle=\frac{1}{|A|}\operatorname{Tr}_{B}\\!\left[J^{\mathcal{N}}_{B\tilde{A}B^{\prime}}\left(\left(\rho_{B}\right)^{T}\otimes
I_{\tilde{A}B^{\prime}}\right)\right]$ (50)
$\displaystyle=\frac{1}{|A|}\operatorname{Tr}_{B}\\!\left[\mathbf{u}_{\tilde{A}}\otimes
J^{\mathcal{N}}_{BB^{\prime}}\left(\left(\rho_{B}\right)^{T}\otimes
I_{\tilde{A}B^{\prime}}\right)\right]$ (51)
$\displaystyle=\mathbf{u}_{\tilde{A}}\otimes\frac{1}{|A|}\operatorname{Tr}_{B}\\!\left[J^{\mathcal{N}}_{BB^{\prime}}\left(\left(\rho_{B}\right)^{T}\otimes
I_{B^{\prime}}\right)\right].$ (52)

The first equality is a well known identity in quantum information, indicating
how the action of a channel on an input state can be understood in terms of a
propagation formula using its Choi matrix (see Eq. (2.66) of [8]). The third
equality above follows from applying (46), which holds by assumption. It then
follows that
$\frac{1}{|A|}\operatorname{Tr}_{B}\\!\left[J^{\mathcal{N}}_{BB^{\prime}}\left(\left(\rho_{B}\right)^{T}\otimes
I_{B^{\prime}}\right)\right]$ is a state on the output system $B^{\prime}$
(i.e., the choice for the state $\sigma_{B^{\prime}}$ in (13)) because
$\frac{1}{|A|}J^{\mathcal{N}}_{BB^{\prime}}$ is the Choi operator of the
channel

$\tau_{B}\to(\operatorname{Tr}_{\tilde{A}}\circ\mathcal{N}_{AB\to\tilde{A}B^{\prime}})(\mathbf{u}_{A}\otimes\tau_{B}).$
(53)

We now prove that the Choi matrix of
$\mathcal{N}_{AB\rightarrow\tilde{A}B^{\prime}}$ has the form in (46) if
$\mathcal{N}_{AB\rightarrow\tilde{A}B^{\prime}}$ is conditionally unital.
Recall from (13) that the defining property of a conditionally unital channel
is that for every state $\rho_{B}$, there exists a state $\sigma_{B^{\prime}}$
such that

$\mathcal{N}_{AB\to\tilde{A}B^{\prime}}(\mathbf{u}_{A}\otimes\rho_{B})=\mathbf{u}_{\tilde{A}}\otimes\sigma_{B^{\prime}}.$
(54)

By taking the trace over $\tilde{A}$ on both sides of the equation above, we
find that

$\displaystyle\sigma_{B^{\prime}}$ $\displaystyle=\mathcal{N}_{AB\to
B^{\prime}}(\mathbf{u}_{A}\otimes\rho_{B})$ (55) $\displaystyle={\rm
Tr}_{AB}\\!\left[J_{ABB^{\prime}}^{\mathcal{N}}\left(\mathbf{u}_{A}\otimes\left(\rho_{B}\right)^{T}\otimes
I_{B^{\prime}}\right)\right]$ (56) $\displaystyle=\frac{1}{|A|}{\rm
Tr}_{B}\\!\left[J_{BB^{\prime}}^{\mathcal{N}}\left(\left(\rho_{B}\right)^{T}\otimes
I_{B^{\prime}}\right)\right]\;.$ (57)

On the other hand, observe that

$\displaystyle\mathcal{N}_{AB\to\tilde{A}B^{\prime}}(\mathbf{u}_{A}\otimes\rho_{B})$
$\displaystyle=\operatorname{Tr}_{AB}\\!\left[J_{AB\tilde{A}B^{\prime}}^{\mathcal{N}}\left(\mathbf{u}_{A}\otimes\left(\rho_{B}\right)^{T}\otimes
I_{\tilde{A}B^{\prime}}\right)\right]$ (58)
$\displaystyle=\frac{1}{|A|}\operatorname{Tr}_{B}\\!\left[J_{B\tilde{A}B^{\prime}}^{\mathcal{N}}\left(\left(\rho_{B}\right)^{T}\otimes
I_{\tilde{A}B^{\prime}}\right)\right]\;.$ (59)

Therefore, from the two expressions above for $\sigma_{B}$ and
$\mathcal{N}(\mathbf{u}_{A}\otimes\rho_{B})$ we conclude that (54) can be
expressed as

$\operatorname{Tr}_{B}\\!\left[J_{B\tilde{A}B^{\prime}}^{\mathcal{N}}\left(\left(\rho_{B}\right)^{T}\otimes
I_{\tilde{A}B^{\prime}}\right)\right]\\\ ={\rm
Tr}_{B}\\!\left[(\mathbf{u}_{\tilde{A}}\otimes
J_{BB^{\prime}}^{\mathcal{N}})\left(\left(\rho_{B}\right)^{T}\otimes
I_{\tilde{A}B^{\prime}}\right)\right]\;,$ (60)

holding for all $\rho_{B}\in\mathfrak{D}(B)$. Let

$\eta_{B\tilde{A}B^{\prime}}\coloneqq
J_{B\tilde{A}B^{\prime}}^{\mathcal{N}}-\mathbf{u}_{\tilde{A}}\otimes
J_{BB^{\prime}}^{\mathcal{N}},$ (61)

and observe that (60) can be written as

${\rm
Tr}_{B}\\!\left[\eta_{B\tilde{A}B^{\prime}}\left(\left(\rho_{B}\right)^{T}\otimes
I_{\tilde{A}B^{\prime}}\right)\right]=0\;\;\quad\forall\;\rho_{B}\in\mathfrak{D}(B).$
(62)

Due to the existence of bases of density operators that span the space of
linear operators acting on ${B}$ (see Example 2.7 of [8]), we conclude from
(62) that for every Hermitian operator $X_{B}\in\mathfrak{L}(B)$, we have

$\operatorname{Tr}_{B}\\!\left[\eta_{B\tilde{A}B^{\prime}}\left(X_{B}\otimes
I_{\tilde{A}B^{\prime}}\right)\right]=0\;.$ (63)

Note that by multiplying both sides of the equation above by an arbitrary
element $Y_{\tilde{A}B^{\prime}}\in\mathfrak{L}(\tilde{A}B^{\prime})$ and
taking the trace, we get that

${\rm Tr}\big{[}\eta_{B\tilde{A}B^{\prime}}\left(X_{B}\otimes
Y_{\tilde{A}B^{\prime}}\right)\big{]}=0\;.$ (64)

Since the equation above holds for all $X_{B}\in\mathfrak{L}(B)$ and all
$Y_{\tilde{A}B^{\prime}}\in\mathfrak{L}(\tilde{A}B^{\prime})$ it also holds
for all linear combinations of matrices of the form $X_{B}\otimes
Y_{\tilde{A}B^{\prime}}$. Since matrices of the form $X_{B}\otimes
Y_{\tilde{A}B^{\prime}}$ span the whole space
$\mathfrak{L}(B\tilde{A}B^{\prime})$ we conclude that

${\rm
Tr}\big{[}\eta_{B\tilde{A}B^{\prime}}W_{B\tilde{A}B^{\prime}}\big{]}=0\quad\quad\forall\;W_{B\tilde{A}B^{\prime}}\in\mathfrak{L}(B\tilde{A}B^{\prime})\;.$
(65)

Therefore, we conclude that $\eta_{B\tilde{A}B^{\prime}}=0$, which is
equivalent to (46).

###  B.2 Choi matrix formulation of locally balanced channels

Here we provide a Choi matrix formulation for locally balanced channels.
Before doing so, let us first recall [34, Eq. (40)], which indicates how semi-
causality can be expressed in terms of the Choi matrix.

######  Lemma 2 ([34, 49])

The channel $\mathcal{N}_{AB\rightarrow AB^{\prime}}$ is $A\not\to B^{\prime}$
semi-causal if and only if the marginals of its Choi matrix
$J^{\mathcal{N}}_{AB\tilde{A}B^{\prime}}$ satisfy

$\displaystyle J^{\mathcal{N}}_{ABB^{\prime}}=\mathbf{u}_{A}\otimes
J^{\mathcal{N}}_{BB^{\prime}}.$ (66)

As a direct corollary of (44)–(45) and Lemmas 1 and 2, we have the following
simple semi-definite characterization of a locally balanced channel in terms
of its Choi matrix.

###### Corollary 2

A matrix $J_{AB\tilde{A}B^{\prime}}^{\mathcal{N}}$ is the Choi matrix of a
locally balanced channel $\mathcal{N}_{AB\rightarrow\tilde{A}B^{\prime}}$ if
and only if

$\displaystyle J_{AB\tilde{A}B^{\prime}}^{\mathcal{N}}$ $\displaystyle\geq 0,$
(67)
$\displaystyle\operatorname{Tr}_{\tilde{A}B^{\prime}}[J_{AB\tilde{A}B^{\prime}}^{\mathcal{N}}]$
$\displaystyle=I_{AB},$ (68) $\displaystyle J^{\mathcal{N}}_{ABB^{\prime}}$
$\displaystyle=\mathbf{u}_{A}\otimes J^{\mathcal{N}}_{BB^{\prime}},$ (69)
$\displaystyle J^{\mathcal{N}}_{B\tilde{A}B^{\prime}}$
$\displaystyle=J^{\mathcal{N}}_{BB^{\prime}}\otimes\mathbf{u}_{\tilde{A}}.$
(70)

Corollary 2 simplifies the task of optimizing an objective function over the
set of locally balanced channels by making use of semi-definite programming.
Corollary 2 also clarifies why we have named these channels locally balanced.
By inspecting (69)–(70), we see that the properties of these channels are
invariant under the exchange of the input system $A$ and the output system
$\tilde{A}$.

##  Appendix C Quantum conditional majorization reduces to classical
conditional majorization

In [35], a pre-order $\succ_{C}$ between two joint probability distributions
(i.e., classical states) denotes _classical conditional majorization_. In this
appendix, we prove that the approach to conditional majorization defined in
Section III.1 is a generalization of classical conditional majorization. To
this end, we demonstrate that quantum conditional majorization is equivalent
to the classical conditional majorization when we restrict the underlying
bipartite quantum states to classical states.

Suppose the system $A\coloneqq X$ is classical. We call a channel
$\mathcal{M}_{XB\to XB^{\prime}}$ _conditionally doubly stochastic_ (CDS for
short) if it has the following form:

$\mathcal{M}_{XB\to XB^{\prime}}=\sum_{j}\mathcal{D}_{X\to
X}^{(j)}\otimes\mathcal{F}_{B\to B^{\prime}}^{(j)},$ (71)

where each $\mathcal{D}^{(j)}$ is a classical doubly stochastic channel and
each $\mathcal{F}_{B\to B^{\prime}}^{(j)}$ is a completely positive (CP) map
such that $\sum_{j}\mathcal{F}_{B\to B^{\prime}}^{(j)}$ is a quantum channel.
CDS maps with classical $B$ and $B^{\prime}$ systems were introduced and
studied in [35], and CDS maps with quantum $B$ and $B^{\prime}$ systems were
introduced and studied in [50].

######  Definition 1 ([35])

Let $\rho_{XY}$ and $\sigma_{XY^{\prime}}$ be classical bipartite states such
that $A=X$, $B=Y$, and $B^{\prime}=Y^{\prime}$ are all classical systems. We
say that $\rho_{XY}$ conditionally majorizes $\sigma_{XY^{\prime}}$ and write
$\sigma_{XY^{\prime}}\succ_{C}\rho_{XY}$ if there exists a CDS channel
$\mathcal{N}_{XY\to XY^{\prime}}$ such that
$\sigma_{XY^{\prime}}=\mathcal{N}_{XY\to XY^{\prime}}(\rho_{XY})$.

###### Lemma 3

Suppose all the systems involved are classical with $A\coloneqq X$,
$B\coloneqq Y$, and $B^{\prime}\coloneqq Y^{\prime}$. Then every CDS channel
is locally balanced.

Proof. Recall that if $\mathcal{M}_{XY\rightarrow XY^{\prime}}$ is a CDS
channel, then there exists a set of classical doubly stochastic channels
$\\{\mathcal{D}^{(j)}\\}_{j}$ and a quantum instrument
$\\{\mathcal{F}_{Y\rightarrow Y^{\prime}}^{(j)}\\}_{j}$ such that

$\mathcal{M}_{AB\to
AB^{\prime}}=\sum_{j}\mathcal{D}_{A}^{(j)}\otimes\mathcal{F}_{B\to
B^{\prime}}^{(j)}.$ (72)

Then for every input of the form $\mathbf{u}_{A}\otimes\sigma_{B}$, it follows
that

$\displaystyle\mathcal{M}_{AB\to
AB^{\prime}}(\mathbf{u}_{A}\otimes\sigma_{B})$
$\displaystyle=\sum_{j}\mathcal{D}_{A}^{(j)}(\mathbf{u}_{A})\otimes\mathcal{F}_{B\to
B^{\prime}}^{(j)}(\sigma_{B})$
$\displaystyle=\mathbf{u}_{A}\otimes\sum_{j}\mathcal{F}_{B\to
B^{\prime}}^{(j)}(\sigma_{B})$ (73)

and therefore $\mathcal{M}$ is conditionally unital. (Note that the third line
of the above follows from the fact that $\mathcal{D}^{(j)}$ is doubly
stochastic, so that $\mathcal{D}^{(j)}(\mathbf{u}_{A})=\mathbf{u}_{A}$ for all
$j$.)

Finally, we show that $\mathcal{M}$ is semi-causal. Let $\mathcal{T}_{A}$ be
an arbitrary classical channel. Then consider that

$\displaystyle\operatorname{Tr}_{A}\\!\left[\mathcal{M}\circ\mathcal{T}_{A}\right]$
$\displaystyle=\operatorname{Tr}_{A}\\!\left[\sum_{j}(\mathcal{D}_{A}^{(j)}\circ\mathcal{T}_{A})\otimes\mathcal{F}_{B\to
B^{\prime}}^{(j)}\right]$ (74)
$\displaystyle=\sum_{j}\operatorname{Tr}_{A}\\!\left[\mathcal{D}_{A}^{(j)}\circ\mathcal{T}_{A}\right]\otimes\mathcal{F}_{B\to
B^{\prime}}^{(j)}$ (75)
$\displaystyle=\sum_{j}\operatorname{Tr}_{A}\\!\left[\mathcal{D}_{A}^{(j)}\right]\otimes\mathcal{F}_{B\to
B^{\prime}}^{(j)}$ (76)
$\displaystyle=\operatorname{Tr}_{A}\\!\left[\mathcal{M}_{AB\rightarrow
AB^{\prime}}\right].$ (77)

Given that $\mathcal{M}$ is conditionally unital and semi-causal, then the
statement of the lemma follows.

###### Theorem 3

Let $\rho_{XY}$ and $\sigma_{XY^{\prime}}$ be classical bipartite states such
that $A=X$, $B=Y$, and $B^{\prime}=Y^{\prime}$ are all classical systems. Then
$\sigma_{XY^{\prime}}\succ_{X}\rho_{XY}$ if and only if
$\sigma_{XY^{\prime}}\succ_{C}\rho_{XY}$, where $\succ_{C}$ is the classical
conditional majorization defined in [35].

Proof. It immediately follows from Lemma 3 that
$\rho_{XY}\succ_{C}\sigma_{XY^{\prime}}$ implies
$\rho_{XY}\succ_{X}\sigma_{XY^{\prime}}$.

To show the other direction, let us suppose that
$\rho_{XY}\succ_{X}\sigma_{XY^{\prime}}$ as defined in (17)–(19). That is,
there exists a locally balanced channel $\mathcal{N}_{XY\to XY^{\prime}}$ such
that

$\sigma_{XY^{\prime}}=\mathcal{N}_{XY\to XY^{\prime}}(\rho_{XY})\ .$ (78)

Since $\mathcal{N}$ is semi-causal, it has the form

$\mathcal{N}_{XY\to XY^{\prime}}=\sum_{j=1}^{k}\mathcal{E}_{X\to
X}^{(j)}\otimes\mathcal{F}_{Y\to Y^{\prime}}^{(j)}\ ,$ (79)

where for each $j\in[K]$, the map $\mathcal{E}^{(j)}_{X\to X}$ is a channel
and $\mathcal{F}^{(j)}_{Y\to Y^{\prime}}$ is a completely positive map with
$\sum_{j}\mathcal{F}^{(j)}_{Y\to Y^{\prime}}$ a channel. Hence,

$\sigma_{XY^{\prime}}=\sum_{j=1}^{k}\mathcal{E}_{X\to
X}^{(j)}\otimes\mathcal{F}_{Y\to Y^{\prime}}^{(j)}(\rho_{XY})\ .$ (80)

Since $\rho$ and $\sigma$ are classical, we can make the identification
$\rho_{XY}\cong P$ and $\sigma_{XY^{\prime}}\cong Q$, where $P$ and $Q$ are
probability matrices. Thus, (80) can be expressed as

$Q=\sum_{j=1}^{k}E^{(j)}PR^{(j)}\ ,$ (81)

where for each $j\in[k]$, the matrix $E^{(j)}$ is the transition matrix of
$\mathcal{E}^{(j)}$, and $R^{(j)}$ is the transpose of the transition matrix
of $\mathcal{F}^{(j)}$. Hence, each $E^{(j)}$ is column stochastic and
$R\coloneqq\sum_{j=1}^{k}R^{(j)}$ is row stochastic. Let
$\\{\mathbf{p}_{y}\\}_{y\in[n]}$ be the columns of $P$, and observe that in
component form, the above relation can be expressed as

$q_{xw}=\sum_{j=1}^{k}\sum_{y=1}^{n}(E^{(j)}\mathbf{p}_{y})_{x}r_{yw}^{(j)}\
.$ (82)

So far we only used the constraint that $\mathcal{N}$ is semi-causal. The
other constraint that $\mathcal{N}$ is conditionally unital implies that
$q_{yw}=\frac{1}{m}q_{w}$ if $p_{xy}=\frac{1}{m}p_{y}$. Therefore, for
simplicity we take $p_{xy}=\frac{1}{m}\delta_{y}{y_{0}}$ for some fixed
$y_{0}\in[n]$. Then the above equation becomes

$\frac{1}{m}q_{w}=\sum_{j}(E^{(j)}\mathbf{u})_{x}r^{(j)}_{y_{0}w}\ .$ (83)

Summing over $x$ on both sides of the equation, and using the fact that each
$E^{(j)}$ is column stochastic, which implies that $E^{(j)}\mathbf{u}$ is a
probability vector, we have

$q_{w}=\sum_{j}r_{y_{0}w}^{(j)}\ .$ (84)

Note that we assumed that $y_{0}$ was fixed, and therefore, as a result, the
equation above does not imply that $q_{w}$ is independent of $y_{0}$ if we
allow $y_{0}$ to vary. In other words, each value of $y_{0}$ corresponds to a
different $P$ matrix and therefore possibly resulting in a different $Q$
matrix. For simplicity, we rename $y_{0}$ as $y$ and denote

$q_{w}=t_{yw}\coloneqq\sum_{j}r^{(j)}_{yw}\ .$ (85)

By definition, the matrix $T=(t_{yw})$ is row-stochastic, and with the above
notations, we can express (83) as

$\mathbf{u}=\sum_{j}\frac{r_{yw}^{(j)}}{t_{yw}}E^{(j)}\mathbf{u}\quad
y\in[n],\ w\in[\ell]\ .$ (86)

Therefore, the matrices

$D_{(y,w)}\coloneqq\sum_{j}\frac{r_{yw}^{(j)}}{t_{yw}}E^{(j)}\quad y\in[n],\
w\in[\ell]$ (87)

are all doubly stochastic. To see this, observe that for each $y$ and $w$, the
set $\left\\{r_{yw}^{(j)}/t_{yw}\right\\}_{j}$ forms a probability
distribution over $j$, and the fact that each $E^{(j)}$ is column stochastic
implies that $D_{(y,w)}$ is column stochastic. Moreover, the relation
$\mathbf{u}=D_{(y,w)}\mathbf{u}$ implies that each $D_{(y,w)}$ is row
stochastic. Finally, for general probability matrices
$P=[\mathbf{p}_{1},\ldots,\mathbf{p}_{n}]$ and
$Q=[\mathbf{q}_{1},\ldots,\mathbf{q}_{n^{\prime}}]$, we conclude that (82) is
equivalent to

$\mathbf{q}_{w}=\sum_{y=1}^{n}t_{yw}D_{(y,w)}\mathbf{p}_{y}\quad\forall
w\in[n^{\prime}]\ .$ (88)

The above relation is precisely the condition given in [35, Lemma 3].
Therefore, we conclude that $\rho_{XY}\succ_{X}\sigma_{XY^{\prime}}$ implies
classical conditional majorization.

##  Appendix D Proofs of properties of quantum conditional entropy

Suppose that $\rho_{AB}=\omega_{A}\otimes\tau_{B}$ is a product state. Let
$\mathcal{E}_{B}$ be the completely randomizing channel acting on system $B$,
which traces out system $B$ and replaces with the uniform state
$\mathbf{u}_{B}$. Then it follows that $\mathcal{I}_{A}\otimes\mathcal{E}_{B}$
is a conditionally unital channel and that

$\mathcal{I}_{A}\otimes\mathcal{E}_{B}\left(\omega_{A}\otimes\tau_{B}\right)=\omega_{A}\otimes\mathbf{u}_{B}.$
(89)

Moreover, let $\mathcal{R}_{B}$ be the replacement channel on system $B$,
which takes every quantum state to a fixed state $\tau_{B}$. Then,
$\mathcal{I}_{A}\otimes\mathcal{R}_{B}$ is conditionally unital and

$\mathcal{I}_{A}\otimes\mathcal{R}_{B}\left(\omega_{A}\otimes\mathbf{u}_{B}\right)=\omega_{A}\otimes\tau_{B}\
.$ (90)

Thus,

$\omega_{A}\otimes\tau_{B}\succ_{A}\omega_{A}\otimes\mathbf{u}_{B}\quad\text{and}\quad\omega_{A}\otimes\mathbf{u}_{B}\succ_{A}\omega_{A}\otimes\tau_{B},$
(91)

which implies, by the monotonicity property of the conditional entropy
$\mathbf{H}$, that

$\mathbf{H}(A|B)_{\omega_{A}\otimes\tau_{B}}=\mathbf{H}(A|B)_{\omega_{A}\otimes\mathbf{u}_{B}}.$
(92)

Thus, $\mathbf{H}(A|B)_{\omega_{A}\otimes\tau_{B}}$ depends on $\omega_{A}$
only. Moreover, the function
$\omega_{A}\mapsto\mathbf{H}(A|B)_{\omega_{A}\otimes\tau_{B}}$ satisfies the
two postulates of entropy in (11)–(12) and therefore is an entropy of
$\omega_{A}$. Note that the same statement also holds when system $|B|$ is
trivial, i.e., when $|B|=1$.

We now prove that $\mathbf{H}(A|B)$ is invariant under local isometric
channels. It follows immediately from the definition of quantum conditional
entropy (specifically, (17)–(19) and (22)) that it is invariant under local
isometric channels acting on system $A$. So we prove invariance under
isometric channels acting on system $B$. The inequality

$\mathbf{H}(A|B)_{\rho}\leq\mathbf{H}(A|B^{\prime})_{\omega}$ (93)

follows because $\mathcal{V}_{B\to B^{\prime}}$ is a conditionally unital
channel. Let $\tau_{B}$ be a state. The reverse inequality follows because

$\mathcal{R}^{\mathcal{V}}_{B^{\prime}\to
B}(\cdot)\coloneqq\mathcal{V}^{{\dagger}}(\cdot)+\operatorname{Tr}[(\operatorname{id}_{B^{\prime}}-\mathcal{V}^{\dagger})(\cdot)]\tau_{B}$
(94)

is a channel that is a left inverse of $\mathcal{V}_{B\to B^{\prime}}$ [7,
Section 4.6.3]. Thus, $\mathcal{R}^{\mathcal{V}}_{B^{\prime}\to B}$ is a
conditionally unital channel, from which we conclude that

$\mathbf{H}(A|B^{\prime})_{\omega}\leq\mathbf{H}(A|B)_{\mathcal{R}^{\mathcal{V}}(\omega)}=\mathbf{H}(A|B)_{\rho}.$
(95)

This concludes the proof.

##  Appendix E A subclass of conditional entropies

Here we consider a subclass of conditional entropies in which the postulate in
(22) is replaced by monotonicity under conditionally unital channels. Since
the set of conditionally unital channels contains the set of locally balanced
channels, every function that is a conditional entropy according to this
alternative definition is also a conditional entropy $\mathbf{H}$, as defined
in (21)–(23). We will later see that this approach is consistent and
sufficient for deriving various properties of conditional entropy.

Let us begin by defining another version of a conditional majorization pre-
order on bipartite quantum states, based on conditionally unital channels
exclusively. We call this approach relaxed conditional majorization. Given two
bipartite states $\rho_{AB}$ and $\sigma_{A^{\prime}B^{\prime}}$, we say that
$\rho_{AB}$ conditionally majorizes $\sigma_{A^{\prime}B^{\prime}}$ in the
relaxed sense and with respect to system $A$, and write

$\rho_{AB}\succ^{A}\sigma_{A^{\prime}B^{\prime}}$ (96)

if either $|A^{\prime}|\geq|A|$, there exists an isometric channel
$\mathcal{V}_{A\to A^{\prime}}$, and a conditionally unital channel
$\mathcal{N}_{AB\rightarrow AB^{\prime}}$, such that

$\displaystyle\sigma_{A^{\prime}B^{\prime}}=\mathcal{V}_{A\to
A^{\prime}}\circ\mathcal{N}_{AB\rightarrow AB^{\prime}}(\rho_{AB})\;,$ (97)

or $|A|\geq|A^{\prime}|$, there exists an isometric channel
$\mathcal{U}_{A^{\prime}\to A}$, and a conditionally unital channel
$\mathcal{N}_{AB\rightarrow AB^{\prime}}$, such that

$\displaystyle\mathcal{U}_{A^{\prime}\to
A}\left(\sigma_{A^{\prime}B^{\prime}}\right)=\mathcal{N}_{AB\rightarrow
AB^{\prime}}(\rho_{AB}).$ (98)

We define a function $f$ to be a conditional uncertainty measure in the
relaxed sense if it is not equal to the zero function and if it reverses the
relaxed conditional majorization pre-order, i.e.,

$\rho_{AB}\succ^{A}\sigma_{A^{\prime}B^{\prime}}\quad\Rightarrow\quad
f(\rho_{AB})\leq f(\sigma_{A^{\prime}B^{\prime}}).$ (99)

We now define this other notion of conditional entropy. Formally, a function

$\mathbf{H}^{\blacktriangle}:\bigcup_{A,B}\mathfrak{D}(AB)\rightarrow\mathbb{R}$
(100)

is a quantum conditional entropy if it is not equal to the zero function and
satisfies the following postulates for all systems $A$, $B$, $A^{\prime}$,
$B^{\prime}$ and states $\rho_{AB}$ and $\sigma_{A^{\prime}B^{\prime}}$:

  1. 1.

Monotonicity:

$\rho_{AB}\succ^{A}\sigma_{A^{\prime}B^{\prime}}\quad\Rightarrow\quad\mathbf{H}^{\blacktriangle}(A|B)_{\rho}\leq\mathbf{H}^{\blacktriangle}(A^{\prime}|B^{\prime})_{\sigma}.$
(101)

  2. 2.

Additivity:

$\mathbf{H}^{\blacktriangle}(AA^{\prime}|BB^{\prime})_{\rho\otimes\sigma}=\mathbf{H}^{\blacktriangle}(A|B)_{\rho}+\mathbf{H}^{\blacktriangle}(A^{\prime}|B^{\prime})_{\sigma}.$
(102)

Let us now recall a different definition of conditional min-entropy from [15]

$H_{\min}^{\uparrow}(A|B)_{\rho}\coloneqq\sup_{\sigma_{B}\in\mathfrak{D}(B)}H_{\min}(\rho_{AB}|\sigma_{B}),$
(103)

where

$H_{\min}(\rho_{AB}|\sigma_{B})\coloneqq-\inf_{\lambda\geq
0}\log_{2}\\{\lambda:\rho_{AB}\leq\lambda I_{A}\otimes\sigma_{B}\\}.$ (104)

Note that $H_{\min}^{\uparrow}(A|B)_{\rho}$ is a conditional entropy
$\mathbf{H}^{\blacktriangle}$ because it is additive and [15, Lemma 3.1.12]
implies that $H_{\min}^{\uparrow}(A|B)_{\rho}$ is non-decreasing under
conditionally unital channels.

We then have the following findings, analogous to those from Theorem 1 and
Corollary 1, respectively.

###### Theorem 4

Let $\mathbf{H}^{\blacktriangle}$ be a quantum conditional entropy, as defined
in (100)–(102). Then, for every state $\rho_{AB}$,

$\mathbf{H}^{\blacktriangle}(A|B)_{\rho}\geq H^{\uparrow}_{\min}(A|B)_{\rho}.$
(105)

Equality is attained in (105) if $\rho_{AB}$ is equal to a maximally entangled
state $\Phi^{(k)}_{A^{\prime}B^{\prime}}$ by the action of local isometric
channels. Thus,

$\mathbf{H}^{\blacktriangle}(A|B)_{\Phi^{(k)}}=-\log_{2}k$ (106)

for every conditional entropy $\mathbf{H}^{\blacktriangle}$.

###### Corollary 3

Let $\rho_{AB}$ be a bipartite state. Then, the following are equivalent:

  1. 1.

For every conditional entropy $\mathbf{H}^{\blacktriangle}$,

$\mathbf{H}^{\blacktriangle}(A|B)_{\rho}\geq 0.$ (107)

  2. 2.

There exists a state $\sigma_{B}$ such that
$I_{A}\otimes\sigma_{B}\geq\rho_{AB}$.

Proof. The proof of Corollary 3 is immediate from Theorem 4. Indeed, if the
first condition holds, then the inequality
$H^{\uparrow}_{\min}(A|B)_{\rho}\geq 0$ holds in particular (since
$H^{\uparrow}_{\min}(A|B)_{\rho}$ is a conditional entropy), and the second
condition is then a consequence of the definition in (103). Now suppose that
the second condition holds. This then means that there exists $\lambda\leq 1$
and a state $\sigma_{B}$ such that $\rho_{AB}\leq\lambda
I_{A}\otimes\sigma_{B}$. According to the definition in (103), it follows that
$H^{\uparrow}_{\min}(A|B)_{\rho}\geq 0$ and then Theorem 4 implies the first
condition.

We have opted to emphasize the conditional entropy $\mathbf{H}$ over
$\mathbf{H}^{\blacktriangle}$ in the main text because

  1. 1.

locally balanced channels have a strong motivation in terms of no information
leakage from Alice to Bob, as would be expected for a measure of conditional
uncertainty,

  2. 2.

conditional majorization defined in this way reduces to classical conditional
majorization, as defined in [35], for the classical case

  3. 3.

the conditional min-entropy in (29) is in fact the smallest conditional
entropy among all conditional entropies consistent with both sets of
postulates,

  4. 4.

every conditional entropy defined in this other way is in fact a conditional
entropy $\mathbf{H}$, because every function that is monotone under all
conditionally unital channels is also monotone under the subset of all locally
balanced channels.

###  E.1 Proof of Theorem 4

Let $\sigma_{B}$ be a state that achieves the optimal value of
$H_{\min}^{\uparrow}(A|B)_{\rho}$, in the definition in (103).

Let us first consider the case when $H_{\min}^{\uparrow}(A|B)_{\rho}\geq 0$.
Set

$\displaystyle k$ $\displaystyle\coloneqq\left|A\right|,$ (108) $\displaystyle
m$ $\displaystyle\coloneqq\left\lfloor
2^{H_{\min}^{\uparrow}(A|B)_{\rho}}\right\rfloor,$ (109)

and let $X$ be a classical system with dimension $k$. By the assumption that
$H_{\min}^{\uparrow}(A|B)_{\rho}\geq 0$, and given the dimension bound
$H_{\min}^{\uparrow}(A|B)_{\rho}\leq\log_{2}k$ [51, Lemma 5.2], it follows
that $m\in\left[k\right]$.

Without loss of generality, we can suppose that $k>m$; if it is not the case,
then we can embed the system $A$ of $\rho_{AB}$ in a larger Hilbert space, so
that $H_{\min}^{\uparrow}(A|B)_{\rho}$ stays constant but $k$ increases. Set
$\Pi_{X}$ to be a projection onto an $m$-dimensional subspace of $X$ (i.e.,
set $\Pi_{X}\coloneqq\sum_{x=1}^{m}|x\rangle\\!\langle x|_{X}$, where
$\\{|x\rangle\\}_{x}$ is an orthonormal basis specifying the classical system
$X$), and define $\tau_{AB}^{(m)}$ as follows:

$\tau_{AB}^{(m)}\coloneqq\frac{I_{A}\otimes\sigma_{B}-m\rho_{AB}}{k-m}.$ (110)

The operator $\tau_{AB}^{(m)}$ is positive semi-definite because $k-m>0$ and

$\displaystyle\frac{1}{m}I_{A}\otimes\sigma_{B}-\rho_{AB}$ $\displaystyle\geq
2^{-H_{\min}^{\uparrow}(A|B)_{\rho}}I_{A}\otimes\sigma_{B}-\rho_{AB}$ (111)
$\displaystyle=2^{D_{\max}(\rho_{AB}\|I_{A}\otimes\sigma_{B})}I_{A}\otimes\sigma_{B}-\rho_{AB}$
(112) $\displaystyle\geq 0.$ (113)

Also, $\tau_{AB}^{(m)}$ has trace equal to one and is thus a state. Let us now
define the following measure-and-prepare channel:

$\mathcal{N}_{X\rightarrow
AB}(\omega_{X})\coloneqq\operatorname{Tr}[\Pi_{X}\omega_{X}]\rho_{AB}\\\
+\operatorname{Tr}[\left(I_{X}-\Pi_{X}\right)\omega_{X}]\tau_{AB}^{(m)}.$
(114)

Indeed, the action of this channel is to perform a measurement according to
the POVM $\left\\{\Pi_{X},I_{X}-\Pi_{X}\right\\}$ and prepare the state
$\rho_{AB}$ if the first outcome is obtained and the state $\tau_{AB}^{(m)}$
if the second outcome is obtained. It should be understood that Alice has
access to the input system $X$.

This channel is conditionally unital because

$\displaystyle\mathcal{N}_{X\rightarrow AB}(I_{X})$
$\displaystyle=\operatorname{Tr}[\Pi_{X}I_{X}]\rho_{AB}+\operatorname{Tr}[\left(I_{X}-\Pi_{X}\right)I_{X}]\tau_{AB}^{(m)}$
(115) $\displaystyle=m\rho_{AB}+\left(k-m\right)\tau_{AB}^{(m)}$ (116)
$\displaystyle=I_{A}\otimes\sigma_{B}.$ (117)

Also, if we input the uniform state $\mathbf{u}^{\Pi}_{X}\coloneqq\Pi_{X}/m$
on the subspace onto which $\Pi_{X}$ projects, the output is given by

$\mathcal{N}_{X\rightarrow AB}(\mathbf{u}^{\Pi}_{X})=\rho_{AB}.$ (118)

Putting these observations together, we conclude that

$\displaystyle\log_{2}\left\lfloor
2^{H_{\min}^{\uparrow}(A|B)_{\rho}}\right\rfloor$
$\displaystyle=\mathbf{H}^{\blacktriangle}(X)_{\mathbf{u}^{\Pi}}$ (119)
$\displaystyle\leq\mathbf{H}^{\blacktriangle}(A|B)_{\mathcal{N}(\mathbf{u}^{\Pi})}$
(120) $\displaystyle=\mathbf{H}^{\blacktriangle}(A|B)_{\rho}.$ (121)

The first equality follows because the entropy of a uniform state is equal to
the logarithm of its rank and from the definition of $m$ in (109). The
inequality follows from the fact that $\mathcal{N}_{X\rightarrow AB}$ is
conditionally unital (see (115)–(117)) and $\mathbf{H}^{\blacktriangle}$ is a
quantum conditional entropy, thus obeying the first postulate in (101). The
final equality follows from (118).

Therefore, since all conditional entropies are additive for tensor-product
states, we conclude that

$\displaystyle\mathbf{H}^{\blacktriangle}(A|B)_{\rho}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\mathbf{H}^{\blacktriangle}(A^{n}|B^{n})_{\rho^{\otimes
n}}$ (122) $\displaystyle\geq\lim_{n\to\infty}\frac{1}{n}\log\left\lfloor
2^{H_{\min}^{\uparrow}(A^{n}|B^{n})_{\rho^{\otimes n}}}\right\rfloor$ (123)
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\log\left\lfloor
2^{nH_{\min}^{\uparrow}(A|B)_{\rho}}\right\rfloor$ (124)
$\displaystyle=H_{\min}^{\uparrow}(A|B)_{\rho}\;.$ (125)

The inequality follows from (119)–(121). The second equality follows from
additivity, and the final equality from the assumption that
$H_{\min}^{\uparrow}(A|B)_{\rho}\geq 0$.

Now let us consider the case when $H_{\min}^{\uparrow}(A|B)<0$. Let

$\displaystyle t$ $\displaystyle\coloneqq 2^{-H_{\min}^{\uparrow}(A|B)},$
(126) $\displaystyle k^{\prime}$ $\displaystyle\coloneqq\left\lceil
t\right\rceil,$ (127) $\displaystyle k$
$\displaystyle\coloneqq\left|A\right|.$ (128)

Observe that $t>1$ by assumption. Also, observe that $t$ is the smallest real
satisfying $\rho_{AB}\leq tI_{A}\otimes\sigma_{B}$. Let $A^{\prime}$ be a
system of dimension $k^{\prime}$, and let $X$ be a classical system of
dimension $\left|X\right|\coloneqq kk^{\prime}$. Now define

$\tau_{AB}^{(k,k^{\prime})}\coloneqq\frac{k^{\prime}I_{A}\otimes\sigma_{B}-\rho_{AB}}{kk^{\prime}-1},$
(129)

and observe that $\tau_{AB}^{(k,k^{\prime})}$ is positive semi-definite
because $kk^{\prime}>1$ and

$\displaystyle k^{\prime}I_{A}\otimes\sigma_{B}-\rho_{AB}$ $\displaystyle\geq
2^{-H_{\min}^{\uparrow}(A|B)}I_{A}\otimes\sigma_{B}-\rho_{AB}$ (130)
$\displaystyle=2^{D_{\max}(\rho_{AB}\|I_{A}\otimes\sigma_{B})}I_{A}\otimes\sigma_{B}-\rho_{AB}$
(131) $\displaystyle\geq 0.$ (132)

Since $\tau_{AB}^{(k,k^{\prime})}$ has trace equal to one, it follows that it
is a state. We then construct the following channel:

$\mathcal{N}_{X\rightarrow AA^{\prime}B}(\omega_{X})\coloneqq\\\
\left(\operatorname{Tr}[|1\rangle\\!\langle
1|_{X}\omega_{X}]\rho_{AB}+\operatorname{Tr}[\Pi_{X}\omega_{X}]\tau_{AB}^{(k,k^{\prime})}\right)\otimes\mathbf{u}_{A^{\prime}},$
(133)

where

$\Pi_{X}\coloneqq I_{X}-|1\rangle\\!\langle 1|_{X},$ (134)

so that $\operatorname{Tr}[\Pi_{X}]=kk^{\prime}-1$. Also, it should be
understood that Alice has access to the $X$ input system. Consider that

$\mathcal{N}_{X\rightarrow AA^{\prime}B}(|1\rangle\\!\langle
1|_{X})=\rho_{AB}\otimes\mathbf{u}_{A^{\prime}}.$ (135)

Furthermore, the channel is conditionally unital because

$\displaystyle\mathcal{N}_{X\rightarrow AA^{\prime}B}(I_{X})$
$\displaystyle=\left(\operatorname{Tr}[|1\rangle\\!\langle
1|_{X}I_{X}]\rho_{AB}+\operatorname{Tr}[\Pi_{X}I_{X}]\tau_{AB}^{(k,k^{\prime})}\right)\otimes\mathbf{u}_{A^{\prime}}$
(136)
$\displaystyle=\left(\rho_{AB}+\left(kk^{\prime}-1\right)\tau_{AB}^{(k,k^{\prime})}\right)\otimes\mathbf{u}_{A^{\prime}}$
(137)
$\displaystyle=k^{\prime}I_{A}\otimes\sigma_{B}\otimes\mathbf{u}_{A^{\prime}}$
(138) $\displaystyle=I_{A}\otimes\sigma_{B}\otimes I_{A^{\prime}}.$ (139)

Then it follows that

$\displaystyle 0$
$\displaystyle=\mathbf{H}^{\blacktriangle}(X)_{|1\rangle\\!\langle 1|}$ (140)
$\displaystyle\leq\mathbf{H}^{\blacktriangle}(AA^{\prime}|B)_{\mathcal{N}(|1\rangle\\!\langle
1|)}$ (141)
$\displaystyle=\mathbf{H}^{\blacktriangle}(AA^{\prime}|B)_{\rho\otimes\mathbf{u}}$
(142)
$\displaystyle=\mathbf{H}^{\blacktriangle}(A|B)_{\rho}+\mathbf{H}(A^{\prime})_{\mathbf{u}}$
(143)
$\displaystyle=\mathbf{H}^{\blacktriangle}(A|B)_{\rho}+\log_{2}\left\lceil
2^{-H_{\min}^{\uparrow}(A|B)}\right\rceil.$ (144)

The first equality follows because the entropy of a pure state is equal to
zero. The inequality follows because $\mathcal{N}_{X\rightarrow AA^{\prime}B}$
is a conditionally unital channel and $\mathbf{H}^{\blacktriangle}$ is a
quantum conditional entropy, thus obeying the first postulate in (101). The
second equality follows from (135). The penultimate equality follows from the
additivity postulate of quantum conditional entropy. The final equality
follows because the entropy of the uniform state $\mathbf{u}_{A^{\prime}}$ is
equal to the logarithm of its rank, which is in turn equal to $\left\lceil
2^{-H_{\min}^{\uparrow}(A|B)}\right\rceil$.

Now, since $\mathbf{H}^{\blacktriangle}(A|B)_{\rho}$ is additive for tensor-
product states, we find that

$\displaystyle\mathbf{H}^{\blacktriangle}(A|B)_{\rho}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\mathbf{H}^{\blacktriangle}(A^{n}|B^{n})_{\rho^{\otimes
n}}$ (145) $\displaystyle\geq\lim_{n\to\infty}-\frac{1}{n}\log\left\lceil
2^{-H_{\min}^{\uparrow}(A^{n}|B^{n})_{\rho^{\otimes n}}}\right\rceil$ (146)
$\displaystyle=\lim_{n\to\infty}-\frac{1}{n}\log\left\lceil
2^{-nH_{\min}^{\uparrow}(A|B)_{\rho}}\right\rceil$ (147)
$\displaystyle=\lim_{n\to\infty}-\frac{1}{n}\log\left\lceil t^{n}\right\rceil$
(148) $\displaystyle\geq\lim_{n\to\infty}-\frac{1}{n}\log\left(t^{n}+1\right)$
(149) $\displaystyle=-\log t=H_{\min}^{\uparrow}(A|B)_{\rho}\;.$ (150)

The first inequality follows from (140)–(144). The second equality follows
from additivity, and the final equality from the assumption that $t>1$. This
completes the proof of the lower bound.

It is left to prove the equality on maximally entangled states. Since
conditional entropy is invariant under local isometries we can assume without
loss of generality that $k\coloneqq|A|=|B|$. Now, consider the state
$\Phi^{(k)}_{AB}\otimes\mathbf{u}_{\tilde{A}}$ where $|\tilde{A}|=k$, and
observe that by introducing a trivial system $B_{2}$ such that $|B_{2}|=1$ we
get

$\displaystyle\mathbf{H}^{\blacktriangle}(A\tilde{A}|B)_{\Phi^{(k)}_{AB}\otimes\mathbf{u}_{\tilde{A}}}$
$\displaystyle=\mathbf{H}^{\blacktriangle}(A\tilde{A}|BB_{2})_{\Phi^{(k)}_{AB}\otimes\mathbf{u}_{\tilde{A}B_{2}}}$
(151)
$\displaystyle=\mathbf{H}^{\blacktriangle}(A|B)_{\Phi^{(k)}}+\mathbf{H}^{\blacktriangle}(\tilde{A}|B_{2})_{\mathbf{u}_{\tilde{A}B_{2}}}$
(152)
$\displaystyle=\mathbf{H}^{\blacktriangle}(A|B)_{\Phi^{(k)}}+\mathbf{H}^{\blacktriangle}(\mathbf{u}_{\tilde{A}})$
(153) $\displaystyle=\mathbf{H}^{\blacktriangle}(A|B)_{\Phi^{(k)}}+\log k,$
(154)

where we used the additivity property of conditional entropy and the fact that
the entropy of the uniform state $\mathbf{u}_{\tilde{A}}$ is $\log_{2}k$. It
is therefore sufficient to show that

$\mathbf{H}^{\blacktriangle}(A\tilde{A}|B)_{\Phi^{(k)}_{AB}\otimes\mathbf{u}_{\tilde{A}}}\leq
0$ (155)

since the above equation implies that

$\mathbf{H}^{\blacktriangle}(A|B)_{\Phi^{(k)}}\leq-\log
k=H_{\min}^{\uparrow}(A|B)_{\Phi^{(k)}}\;.$ (156)

For this purpose, let $X$ be a classical system of dimension
$\left|X\right|=k^{2}$ and let $\mathcal{N}_{A\tilde{A}B\rightarrow X}$ a
quantum channel defined by

$\mathcal{N}_{A\tilde{A}B\rightarrow X}\coloneqq\mathcal{E}_{AB\rightarrow
X}\circ\operatorname{Tr}_{\tilde{A}},$ (157)

where

$\mathcal{E}_{AB\rightarrow
X}(\omega_{AB})\coloneqq\operatorname{Tr}[\Phi_{AB}^{k}\omega_{AB}]|1\rangle\\!\langle
1|_{X}\\\
+\operatorname{Tr}[(I_{AB}-\Phi_{AB}^{(k)})\omega_{AB}]\frac{I_{X}-|1\rangle\\!\langle
1|_{X}}{k^{2}-1}.$ (158)

This channel is conditionally unital because

$\displaystyle\mathcal{N}_{A\tilde{A}B\rightarrow X}(I_{A}\otimes
I_{\tilde{A}}\otimes\sigma_{B})$ $\displaystyle=(\mathcal{E}_{AB\rightarrow
X}\circ\operatorname{Tr}_{\tilde{A}})(I_{A}\otimes
I_{\tilde{A}}\otimes\sigma_{B})$ (159) $\displaystyle=k\
\mathcal{E}_{AB\rightarrow X}(I_{A}\otimes\sigma_{B})$ (160) $\displaystyle=k\
\left(\begin{array}[c]{c}\operatorname{Tr}[\Phi_{AB}^{(k)}(I_{A}\otimes\sigma_{B})]|1\rangle\\!\langle
1|_{X}\\\
+\operatorname{Tr}[(I_{AB}-\Phi_{AB}^{(k)})(I_{A}\otimes\sigma_{B})]\frac{I_{X}-|1\rangle\\!\langle
1|_{X}}{k^{2}-1}\end{array}\right)$ (163) $\displaystyle=k\
\left(\frac{1}{k}|1\rangle\\!\langle
1|_{X}+\left(k-\frac{1}{k}\right)\frac{I_{X}-|1\rangle\\!\langle
1|_{X}}{k^{2}-1}\right)$ (164) $\displaystyle=|1\rangle\\!\langle
1|_{X}+\left(k^{2}-1\right)\frac{I_{X}-|1\rangle\langle 1|_{X}}{k^{2}-1}$
(165) $\displaystyle=I_{X}.$ (166)

Also, consider that

$\mathcal{N}_{A\tilde{A}B\rightarrow
X}(\Phi_{AB}^{(k)}\otimes\mathbf{u}_{\tilde{A}})=|1\rangle\\!\langle 1|_{X}.$
(167)

Then

$\displaystyle\mathbf{H}^{\blacktriangle}(A|B)_{\Phi^{(k)}}+\log k$
$\displaystyle=\mathbf{H}^{\blacktriangle}(A\tilde{A}|B)_{\Phi^{(k)}\otimes\mathbf{u}}$
(168)
$\displaystyle\leq\mathbf{H}^{\blacktriangle}(X)_{\mathcal{N}(\Phi^{(k)}\otimes\mathbf{u})}$
(169) $\displaystyle=\mathbf{H}^{\blacktriangle}(X)_{|1\rangle\\!\langle 1|}$
(170) $\displaystyle=0.$ (171)

The first equality follows from (151)–(154). The inequality follows because
the channel $\mathcal{N}_{A\tilde{A}B\rightarrow X}$ is conditionally unital.
The second equality follows from (167) and the last because the entropy of
every pure state is equal to zero. This concludes the proof.

###  E.2 Proof of Theorem 1

Here the idea is essentially the same as that given in Appendix E.1, except
that we need to construct channels that are locally balanced (i.e., both
conditionally unital and $A\not\to B$ semi-causal.

First, throughout, we make the following replacement in the proof:

$H_{\min}^{\uparrow}(A|B)_{\rho}\quad\to\quad H_{\min}(A|B)_{\rho}.$ (172)

To handle the case when $H_{\min}(A|B)_{\rho}\geq 0$, we employ the same
channel in (114), with the exception that we set

$\tau_{AB}^{(m)}\coloneqq\frac{I_{A}\otimes\rho_{B}-m\rho_{AB}}{k-m}.$ (173)

All of the steps in (108)–(125) go through with the replacements in (172) and
(173). We now verify that the $A\not\to B$ semi-causal constraint holds for
this channel. Consider, for the modified channel, that

$\displaystyle\operatorname{Tr}_{A}[\mathcal{N}_{X\to AB}(\omega_{X})]$
$\displaystyle=\operatorname{Tr}[\Pi_{X}\omega_{X}]\operatorname{Tr}_{A}[\rho_{AB}]+\operatorname{Tr}[\left(I_{X}-\Pi_{X}\right)\omega_{X}]\operatorname{Tr}_{A}[\tau_{AB}^{(m)}]$
$\displaystyle=\operatorname{Tr}[\Pi_{X}\omega_{X}]\rho_{B}+\operatorname{Tr}[\left(I_{X}-\Pi_{X}\right)\omega_{X}]\rho_{B}$
$\displaystyle=\rho_{B}.$ (174)

Thus, the output state of $B$ has no dependence on the input state
$\omega_{X}$ when system $A$ is traced out, so that the semi-causal constraint
holds.

Now let us consider the case when $H_{\min}(A|B)_{\rho}<0$. We employ the same
channel in (133), with the exception that we set

$\tau_{AB}^{(k,k^{\prime})}\coloneqq\frac{k^{\prime}I_{A}\otimes\rho_{B}-\rho_{AB}}{kk^{\prime}-1}.$
(175)

Then all of the steps in (126)–(150) go through, with the replacements in
(172) and (175). We now verify that the $A\not\to B$ semi-causal constraint
holds for this channel. Consider, for the modified channel, that

$\displaystyle\operatorname{Tr}_{AA^{\prime}}[\mathcal{N}_{X\rightarrow
AA^{\prime}B}(\omega_{X})]$
$\displaystyle=\left(\operatorname{Tr}[|1\rangle\\!\langle
1|_{X}\omega_{X}]\operatorname{Tr}_{A}[\rho_{AB}]+\operatorname{Tr}[\Pi_{X}\omega_{X}]\operatorname{Tr}_{A}[\tau_{AB}^{(k,k^{\prime})}]\right)$
$\displaystyle\qquad\otimes\operatorname{Tr}_{A^{\prime}}[\mathbf{u}_{A^{\prime}}]$
(176) $\displaystyle=\operatorname{Tr}[|1\rangle\\!\langle
1|_{X}\omega_{X}]\rho_{B}+\operatorname{Tr}[\Pi_{X}\omega_{X}]\rho_{B}$ (177)
$\displaystyle=\rho_{B}.$ (178)

Thus, the output state of $B$ has no dependence on the input state
$\omega_{X}$ when system $A$ is traced out, so that the semi-causal constraint
holds. This establishes the inequality in (105).

Finally, we consider the equality in (106). The argument here is actually
exactly the same as in (151)–(171), except using the replacement in (172). We
just need to verify that the channel in (157) is $A\not\to B$ semi-causal.
However, the only output is system $X$, which belongs to Alice. Thus, after
tracing it out, there is no remaining system and the channel is then semi-
causal.

##  Appendix F Proof of Theorem 2

First, we demonstrate that $\mathbf{H}$ satisfies the monotonicity property of
conditional entropy. Let $\mathcal{N}_{AB\rightarrow A^{\prime}B^{\prime}}$ be
a locally balanced channel, and consider the bipartite density matrix
$\rho_{AB}$. We begin by considering the case where $A=A^{\prime}$ and

$\mathbf{H}(A\big{|}B)_{\mathcal{N}(\rho)}=\\\
\log|A|-\mathbf{D}(\mathcal{N}(\rho_{AB})\big{\|}\mathbf{u}_{A}\otimes\operatorname{Tr}_{A}\\!\left[\mathcal{N}(\rho_{AB})\right])$
(179)

and from using the fact that $\mathcal{N}$ is semi-causal and conditionally
unital, we find that

$\displaystyle\mathbf{u}_{A}\otimes\operatorname{Tr}_{A}\\!\left[\mathcal{N}(\rho_{AB})\right]$
$\displaystyle=\mathbf{u}_{A}\otimes\operatorname{Tr}_{A}\\!\left[\mathcal{N}\left(\mathbf{u}_{A}\otimes\rho_{B}\right)\right]$
(180) $\displaystyle=\mathcal{N}(\mathbf{u}_{A}\otimes\rho_{B}),$ (181)

from which we have

$\displaystyle\mathbf{H}(A\big{|}B)_{\mathcal{N}(\rho)}$
$\displaystyle=\log|A|-\mathbf{D}\left(\mathcal{N}(\rho_{AB})\big{\|}\mathcal{N}(\mathbf{u}_{A}\otimes\rho_{B})\right)$
$\displaystyle\geq\log|A|-\mathbf{D}\left(\rho_{AB}\big{\|}\mathbf{u}_{A}\otimes\rho_{B}\right),$
(182)

where the last line follows from the data-processing inequality.

We also need to prove that it is invariant under the action of a local
isometric channel acting on system $A$. Let $\mathcal{V}_{A\rightarrow
A^{\prime}}$ be an arbitrary isometric channel, and let $C$ represent a
Hilbert space such that $|C|=|A^{\prime}|-|A|$. Then

$\mathbf{H}(A|B)_{\mathcal{V}(\rho)}=\\\
\log|A^{\prime}|-\mathbf{D}(\mathcal{V}_{A\rightarrow
A^{\prime}}(\rho_{AB})\|\mathbf{u}_{A^{\prime}}\otimes\rho_{B}).$ (183)

Clearly, if $\mathcal{V}$ is a unitary channel such that $A\simeq A^{\prime}$,
then $\mathbf{H}(A^{\prime}|B)_{\mathcal{V}(\rho)}=\mathbf{H}(A|B)_{\rho}$.
Then without loss of generality, we assume that

$\displaystyle\mathcal{V}_{A\rightarrow A^{\prime}}(\rho_{AB})$
$\displaystyle=\rho_{AB}\oplus\mathbf{0}_{CB}$ (184)
$\displaystyle=\begin{pmatrix}\rho_{AB}&\mathbf{0}\\\
\mathbf{0}&\mathbf{0}_{CB}\end{pmatrix},$ (185)

because the conditional entropy is invariant under local unitaries. We can
additionally rewrite

$\mathbf{u}_{A^{\prime}}=t\mathbf{u}_{A}\oplus(1-t)\mathbf{u}_{C},$ (186)

where $t\coloneqq\frac{|A|}{|A^{\prime}|}$. From this, it follows that

$\displaystyle\mathbf{D}(\mathcal{V}_{A\rightarrow
A^{\prime}}(\rho_{AB})\big{\|}\mathbf{u}_{A^{\prime}}\otimes\rho_{B})$
$\displaystyle=\mathbf{D}\left(\rho_{AB}\oplus\mathbf{0}_{CB}\big{\|}\left(t\mathbf{u}_{A}\otimes\rho_{B}\right)\oplus\left(\left(1-t\right)\mathbf{u}_{C}\otimes\rho_{B}\right)\right)$
$\displaystyle=\mathbf{D}\left(\rho_{AB}\big{\|}t\mathbf{u}_{A}\otimes\rho_{B}\right)$
$\displaystyle=\mathbf{D}\left(\rho_{AB}\big{\|}\mathbf{u}_{A}\otimes\rho_{B}\right)-\log(t),$
(187)

where the second equality follows from a property of relative entropy proved
in [52]. Thus, upon substitution, we have that

$\displaystyle\mathbf{H}(A^{\prime}|B)_{\mathcal{V}(\rho)}$
$\displaystyle=\log|A^{\prime}|-\mathbf{D}\left(\rho_{AB}\big{\|}\mathbf{u}_{A}\otimes\rho_{B}\right)+\log(t)$
$\displaystyle=\mathbf{H}(A|B)_{\rho}.$ (188)

Finally, additivity of $\mathbf{H}$ follows immediately from additivity of
$\mathbf{D}$.

###  F.1 Conditional min-entropy is a conditional entropy

Here we justify that the conditional min-entropy is indeed a conditional
entropy according to the definition in (21)–(23). Indeed, we use the
definition of conditional min-entropy in (29) to rewrite it in terms of the
max-relative entropy $D_{\max}(\rho\|\sigma)$ as

$H_{\min}(A|B)_{\rho}=\log_{2}|A|-D_{\max}(\rho_{AB}\|\mathbf{u}_{A}\otimes\rho_{B}),$
(189)

where the max-relative entropy of states $\rho$ and $\sigma$ is defined as
[53]:

$D_{\max}(\rho\|\sigma)\coloneqq\log_{2}\inf_{\lambda\geq
0}\\{\rho\leq\lambda\sigma\\}.$ (190)

Then we apply Theorem 2.

##  Appendix G Example of non-negative weakly additive monotonic function

In this section we prove that there exists a non-zero function that satisfies
the following three properties:

  1. 1.

Monotonicity under conditional majorization; i.e., satisfying (22).

  2. 2.

Weak additivity of the form (37).

  3. 3.

Non-negative.

The third property above demonstrates that the negativity of conditional
entropy is closely related to the full additivity postulate. The construction
of the example is based on a technique developed in [37] for the extension of
resource monotones from one domain to another.

Let $\mathbb{H}$ be a classical conditional-entropy. In [37] it was shown that
any such function has two optimal extensions to the quantum domain. Here we
are interested in the following extension. For any $\rho\in\mathfrak{D}(AB)$
we define

$f(A|B)_{\rho}\coloneqq\inf_{\rho_{AB}\succ_{A}\sigma_{XY}}\mathbb{H}(X|Y)_{\sigma}\;,$
(191)

where the infimum above is over all classical systems $X$ and $Y$ and all
classical states $\sigma_{XY}$ with with the property that
$\rho_{AB}\succ_{A}\sigma_{XY}$. The function $f$ has the following key
properties [37]:

  1. 1.

Reduction: For all classical states $\rho\in\mathfrak{D}(XY)$

$f(X|Y)_{\rho}=\mathbb{H}(X|Y)_{\rho}\;.$ (192)

  2. 2.

Monotonicity: For all $\rho\in\mathfrak{D}(AB)$ and
$\omega\in\mathfrak{D}(A^{\prime}B^{\prime})$ with
$\rho_{AB}\succ_{A}\omega_{A^{\prime}B^{\prime}}$

$f(A^{\prime}|B^{\prime})_{\omega}\geq f(A|B)_{\rho}\;.$ (193)

  3. 3.

Subadditivity: The function $f$ is subadditive under tensor products.

  4. 4.

Positivity: The function $f$ is non-negative.

The last property follows from the definition in (191). Since $f$ is
subadditive, the limit

$g(A|B)_{\rho}\coloneqq\lim_{n\to\infty}\frac{1}{n}f(A^{n}|B^{n})_{\rho^{\otimes
n}}$ (194)

exists. Therefore, the function $g$ is weakly additive. Moreover, the function
$g$ satisfies the first two properties above, namely, reduction to
$\mathbb{H}$ on classical states and behaves monotonically under conditional
majorization. Observe that the reduction of $g$ to $\mathbb{H}$ on classical
states implies that it is not equal to the zero function since $\mathbb{H}$ is
not the zero function. Since $g$ is non-negative it cannot be a conditional
entropy. This means that $g$ cannot be fully additive, as this is the only
property that does not follow directly from its definition.