arXiv:1508.06624v2 [quant-ph] 19 Jul 2016

Discriminating quantum states: the multiple
Chernoff distance
Ke Li
IBM T.J. Watson Research Center
and Massachusetts Institute of Technology

Abstract
We consider the problem of testing multiple quantum hypotheses
⊗n
{ρ⊗n
1 , . . . , ρr }, where an arbitrary prior distribution is given and each
of the r hypotheses is n copies of a quantum state. It is known that the
minimal average error probability Pe decays exponentially to zero, that
is, Pe = exp{−ξn + o(n)}. However, this error exponent ξ is generally
unknown, except for the case that r = 2.
In this paper, we solve the long-standing open problem of identifying the above error exponent, by proving Nussbaum and Szkola’s
conjecture that ξ = mini6=j C(ρi , ρj ). The right-hand side of this equality is called the multiple quantum Chernoﬀ distance, and C(ρi , ρj ) :=
} has been previously identiﬁed as the optimax0≤s≤1 {− log Tr ρsi ρ1−s
j
mal error exponent for testing two hypotheses, ρ⊗n
versus ρ⊗n
i
j .
The main ingredient of our proof is a new upper bound for the
average error probability, for testing an ensemble of ﬁnite-dimensional,
but otherwise general, quantum states. This upper bound, up to a
states-dependent factor, matches the multiple-state generalization of
Nussbaum and Szkola’s lower bound. Specialized to the case r = 2, we
give an alternative proof to the achievability of the binary-hypothesis
Chernoﬀ distance, which was originally proved by Audenaert et al.

Email: carl.ke.lee@gmail.com
Supported by NSF grants CCF-1110941 and CCF-1111382.
AMS 2000 subject classifications. 62P35, 62G10.
Key words and phrases. quantum state discrimination, quantum hypothesis testing,
error exponent, quantum Chernoﬀ distance, multiple hypotheses

1

1

Introduction

A basic problem in information theory and statistics, is to test a system
that may be prepared in one of r random states. Treated in the framework
of quantum mechanics, the testing is performed via quantum measurement,
and the physical states are described by density matrices ω1 , ω2 , . . . , ωr ,
namely, positive semideﬁnite Hermitian matrices of trace 1. It is a notable
fact that, when ωi ’s commute, the problem reduces to classical statistical
testing, among r probability distributions that are given by the arrays of
eigenvalues of each of the density matrices. However, the generally noncommutative feature makes quantum statistics much richer than its classical
counterpart.
Our main focus in the current paper will be on the asymptotic setting.
Let the tensor product state ρ⊗n denotes n independent copies of ρ, in
analogy to the probability distribution of i.i.d. random variables. We are
interested in the asymptotic behavior of the average error Pe , in discrimi⊗n
nating a set of quantum states {ρ⊗n
1 , . . . , ρr }, when an arbitrary prior that
is independent of n is given. Parthasarathy showed that Pe decays exponentially, that is, Pe = exp{−ξn+o(n)} [34]. However, to date the optimal error
exponent ξ, as a functional of the states ρ1 , . . . , ρr , is generally unknown.
Signiﬁcant achievements have been made for the case of testing two
quantum hypotheses (r = 2). In two breakthrough papers, [1] and [29], it
has been established that the optimal error exponent in discriminating ρ⊗n
1
,
equals
the
quantum
Chernoﬀ
distance
and ρ⊗n
2
C(ρ1 , ρ2 ) := max {− log Tr ρs1 ρ1−s
2 }.
0≤s≤1

Audenaert et al in [1] solved the achievability part, in the meantime Nussbaum and Szkola in [29] proved the optimality part. This provides the
quantum generalization of the Chernoﬀ information as the optimal error
exponent in classical hypotheses testing [9]; see also [10].
The solution for the general cases r > 2 is still lacking and it does
not follow from the binary case directly. The optimal tests, as analogs of
the classical maximum likelihood decision rule, have been formulated in the
1970s. For discriminating two states it has an explicit expression known as
the Holevo?Helstrom test [16, 21], and indeed, the proof in [1] relies on a
nontrivial application of this Holevo?Helstrom test. In contrast, for discriminating multiple quantum states the corresponding optimal measurement can
only be formulated in a very complicated, implicit way [20, 41]. Such a situation illustrates the diﬃculty in dealing with the asymptotic error exponent,
2

for the multiple case r > 2. Intuitively, competitions among pairs make the
problem complicated.
Nussbaum and Szkola introduced the multiple quantum Chernoﬀ distance
C(ρ1 , . . . , ρr ) := min C(ρi , ρj ),
(i,j):i6=j

and conjectured that it is the optimal asymptotic error exponent, in discrim⊗n [30, 31, 32]. This is in full analogy to
inating quantum states ρ⊗n
1 , . . . , ρr
the existing results in classical statistical hypothesis testing [23, 36, 37, 39].
Signiﬁcant progress has been made towards proving this conjecture. Besides
the case of commuting states which reduces to the classical situation, it has
been proven to be true in several interesting special cases. These include
when the supporting spaces of the states ρ1 , . . . , ρr are disjoint [32], and
when one pair of the states is substantially closer than the other pairs, in
Chernoﬀ distance [28, 2]. In general, Nussbaum and Szkola showed that the
optimal error exponent ξ in testing multiple quantum hypotheses, satisﬁes
C/3 ≤ ξ ≤ C [32], and Audenaert and Mosonyi recently strengthened this
bound, showing that C/2 ≤ ξ ≤ C [2].
In this paper, we shall prove the aforementioned conjecture, that is, we
show that the long-sought error exponent in asymptotic quantum (multiple)
state discrimination, is given by the (multiple) quantum Chernoﬀ distance.
Besides, as a main ingredient of the proof we derive a new upper bound
for the optimal average error probability, for discriminating a set of ﬁnitedimensional, but otherwise general, quantum states. This one-shot upper
bound has the advantage that, up to a states-dependent factor, it coincides with a multiple-state generalization of Nussbaum and Szkola’s lower
bound [29].
Before concluding this section, we review the relevant literature. Asymptotics of statistical hypothesis testing is an important topic in statistics and
information theory, and is especially useful in identifying basic information
quantities. We refer the interested readers for a partial list of classical results to [6, 9, 10, 13, 14, 19, 23], and quantum results to [1, 3, 5, 8, 18,
24, 27, 29, 33, 38]. The optimal or approximately optimal average error in
quantum state discrimination, and the corresponding tests to achieve it, is
a basic problem in quantum information theory and has attracted extensive
study; see, for example, [2, 4, 15, 16, 20, 21, 22, 35, 40, 41].
The remainder of this paper is organized as follows. After introducing
some basic notations, concepts and the relevant aspects of the quantum
formalism in Section 2, we present the main results in Section 3. Section 4
is dedicated to the proofs. At last, in Section 5, we conclude the paper with
3

some discussion and open questions.

2

Notation and preliminaries

Let B(H) denote the set of linear operators on a complex, ﬁnite-dimensional
Hilbert space H. Let P(H) ⊂ B(H) be the set of positive semideﬁnite
matrices, and D(H) := {ω : ω ∈ P(H), and Tr ω = 1} is the set of density
matrices. We say a matrix A ≥ 0 if A ∈ P(H), and A ≥ B if A−B ≥ 0. The
dimension of the Hilbert space H is denoted as |H|. 11 denotes the identity
matrix. We use the Dirac notation |vi ∈ H to denote a unit vector, hv| its
conjugate transpose, and hv|wi the inner product. A Hermitian
matrix X
P
can be written in the spectral decomposition form: X = i λi Qi , where λi ’s
satisfying λP
i 6= λj for i 6= j are the eigenvalues, and Qi ’s satisfying Qi Qj =
δij Qi and i Qi = 11 are the orthogonal projectors onto the eigenspaces.
supp(X) is the supporting space of X and
Pis spanned by all the eigenvectors
with non-zero eigenvalues, {X > 0} := i:λi >0 Qi represents the projector
onto the positive supporting space of X, and Ω(X) := |{λi }i | denotes the
number of eigenspaces, or distinct eigenvalues. For a subspace S ⊂ H,
proj(S) is the projector onto S. The sum of two subspaces S1 , S2 ⊂ H, is
deﬁned as S1 + S2 := {u + v|u ∈ S1 , v ∈ S2 }. When we say the overlap
between two subspaces S1 and S2 , we mean the maximal overlap between
two unit vectors from each of them: max{|hv|wi| : |vi ∈ S1 , |wi ∈ S2 }.
We brieﬂy review some aspects of the quantum formalism, relevant in
this paper. Every physical system is associated with a complex Hilbert
space, which is called the state space. The states of a system are described
by density matrices. Pure states are of particular interest, and are represented by rank-one projectors, or simply the corresponding unit vectors.
Throughout this paper, we are concerned with quantum states of a ﬁnite
system, associated with a ﬁnite-dimensional Hilbert space. A density matrix ω can
Pbe decomposed as the sum of an ensemble of pure states, that
is, ω =
i pi |ψi ihψi |, with {pi } a probability distribution. An intuitive
understanding is that pure states represent “deterministic events”, and a
density matrix is the quantum analogue of a probability distribution over
these events. However, note that this decomposition is not unique, and
non-orthogonal pure states are not perfectly distinguishable.
The procedure of detecting the state of a quantum system is called quantum measurement, which, in the most general form, is formulated as positive
operator-valued measure (POVM), that
Pis, M = {Mi }i , with the POVM elements satisfying 0 ≤ Mi ≤ 11 and
i Mi = 11. When performing the
4

measurement on a system in the state ω, we get outcome i with probability
Tr(ωMi ). Projective measurements, or von Neumann measurements, are
special situations of POVMs, where all the POVM elements are orthogonal
projectors: Mi Mj = δij Mi , with δij the Kronecker delta function.
Suppose a physical system, also called an information source, is in one of
a ﬁnite set of hypothesized states {ω1 , . . . , ωr }, with a given prior {p1 , . . . , pr }.
For convenience, we denote them as a normalized ensemble {A1 := p1 ω1 , . . . , Ar :=
pr ωr }. To determine the true state, we make a POVM measurement {M1 , . . . , Mr },
and infer that it is in the state ωi if we get outcome i. The average (Bayesian)
error probability is
Pe ({A1 , . . . , Ar }; {M1 , . . . , Mr }) :=

r
X

Tr Ai (11 − Mi ).

(1)

i=1

Minimized over all possible measurements, this gives the optimal error probability
(r
)
X
∗
Pe ({A1 , . . . , Ar }) := min
Tr Ai (11 − Mi ) : POVM {M1 , . . . , Mr } . (2)
i=1

We note here that the deﬁnitions (1) and (2) apply, as well, to a nonnormalized ensemble of quantum states {A1 , . . . , Ar } which only satisﬁes
the constraint (∀i) Ai ≥ 0. In this case, Pe and Pe∗ may not have a clear
meaning but sometimes can be useful.
In the asymptotic setting where ωi is replaced by the tensor product
∗
state ρ⊗n
i , we are interested in the behavior of the optimal error Pe , as
n → ∞. An important quantity characterizing this asymptotic behavior, is
the rate of exponential decay, or simply error exponent
lim inf
n→∞

3


−1
⊗n
log Pe∗ {p1 ρ⊗n
1 , . . . , p r ρr } .
n

Results

Our main result is the following Theorem 1. Recall that, for the case r = 2
of testing two hypotheses, it has been proven nearly a decade ago in 2006;
see [1] and [29].
Theorem 1. Let {ρ1 , . . . , ρr } be a finite set of quantum states on a finitedimensional Hilbert space H. Then the asymptotic error exponent for testing

5

⊗n
{ρ⊗n
1 , . . . , ρr }, for an arbitrary prior {p1 , . . . , pr }, is given by the multiple
quantum Chernoff distance:
o
n

−1
⊗n
s 1−s
lim
. (3)
log Pe∗ {p1 ρ⊗n
,
.
.
.
,
p
ρ
}
=
min
max
−
log
Tr
ρ
ρ
r r
i j
1
n→∞ n
(i,j):i6=j 0≤s≤1

The optimality part, that is, the left-hand side of equation (3) being
upper bounded by the right-hand side, follows easily from the optimality of
the binary case r = 2 [29]; see the argument in [31]. Roughly speaking, this
is because, discriminating an arbitrary pair within a set of quantum states is
easier than discriminating all of them. On the other hand, the achievability
part is the main diﬃculty in proving Theorem 1. In [1], Audenaert et al em-
⊗n
⊗n
⊗n
ployed the Holevo?Helstrom tests {ρ⊗n
1 − ρ2 > 0}, 11 − {ρ1 − ρ2 > 0}
⊗n
to achieve the binary Chernoﬀ distance in testing ρ⊗n
1 versus ρ2 . However,
to date we do not have a way to generalize the method of Audenaert et al to
deal with the r > 2 cases, even though there is the multiple generalization
of the Holevo?Helstrom tests [20, 41]; see discussions in [32] and [2] on this
issue. Here, using a conceptually diﬀerent method, we derive a new upper
bound for the optimal error probability of equation (2). This one-shot error bound, as stated in Theorem 2, works for testing any ﬁnite number of
ﬁnite-dimensional quantum states, and when applied in the asymptotics for
i.i.d. states, accomplishes the achievability part of Theorem 1.
Our method is inspired by the previous work of Nussbaum and Szkola [32].
It is shown in [32] that if the supporting spaces of the hypothetic states
ρ1 , . . . , ρr are pairwise disjoint (this means that the supporting spaces of
⊗n
ρ⊗n
1 , . . . , ρr are asymptotically highly orthogonal), then the Gram-Schmidt
orthonormalization can be employed to construct a good measurement,
which achieves the error exponent of Theorem 1. Here to prove Theorem 1
for general hypothetic states, we ﬁnd a way to remove a subspace from
⊗n
each eigenspace of the states ρ⊗n
1 , . . . , ρr . Then we show that, on the one
hand this removal will cause an error that matches the right-hand side of
equation (3) in the exponent, and on the other hand the pairwise overlaps
⊗n are made suﬃciently small,
between the supporting spaces of ρ⊗n
1 , . . . , ρr
such that the Gram-Schmidt orthonormalization method is applicable. For
the sake of generality, we will actually realize these ideas for general nonnegative matrices A1 , . . . , Ar , yielding the following Theorem 2.
Theorem 2. Let A1 , . . . , Ar ∈ P(H) be nonnegative matrices
on a finiteP i
λik Qik be the
dimensional Hilbert space H. For all 1 ≤ i ≤ r, let Ai = Tk=1
spectral decomposition of Ai , and write T := max{T1 , . . . , Tr }. There exists
6

a function f (r, T ) such that
Pe∗ ({A1 , . . . , Ar }) ≤ f (r, T )

X X

min{λik , λjℓ } Tr Qik Qjℓ

(4)

(i,j):i<j k,ℓ

and we have f (r, T ) < 10(r−1)2 T 2 .
Our upper bound of equation (4), up to an r- and T -dependent factor, coincides with the multiple-state generalization of the lower bound of
Nussbaum and Szkola [29]. To see this, using the result in [35], we easily
generalize the bound obtained in [29] and get
X X
1
Pe∗ ({A1 , . . . , Ar }) ≥
min{λik , λjℓ } Tr Qik Qjℓ .
(5)
2(r − 1)
(i,j):i<j k,ℓ

In the case that r = 2, it is interesting to compare equation (4) with the
upper bound of Audenaert et al [1]:
Pe∗ ({A1 , A2 }) ≤ min Tr As1 A1−s
2 .
0≤s≤1

While we see that our bound is stronger, in the sense that
X
min{λ1k , λ2ℓ } Tr Q1k Q2ℓ ≤ min Tr As1 A21−s
0≤s≤1

k,ℓ

(6)

(7)

is always true, we also notice that it is weaker because it has an additional
multiplier depending on the number of eigenspaces of the two states.

4

Proofs

This section is dedicated to the proofs of Theorem 1 and Theorem 2. At ﬁrst,
we present a deﬁnition and some necessary lemmas in Section 4.1. Then we
construct the measurement for discriminating multiple quantum states in
Section 4.2. Using this measurement, we prove Theorem 2 in section 4.3.
At last, built on Theorem 2, Theorem 1 will be proven in Section 4.4.

4.1

Technical preliminaries

We begin with the deﬁnition of the operation “ǫ-subtraction” between two
projectors or two subspaces. This operation, say, for two subspaces S1 and
S2 , reduces the overlap between them by removing a subspace from S1 , actually, in the most eﬃcient way. It will constitute a key step in the construction
of measurement.
7

Definition 3 (ǫ-subtraction). Let S1 , S2 be two subspaces of a Hilbert space
H. Let P1 , P2 ∈ P(H) be the projectors onto S1 and
PS2 , respectively. Write
P1 P2 P1 in the spectral decomposition,
P
P
P
=
1 2 1
x λx Qx , with Qx being
P
orthogonal projectors and x Qx = 11H . For 0 ≤ ǫ ≤ 1, the ǫ-subtraction of
P2 from P1 is defined as
X
P1 ⊖ǫ P2 := P1 −
Qx .
(8)
x:λx ≥ǫ2 ,λx 6=0

Accordingly, the ǫ-subtraction between subspaces is defined as
S1 ⊖ǫ S2 := supp(P1 ⊖ǫ P2 ).

(9)

Note that in equation (8) the constraint λx 6= 0 makes sense only when
ǫ = 0. The following lemma states some basic properties of the ǫ-subtraction.
Lemma 4. Let S1 , S2 be two subspaces of a Hilbert space H. Let P1 , P2 ∈
P(H) be the projectors onto S1 and S2 , respectively. Write S1′ = S1 ⊖ǫ S2 ,
and P1′ = P1 ⊖ǫ P2 . Then
1. S1′ is a subspace of S1 ; P1′ is a projector, and 0 ≤ P1′ ≤ P1 .
2. S1′ has bounded overlap with S2 :
max

|v1 i∈S1′ ,|v2 i∈S2

|hv1 |v2 i| ≤ ǫ,

where the maximization is over unit vectors hv1 |v1 i = hv2 |v2 i = 1.
3. For 0 < ǫ ≤ 1, we have
Tr(P1 − P1′ ) ≤

1
Tr P1 P2 .
ǫ2

P
Proof. Let P1 P2 P1 = x λx Qx be the spectral decomposition of P1 P2 P1 ,
with 0 ≤ λx ≤ 1.
1. Obviously, supp(P1 P2 P1 ) ⊆ S1 . Thus the following three projectors
satisfy
X
X
Qx ≤
Qx ≤ P1 .
(10)
x:λx ≥ǫ2 ,λx 6=0

x:λx 6=0

This, together with Deﬁnition 3, implies that P1′ is a projector and satisﬁes
0 ≤ P1′ ≤ P1 . The fact that S1′ is a subspace of S1 , follows directly.

8

2. It follows from equation (10) and Deﬁnition 3 that we can write S1′ as


M
\ 
M
supp(Qx )|λx =0 S1 .
supp(Qx )
S1′ = 
x:0<λx <ǫ2

That is to say, S1′ is the direct sum of the eigenspaces of P1 P2 P1 with
corresponding eigenvalues in the interval (0, ǫ2 ), together with a subspace of
the kernel of P1 P2 P1 . So, for any unit vectors |v1 i ∈ S1′ , |v2 i ∈ S2 ,
p
p
p
|hv1 |v2 i| = hv1 |v2 ihv2 |v1 i ≤ hv1 |P2 |v1 i = hv1 |P1 P2 P1 |v1 i ≤ ǫ.
3. This inequality can be veriﬁed as follows.
X
Tr(P1 − P1′ ) = Tr
Qx
x:λx ≥ǫ2

≤ Tr

X λx
X λx
Q
≤
Tr
Qx
x
ǫ2
ǫ2
2
x

x:λx ≥ǫ

=

1
1
Tr P1 P2 P1 = 2 Tr P1 P2 .
ǫ2
ǫ

⊔
⊓
Lemma 5 and Lemma 6 below are basic results for subspaces of an inner
product space.
Lemma 5. Let V, WL
be subspaces of a Hilbert
L 2 space H, and have direct-sum
1
decompositions V = Ti=1
Vi and W = Tj=1
Wj . Suppose we have
max

|vi∈Vi ,|wi∈Wj

|hv|wi| ≤ δ,

for all 1 ≤ i ≤ T1 , 1 ≤ j ≤ T2 .

Then the overlap between V and W is bounded as
p
max
|hv|wi| ≤ T1 T2 δ.
|vi∈V,|wi∈W

Proof. Let |vi ∈ V and
P
P |wi ∈ W be any two unit vectors. Write
P |vi2 =
α
|v
i
and
|wi
=
β
|w
i,
with
|v
i
∈
V
,
|w
i
∈
W
and
i
i
j
j
i
i
j
j
i
j
i |αi | =

9

P

j

|βj |2 = 1. Making use of the Cauchy-Schwarz inequality, we have

|hv|wi| =

X

αi βj hvi |wj i

i,j

≤

X

|αi | · |βj |δ

i,j

=

X

 X

|αi |
|βj | δ

i=1

≤
and this ﬁnishes the proof.

p

j=1

T1 T2 δ,
⊔
⊓

Lemma 6. Let S1 , S2 , . . . , Sr be subspaces of a Hilbert space, such that the
overlaps between them are bounded as
max

|vi i∈Si ,|vj i∈Sj

|hvi |vj i| ≤ δ,

1 ≤ i 6= j ≤ r.

For all 1 ≤ i ≤ r, denote the projector onto Si as Pi , and denote the projector
1
onto S = S1 + S2 + · · · + Sr as P . Suppose δ < 2(r−1)
. Then
P ≤

r
1 − (r − 1)δ X
Pi .
1 − 2(r − 1)δ

(11)

i=1

Proof. For an arbitrary unit vector |vi ∈ S, write |vi =
|vi i ∈ Si . Then
hv|

r
X
k=1

Pk |vi =

X X

αi αj hvi |Pk |vj i +

(i,k):i=k j

−

X

i

αi αj hvi |Pk |vj i +

=2hv|vi −

i=1

X

i=1 αi |vi i,

with

αi αj hvi |Pk |vj i

(j,k):j=k

XX X

αi αj hvi |Pk |vj i

k i:i6=k j:j6=k

(i,j,k):
i=j=k
r
X

X

Pr

2

|αi | +

r
X
k=1

10

(hv| − αk hvk |) Pk (|vi − αk |vk i) .

The last term is nonnegative. Besides, we have
1 =hv|vi =

r
X
i=1

≥

r
X

≥

r
X

αi αj hvi |vj i

(i,j):i6=j

X

|αi |2 −

i=1

X

|αi |2 +

|αi | · |αj | · |hvi |vj i|

(i,j):i6=j

|αi | −

i=1


|αi |2 + |αj |2 δ
2

X

2

(i,j):i6=j
r
X

= 1 − (r − 1)δ



|αi |2 .

i=1

Combining the above arguments, we get
hv|

r
X

Pk |vi ≥ 2 −

k=1

1 − 2(r − 1)δ
1
=
,
1 − (r − 1)δ
1 − (r − 1)δ

which implies equation (11).

4.2

⊔
⊓

Construction of the measurements

In the following, we will describe the procedure of constructing a family of
projective measurements {Π1 (ǫ), . . . , Πr−1 (ǫ), Πr (ǫ) + Πr+1 (ǫ)}, which will
be used to show that the right-hand side of equation (4) is an achievable
error probability.
Our construction is similar to the ones explored in [31, 32] and earlier in [21], especially, in applying the Gram-Schmidt orthonormalization
to states that are ordered according to the corresponding eigenvalues, for
formulating the projective measurements. However, our method is also signiﬁcantly diﬀerent from those of [21, 31, 32]. At ﬁrst, instead of dealing with
every eigenvector of the hypothetic states individually, we treat each of the
eigenspaces as a whole. This, for i.i.d. states of the form ω ⊗n , is reminiscent
of the method of types [11, 12], from which we indeed beneﬁt. Secondly, we
carefully remove from each of these eigenspaces a subspace, in a way such
that the perturbation to the hypothetic states is limited but the overlaps
between the supporting spaces of them become suﬃciently small. As a result, we can eﬀectively employ the Gram-Schmidt process to formulate an
approximately optimal measurement.

11

PTi
Recall that for 1 ≤ i ≤ r, Ai =
k=1 λik Qik is the spectral decomposition. Let Sik := supp(Qik ) be the eigenspaces of Ai . From now on,
we always identify the subscript “ik” with “(i,k)”. So λik , Qik and Sik are
also denoted
as λ(i,k) , Q(i,k) and S(i,k) , respectively. Deﬁne the index set
S
O := ri=1 {(i, k) : k ∈ N, 1 ≤ k ≤ Ti }. Now we arrange all the eigenvalues
{λik }(i,k)∈O in a decreasing order, and let g : {0, 1, 2, . . . , |O|} 7→ {(0, 0)}∪ O
be the bijection indicating the position of each λik in such an ordering:
λg(1) ≥ λg(2) ≥ · · · ≥ λg(|O|) ,

(12)

and g(0) = (0, 0) is introduced for later convenience. Our construction
consists of the following three steps.
Step 1: reducing the overlaps between the eigenspaces. For this purpose,
we employ the operation ǫ-subtraction to remove a subspace from each of
these eigenspaces. Let ⊖ǫ be endowed with a left associativity, that is,
A ⊖ǫ B ⊖ǫ C := (A ⊖ǫ B) ⊖ǫ C. Set Qg(0) = 0 and Sg(0) = {0}. We deﬁne
Q̃g(m) :=

(

Qg(0) , if m = 0
Qg(m) ⊖ǫ Qg(0) ⊖ǫ Qg(1) ⊖ǫ · · · ⊖ǫ Qg(m−1) , if 1 ≤ m ≤ |O|
(13)

and
(

Sg(0) , if m = 0
Sg(m) ⊖ǫ Sg(0) ⊖ǫ Sg(1) ⊖ǫ · · · ⊖ǫ Sg(m−1) , if 1 ≤ m ≤ |O|.
(14)


Note that, according to Deﬁnition 3, S̃g(m) = supp Q̃g(m) . Now we denote
S̃g(m) :=

Ãi :=

Ti
X

λik Q̃ik ,

1 ≤ i ≤ r.

(15)

k=1

We will show later that, for the purpose of the current paper, Ãi is a good
approximation of Ai .
Step 2: orthogonalizing the eigenspaces. To formulate the projective
measurement, we need to assign each of the states {Ai }i an orthogonal
subspace, for the projectors to be supported on. To do so, we treat Ãi ’s
as representives of Ai ’s, and orthogonalize the subspaces {S̃g(m) }m , using a
Gram-Schmidt process. Deﬁne Ŝg(0) := {0}, and for all 1 ≤ m ≤ |O|,




Ŝg(m) := S̃g(0) + · · · + S̃g(m) ⊖1 S̃g(0) + · · · + S̃g(m−1) ,
12

(16)

where ⊖1 is the operation “ǫ-subtraction” with ǫ = 1. Recalling Deﬁnition 3,
we easily see that the right-hand side of equation (16) is just the orthogonal complement of S̃g(0) + · · · + S̃g(m−1) , in the space S̃g(0) + · · · + S̃g(m) ,
noticing that obviously the former is a subspace of the latter. So the subspaces Ŝg(1) , . . . , Ŝg(m) are mutually orthogonal. Thus the deﬁnition in equation (16) is equivalent to
S̃g(1) + · · · + S̃g(m) =

m
M

Ŝg(t) ,

for all 1 ≤ m ≤ |O|.

(17)

t=1

Note that it is possible that Ŝg(m) = {0} for certain values of m, and in


these cases we have proj Ŝg(m) = 0.
Step 3: deﬁning the family of projective measurements. We set
Πi (ǫ) :=

Ti
X
k=1

 
proj Ŝik ,

and let
Πr+1 (ǫ) := 11 −

r
X

1 ≤ i ≤ r,

Πi (ǫ).

(18)

(19)

i=1

Here the parameter ǫ is introduced
P in step 1. By deﬁnition, Π1 (ǫ), . . . , Πr+1 (ǫ)
are orthogonal projectors and r+1
i=1 Πi (ǫ) = 11. So, they form a projective
measurement. Our strategy for testing A1 , . . . , Ar is that, if we get the measurement outcome associated with Πi (ǫ), we conclude that the state is Ai .
For the outcome associated with the extra projector Πr+1 (ǫ), we can make
any decision, or just report an error; here we simply assign it to Ar . Thus,
the family of measurements that we construct for use is
Π = {Π1 (ǫ), . . . , Πr−1 (ǫ), Πr (ǫ) + Πr+1 (ǫ)} .

4.3

(20)

Proof of the one-shot achievability bound: Theorem 2

We show that, for properly chosen ǫ ∈ [0, 1], the measurement constructed
in Section 4.2 will achieve an error probability that equals the right-hand
side of equation (4).
Proof of Theorem 2. For the ensemble of nonnegative matrices A = {A1 , . . . , Ar },

13

and the measurement Π speciﬁed in equation (20), we have
Pe (A; Π) =

r−1
X

Tr Ai (11 − Πi (ǫ)) + Tr Ar (11 − Πr (ǫ) − Πr+1 (ǫ))

i=1

≤

r
X

Tr Ai (11 − Πi (ǫ)) .

i=1

We now make use of the matrices {Ãi }, which are deﬁned in step 1 of the
measurement construction in section 4.2; cf. equantion (15). Substituting
(Ai −Ãi )+Ãi for Ai , and noticing that it is an obvious result of equations (13)
and (15) that Ai − Ãi ≥ 0, we further bound the error probability as
Pe (A; Π) ≤

r
X

Tr(Ai − Ãi ) +

r
X

Tr Ãi (11 − Πi (ǫ)) .

(21)

i=1

i=1

In the following, we will evaluate the two terms of the right-hand side of
equation (21), separately.
Invoking the spectral decomposition of Ai , and using equation (15), we
can write
r
X

Tr(Ai − Ãi ) =

Ti
r X
X

λik Tr(Qik − Q̃ik )

i=1 k=1

i=1

=

|O|
X

(22)




λg(m) Tr Qg(m) − Q̃g(m) ,

m=1

where we have used the map g, introduced in the previous section, to indicate
the subscripts. For each integer 2 ≤ m ≤ |O|, applying the third result of
Lemma 4 to the ǫ-subtraction formulas

Qg(m) ⊖ǫ Qg(0) ⊖ǫ Qg(1) ⊖ǫ · · · ⊖ǫ Qg(t−1) ⊖ǫ Qg(t) , 1 ≤ t ≤ m − 1,
we obtain



Tr Qg(m) ⊖ǫ Qg(0) ⊖ǫ · · · ⊖ǫ Qg(t−1) − Tr Qg(m) ⊖ǫ Qg(0) ⊖ǫ · · · ⊖ǫ Qg(t)

1
≤ 2 Tr Qg(m) ⊖ǫ Qg(0) ⊖ǫ · · · ⊖ǫ Qg(t−1) Qg(t)
ǫ
1
≤ 2 Tr Qg(m) Qg(t) ,
ǫ
(23)
14

where for the last inequality we have used repeatedly the ﬁrst result of
Lemma 4. Summing over t ∈ {1, 2, . . . , m − 1} at both the ﬁrst and the last
line of Equation (23), yields

Tr Qg(m) − Tr Qg(m) ⊖ǫ Qg(0) ⊖ǫ Qg(1) ⊖ǫ · · · ⊖ǫ Qg(m−1)
≤

m−1
1 X
Tr Qg(m) Qg(t) ,
ǫ2 t=1

(24)

for all 2 ≤ m ≤ |O|. Combining equations (13) and (24), and directly
verifying the case m = 1, we get


Tr Qg(m) − Q̃g(m)



m−1
1 X
≤ 2
Tr Qg(m) Qg(t) ,
ǫ t=0

1 ≤ m ≤ |O|.

(25)

Eventually, inserting equation (25) into equation (22), and changing the
subscripts, we arrive at
|O| m−1
1 XX
λg(m) Tr Qg(m) Qg(t)
Tr(Ai − Ãi ) ≤ 2
ǫ
m=1 t=0
i=1
1 X X
= 2
min{λik , λjℓ } Tr Qik Qjℓ .
ǫ

r
X

(26)

(i,j):i<j k,ℓ

Now we evaluate the second term of the right-hand side of equation (21).
Using equations (15) and (18), and employing the map g to indicate the
subscripts, we can write
!
Ti
Ti
r X
r
 
X
X
X
Tr Ãi (11 − Πi (ǫ)) =
λik Tr Q̃ik 11 −
proj Ŝiℓ
i=1 k=1

i=1

≤

Ti
r X
X
i=1 k=1

=

|O|
X

m=1

ℓ=1



 
λik Tr Q̃ik 11 − proj Ŝik




λg(m) Tr Q̃g(m) 11 − proj Ŝg(m) .

Equation (17) implies that




supp Q̃g(m) = S̃g(m) ⊆

m
M
t=1

15

Ŝg(t) .

(27)

As a result, the identity
in the third line of equation (27) can be

 matrix
Pm
replaced by t=1 proj Ŝg(t) . This gives
r
X

Tr Ãi (11 − Πi (ǫ)) ≤

|O|
X

λg(m) Tr Q̃g(m)

m=1

i=1

t=0

|O|

=

X

m−1
X



proj Ŝg(t)

λg(m) Tr Q̃g(m) proj

m=1

m−1
X

S̃g(t)

t=0

!

(28)
,

where we have Ŝg(0) = S̃g(0) = {0}, and for the equality we used equaP

m−1
tion (17). The next step is to upper bound proj
S̃
g(t) , with a
t=0
Pm−1
quantity in terms of t=0 Q̃g(t) . This can be done by directly applying
Lemma 6. However, we notice that, for each 1 ≤ i ≤ r the subspaces in
the set {S̃ik }k are orthogonal and we can make use of this fact to derive
a tighter bound. For a pair of numbers (x, y), let [(x, y)]1 denote the ﬁrst
component: [(x, y)]1 = x. We write
m−1
X

S̃g(t) =

t=0

r
X

S̃im ,

with S̃im :=

i=1

M

S̃g(t) .

(29)

t:0≤t≤m−1,
[g(t)]1 =i

We will use Lemma 5 to bound the overlaps between each pair of the subspaces {S̃im }ri=1 , and then we apply Lemma 6. Although we will only get a
slightly better bound, compared to applying Lemma 6 directly, it is possible
to make this improvement bigger by strengthening the result of Lemma 6.
Now, due to Lemma 4 and the deﬁnition of S̃g(t) [cf. equation (14)], we can
bound
hv|v ′ i ≤ ǫ, 0 ≤ t′ < t ≤ |O|.
max
|vi∈S̃g(t) ,|v′ i∈Sg(t′ )

Since S̃g(t′ ) is a subspace of Sg(t′ ) , it follows that
hv|v ′ i ≤ ǫ,

max

0 ≤ t 6= t′ ≤ |O|.

|vi∈S̃g(t) ,|v′ i∈S̃g(t′ )

Recalling the spectral decomposition of each Ai , we notice that the direct
sum in equation (29) has at most Ti terms. So, an application of Lemma 5
gives us that, for every 1 ≤ m ≤ |O|,
max

|vi∈S̃im ,|wi∈S̃jm

|hv|wi| ≤ T ǫ,

16

1 ≤ i 6= j ≤ r,

(30)

where T = max{T1 , . . . , Tr }. Equation (30) allows us to apply Lemma 6 and
obtain
!
m−1
m−1
X
1−(r−1)T ǫ X
Q̃ , 1 ≤ m ≤ |O|,
(31)
proj
S̃g(t) ≤
1−2(r−1)T ǫ t=0 g(t)
t=0


for which we have also used equation (29) and the fact that proj S̃g(t) =
Q̃g(t) . Note that here the condition on δ in Lemma 6 is satisﬁed for our later
choice of ǫ. Now, inserting equation (31) into equation (28), and making use
of the relation Q̃g(m) ≤ Qg(m) for all 0 ≤ m ≤ |O|, we arrive at
r
X
i=1

|O|
m−1
X
1−(r−1)T ǫ X
Tr Ãi (11 − Πi (ǫ)) ≤
λg(m)
Tr Qg(m) Qg(t) ,
1−2(r−1)T ǫ m=1
t=0

which translates to
r
X
1−(r−1)T ǫ
Tr Ãi (11 − Πi (ǫ)) ≤
1−2(r−1)T ǫ
i=1

X X

(32)

min{λik , λjℓ } Tr Qik Qjℓ .

(i,j):i<j k,ℓ

(33)
Eventually, inserting equations (26) and (33) into equation (21)and set2
lets us obtain equation (4), with
ting ǫ = 5(r−1)T
f (r, T ) =

25(r − 1)2 T 2
+ 3 < 10(r−1)2 T 2 ,
4

and we are done.

4.4

⊔
⊓

Proof of the error exponent

We are now ready for the proof of Theorem 1.
Proof of Theorem 1. For the achievability part, we use Theorem 2. Let
d = |H| be the dimension of the associated Hilbert space of the states
ρ1 , . . . , ρr . The type counting lemma (see, e.g. [10], Theorem 12.1.1) provides
⊗n satisﬁes
that the number of eigenspaces of the states ρ⊗n
1 , . . . , ρr

Ω ρ⊗n
≤ (n + 1)d , ∀ 1 ≤ i ≤ r.
i
P (n) (n)
For all 1 ≤ i ≤ r, let ρ⊗n
= k λik Qik be written in the spectral decomi
position. Theorem 2 gives

⊗n
Pe∗ {p1 ρ⊗n
1 , . . . , pr ρr }
X X
(n)
(n)
(n) (n)
(34)
≤10(r−1)2 (n + 1)2d
min{pi λ , pj λ } Tr Q Q .
ik

(i,j):i<j k,ℓ

17

jℓ

ik

jℓ

Furthermore, for any 1 ≤ i < j ≤ r, we have
X
(n)
(n)
(n) (n)
min{pi λik , pj λjℓ } Tr Qik Qjℓ
k,ℓ

≤ max{pi , pj } min

0≤s≤1

= max{pi , pj } min

0≤s≤1

X
k,ℓ

(n) s

λik

(n) 1−s

λjℓ

(n)

(n)

Tr Qik Qjℓ

(35)

n

Tr ρsi ρj1−s .

Inserting equation (35) into equation (34), together with some basic calculus,
results in

⊗n
Pe∗ {p1 ρ⊗n
1 , . . . , p r ρr }
n

(36)
,
≤10(r−1)2 Cr2 (n + 1)2d max{p1 , . . . , pr } max min Tr ρsi ρ1−s
j
(i,j):i6=j 0≤s≤1

Where Cr2 = r(r−1)
is a binomial coeﬃcient. From equation (36) we easily
2
derive
o
n

−1
s 1−s
⊗n
.
log Pe∗ {p1 ρ⊗n
−
log
Tr
ρ
ρ
,
.
.
.
,
p
ρ
}
≥
min
max
lim inf
r
i j
r
1
n→∞ n
(i,j):i6=j 0≤s≤1
(37)
On the other hand, the optimality part, that
lim sup
n→∞

o
n

−1
⊗n
s 1−s
,
log Pe∗ {p1 ρ⊗n
,
.
.
.
,
p
ρ
}
≤
min
max
−
log
Tr
ρ
ρ
r
i j
r
1
n
(i,j):i6=j 0≤s≤1
(38)

is a straightforward generalization of the r = 2 situation [29]; see [31] for the
proof. Alternatively, one can start with the one-shot bound of equation (5).
Then we use the fact that equation (7), when applied to the i.i.d. states and
acted by “ −1
n log” at both sides, becomes asymptotically an equality. Note
that this is still based on the results of Nussbaum and Szkola in [29].
At last, equation (37) and equation (38) together are obviously equivalent
to equation (3) and we conclude the proof of Theorem 1.
⊔
⊓

5

Discussion

By explicitly constructing a family of asymptotically optimal measurements
⊗n
for testing quantum hypotheses {ρ⊗n
1 , . . . , ρr }, we have proven the achievability of the multiple quantum Chernoﬀ distance, and eventually established that this is the optimal rate exponent at which the error decays.
18

In the nonasymptotic setting, we have obtained a new upper bound for
the optimal average error probability in discriminating a set of density matrices {A1 , . . . , Ar }, which satisfy Ai ≥ 0 and are not necessarily normalized.
Yuen, Kennedy and Lax [41] derived a formula for the optimal average error:
X
Pe∗ (A1 , . . . , Ar ) = Tr
Ai − min {Tr X : X ≥ Ai , i = 1, . . . , r} ; (39)
i

see also [22] and [2] for alternative formulations. However, the fact that
equation (39) involves an optimization problem itself, makes it diﬃcult to
apply this formula directly. Our upper bound stated in Theorem 2, though
looser compared to equation (39), has an explicit form and there is a dual
lower bound as shown in equation (5). We thus hope that it will ﬁnd more
applications.
We wonder whether the states-dependent factor f (r, T ) can be replaced
by a constant, or at least can be improved such that it only depends on r
(see also a similar conjecture made in [2]). While it is possible that we can
improve Lemma 6 to give a better bound on f (r, T ), we do not think that
this can remove the dependence on T and r. In this direction, the pretty
good measurement [4, 15] and its variant [40], both of which achieve an error
probability lying between Pe∗ and 2Pe∗ , may be useful tools to try. In fact,
in Theorem 2 the dependence of our bound on T is not necessary: using
the argument in [38], we can convert it into a dependence on the relation
between the maximal and the minimal eigenvalues of the hypothetic states;
see Proposition 7 below and the proof in the Appendix. This conversion is
useful when the spectrum of each Ai is suﬃciently ﬂat, no matter how big
the number of their eigenspaces is.
Proposition 7. For all i = 1, . . . , r, let λmax (Ai ) be the maximal eigenvalue,
and λmin (Ai ) be the minimal nonzero eigenvalue of Ai . Denote




2λmax (Ar )
2λmax (A1 )
, . . . , log2
.
L := max log2
λmin (A1 )
λmin (Ar )
Then, in Theorem 2 the states-dependent factor f (r, T ) can be replaced by
h(r, L) := 40(r − 1)2 L2 .
Another interesting question is how our method can be extended to deal
with the problem of discriminating correlated states, where each of the hy(n)
(n)
pothetic states ρ1 , . . . , ρr can be correlated among the n subsystems. The
upper bound stated in Theorem 2 (also in Proposition 7 for an alternative
states-dependent factor), together with the dual lower bound of equation (5),
19

can be used to analyse the asymptotic behavior of the error. This method
may identify the optimal error exponent which can be quite diﬀerent from
reasonable generalizations of the Chernoﬀ distance, in contrast to previous
works which under certain conditions yield the mean quantum Chernoﬀ distance; see, for example, [17, 25, 26, 30]. However, the main diﬃculty we will
confront in this method is to characterize the spectral decomposition of the
correlated states when n goes to inﬁnity. At last, a particularly interesting
problem in this setting, proposed by Audenaert
and Mosonyi [2], is testing
P
⊗n
⊗n
composite hypotheses, say, ρ versus i qi σi . Here the sum may be replaced by an integral. See also discussions in [5] and [7] of this problem
in the asymmetric case of Stein’s lemma. While our method for proving
Theorem 1 does shed some light on this problem, it seems that a complete
solution needs further ideas.
Acknowledgments. The author is grateful to Charles Bennett, Aram
Harrow, Graeme Smith, John Smolin and Andreas Winter, for very helpful discussions and comments. He further thanks Fernando Brandão, Milán
Mosonyi, Marco Tomamichel and the anonymous referees for their enthusiasm and/or helpful comments.
Appendix A: proof of Proposition 7
P
Proof. For an arbitrary nonnegative matrix A = k λk Qk written in the
spectral decomposition form, deﬁne the modiﬁed version of A as
A′ =

M
X

2m λmin (A)

m=1

j

where M := log2

2λmax (A)
λmin (A)

k

X

Qk ,

k:λk ∈Om

= Ω(A′ ) and Om := {λk : 2m−1 λmin (A) ≤ λk <

2m λmin (A)}. Then we have A ≤ A′ ≤ 2A, and also A and A′ commute. Now
for A1 , . . . , Ar , we deﬁne
A′1 , . . . , Ak′r in a similarly way as A′ was deﬁned.
j

Obviously, Ω(A′i ) = log2

2λmax (Ai )
λmin (Ai )

. Applying Theorem 2, we can evaluate


Pe∗ {A′1 , . . . , A′r }
X X
≤10(r − 1)2 L2 · 4
min{λik , λjℓ } Tr Qik Qjℓ .

(40)

(i,j):i<j k,ℓ

On the other hand, since for all i, Ai ≤ A′i , we have by the deﬁnition of Pe∗
that

Pe∗ ({A1 , . . . , Ar }) ≤ Pe∗ {A′1 , . . . , A′r } .
(41)

Equations (40) and (41) together lead to the advertised result.
20

⊔
⊓

References
[1] Audenaert, K. M. R., Casamiglia, J., Munoz-Tapia, R.,
Bagan, E., Masanes, Ll., Acin, A. and Verstraete, F. (2007).
Discriminating states: the quantum Chernoﬀ bound. Phys. Rev. Lett.
98 160501. arXiv:quant-ph/0610027.
[2] Audenaert, K. M. R. and Mosonyi, M. (2014). Upper bounds on
the error probabilities and asymptotic error exponents in quantum multiple state discrimination. J. Math. Phys. 55 102201.
[3] Audenaert, K. M. R., Nussbaum, M., Szkola, A. and Verstraete, F. (2008). Asymptotic error rates in quantum hypothesis
testing. Comm. Math. Phys. 279 (1) 251–283.
[4] Barnum, H. and Knill, E. (2002). Reversing quantum dynamics with
near-optimal quantum and classical ﬁdelity. J. Math. Phys. 43 2097–
2106.
[5] Bjelaković, I., Deuschel, J. D., Krüger, T., Seiler, R.,
Siegmund-Schultze, Ra. and Szkola, A. (2005). A quantum version of Sanov’s theorem. Comm. Math. Phys. 260 (3) 659–671.
[6] Blahut, R. E. (1974). Hypothesis testing and information theory.
IEEE Trans. Inf. Theory 20 (4) 405–417.
[7] Brandão, F. G. S. L., Harrow, A. W., Oppenheim, J. and
Strelchuk, S. (2015). Quantum conditional mutual information,
reconstructed states, and state redistribution. Phys. Rev. Lett. 115
050501.
[8] Brandão, F. G. S. L. and Plenio, M. B. (2010). A generalization
of quantum Stein’s lemma. Comm. Math. Phys. 295 (3) 791–828.
[9] Chernoff, H. (1952). A measure of asymptotic eﬃciency for tests of
a hypothesis based on the sum of observations. Ann. Math. Statist. 23
(4) 493–507.
[10] Cover, T. M. and Thomas, J. A. (1991). Elements of Information
Theory. Wiley Series in Telecommunications, John Wiley & Sons, New
York.
[11] Csiszár, I. (1998). The method of types. IEEE Trans. Inf. Theory 44
(6) 2505–2523.
21

[12] Csiszár, I. and Körner, J. (1981). Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic Press, New York.
[13] Csiszár, I. and Longo, G. (1971). On the error exponent for source
coding and for testing simple statistical hypotheses. Studia Sci. Math.
Hungarica 6 181–191.
[14] Han, T. S. and Kobayashi, K. (1989). The strong converse theorem
for hypothesis testing. IEEE Trans. Inf. Theory 35 (1) 178–180.
[15] Hausladen, P. and Wootters, W. (1994). A “pretty good” measurement for disdinguishing quantum states. J. Mod. Opt. 41 2385.
[16] Helstrom, C. W. (1976). Quantum Detection and Estimation Theory.
Academic Press, New York.
[17] Hiai, F., Mosonyi, M. and Ogawa, T. (2007). Large deviations and
Chernoﬀ bound for certain correlated states on a spin chain. J. Math.
Phys. 48 123301.
[18] Hiai, F. and Petz, D. (1991). The proper formula for relative entropy
and its asymptotics in quantum probability. Comm. Math. Phys. 143
(1) 99–114.
[19] Hoeffding, W. (1965). Asymptotically optimal tests for multinomial
distributions. Ann. Math. Statist. 36 (2) 369–401.
[20] Holevo, A. S. (1973). Statistical decision theory for quantum systems.
J. Multivariate Anal. 3 337–394.
[21] Holevo, A. S. (1978). On asymptotically optimal hypothesis testing
in quantum statistics. Theor. Prob. Appl. 23 411–415.
[22] König, R., Renner, R. and Schaffner, C. (2009). The operational
meaning of min- and max-entropy. IEEE Trans. Inf. Theory 55 (9)
4337–4347.
[23] Leang, C. C. and Johnson, D. H. (1997). On the asymptotics of
M-hypothesis Bayesian detection. IEEE Trans. Inf. Theory 43 (1) 280–
282.
[24] Li, K. (2014). Second-order asymptotics for quantum hypothesis testing. Ann. Statist. 42 (1) 171–189.

22

[25] Mosonyi, M. (2009). Hypothesis testing for Gaussian states on bosonic
lattices. J. Math. Phys. 50 032105.
[26] Mosonyi, M., Hiai, F., Ogawa, T. and Fannes, M. (2008). Asymptotic distinguishability measures for shift-invariant quasi-free states of
fermionic lattice systems. J. Math. Phys. 49 072104.
[27] Mosonyi, M. and Ogawa, T. (2015). Quantum hypothesis testing and
the operational interpretation of the quantum Renyi relative entropies.
Comm. Math. Phys. 334 (3) 1617–1648.
[28] Nussbaum, M. (2013). Attainment of the multiple quantum Chernoﬀ
bound for certain ensembles of mixed states. In Proceedings of the First
International Workshop on Entangled Coherent States and Its Application to Quantum Information Science, Tamagawa University, Tokyo,
Japan 77–81.
[29] Nussbaum, M. and Szkola, A. (2009). The Chernoﬀ lower bound for
symmetric quantum hypothesis testing. Ann. Statist. 37 (2) 1040–1057.
arXiv:quant-ph/0607216.
[30] Nussbaum, M. and Szkola, A. (2010). Exponential error rates in
multiple state discrimination on a quantum spin chain. J. Math. Phys.
51 072203.
[31] Nussbaum, M. and Szkola, A. (2011). Asymptotically optimal discrimination between multiple pure quantum states. In Theory of Quantum Computation, Communication and Cryptography. 5th Conference,
TQC 2010, Leeds, UK. Lecture Notes in Computer Science 6519 1–8.
Springer, Berlin.
[32] Nussbaum, M. and Szkola, A. (2011). An asymptotic error bound for
testing multiple quantum hypotheses. Ann. Statist. 39 (6) 3211–3233.
[33] Ogawa, T. and Nagaoka, H. (2000). Strong converse and Stein’s
lemma in the quantum hypothesis testing. IEEE Trans. Inf. Theory 46
(7) 2428–2433.
[34] Parthasarathy, K. R. (2001). On consistency of the maximum likelihood method in testing multiple quantum hypotheses. In Stochastics
in Finite and Infinite Dimensions 361–377. Birkhäuser, Boston.
[35] Qiu, D. W. (2008). Minimum-error discrimination between mixed
quantum states. Phys. Rev. A 77 012328.
23

[36] Salihov, N. P. (1973). Asymptotic properties of error probabilities
of tests for distinguishing between several multinomial testing schemes.
Dokl. Akad. Nauk SSSR 209 54–57.
[37] Salihov, N. P. (1998). On a generalization of Chernoﬀ distance. Teor.
Veroyatn. Primen. 43 294–314. Translation in Theory Probab. Appl. 43
(1999) 239–255.
[38] Tomamichel, M. and Hayashi, M. (2013). A hierarchy of information
quantities for ﬁnite block length analysis of quantum tasks. IEEE Trans.
Inf. Theory 59 (11) 7693–7710.
[39] Torgersen, E. N. (1981). Measures of information based on comparison with total information and with total ignorance. Ann. Statist. 9
638–657.
[40] Tyson, J. (2009). Two-sided estimates of minimum-error distinguishability of mixed quantum states via generalized Holevo-Curlander
bounds. J. Math. Phys. 50 032106.
[41] Yuen, H. P., Kennedy, R. S. and Lax, M. (1975). Optimum testing
of multiple hypotheses in quantum detection theory. IEEE Trans. Inf.
Theory 21 (2) 125–134.

24

