POVMs are equivalent to projections for perfect state exclusion
of three pure states in three dimensions
Abel Molina
Institute for Quantum Computing and School for Computer Science, University of Waterloo
January 25, 2019
Performing perfect/conclusive quantum state
exclusion means to be able to discard with cer-
tainty at least one out of n possible quantum
state preparations by performing a measure-
ment of the resulting state. This task of state
exclusion has recently been studied at length in
[5], and it is at the heart of the celebrated PBR
thought experiment [31]. When all the prepara-
tions correspond to pure states and there are no
more of them than their common dimension, it is
an open problem whether POVMs give any ad-
ditional power for this task with respect to pro-
jective measurements. This is the case even for
the simple case of three states in three dimen-
sions, which is mentioned in [11] as unsuccess-
fully tackled. In this paper, we give an analyt-
ical proof that in this case considering POVMs
does indeed not give any additional power with
respect to projective measurements. To do so,
we first make without loss of generality some
assumptions about the structure of an optimal
POVM. The justification of these assumptions
involves arguments based on convexity, rank and
symmetry properties. We show then that any
pure states perfectly excluded by such a POVM
meet the conditions identified in [11] for perfect
exclusion by a projective measurement of three
pure states in three dimensions. We also dis-
cuss possible generalizations of our work, includ-
ing an application of Quadratically Constrained
Quadratic Programming that might be of special
interest.
1 Context and Motivation
The task of quantum state exclusion corresponds to a
setting where an agent Alice is given a quantum sys-
tem. The state of this system is chosen at random be-
tween n options {ρ
1
, . . . , ρ
n
}, with corresponding non-
zero probabilities {p
1
, . . . , p
n
}. It is unknown to Alice
which of the ρ
i
was chosen, but she does know the {ρ
i
}
and {p
i
} values characterizing the corresponding distri-
bution. Alice’s goal in the state exclusion task is to be
able to give an index j such that the state was not pre-
pared in the state ρ
j
. When Alice can achieve this with
probability 1, we will say that we have perfect state ex-
clusion. This task of state exclusion has recently been
studied at length in [5], and is at the heart of the cel-
ebrated PBR thought experiment [31], where [11] (the
article from where we take the problem we solve) is cred-
ited as the original source for the concept. The concept
of this task has also been used for proving results in the
context of quantum communication complexity [24, 30],
as well as for designing quantum signature schemes [2].
Formalizing further this concept of state exclusion, [5]
obtains the following semidefinite programming (SDP)
formulation:
minimize:
X
i
p
i
hM
i
, ρ
i
i
subject to:
X
i
M
i
= I
M
i
≥ 0.
(1)
where M
i
≥ 0 means that M
i
is positive semi-definite.
Being able to perform perfect state exclusion corre-
sponds to the optimal value of this SDP being equal to
0. Similarly, any optimal solution to the semidefinite
program corresponds to an optimal positive-operator
valued measure (POVM) for state exclusion. Note that
since we are only concerned with perfect state exclusion,
we can just ignore the p
i
in the rest of this presentation,
since whether the value of the SDP is 0 or not does not
depend on them.
Perfect exclusion of quantum states is also a meaning-
ful concept in the context of the foundations of quantum
mechanics, in particular when considering the topic of
quantum state compatibility. In that framework, one
considers several quantum states {ρ
1
, . . . , ρ
n
} as differ-
ent beliefs about the same system. Then, one can ask
whether the outcome of a measurement on the system
will disprove some of these beliefs, or they will all still
be possible. In the latter case, we say that the states
are compatible with each other. Different ways of for-
malizing this idea will lead to different definitions of
Accepted in Quantum 2019-01-14, click title to verify 1
arXiv:1702.06449v4 [quant-ph] 23 Jan 2019
quantum state compatibility. [11] proposes several for-
malizations, one of which corresponds to the impossi-
bility of performing perfect state exclusion. Since this
formalization is a generalization of previous work by
Peierls [28], they refer to it as post-Peierls (PP) com-
patibility.
In more detail, the post-Peierls compatibility of sev-
eral quantum states {ρ
1
, . . . , ρ
n
} (relative to a subset
S of all POVMs) means that for all measurements in
S, there will be at least one outcome that can be ob-
tained with non-zero probability for all of the possible
states/beliefs {ρ
1
, . . . , ρ
n
}. If we consider the negation
of this definition, we obtain that this negation corre-
sponds with the existence of a measurement in S such
that each outcome of the measurement excludes at least
one of the quantum states, which corresponds to an
agent being able to perform perfect state exclusion given
a mixture of the quantum states {ρ
1
, . . . , ρ
n
} and ac-
cess to measurements in S. When the set S of allowed
measurements corresponds to the set of all POVMs,
the corresponding compatibility criteria is called PP-
POVM compatibility. When S is restricted to the set
of projective measurements (or more precisely, the set
of measurements defined by one-dimensional orthogo-
nal projectors), [11] names the corresponding criteria
as PP-ODOP compatibility.
One can consider the case where all of the n
states/beliefs {ρ
1
, . . . , ρ
n
} are known to belong to a par-
ticular subset A of all quantum states, and ask whether
for all such tuples of n beliefs in A the PP-ODOP
and PP-POVM criteria will coincide with each other.
When this happens, we will say that in that context PP-
ODOP=PP-POVM. Note that this is equivalent to pro-
jections being optimal for perfect state exclusion within
the context of input states in A.
In [11], the authors identify a necessary and sufficient
condition for PP-ODOP incompatibility of 3 pure states
{a, b, c} in 3 dimensions (i.e. they establish a condition
for the states to be perfectly excludable via a projec-
tive measurement). This condition can be expressed in
terms of the magnitudes of their inner products, given
by |ha, bi|, |ha, ci|, |hb, ci|, and which we will denote as
j
1
, j
2
and j
3
, respectively. In particular, the condition
obtained in [11] is that 3 pure states will be PP-ODOP
incompatible whenever
j
2
1
+ j
2
2
+ j
2
3
+ 2j
1
j
2
j
3
≤ 1. (2)
We will refer to this formula as the Caves-Fuchs-
Schack inequality, after the authors of [11]. Note
that we have corrected in our presentation of this for-
mula the original strict inequality sign that they use,
following the indications in [6, 33], and we have also
merged the two conditions from the original presenta-
tion in [11] into one single condition.
When this result was introduced in [11], it was men-
tioned that the authors were not able to prove that
PP-ODOP = PP-POVM in the context of 3 pure states
in 3 dimensions, despite having numerical evidence that
this is the case. The authors also present results es-
tablishing that this is the first open case – they cite
previous work [25] showing that for two pure states in
any dimension PP-ODOP = PP-POVM, and establish
that for k > 2 pure states in 2 dimensions this will not
necessarily be the case.
We will give now an analytical proof which an-
swers the corresponding question, by showing that
PP-ODOP = PP-POVM in the context of 3 pure states
in 3 dimensions.
Our work can be seen as part of the line of work that
studies POVMs in the context of low-dimensional sys-
tems of a fixed dimension. For example, [36] and [38] re-
cently examined 2-dimensional POVMs in the contexts
of nonlocal games and quantum state discrimination, re-
spectively, while [40] looked into 4-dimensional POVMs
in the context of imposing symmetry conditions.
We conclude with a discussion about different ways in
which our work might be generalized. Of special interest
here might be our discussion on the usage of Quadrati-
cally Constrained Quadratic Programming (QCQP) to
model the n-dimensional variant of the question we
solve. This is a type of mathematical optimization for-
malism that has seen a large number of applications
in recent years, but only limited usage so far within
the context of quantum information processing. To our
knowledge, this is the first time that state exclusion of
pure states through projections is expressed through a
problem in a standard form of a mathematical optimiza-
tion framework.
In our derivation, we will use standard quantum in-
formation theory notation and vocabulary – standard
texts on the topic (e.g. [37, 39]) can be consulted for
definitions of the corresponding terms.
2 Main derivation
2.1 Restrictions that can be imposed without
loss of generality on POVMs that achieve perfect
exclusion
Our goal is to prove that for any set of 3 pure states in
3 dimensions that are perfectly excluded by a POVM,
they are also perfectly excluded by a projective mea-
surement. Following Equation (1) and our analysis of
it, we can identify the perfect exclusion of three pure
states a, b and c with obtaining an optimal value of 0 in
the following semidefinite program:
Accepted in Quantum 2019-01-14, click title to verify 2
minimize: a
∗
M
1
a + b
∗
M
2
b + c
∗
M
3
c
subject to:
X
i
M
i
= I
M
i
≥ 0,
(3)
Note that all the operators involved can be represented
as 3 × 3 matrices. It is well-known in convex optimiza-
tion that the solution to optimizing a linear function
over a non-empty compact convex set in a finite di-
mensional Hilbert space can be assumed without loss of
generality to be an extreme point of the set of feasible
solutions
1
(note that in this case, that feasible set is the
set of POVMs). Therefore, we can assume that at most
one out of the M
i
has rank greater than 1. Otherwise,
assume for the sake of contradiction that two of them
(say M
1
and M
2
) have rank at least 2, so there is a com-
mon vector u in the images of M
1
and M
2
. Then, for
small enough both {M
1
+ uu
∗
, M
2
− uu
∗
, M
3
} and
{M
1
−uu
∗
, M
2
+uu
∗
, M
3
} are POVMs, which implies
{M
1
, M
2
, M
3
} is not an extreme point of the feasible
set.
Without loss of generality, we can permute indices
so that the ranks of M
1
, M
2
, and M
3
are sorted in
non-increasing order. Also, if M
1
has rank 3 it cannot
exclude any quantum state, so it must be the case that
its rank is at most 2. Note too that if the ranks are
of the form (1, 1, 1), it is not hard to see that the con-
dition M
1
+ M
2
+ M
3
= I implies that {M
1
, M
2
, M
3
}
form a projective measurement themselves. Similarly,
in the case where the ranks are of the form (2, 1, 0),
M
1
= I − M
2
implies that M
1
and M
2
form a pro-
jective measurement (this is because for the right hand
side I −M
2
to have rank 2, M
2
must have its non-zero
eigenvalue equal to 1, which implies then the same for
the eigenvalues of I − M
2
= M
1
).
We can assume then without loss of generality that
there is an optimal POVM {M
1
, M
2
, M
3
} with ranks of
the form (2, 1, 1). We can also choose now without loss
of generality to work in a basis such that M
1
is diagonal
and it perfectly excludes a = |0 i.
We have then that M
1
will be determined by the
choice of a real diagonal vector (0, 1 −x, 1 −y), and M
2
and M
3
by a choice of complex vectors v = (v
1
, v
2
, v
3
)
and w = (w
1
, w
2
, w
3
) such that M
2
= vv
∗
and M
3
=
ww
∗
. We claim now that we can assume y = 0, v
1
6= 0,
w
1
6= 0, v
2
6= 0, w
2
6= 0, v
3
= 0, w
3
= 0 To see why,
consider the following five observations:
1
This fact follows from applications of the Krein-Milman and
Extreme Value theorems, which in their most general versions
require in fact constraints less strong than the ones we have here.
1. The condition M
1
+ M
2
+ M
3
= I corresponds to
the equations
v
1
v
∗
1
+ w
1
w
∗
1
= 1 (4)
v
2
v
∗
2
+ w
2
w
∗
2
= x (5)
v
3
v
∗
3
+ w
3
w
∗
3
= y (6)
v
1
v
∗
2
= −w
1
w
∗
2
(7)
v
1
v
∗
3
= −w
1
w
∗
3
(8)
v
2
v
∗
3
= −w
2
w
∗
3
. (9)
2. We can assume v
1
6= 0 and w
1
6= 0, as otherwise
{M
1
, M
2
, M
3
} can be trivially transformed into a
projective measurement. To see this, suppose for
example that w
1
= 0. Then, (4) implies that |v
1
| =
1, (7) that v
2
= 0, and (8) that v
3
= 0. We have
then that M
2
is diagonal, and its diagonal is equal
to (1, 0, 0). This implies that M
3
is diagonal as
well, while w
1
= 0 implies that the first term in
its diagonal is equal to 0, so we can group M
1
and
M
3
into a single operator and obtain a projective
measurement.
3. Suppose we had v
2
6= 0 and v
3
6= 0. Then, (9)
implies w
2
6= 0 and w
3
6= 0. This means we can
divide (7) by (8) and the conjugate of (9), and
obtain that
v
1
w
1
=
v
2
w
2
=
v
3
w
3
. Let λ be the value
of these ratios. Then, each of equations (7)-(9)
implies that λ = 0, which contradicts v
1
6= 0.
4. We have then that either v
2
= 0 or v
3
= 0, and
by symmetry we can assume without loss of gen-
erality that v
3
= 0. Then, w
3
= 0 as well, since
otherwise (8) would imply w
1
= 0, which we know
not to be the case. (6) implies then that y = 0.
5. If we were now to additionally impose that v
2
=
0, (7) would imply that w
2
= 0, which can only
happen when x = 0, by (5). However, in the x = 0
case we have that M
1
is a projection on |1i and |2i,
and M
2
and M
3
can be merged into a projection on
|0i, so there trivially is an optimal projection for
state exclusion, and the case is not of interest to
us. We can assume then that v
2
6= 0, and similarly
that w
2
6= 0.
We can introduce now a parameter r, which deter-
mines the distribution of the weight x between M
2
and
M
3
, and let |v
2
|
2
be equal to x
1
r+1
(r ∈ (0, ∞)). We
have then that (5) implies |w
2
|
2
= x
r
r+1
, and that (7)
and (4) imply then that |v
1
|
2
=
r
r+1
, |w
1
|
2
=
1
r+1
. The
magnitudes of each element of v and w are then com-
pletely characterized by the values of r and x.
Accepted in Quantum 2019-01-14, click title to verify 3
As for the phases of the elements of v and w, we can
assume that v
1
, w
1
∈ R without affecting the values of
M
2
and M
3
. Then, if the phase of v
2
is given by θ, (7)
implies that the phase of w
2
is given by π + θ.
We reach then our final form for what a POVM
{M
1
, M
2
, M
3
} for perfect state exclusion of 3 pure states
in 3 dimensions can be assumed to be without loss of
generality. In matrix form, it is given by
M
1
=
0 0 0
0 1 − x 0
0 0 1
, (10)
M
2
=
1
r + 1
r e
−iθ
√
rx 0
e
iθ
√
rx x 0
0 0 0
(11)
M
3
=
1
r + 1
1 −e
−iθ
√
rx 0
−e
iθ
rx rx 0
0 0 0
(12)
where 0 < x < 1, r ∈ (0, ∞), 0 ≤ θ < 2π.
2.2 Verification that any states perfectly ex-
cluded by our parametrized optimal POVM satisfy
the Caves-Fuchs-Schack inequality
We look first at the structure of the states b and c per-
fectly excluded by M
2
and M
3
, and obtain that it is
enough to consider a one-parameter family for each of
them. Let b be given by (b
1
, b
2
, b
3
), and c by (c
1
, c
2
, c
3
).
Then, our conclusion follows from the following five ob-
servations:
1. As usual, we can get rid of unphysical global
phases, and assume b
1
is a real positive number.
This is because multiplying b by a phase will not
affect the value of our semidefinite program (3),
and it will not affect either the satisfaction of the
Caves-Fuchs-Schack inequality.
2. It can be seen from (11) that the value of b
2
is com-
pletely determined by the value of b
1
by the con-
straint M
2
b = 0 (which is equivalent to b
∗
M
2
b = 0,
since M
2
is Hermitian). In particular, one obtains
that b
2
= −b
1
e
iθ
p
r
x
.
3. The fact that b has norm 1 (since it represents a
pure state) allows us now to express the magni-
tude of b
3
as a function of b
1
. In particular, the
magnitude of b
3
is given by
q
1 − b
2
1
1 +
r
x
, while
its phase, which we will denote by ϑ, can take any
value.
Note that this implies an upper bound on b
2
1
, given
by 1/
1 +
r
x
.
4. A similar analysis applies to c, and we have that
it can be parametrized by a real positive value c
1
such that 0 ≤ c
2
1
≤ 1/
1 +
1
rx
, together with the
phase γ of c
3
. In this case, the value of c
2
is given
by c
1
e
iθ
q
1
rx
, and the magnitude of c
3
is given by
q
1 − c
2
1
1 +
1
rx
.
5. We can assume now that the phases ϑ and γ of
b
3
and c
3
are selected in order to maximize the
left hand side of the Caves-Fuchs-Schack inequal-
ity. The reason we can do this is because we are
interested in proving that the Caves-Fuchs-Schack
inequality holds, so this is a worst-case scenario in
our situation.
To do so, note that j
1
= b
1
and j
2
= c
1
, so they do
not depend on the phases of b
3
and c
3
. Therefore,
maximizing the left hand side of the Caves-Fuchs-
Schack inequality will be equivalent to maximizing
j
3
= |b
∗
c|. To do that, we compute first the value
of b
∗
c, given by
e
i(γ−ϑ)
r
1 − b
2
1
1 +
r
x
s
1 − c
2
1
1 +
1
rx
+ b
1
c
1
−
1
x
b
1
c
1
. (13)
The magnitude of this expression will be the largest
possible whenever the term in the first line inter-
feres constructively with the term in the second
line. This will happen whenever the first line term
is also real, and has the same sign as b
1
c
1
(1 −1/x)
We can in fact achieve this by picking γ = ϑ + π,
since 0 < x < 1. We obtain then that in our worst-
case situation,
j
3
=
r
1 − b
2
1
1 +
r
x
s
1 − c
2
1
1 +
1
rx
+ b
1
c
1
(1/x − 1). (14)
The Caves-Fuchs-Schack inequality is expressed then in
our case as
j
2
3
+ b
2
1
+ c
2
1
+ 2j
3
b
1
c
1
≤ 1, (15)
where j
3
is given in (14), x ∈ (0, 1), r ∈ (0, ∞),
b
1
∈ [0,
q
1/
1 +
r
x
), c
1
∈ [0,
q
1/
1 +
1
rx
). We
will refer from now on to the left hand side of (15)
as f(x, r, b
1
, c
1
). If b
1
= 0 or c
1
= 0, a simple al-
gebraic manipulation of the value of j
3
gives us that
f(x, r, b
1
, c
1
) ≤ 1. Expanding the value of j
3
, we have
that f(x, r, b
1
, c
1
) is given by
Accepted in Quantum 2019-01-14, click title to verify 4
b
2
1
c
2
1
(1 + 1/x
2
− 2/x)
+
1 − b
2
1
1 +
r
x
1 − c
2
1
1 +
1
rx
+ 2b
1
c
1
(1/x − 1)
r
1 − b
2
1
1 +
r
x
s
1 − c
2
1
1 +
1
rx
+ b
2
1
+ c
2
1
+ 2b
2
1
c
2
1
(1/x − 1)
+ 2b
1
c
1
r
1 − b
2
1
1 +
r
x
s
1 − c
2
1
1 +
1
rx
= 1 − b
2
1
r
x
− c
2
1
1
rx
+ c
2
1
b
2
1
2
x
2
+
1
x
r +
1
r
+ 2b
1
c
1
1
x
r
1 − b
2
1
1 +
r
x
s
1 − c
2
1
1 +
1
rx
.
To prove that this is less or equal than 1, one can act
similarly to the standard proof for x +
1
x
≥ 2, moving
everything to one side of the inequality and writing as
a square what one obtains. In more detail, multiplying
by x and dividing by b
2
1
c
2
1
our last expression, we have
that f(x, r, b
1
, c
1
) will be less or equal than 1 whenever
2
s
1
b
2
1
−
1 +
r
x
s
1
c
2
1
−
1 +
1
rx
≤ r
1
c
2
1
+
1
r
1
b
2
1
−
2
x
+
r +
1
r
(16)
Observe now that both sides of this inequality are
positive. This is trivial for the left hand side, and fol-
lows for the right hand side from the previous obtained
upper bounds on b
1
and c
1
. If we square both sides of
this inequality and simplify the resulting expression, we
obtain
r
2
1
c
4
1
−
2
c
2
1
+ 1
+
1
r
2
1
b
4
1
−
2
b
2
1
+ 1
+2
1
c
2
1
+
1
b
2
1
−
1
b
2
1
c
2
1
− 1
≥ 0. (17)
This can be rewritten as
r
1
c
2
1
− 1
−
1
r
1
b
2
1
− 1
2
≥ 0, (18)
which is true, so we have successfully proved that a,
b and c satisfy the Caves-Fuchs-Schack inequality, and
therefore can be excluded by a projective measurement.
Note that x is not involved at all in (17), although one
can verify computationally that the difference between
the left hand side and the right hand side of (16) does
depend on x.
3 Perspectives for generalization
3.1 Usage of Quadratically Constrained
Quadratic Programs (QCQPs)
We will now discuss how to study the perfect exclu-
sion of n pure states by a projection through a collec-
tion of Quadratically Constrained Quadratic Programs
(QCQPs). For a situation with a n-dimensional com-
plex variable x and m constraints, the standard form
for such a program can be taken to be
minimize: x
∗
Gx
subject to: x
∗
C
k
x ≥ l
k
, ∀k ∈ {1, . . . , m},
(19)
where the l
k
take real values, and G and the C
k
are
n × n Hermitian matrices.
This is a type of mathematical optimization formal-
ism that has received considerable attention in recent
years, with wide-ranging applications in science and en-
gineering (see [1, 9, 19, 22] for just a few amongst many
relevant examples). There has also been a considerable
number of results about the theoretical structure of the
corresponding problems and the design of algorithms
that can solve them (see e.g. [20, 21, 26]). However,
there have only been a handful of applications so far
[4, 14, 23, 34] of the QCQP model to quantum informa-
tion processing.
In our collection of QCQPs, there will be one program
for every n-combination with repetition {s
1
, . . . , s
n
} out
of the set {w
1
, . . . , w
n
} of states to be excluded. Each
choice represents a possibility for how the states ex-
cluded after obtaining different outcomes of the projec-
tion relate to each other, and the reason why we need
to consider those choices is that two different outcomes
of the projection could plausibly lead to excluding the
same state (which in the POVM case would be handled
by grouping those two outcomes into the same one). In
particular, each of the corresponding QCQPs for perfect
state exclusion via projections formalizes the following
two ideas:
• A projection in n dimensions corresponds to a
choice of n unit vectors {v
1
, . . . , v
n
} that are pair-
wise orthogonal.
• We would like for every v
i
to be orthogonal to the
corresponding s
i
.
Accepted in Quantum 2019-01-14, click title to verify 5
These ideas are then reflected in the following QCQP:
minimize:
X
i
v
∗
i
(s
i
s
∗
i
)v
i
subject to:
v
∗
i
v
j
+ v
∗
j
v
i
= 0
∀i, j ∈ {1, . . . , n} s.t. i < j,
v
∗
i
v
i
= 1, ∀i ∈ {1, . . . , n},
v
i
∈ C
n
, ∀i ∈ {1, . . . , n}.
(20)
Note that we have written v
∗
i
v
j
+v
∗
j
v
i
= 0 rather than
v
∗
i
v
j
= 0, in order to have the matrix representing the
constraint be Hermitian, as required in (19) (one can
then go as usual from an equality with 0 constraint to
two constraints of inequality with respect to 0). We can
also write v
∗
i
v
i
≥ 1 rather than v
∗
i
v
i
= 1, making usage
of the fact that such a change does not alter whether
the value of the program is 0 or not. Also, while for
ease of presentation we have stated the problem with
n variables, they can be easily combined into one sin-
gle variable taking values in C
n
2
in order to obtain a
program of the exact same form as (19).
The number of such programs in dimension n that
we need to consider is given by the number of n-
combinations with repetition out of a set of length n,
equal to
2n−1
n
. While asymptotically this will scale
very quickly as a function of n, it will still be com-
putationally tractable for values like n = 5 or n = 6,
which goes beyond the theoretically understood range
of up to n = 3. To compute the final answer, one will
take the minimum value out of all the programs. If this
value is equal to zero, then the states {w
1
, . . . , w
n
} can
be perfectly excluded with a projection, while if it is
a non-zero value then perfect state exclusion of the set
{w
1
, . . . , w
n
} will not be possible.
As for its applications to future results, there are two
main consequences of the formalism we just described,
beyond the indirect consequence of our work possibly
inspiring further usage of the QCQP framework within
quantum information processing.
The first of these consequences correspond to our
newfound ability to use results about QCQPs in or-
der to obtain new structural results about the perfect
exclusion of pure states through projections. One can
straightforwardly check that basic weak duality results
will not help, since the value of the Lagrangian dual
programs will always be zero. However, as we discussed
earlier there is an ongoing stream of non-trivial theo-
retical results about QCQPs, and it seems reasonable
to conjecture that some of those results will eventually
apply to the highly structured programs that we con-
sider.
The second of these consequences corresponds to the
increased potential for the usage of standard mathemat-
ical optimization packages. While the work on solver
software supporting QCQP is not yet at a stage giving
a simple path for an implementation of the programs
described by (20), it seems reasonable to expect that
such a stage will be reached in the near term. Then,
such a piece of software could be compared with an-
other one that implements the program in (1). From
this, one would obtain a numerical study through stan-
dard solvers of the difference between POVMs and pro-
jections for perfect state exclusion of n pure states in n
dimensions.
3.2 Direct generalizations of our proof
A naive approach for generalizing our result would
start by considering conditions equivalent to the Caves-
Fuchs-Schack inequality in the 4-dimensional case.
However, this seems far from trivial, since the original
derivation in [11] presents obstacles to such a general-
ization. In particular, it relies on the fact that when
using the basis determined by an excluding projection,
the sums corresponding to the inner products between
two of the perfectly excluded states {a, b, c} will have ex-
actly one non-zero term. This makes it relatively easy to
obtain formulas for the coefficients of a, b and c in that
basis as a function of the inner products between the
states. However, solving the corresponding equations
in 4 dimensions seems like a significantly more com-
plicated task, as each inner product between excluded
states involves not 2 but 4 non-zero coefficients.
It could also be fruitful to take a geometrical perspec-
tive in order to better understand the situation at hand,
following the approach in [7]. To see at an intuitive level
what this might be like, one can start by observing that
the space of density matrices is a section of the con-
vex cone of positive semidefinite matrices. Also, the
space of probability distributions with 3 outcomes can
be seen as an equilateral triangle, with each vertex of
the triangle corresponding to a different deterministic
distribution. Then, as one can see in Chapter 10 of [7],
for any fixed 3-outcome POVM the map which takes
a density matrix to the probability distribution associ-
ated with applying the POVM to the density matrix
will be an affine map from the convex cone section to
the equilateral triangle.
In light of these facts, we can interpret any limits
to state exclusion via projectors as saying that three
points close to each other in the section of the convex
cone cannot be sent to 3 different faces of the trian-
gle by an affine map corresponding to a projection, as
otherwise some points in the section would be sent out-
side the triangle, which is not allowed. Then, our result
that projections are equivalent to POVMs can be seen
as saying that in the case of pure states this does not
Accepted in Quantum 2019-01-14, click title to verify 6
change when we also allow the affine maps correspond-
ing to non-projection POVMs. It might be interesting
to fully formalize this thought, mathematically prove in
this framework the known results about limits to state
exclusion, and see if it is now easier to extend them to
the case of 4 pure states, where the space of outcomes
of a 4-outcome POVM can be seen as a regular tetra-
hedron.
Another way in which a geometric perspective might
useful would be for obtaining a constructive algorithm
that transforms an excluding POVM into an excluding
projection for the case we analyze in this paper (3 pure
states in 3 dimensions). It seems plausible that obtain-
ing such an algorithm would then give insight about
how to generalize our result.
Along the lines of using state exclusion characteriza-
tions alternative to the one given by (1), the work in [18]
considers a generalization of the explicit perfect state
exclusion criteria given in [11] for the 2-dimensional
case. However, it finds this generalization to be a suf-
ficient condition for the n-dimensional case but not a
necessary one. This work also observes that if pure
states are perfectly excluded via a POVM, they will be
an eigenvector (with eigenvalue 0) of the corresponding
POVM element, and they can be assumed to be an ele-
ment of its spectral decomposition. Then, one can con-
sider the feasibility of an optimization program where
one tries to fill in the remaining coefficients and vectors
in the spectral decomposition of the POVM elements.
While one might expect at first glance that the stan-
dard SDP framework in (1) would offer a greater chance
of applying mathematical optimization results, perhaps
the fact that this formulation is closer in its shape to the
QCQPs in (20) could help make non-trivial connections
between the projection case and the POVM case.
Note too that the main insight that leads to our result
is the fact that one can take a POVM for perfect state
exclusion to be an extremal one. This does not triv-
ially lead to an answer, since there are extremal POVMs
that are not projections, such as those in the family in
Equations (10)–(12). However, an analysis of what the
ranks of an extremal POVM in 3 dimensions have to
look like allows us to obtain a parametrization of the
situation that can be algebraically solved. The usage of
more sophisticated facts about the structure of extremal
POVMs (such as those facts derived in [17, 27, 32])
could be similarly involved in a generalization of our
results to higher dimensionality. In fact, these consid-
erations seem to us a very likely ingredient of any such
generalization.
3.3 Other considerations
It might also be of interest to find relations between the
optimality of projections for tasks involving POVMs,
and the optimality of unitaries (without the use of an-
cillas) for certain tasks involving channels, discussed for
example in [3, 8], specially considering the numerical ev-
idence suggestive of such kind of connection identified
in [3, 5]. When doing so, it might also be of interest
to consider results (such as those in [15]) that charac-
terize from a computational complexity point of view
the power of computing with unitaries as opposed to
general quantum channels.
Note too that for the case of mixed states, state ex-
clusion is mathematically equivalent to state discrimina-
tion (the discriminated states would be those we obtain
by computing I −ρ
i
). This means one can apply exist-
ing results about optimal measurements for mixed state
discrimination [13, 16], and also consider the chance for
generalizing results [12, 35] that look into the optimal-
ity of projections for state discrimination of pure states.
Relatedly, as we discussed earlier the work in [11] gives
a characterization for perfect exclusion of 2-dimensional
pure states that makes it clear that for any number of
k > 2 states in 2 dimensions, projections are not nec-
essarily equivalent to POVMs. It is the case that they
additionally use a reduction to that setting to point out
that for three mixed states in three dimensions, projec-
tions are not equivalent to POVMs within the context
of perfect state exclusion.
Note as well that if one considers the possibility of
constraining the number of non-zero components of a
perfectly excluding POVM, the possibility of doing so
simply corresponds to being able to perfectly exclude a
subset of the set of states under consideration. Another
related variation one might want to study is requiring
that there are no zero components of a perfectly exclud-
ing POVM, as considered in [18].
One could also look into determining whether the re-
sults here carry over to the gradual measure of PP-
incompatibility defined in [10], which is the value of
the SDP in (1) when the uniform distribution is as-
sumed. This would correspond for example to asking
whether projections are optimal for state exclusion of 3
pure states in 3 dimensions even when perfect exclusion
cannot be achieved by POVMs. If that was successfully
answered, it would be natural to relax assumptions even
further, and consider arbitrary distributions. [29] offers
a partial answer to these questions, by giving for an ar-
bitrary number of pure states a sufficient condition for
the existence of an optimal excluding POVM that is a
projection (this is the condition that there is an optimal
POVM such that none of the outcomes are perfectly ex-
cluded, and we also have that the pure states are linearly
independent).
Accepted in Quantum 2019-01-14, click title to verify 7
Note that the QCQP framework discussed in Sec-
tion 3.1 extends without issues to the variants of the
problem discussed in the previous paragraphs. In par-
ticular, if one wishes to study the exclusion of k 6= n
states, one can simply write {w
1
, . . . , w
k
} rather than
{w
1
, . . . , w
n
} for the set of states to be excluded, giving
rise to
k+n−1
n
rather than
2n−1
n
programs of the
form in (20). Similarly, if one wishes to study mixed
states rather than pure states or introduce a probabil-
ity distribution on the states, one can simply modify
the objective function in (20) by replacing the values of
s
i
s
∗
i
with a corresponding ρ
i
and combining them with
a multiplicative term p
i
, respectively.
Furthermore, if one wishes to study non-perfect state
exclusion, the programs given in Section 3.1 can be used
towards that purpose without additional modifications.
As for the variant that limits the number of non-zero
components of a perfectly excluding POVM, it will
correspond to limiting the number of distinct terms
that can appear in the n-combinations with repetition
of {w
1
, . . . , w
n
} that characterize the programs in (20).
Similarly, the requirement that there are no zero com-
ponents of the POVM corresponds to requiring that
every state is excluded by a measurement outcome,
and therefore to only considering the n-combination
given by {s
1
, . . . , s
n
} = {w
1
, . . . , w
n
}.
Acknowledgments
Thanks are due to John Watrous for numerous help-
ful suggestions, as well as to Juani Bermejo-Vega, Alex
Bredariol-Grilo, Richard Cleve, Philippe Faist, Nicolás
Guarín-Zapata, George Knee, Robin Kothari, Deb-
bie Leung, Alexandre Nolin, Christopher Perry, Bu-
rak Şahinoğlu, Jamie Sikora and Jon Tyson for insight-
ful discussions. This work was partially supported by
NSERC, the Canada Graduate Scholarship program,
the Mike and Ophelia Lazaridis Fellowship program,
and the David R. Chariton Graduate Scholarship pro-
gram.
References
[1] Chris Aholt, Sameer Agarwal, and Rekha Thomas.
A QCQP approach to triangulation. In European
Conference on Computer Vision, pages 654–667.
Springer, 2012. DOI: 10.1007/978-3-642-33718-
5_47.
[2] Juan Miguel Arrazola, Petros Wallden, and
Erika Andersson. Multiparty quantum signature
schemes. arXiv preprint, 2015. URL https:
//arxiv.org/abs/1505.07509.
[3] Srinivasan Arunachalam, Abel Molina, and Vin-
cent Russo. Quantum hedging in two-round
prover-verifier interactions. In LIPIcs-Leibniz In-
ternational Proceedings in Informatics, volume 73.
Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik,
2018. DOI: 10.4230/LIPIcs.TQC.2017.5.
[4] Koenraad MR Audenaert and Stefan Scheel. Quan-
tum tomographic reconstruction with error bars:
a Kalman filter approach. New Journal of
Physics, 11(2):023028, 2009. DOI: 10.1088/1367-
2630/11/2/023028.
[5] Somshubhro Bandyopadhyay, Rahul Jain,
Jonathan Oppenheim, and Christopher Perry.
Conclusive exclusion of quantum states. Physical
Review A, 89(2):022336, 2014. DOI: 10.1103/phys-
reva.89.022336.
[6] Jonathan Barrett, Eric G Cavalcanti, Raymond
Lal, and Owen JE Maroney. No ψ-epistemic
model can fully explain the indistinguishabil-
ity of quantum states. Physical Review Let-
ters, 112(25):250403, 2014. DOI: 10.1103/phys-
revlett.112.250403.
[7] Ingemar Bengtsson and Karol Zyczkowski. Geom-
etry of Quantum States: An Introduction to Quan-
tum Entanglement. Cambridge University Press,
2007. DOI: 10.1017/9781139207010.
[8] Michael R Beran and Scott M Cohen. Nonoptimal-
ity of unitary encoding with quantum channels as-
sisted by entanglement. Physical Review A, 78(6):
062337, 2008. DOI: 10.1103/PhysRevA.78.062337.
[9] Subhonmesh Bose, Dennice F Gayme, K Mani
Chandy, and Steven H Low. Quadratically con-
strained quadratic programs on acyclic graphs with
application to power flow. IEEE Transactions on
Control of Network Systems, 2(3):278–287, 2015.
DOI: 10.1109/tcns.2015.2401172.
[10] Todd A Brun, Min-Hsiu Hsieh, and Christopher
Perry. Compatibility of state assignments and
pooling of information. Physical Review A, 92(1):
012107, 2015. DOI: 10.1103/physreva.92.012107.
[11] Carlton M Caves, Christopher A Fuchs, and
Rüdiger Schack. Conditions for compatibility
of quantum-state assignments. Physical Re-
view A, 66(6):062111, 2002. DOI: 10.1103/phys-
reva.66.062111.
[12] Yonina C Eldar, Alexandre Megretski, and
George C Verghese. Designing optimal quantum
detectors via semidefinite programming. IEEE
Transactions on Information Theory, 49(4):1007–
1012, 2003. DOI: 10.1109/tit.2003.809510.
[13] Yonina C Eldar, Mihailo Stojnic, and Babak
Hassibi. Optimal quantum detectors for unam-
biguous detection of mixed states. Physical Re-
Accepted in Quantum 2019-01-14, click title to verify 8
view A, 69(6):062318, 2004. DOI: 10.1103/phys-
reva.69.062318.
[14] Youping Fan and Bernd Tibken. Optimization
problems of determining the C-numerical range.
IFAC Proceedings Volumes, 41(2):10051–10056,
2008. DOI: 10.3182/20080706-5-kr-1001.01701.
[15] Bill Fefferman and Cedric Yen-Yu Lin. A com-
plete characterization of unitary quantum space.
arXiv preprint, 2016. URL https://arxiv.org/
abs/1604.01384.
[16] Jaromír Fiurášek and Miroslav Ježek. Optimal
discrimination of mixed quantum states involving
inconclusive results. Physical Review A, 67(1):
012321, 2003. DOI: 10.1103/physreva.67.012321.
[17] Erkka Haapasalo, Teiko Heinosaari, and Juha-
Pekka Pellonpää. Quantum measurements on fi-
nite dimensional systems: relabeling and mix-
ing. Quantum Information Processing, 11(6):1751–
1763, 2012. DOI: 10.1007/s11128-011-0330-2.
[18] Teiko Heinosaari and Oskari Kerppo. Antidistin-
guishability of pure quantum states. Journal of
Physics A: Mathematical and Theoretical, 51(36):
365303, 2018. DOI: 10.1088/1751-8121/aad1fc.
[19] Yongwei Huang and Daniel P Palomar. Random-
ized algorithms for optimal solutions of double-
sided QCQP with applications in signal processing.
IEEE Transactions on Signal Processing, 62(5):
1093–1108, 2014. DOI: 10.1109/tsp.2013.2297683.
[20] Cédric Josz and Daniel K Molzahn. Moment/sum-
of-squares hierarchy for complex polynomial op-
timization. arXiv preprint, 2015. URL https:
//arxiv.org/abs/1508.02068.
[21] Aritra Konar and Nicholas D Sidiropoulos.
Hidden convexity in QCQP with Toeplitz-
Hermitian quadratics. IEEE Signal Process-
ing Letters, 22(10):1623–1627, 2015. DOI:
10.1109/lsp.2015.2419571.
[22] Quanzhong Li, Qi Zhang, and Jiayin Qin. A special
class of fractional QCQP and its applications on
cognitive collaborative beamforming. IEEE Trans.
Signal Processing, 62(8):2151–2164, 2014. DOI:
10.1109/tsp.2014.2309072.
[23] Yeong-Cherng Liang and Andrew C Doherty.
Bounds on quantum correlations in Bell-inequality
experiments. Physical Review A, 75(4):042103,
2007. DOI: 10.1103/physreva.75.042103.
[24] Zi-Wen Liu, Christopher Perry, Yechao Zhu,
Dax Enshan Koh, and Scott Aaronson. Doubly
infinite separation of quantum information and
communication. Physical Review A, 93(1):012347,
2016. DOI: 10.1103/physreva.93.012347.
[25] N David Mermin. Whose knowledge? In Quantum
[Un] speakables, pages 271–280. Springer, 2002.
DOI: 10.1007/978-3-662-05032-3_19.
[26] Jaehyun Park and Stephen Boyd. General
heuristics for nonconvex quadratically constrained
quadratic programming. arXiv preprint, 2017.
URL https://arxiv.org/abs/1703.07870.
[27] KR Parthasarathy. Extremal decision rules
in quantum hypothesis testing. Infinite Di-
mensional Analysis, Quantum Probability and
Related Topics, 2(04):557–568, 1999. DOI:
10.1142/s0219025799000321.
[28] Rudolf Ernst Peierls. More Surprises in Theoretical
Physics, volume 19. Princeton University Press,
1991. ISBN 9780691025223.
[29] Christopher Perry. Conclusive exclusion of quan-
tum states and aspects of thermo-majorization.
PhD thesis, UCL (University College London),
2016. URL http://discovery.ucl.ac.uk/id/
eprint/1473944.
[30] Christopher Perry, Rahul Jain, and Jonathan
Oppenheim. Communication tasks with infinite
quantum-classical separation. Physical Review Let-
ters, 115(3):030504, 2015. DOI: 10.1103/phys-
revlett.115.030504.
[31] Matthew F Pusey, Jonathan Barrett, and Terry
Rudolph. On the reality of the quantum
state. Nature Physics, 8(6):475–478, 2012. DOI:
10.1038/nphys2309.
[32] G Sentís, B Gendra, SD Bartlett, and AC Do-
herty. Decomposition of any quantum measure-
ment into extremals. Journal of Physics A: Mathe-
matical and Theoretical, 46(37):375302, 2013. DOI:
10.1088/1751-8113/46/37/375302.
[33] Blake C Stacey. SIC-POVMs and compatibil-
ity among quantum states. Mathematics, 4(2):36,
2016. DOI: 10.3390/math4020036.
[34] Guo Chuan Thiang. Some attempts at proving
the non-existence of a full set of mutually unbi-
ased bases in dimension 6. arXiv preprint, 2010.
URL https://arxiv.org/abs/1012.3147.
[35] MAP Touzel, RBA Adamson, and Aephraim M
Steinberg. Optimal bounded-error strategies for
projective measurements in nonorthogonal-state
discrimination. Physical Review A, 76(6):062314,
2007. DOI: 10.1103/physreva.76.062314.
[36] T Vértesi and E Bene. Two-qubit Bell inequality
for which positive operator-valued measurements
are relevant. Physical Review A, 82(6):062115,
2010. DOI: 10.1103/physreva.82.062115.
[37] John Watrous. The Theory of Quantum Informa-
tion. Cambridge University Press, 2018. DOI:
10.1017/9781316848142.
[38] Graeme Weir, Stephen M. Barnett, and Sarah
Croke. Optimal discrimination of single-qubit
mixed states. Physical Review A, 96:022312, Aug
2017. DOI: 10.1103/physreva.96.022312.
Accepted in Quantum 2019-01-14, click title to verify 9
[39] Mark M Wilde. Quantum Information The-
ory. Cambridge University Press, 2013. DOI:
10.1017/CBO9781139525343.
[40] Huangjun Zhu, Yong Siah Teo, and Berthold-
Georg Englert. Two-qubit symmetric information-
ally complete positive-operator-valued measures.
Physical Review A, 82(4):042308, 2010. DOI:
10.1103/physreva.82.042308.
Accepted in Quantum 2019-01-14, click title to verify 10