- Source: Min-entropy
The min-entropy, in information theory, is the smallest of the Rényi family of entropies, corresponding to the most conservative way of measuring the unpredictability of a set of outcomes, as the negative logarithm of the probability of the most likely outcome. The various Rényi entropies are all equal for a uniform distribution, but measure the unpredictability of a nonuniform distribution in different ways. The min-entropy is never greater than the ordinary or Shannon entropy (which measures the average unpredictability of the outcomes) and that in turn is never greater than the Hartley or max-entropy, defined as the logarithm of the number of outcomes with nonzero probability.
As with the classical Shannon entropy and its quantum generalization, the von Neumann entropy, one can define a conditional version of min-entropy. The conditional quantum min-entropy is a one-shot, or conservative, analog of conditional quantum entropy.
To interpret a conditional information measure, suppose Alice and Bob were to share a bipartite quantum state
ρ
A
B
{\displaystyle \rho _{AB}}
. Alice has access to system
A
{\displaystyle A}
and Bob to system
B
{\displaystyle B}
. The conditional entropy measures the average uncertainty Bob has about Alice's state upon sampling from his own system. The min-entropy can be interpreted as the distance of a state from a maximally entangled state.
This concept is useful in quantum cryptography, in the context of privacy amplification (See for example ).
Definition for classical distributions
If
P
=
(
p
1
,
.
.
.
,
p
n
)
{\displaystyle P=(p_{1},...,p_{n})}
is a classical finite probability distribution, its min-entropy can be defined as
H
m
i
n
(
P
)
=
log
1
P
m
a
x
,
P
m
a
x
≡
max
i
p
i
.
{\displaystyle H_{\rm {min}}({\boldsymbol {P}})=\log {\frac {1}{P_{\rm {max}}}},\qquad P_{\rm {max}}\equiv \max _{i}p_{i}.}
One way to justify the name of the quantity is to compare it with the more standard definition of entropy, which reads
H
(
P
)
=
∑
i
p
i
log
(
1
/
p
i
)
{\displaystyle H({\boldsymbol {P}})=\sum _{i}p_{i}\log(1/p_{i})}
, and can thus be written concisely as the expectation value of
log
(
1
/
p
i
)
{\displaystyle \log(1/p_{i})}
over the distribution. If instead of taking the expectation value of this quantity we take its minimum value, we get precisely the above definition of
H
m
i
n
(
P
)
{\displaystyle H_{\rm {min}}({\boldsymbol {P}})}
.
From an operational perspective, the min-entropy equals the negative logarithm of the probability of successfully guessing the outcome of a random draw from
P
{\displaystyle P}
.
This is because it is optimal to guess the element with the largest probability and the chance of success equals the probability of that element.
Definition for quantum states
A natural way to generalize "min-entropy" from classical to quantum states is to leverage the simple observation that quantum states define classical probability distributions when measured in some basis. There is however the added difficulty that a single quantum state can result in infinitely many possible probability distributions, depending on how it is measured. A natural path is then, given a quantum state
ρ
{\displaystyle \rho }
, to still define
H
m
i
n
(
ρ
)
{\displaystyle H_{\rm {min}}(\rho )}
as
log
(
1
/
P
m
a
x
)
{\displaystyle \log(1/P_{\rm {max}})}
, but this time defining
P
m
a
x
{\displaystyle P_{\rm {max}}}
as the maximum possible probability that can be obtained measuring
ρ
{\displaystyle \rho }
, maximizing over all possible projective measurements.
Using this, one gets the operational definition that the min-entropy of
ρ
{\displaystyle \rho }
equals the negative logarithm of the probability of successfully guessing the outcome of any measurement of
ρ
{\displaystyle \rho }
.
Formally, this leads to the definition
H
m
i
n
(
ρ
)
=
max
Π
log
1
max
i
tr
(
Π
i
ρ
)
=
−
max
Π
log
max
i
tr
(
Π
i
ρ
)
,
{\displaystyle H_{\rm {min}}(\rho )=\max _{\Pi }\log {\frac {1}{\max _{i}\operatorname {tr} (\Pi _{i}\rho )}}=-\max _{\Pi }\log \max _{i}\operatorname {tr} (\Pi _{i}\rho ),}
where we are maximizing over the set of all projective measurements
Π
=
(
Π
i
)
i
{\displaystyle \Pi =(\Pi _{i})_{i}}
,
Π
i
{\displaystyle \Pi _{i}}
represent the measurement outcomes in the POVM formalism, and
tr
(
Π
i
ρ
)
{\displaystyle \operatorname {tr} (\Pi _{i}\rho )}
is therefore the probability of observing the
i
{\displaystyle i}
-th outcome when the measurement is
Π
{\displaystyle \Pi }
.
A more concise method to write the double maximization is to observe that any element of any POVM is a Hermitian operator such that
0
≤
Π
≤
I
{\displaystyle 0\leq \Pi \leq I}
, and thus we can equivalently directly maximize over these to get
H
m
i
n
(
ρ
)
=
−
max
0
≤
Π
≤
I
log
tr
(
Π
ρ
)
.
{\displaystyle H_{\rm {min}}(\rho )=-\max _{0\leq \Pi \leq I}\log \operatorname {tr} (\Pi \rho ).}
In fact, this maximization can be performed explicitly and the maximum is obtained when
Π
{\displaystyle \Pi }
is the projection onto (any of) the largest eigenvalue(s) of
ρ
{\displaystyle \rho }
. We thus get yet another expression for the min-entropy as:
H
m
i
n
(
ρ
)
=
−
log
‖
ρ
‖
o
p
,
{\displaystyle H_{\rm {min}}(\rho )=-\log \|\rho \|_{\rm {op}},}
remembering that the operator norm of a Hermitian positive semidefinite operator equals its largest eigenvalue.
Conditional entropies
Let
ρ
A
B
{\displaystyle \rho _{AB}}
be a bipartite density operator on the space
H
A
⊗
H
B
{\displaystyle {\mathcal {H}}_{A}\otimes {\mathcal {H}}_{B}}
. The min-entropy of
A
{\displaystyle A}
conditioned on
B
{\displaystyle B}
is defined to be
H
min
(
A
|
B
)
ρ
≡
−
inf
σ
B
D
max
(
ρ
A
B
‖
I
A
⊗
σ
B
)
{\displaystyle H_{\min }(A|B)_{\rho }\equiv -\inf _{\sigma _{B}}D_{\max }(\rho _{AB}\|I_{A}\otimes \sigma _{B})}
where the infimum ranges over all density operators
σ
B
{\displaystyle \sigma _{B}}
on the space
H
B
{\displaystyle {\mathcal {H}}_{B}}
. The measure
D
max
{\displaystyle D_{\max }}
is the maximum relative entropy defined as
D
max
(
ρ
‖
σ
)
=
inf
λ
{
λ
:
ρ
≤
2
λ
σ
}
{\displaystyle D_{\max }(\rho \|\sigma )=\inf _{\lambda }\{\lambda :\rho \leq 2^{\lambda }\sigma \}}
The smooth min-entropy is defined in terms of the min-entropy.
H
min
ϵ
(
A
|
B
)
ρ
=
sup
ρ
′
H
min
(
A
|
B
)
ρ
′
{\displaystyle H_{\min }^{\epsilon }(A|B)_{\rho }=\sup _{\rho '}H_{\min }(A|B)_{\rho '}}
where the sup and inf range over density operators
ρ
A
B
′
{\displaystyle \rho '_{AB}}
which are
ϵ
{\displaystyle \epsilon }
-close to
ρ
A
B
{\displaystyle \rho _{AB}}
. This measure of
ϵ
{\displaystyle \epsilon }
-close is defined in terms of the purified distance
P
(
ρ
,
σ
)
=
1
−
F
(
ρ
,
σ
)
2
{\displaystyle P(\rho ,\sigma )={\sqrt {1-F(\rho ,\sigma )^{2}}}}
where
F
(
ρ
,
σ
)
{\displaystyle F(\rho ,\sigma )}
is the fidelity measure.
These quantities can be seen as generalizations of the von Neumann entropy. Indeed, the von Neumann entropy can be expressed as
S
(
A
|
B
)
ρ
=
lim
ϵ
→
0
lim
n
→
∞
1
n
H
min
ϵ
(
A
n
|
B
n
)
ρ
⊗
n
.
{\displaystyle S(A|B)_{\rho }=\lim _{\epsilon \rightarrow 0}\lim _{n\rightarrow \infty }{\frac {1}{n}}H_{\min }^{\epsilon }(A^{n}|B^{n})_{\rho ^{\otimes n}}~.}
This is called the fully quantum asymptotic equipartition theorem.
The smoothed entropies share many interesting properties with the von Neumann entropy. For example, the smooth min-entropy satisfy a data-processing inequality:
H
min
ϵ
(
A
|
B
)
ρ
≥
H
min
ϵ
(
A
|
B
C
)
ρ
.
{\displaystyle H_{\min }^{\epsilon }(A|B)_{\rho }\geq H_{\min }^{\epsilon }(A|BC)_{\rho }~.}
Operational interpretation of smoothed min-entropy
Henceforth, we shall drop the subscript
ρ
{\displaystyle \rho }
from the min-entropy when it is obvious from the context on what state it is evaluated.
= Min-entropy as uncertainty about classical information
=Suppose an agent had access to a quantum system
B
{\displaystyle B}
whose state
ρ
B
x
{\displaystyle \rho _{B}^{x}}
depends on some classical variable
X
{\displaystyle X}
. Furthermore, suppose that each of its elements
x
{\displaystyle x}
is distributed according to some distribution
P
X
(
x
)
{\displaystyle P_{X}(x)}
. This can be described by the following state over the system
X
B
{\displaystyle XB}
.
ρ
X
B
=
∑
x
P
X
(
x
)
|
x
⟩
⟨
x
|
⊗
ρ
B
x
,
{\displaystyle \rho _{XB}=\sum _{x}P_{X}(x)|x\rangle \langle x|\otimes \rho _{B}^{x},}
where
{
|
x
⟩
}
{\displaystyle \{|x\rangle \}}
form an orthonormal basis. We would like to know what the agent can learn about the classical variable
x
{\displaystyle x}
. Let
p
g
(
X
|
B
)
{\displaystyle p_{g}(X|B)}
be the probability that the agent guesses
X
{\displaystyle X}
when using an optimal measurement strategy
p
g
(
X
|
B
)
=
∑
x
P
X
(
x
)
tr
(
E
x
ρ
B
x
)
,
{\displaystyle p_{g}(X|B)=\sum _{x}P_{X}(x)\operatorname {tr} (E_{x}\rho _{B}^{x}),}
where
E
x
{\displaystyle E_{x}}
is the POVM that maximizes this expression. It can be shown that this optimum can be expressed in terms of the min-entropy as
p
g
(
X
|
B
)
=
2
−
H
min
(
X
|
B
)
.
{\displaystyle p_{g}(X|B)=2^{-H_{\min }(X|B)}~.}
If the state
ρ
X
B
{\displaystyle \rho _{XB}}
is a product state i.e.
ρ
X
B
=
σ
X
⊗
τ
B
{\displaystyle \rho _{XB}=\sigma _{X}\otimes \tau _{B}}
for some density operators
σ
X
{\displaystyle \sigma _{X}}
and
τ
B
{\displaystyle \tau _{B}}
, then there is no correlation between the systems
X
{\displaystyle X}
and
B
{\displaystyle B}
. In this case, it turns out that
2
−
H
min
(
X
|
B
)
=
max
x
P
X
(
x
)
.
{\displaystyle 2^{-H_{\min }(X|B)}=\max _{x}P_{X}(x)~.}
Since the conditional min-entropy is always smaller than the conditional Von Neumann entropy, it follows that
p
g
(
X
|
B
)
≥
2
−
S
(
A
|
B
)
ρ
.
{\displaystyle p_{g}(X|B)\geq 2^{-S(A|B)_{\rho }}~.}
Min-entropy as overlap with the maximally entangled state
The maximally entangled state
|
ϕ
+
⟩
{\displaystyle |\phi ^{+}\rangle }
on a bipartite system
H
A
⊗
H
B
{\displaystyle {\mathcal {H}}_{A}\otimes {\mathcal {H}}_{B}}
is defined as
|
ϕ
+
⟩
A
B
=
1
d
∑
x
A
,
x
B
|
x
A
⟩
|
x
B
⟩
{\displaystyle |\phi ^{+}\rangle _{AB}={\frac {1}{\sqrt {d}}}\sum _{x_{A},x_{B}}|x_{A}\rangle |x_{B}\rangle }
where
{
|
x
A
⟩
}
{\displaystyle \{|x_{A}\rangle \}}
and
{
|
x
B
⟩
}
{\displaystyle \{|x_{B}\rangle \}}
form an orthonormal basis for the spaces
A
{\displaystyle A}
and
B
{\displaystyle B}
respectively.
For a bipartite quantum state
ρ
A
B
{\displaystyle \rho _{AB}}
, we define the maximum overlap with the maximally entangled state as
q
c
(
A
|
B
)
=
d
A
max
E
F
(
(
I
A
⊗
E
)
ρ
A
B
,
|
ϕ
+
⟩
⟨
ϕ
+
|
)
2
{\displaystyle q_{c}(A|B)=d_{A}\max _{\mathcal {E}}F\left((I_{A}\otimes {\mathcal {E}})\rho _{AB},|\phi ^{+}\rangle \langle \phi ^{+}|\right)^{2}}
where the maximum is over all CPTP operations
E
{\displaystyle {\mathcal {E}}}
and
d
A
{\displaystyle d_{A}}
is the dimension of subsystem
A
{\displaystyle A}
. This is a measure of how correlated the state
ρ
A
B
{\displaystyle \rho _{AB}}
is. It can be shown that
q
c
(
A
|
B
)
=
2
−
H
min
(
A
|
B
)
{\displaystyle q_{c}(A|B)=2^{-H_{\min }(A|B)}}
. If the information contained in
A
{\displaystyle A}
is classical, this reduces to the expression above for the guessing probability.
= Proof of operational characterization of min-entropy
=The proof is from a paper by König, Schaffner, Renner in 2008. It involves the machinery of semidefinite programs. Suppose we are given some bipartite density operator
ρ
A
B
{\displaystyle \rho _{AB}}
. From the definition of the min-entropy, we have
H
min
(
A
|
B
)
=
−
inf
σ
B
inf
λ
{
λ
|
ρ
A
B
≤
2
λ
(
I
A
⊗
σ
B
)
}
.
{\displaystyle H_{\min }(A|B)=-\inf _{\sigma _{B}}\inf _{\lambda }\{\lambda |\rho _{AB}\leq 2^{\lambda }(I_{A}\otimes \sigma _{B})\}~.}
This can be re-written as
−
log
inf
σ
B
Tr
(
σ
B
)
{\displaystyle -\log \inf _{\sigma _{B}}\operatorname {Tr} (\sigma _{B})}
subject to the conditions
σ
B
≥
0
{\displaystyle \sigma _{B}\geq 0}
I
A
⊗
σ
B
≥
ρ
A
B
.
{\displaystyle I_{A}\otimes \sigma _{B}\geq \rho _{AB}~.}
We notice that the infimum is taken over compact sets and hence can be replaced by a minimum. This can then be expressed succinctly as a semidefinite program. Consider the primal problem
min:
Tr
(
σ
B
)
{\displaystyle {\text{min:}}\operatorname {Tr} (\sigma _{B})}
subject to:
I
A
⊗
σ
B
≥
ρ
A
B
{\displaystyle {\text{subject to: }}I_{A}\otimes \sigma _{B}\geq \rho _{AB}}
σ
B
≥
0
.
{\displaystyle \sigma _{B}\geq 0~.}
This primal problem can also be fully specified by the matrices
(
ρ
A
B
,
I
B
,
Tr
∗
)
{\displaystyle (\rho _{AB},I_{B},\operatorname {Tr} ^{*})}
where
Tr
∗
{\displaystyle \operatorname {Tr} ^{*}}
is the adjoint of the partial trace over
A
{\displaystyle A}
. The action of
Tr
∗
{\displaystyle \operatorname {Tr} ^{*}}
on operators on
B
{\displaystyle B}
can be written as
Tr
∗
(
X
)
=
I
A
⊗
X
.
{\displaystyle \operatorname {Tr} ^{*}(X)=I_{A}\otimes X~.}
We can express the dual problem as a maximization over operators
E
A
B
{\displaystyle E_{AB}}
on the space
A
B
{\displaystyle AB}
as
max:
Tr
(
ρ
A
B
E
A
B
)
{\displaystyle {\text{max:}}\operatorname {Tr} (\rho _{AB}E_{AB})}
subject to:
Tr
A
(
E
A
B
)
=
I
B
{\displaystyle {\text{subject to: }}\operatorname {Tr} _{A}(E_{AB})=I_{B}}
E
A
B
≥
0
.
{\displaystyle E_{AB}\geq 0~.}
Using the Choi–Jamiołkowski isomorphism, we can define the channel
E
{\displaystyle {\mathcal {E}}}
such that
d
A
I
A
⊗
E
†
(
|
ϕ
+
⟩
⟨
ϕ
+
|
)
=
E
A
B
{\displaystyle d_{A}I_{A}\otimes {\mathcal {E}}^{\dagger }(|\phi ^{+}\rangle \langle \phi ^{+}|)=E_{AB}}
where the bell state is defined over the space
A
A
′
{\displaystyle AA'}
. This means that we can express the objective function of the dual problem as
⟨
ρ
A
B
,
E
A
B
⟩
=
d
A
⟨
ρ
A
B
,
I
A
⊗
E
†
(
|
ϕ
+
⟩
⟨
ϕ
+
|
)
⟩
{\displaystyle \langle \rho _{AB},E_{AB}\rangle =d_{A}\langle \rho _{AB},I_{A}\otimes {\mathcal {E}}^{\dagger }(|\phi ^{+}\rangle \langle \phi ^{+}|)\rangle }
=
d
A
⟨
I
A
⊗
E
(
ρ
A
B
)
,
|
ϕ
+
⟩
⟨
ϕ
+
|
)
⟩
{\displaystyle =d_{A}\langle I_{A}\otimes {\mathcal {E}}(\rho _{AB}),|\phi ^{+}\rangle \langle \phi ^{+}|)\rangle }
as desired.
Notice that in the event that the system
A
{\displaystyle A}
is a partly classical state as above, then the quantity that we are after reduces to
max
P
X
(
x
)
⟨
x
|
E
(
ρ
B
x
)
|
x
⟩
.
{\displaystyle \max P_{X}(x)\langle x|{\mathcal {E}}(\rho _{B}^{x})|x\rangle ~.}
We can interpret
E
{\displaystyle {\mathcal {E}}}
as a guessing strategy and this then reduces to the interpretation given above where an adversary wants to find the string
x
{\displaystyle x}
given access to quantum information via system
B
{\displaystyle B}
.
See also
von Neumann entropy
Generalized relative entropy
max-entropy
References
Kata Kunci Pencarian:
- The Book of Us: Entropy
- Day6
- Venus
- Wonpil
- The Best Day2
- The Book of Us: Gravity
- Min-entropy
- Rényi entropy
- Leftover hash lemma
- Information theory
- Entropy (classical thermodynamics)
- Extractor (mathematics)
- Quantum information
- Randomness merger
- Full entropy
- HKDF
