Separability of diagonal symmetric states: a
quadratic conic optimization problem
Jordi Tura
1 2
, Albert Aloy
1
, Rubén Quesada
3
, Maciej Lewenstein
1 4
, and Anna Sanpera
3 4
1
ICFO - Institut de Ciencies Fotoniques, The Barcelona Institute of Science an d Technology, 08860 Castelldefels (Barcelona),
Spain
2
Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße 1, 85748 Garching, Germany
3
Departament de Física, Universitat Autònoma de Barcelona, E-08193 Bellaterra, Spain
4
ICREA, Pg. Lluís Companys 23, E-08010 Barcelona, Spain
Decemb er 29, 2017
We study the separability problem in mixtures of Dicke states i.e., the separability
of the so-called Diagonal Symmetric (DS) states. First, we show that separability in the
case of DS in
d
⊗
d
(symmetric qudits) can be reformulated as a quadratic conic op-
timization problem. This connection allows us to exchange concepts and ideas between
quantum information and this field of mathematics. For instance, copositive matrices can
be understood as indecomposable entanglement witnesses for DS states. As a consequence,
we show that positivity of the partial transposition (PPT) is sufficient and necessary for
separability of DS states for d ≤ 4. Furthermore, for d ≥ 5, we provide analytic examples
of PPT-entangled states. Second, we develop new sufficient separability conditions beyond
the PPT criterion for bipartite DS states. Finally, we focus on N-partite DS qubits, where
PPT is known to be necessary and sufficient for separability. In this case, we present a
family of almost DS states that are PPT with respect to each partition but nevertheless
entangled.
1 Introduction
Entanglement [1] is one of the most striking features of quantum physics, departing entirely from any
classical analogy. Furthermore, entanglement is a key resource for quantum information processing
tasks, such as quantum cryptography [2] or metrology [3]. Importantly, entanglement is a necessary
resource to enable the existence of Bell correlations [4, 5], which are the resource device-independent
quantum information processing is built upon [6]. Despite its both fundamental and applied interest,
the so-called separability problem (i.e., deciding whether a quantum state is entangled or not, given
its description) remains open except for very specific cases. Although this problem has been shown
to be, in the general case, NP-hard [7], it remains unclear whether this is also the case for physical
systems of interest, where symmetries appear in a natural way.
To tackle the separability problem, simple tests have been put forward, which give a partial char-
acterization of entanglement. The most celebrated entanglement detection criterion is the so-called
positivity under partial transposition (PPT) criterion [8]. It states that every state that is not entan-
gled must satisfy the PPT criterion. Therefore, states that break the PPT criterion are entangled.
Unfortunately, the converse is true only in very low-dimensional systems [9], such as two qubit [10] or
qubit-qutrit systems [11]. Examples of entangled states satisfying the PPT criterion have been found
for strictly larger-dimensional systems [12].
Jordi Tura: jordi.tura@mpq.mpg.de
Accepted in Quantum 2017-12-28, click title to verify 1
arXiv:1706.09423v2 [quant-ph] 28 Dec 2017
Symmetries are ubiquitous in Nature and they play a fundamental role in finding an efficient de-
scription of physical systems. The so-called symmetric states constitute an important class of quantum
systems to describe systems of indistinguishable particles [13]. Symmetric states can be mapped to
spin systems that are invariant under the exchange of particles and, moreover, they are spanned solely
by the largest-spin subspace in the Schur-Weyl duality representation [14]. The Dicke states [15] pro-
vide a convenient basis to represent symmetric states. Moreover, Dicke states are also experimentally
available [16–18] and they also appear naturally as ground states of physically relevant Hamiltonians,
such as the isotropic Lipkin-Meshkov-Glick model [19]. Much theoretical study has been devoted to
the characterization of entanglement in qubit symmetric states: 3-qubit symmetric states are separable
if, and only if, they satisfy the PPT criterion [13], but this is no longer the case already for N ≥ 4
[20, 21]. Despite diverse separability criteria exist for symmetric states (see e.g. [22]), the separability
problem remains still open.
Mixtures of Dicke states are symmetric states that are diagonal in the Dicke basis. These constitute
an important class of quantum states which naturally arise e.g. in dissipative systems such as photonic
or plasmonic one-dimensional waveguides [23]. Mixtures of Dicke states form a small subclass of
the symmetric states. They are the so-called Diagonal Symmetric (DS) states. In this context, the
separability problem has also gained interest. For instance, the best separable approximation (BSA,
[24]) has been found analytically for DS states for N -qubits [25]. In [26], it was conjectured that
N-qubit DS states are separable if, and only if, they satisfy the PPT criterion with respect to every
bipartition. The conjecture was proven by N. Yu in [27] where, moreover, he observed that PPT is a
sufficient and necessary condition for bipartite DS states of qudits with dimension 3 and 4, but becomes
NP-hard for larger dimensions. Within the N -qubit DS set it has been shown in [28] that there is a
family of states that violate the weak Peres conjecture [29]: those states are PPT-bound entangled
with respect to one partition, but they violate a family of permutationally invariant two-body Bell
inequalities [30–32].
In experiments, PPT-entangled states have also been recently observed. In the multipartite case,
the Smolin state has been prepared with four photons, using the polarization degree of freedom for
the qubit encoding [33, 34]. Very recently, although bound entanglement is the hardest to detect [35],
the Leiden-Vienna collaboration has reported the observation of bound entanglement in the bipartite
case with two twisted photons, combining ideas of complementarity [36] and Mutually Unbiased Bases
(MUBs) [37].
Here, we independently recover the results of N. Yu [27] by reformulating the problem in terms
of optimization in the cone of completely-positive
1
matrices. First, we revisit the problem of deter-
mining separability of two DS qudits in arbitrary dimensions. We show that it can be reformulated
in terms of a quadratic conic optimization problem [38]. In particular, we show that separability in
DS states is equivalent to the membership problem in the set of completely-positive matrices. The
equivalence between these two problems allows us to import/export ideas between entanglement theory
and non-convex quadratic optimization
2
. Second, we provide examples of entangled PPTDS states and
entanglement witnesses detecting them. Third, we give further characterization criteria for separability
in DS states in terms of the best diagonal dominant decomposition. Finally, we present a family of
N-qubit almost-DS states that are PPT with respect to each bipartition, but nevertheless entangled.
The word almost here means that by adding an arbitrarily small off-diagonal term (GHZ coherence)
to a family of separable DS N-qubits, the state becomes PPT-entangled.
1
Throughout this paper, the term completely-positive corresponds to the definition given in Def. 3.4 and it is not to
be confounded with the concept of a completely positive map that arises typically in a quantum information context.
2
Quadratic conic optimization problems appear naturally in many situations (see [38] and references therein). These
include economic modelling [39], block designs [40], maximin efficiency-robust tests [41], even Markovian models of DNA
evolution [42]. Recently, they have found their application in data mining and clustering [43], as well as in dynamical
systems and control [44, 45].
Accepted in Quantum 2017-12-28, click title to verify 2
The paper is organized as follows. In Section 2 we establish the notation and the basic definitions
that we are going to use in the next sections. In Section 3 we discuss the separability problem
for bipartite DS states of arbitrary dimension, with particular emphasis in their connection to non-
convex quadratic optimization problems. In Section 4 we provide sufficient criteria to certify either
separability or entanglement. In Section 5 we present a class of PPT-entangled multipartite qubit
almost-diagonal symmetric states. In Section 6 we conclude and discuss further research directions.
Finally, in the Appendix we present some proofs, examples and counterexamples that complement the
results discussed in the text.
2 Preliminaries
In this section we set the notation and define the basic concepts that we are going to use throughout
the paper.
2.1 The separability problem
Definition 2.1. Consider a bipartite quantum state ρ acting on
d
⊗
d
0
. The state ρ is positive
semi-definite (ρ 0) and normalized (Trρ = 1). A state ρ is separable if it can be written as
ρ =
X
i
p
i
ρ
A
i
⊗ ρ
B
i
, (1)
where p
i
form a convex combination (p
i
≥ 0 and
P
i
p
i
= 1) and ρ
A
i
(ρ
B
i
) are quantum states acting on
Alice’s (Bob’s) subsystem; i.e., they are positive semidefinite operators of trace one. If a decomposition
of ρ of the form of Eq. (1) does not exist, then ρ is entangled.
The separability problem; i.e., deciding whether a quantum state ρ admits a decomposition of
the form of Eq. (1) is, in general, an NP-hard problem [7]. However, there exist simple tests that
provide sufficient conditions to certify that ρ is entangled [1]. One of the most renowned separability
criteria is the positivity under partial transposition (PPT) criterion [8]. It states that, if ρ can be
decomposed into the form of Eq. (1), then the state ( ⊗T )[ρ] must be positive semi-definite, where T
is the transposition with respect to the canonical basis of
d
0
. Such state is denoted ρ
T
B
, the partial
transposition of ρ on Bob’s side. Because (ρ
T
B
)
T
= ρ
T
A
, the PPT criterion does not depend on which
side of the bipartite system the transposition operation is applied on. Breaking PPT criterion is a
necessary and sufficient condition for entanglement only in the two qubit [10] and qubit-qutrit [11]
cases, and there exist counterexamples for states of strictly higher physical dimension [12].
In the multipartite case, the definition of separability given in Eq. (1) naturally generalizes to N
subsystems.
Definition 2.2. A quantum state ρ acting on
d
1
⊗···⊗
d
N
is fully separable if it can be written as
ρ =
X
i
p
i
ρ
(A
1
)
i
⊗ ··· ⊗ ρ
(A
N
)
i
, (2)
where ρ
(A
k
)
i
are quantum states acting on the k-th subsystem and p
i
form a convex combination.
Therefore, the PPT criterion also generalizes to 2
bN/2c
criteria, where b·c is the floor function,
depending on which subsystems one chooses to transpose.
2.1.1 Entanglement witnesses
Let us denote by D
sep
the set of separable sates (cf. Eqs. (1), (2)). This set is closed and convex.
Therefore it admits a dual description in terms of its dual cone, which we denote
P = {W = W
†
s. t. hW, ρi ≥ 0 ∀ρ ∈ D
sep
},
Accepted in Quantum 2017-12-28, click title to verify 3
where the usual Hilbert-Schmidt scalar product hW, ρi = Tr(W
†
ρ) is taken. The elements of P can
be thus viewed as half-spaces containing D
sep
. Of course, not every operator in P is useful to detect
entangled states. In order to be non-trivial, one requires that W has at least one negative eigenvalue.
Such operators are called entanglement witnesses (EW) [46] and they form a non-convex set, denoted
W = {W ∈ P s. t. W 6 0}. A state ρ is then separable if, and only if, Tr(W ρ) ≥ 0 for all W ∈ W.
Among EWs, it is worth to make a distinction that relates them to the PPT criterion: decomposable
and indecomposable EWs.
Definition 2.3. Decomposable EWs (DEWs) in a bipartite quantum system are those W ∈ W of the
form
W = P + Q
T
B
, (3)
with P 0 and Q 0. Indecomposable EWs (IEWs) are those EWs that are not of the form of Eq.
(3).
Although DEWs are easier to characterize [47], they do not detect PPT-entangled states, because
Tr(W ρ) = Tr(P ρ) + Tr(Q
T
B
ρ) = Tr(P ρ) + Tr(Qρ
T
B
) ≥ 0. (4)
In Section 4.1 we construct EWs which detect entangled PPTDS states, therefore they correspond to
indecomposable witnesses.
3 Separability in diagonal symmetric states acting on
d
⊗
d
.
In this section, we characterize the bipartite diagonal symmetric two-qudit states in terms of the
separability and the PPT properties. We establish an equivalence between: (i) separability and the
PPT property in DS states and (ii) quadratic conic optimization problems and their relaxations,
respectively.
We first introduce the Dicke basis in its full generality and then we move to the two particular cases
of interest to this paper: the case of N -qubits and the case of 2-qudits. One can think of the space
spanned by the Dicke states as the linear subspace of (
d
)
⊗N
containing all permutationally invariant
states.
Definition 3.1. Consider a multipartite Hilbert space (
d
)
⊗N
of N qudits. The Dicke basis in that
space consists of all vectors which are equal superpositions of k
0
qudits in the state |0i, k
1
qudits in
the state |1i, etc., where the multiindex variable k = (k
0
, . . . , k
d−1
) forms a partition of N; i.e., k
i
≥ 0
and
P
d−1
i=0
k
i
= N. They can be written as
|D
k
i ∝
X
σ∈S
N
σ(|0i
⊗k
0
|1i
⊗k
1
···|d −1i
⊗k
d−1
), (5)
where σ runs over all permutations of N elements.
The Dicke state has
N
k
different elements, where the quantity follows from the multinomial com-
binatorial quantity
N
k
!
=
N!
k
0
!k
1
! ···k
d−1
!
. (6)
Finally, recall that there are as many Dicke states as partitions of N into d (possibly empty) subsets;
therefore, the dimension of the subspace of (
d
)
⊗N
is given by
dim[{|D
k
i : k ` N}] =
N + d − 1
d −1
!
, (7)
where ` denotes partition of.
In this paper, we are particularly interested in the case of N-qubits and 2-qudits:
Accepted in Quantum 2017-12-28, click title to verify 4
• d = 2. For N-qubit states we shall use the notation |D
k
i ≡ |D
N
k
i, where k = k
1
denotes the
number of qubits in the excited (|1i) state. Mixtures of Dicke states correspond to
ρ =
N
X
k=0
p
k
|D
N
k
ihD
N
k
|. (8)
• N = 2. For bipartite d-level systems, we are going to denote the Dicke states by |D
k
i ≡ |D
ij
i,
where i and j are the indices (possibly repeated) of the non-zero k
i
and k
j
. Since the terminology
Dicke states is often reserved for the multipartite case, we call |D
ij
i simply symmetric states.
In the bipartite case (Sections 3 and 4), we focus on diagonal symmetric states, given by Def. 3.2:
Definition 3.2. Let ρ be a state acting on a bipartite Hilbert space H
A
⊗ H
B
=
d
⊗
d
. The state
ρ is said to be diagonal symmetric (DS) if, and only if, ρ can be written in the form
ρ =
X
0≤i≤j<d
p
ij
|D
ij
ihD
ij
|, (9)
where p
ij
≥ 0,
P
ij
p
ij
= 1, |D
ii
i := |iii and |D
ij
i = (|iji + |jii)/
√
2.
In the computational basis, a DS ρ is a d
2
× d
2
matrix that is highly sparse. Therefore, it will
be useful to associate a d × d matrix to ρ that captures all its relevant information. We define the
M-matrix of ρ to be
Definition 3.3. To every DS ρ acting on
d
⊗
d
, there is an associated d × d matrix M(ρ), with
non-negative entries
M(ρ) :=
p
00
p
01
/2 ··· p
0,d−1
/2
p
01
/2 p
11
··· p
1,d−1
/2
.
.
.
.
.
.
.
.
.
.
.
.
p
0,d−1
/2 p
1,d−1
/2 ··· p
d−1,d−1
, (10)
which arises from the partially transposed matrix ρ
T
B
.
Notice that, while a DS state ρ is always diagonal in the Dicke basis, its partial transposition (which
is defined with respect to the computational basis) scrambles its elements. Then ρ
T
B
is block-diagonal
in the Dicke basis and its blocks are 1 × 1 elements corresponding to p
ij
with i < j, and M(ρ). One
can see the effect of the partial transposition operation on a DS state by inspecting the action of T
B
onto the elements |D
ij
ihD
ij
| that compose Eq. (9):
• If i = j, then (|D
ii
ihD
ii
|)
T
B
= |D
ii
ihD
ii
|, because |D
ii
i = |iii.
• If i 6= j, the action of the partial transposition is best seen by expanding |D
ij
i onto the computa-
tional basis: (|D
ij
ihD
ij
|) =
1
2
(|ijihij|+|ijihji|+|jiihij|+|jiihji|). Therefore, two of the terms are
left invariant and the remaining two are to be mapped as (|ijihji|+|jiihij|)
T
B
= |iiihjj|+|jjihii|.
Thus, M(ρ) is the submatrix corresponding to the elements indexed by |iiihjj| for 0 ≤ i, j < d of ρ
T
B
.
Because there is no mixing between other rows or columns, we have that ρ
T
B
decomposes as the direct
sum
ρ
T
B
= M(ρ)
M
0≤i6=j<d
p
ij
2
. (11)
Since p
ij
= p
ji
, we find that the 1 × 1 blocks appear all with multiplicity 2.
Therefore, each M(ρ) with non-negative entries summing 1 is in one-to-one correspondence to a DS
state ρ. In this section we characterize the separability properties of ρ in terms of equivalent properties
of M(ρ), which are naturally related to quadratic conic optimization.
In quadratic conic optimization, one is interested in characterizing the so-called completely positive
(CP) matrices, which are defined as follows
Accepted in Quantum 2017-12-28, click title to verify 5
Definition 3.4. Let A be a d × d matrix. A is completely positive (CP) if, and only if, it admits a
decomposition A = B · B
T
, where B is a d ×k matrix, for some k ≥ 1, such that B
ij
≥ 0.
Matrices which are CP form a proper
3
cone, which is denoted by CP
d
. Note that the sum of two
CP matrices is a CP matrix and the multiplication of a CP matrix by a non-negative scalar is a CP
matrix.
Given a non-convex optimization problem over the simplex, which is NP-hard in general, CP
matrices translate the complexity of the problem by reformulating it as a linear problem in matrix
variables over CP
d
. Therefore, they allow to shift all the difficulty of the original problem into the cone
constraint. Precisely, every non-convex quadratic optimization problem over the simplex (LHS of Eq.
(12)) has an equivalent CP formulation (RHS of Eq. (12)):
max
x
i
≥0, hu|xi=1
hx|Q|xi = max
X∈CP
d
, hu|X|ui=1
Tr(XQ), (12)
where |ui is the unnormalized vector of ones and Q is, without loss of generality
4
, symmetric and
positive semi-definite. Therefore, deciding membership in CP
d
is NP-hard [38].
One can obtain, however, an upper bound on the optimization in Eq. (12) by observing that every
CP matrix A is positive semi-definite, because it allows for a factorization A = B · B
T
. Moreover, it
is also entry-wise non-negative: A
ij
≥ 0. This motivates Definition 3.5:
Definition 3.5. Let A be a d ×d matrix. A is doubly non-negative (DNN) if, and only if, A 0 and
A
ij
≥ 0.
We are now ready to introduce the equivalences between the separability problem in DS states and
quadratic conic optimization. After producing our results, we learned that these equivalences were
independently observed by Nengkun Yu in [27]. We nevertheless prove them in a different way.
Theorem 3.1. Let ρ be a DS state acting on
d
⊗
d
.
ρ is separable ⇐⇒ M(ρ) is CP. (13)
We prove Theorem 3.1 in Appendix A.
By virtue of Theorem 3.1, we recover the result of [27]: Because it is NP-Hard to decide whether
a matrix admits a CP decomposition [38], the separability problem in
d
⊗
d
DS states is NP-Hard.
We remark that the NP-hardness result that we obtain holds under polynomial-time Turing reduc-
tions
5
, as opposed to poly-time many-one
6
reductions [48]. For instance, this is the case for Gurvits’
initial reduction of the weak membership problem
7
in the set of separable states from the NP-complete
problem PARTITION
8
[7]. In the case we present here, the reduction holds because the NP-hardness
of deciding membership in the CP
d
set follows via a Turing reduction, which is the result we use as
our starting point. The part of the reduction that we provide here, however, is many-one.
3
Closed, convex, pointed and full-dimensional.
4
Q can be assumed to be symmetric because hx|Q|xi = (hx|Q|xi)
T
= hx|Q
T
|xi. It can be assumed to be positive
semi-definite because adding to (Q + Q
T
)/2 does not change the optimal |xi; it only adds a bias to the maximum.
5
Intuitively speaking, a Turing reduction describes how to solve problem A by running an algorithm for a second
problem B, possibly multiple times.
6
A many-one reduction is a special case of a Turing reduction, with the particularity that the algorithm for problem
B can be called only one time, and its output is immediately returned as the output of problem A.
7
Weak in the sense that it allows for error in points at a given Euclidean distance from the border of the set.
8
The PARTITION problem is a decision problem corresponding to whether a given set of integer numbers can be
partitioned into two sets of equal sum. This problem is efficiently solvable with a dynamic programming procedure [49],
but becomes NP-hard when the magnitudes of the input integers become exponentially large with the input size.
Accepted in Quantum 2017-12-28, click title to verify 6
We here briefly discuss the steps that would be required to make this result completely rigurous from
a computer science point of view. One would need to embed the NP-hardness into the formalism of the
weak membership problem [7, 50]. This requires, for instance, showing that the convex set of separable
DS states has some desirable properties such as being well-bounded or p-centered. We refer the reader
to [48] for the technical aspects of these definitions. On the other hand, the completely positive cone is
known to be well-bounded and p-centered: in [51] it was proved that the weak membership problem in
the completely positive cone is NP-hard. By using the one-to-one correspondence between DS states
and CP matrices given by M(ρ) in Def. 3.3, then the result is mapped onto the DS set
9
.
Geometrically, the set of separable DS states is convex. Hence, it is fully characterized by its ex-
tremal elements (those that cannot be written as a non-trivial convex combination of other separable
DS states). Identifying such elements is of great importance towards the characterization of the sepa-
rability properties of DS states. For instance, in the set of all separable density matrices, the extremal
ones are the rank-1 projectors onto product vectors. However, this property may be lost when re-
stricting our search in a subspace: observe that the set of separable DS states states is obtained as the
intersection of the subspace of DS states with the convex set of separable density matrices. Therefore,
the set of extremal separable DS states states may contain states that are separable, but not extremal
in the set of separable density matrices (see Fig. 1). Theorem 3.1 allows us to fully characterize
extremality in the set of separable DS states in terms of extremal CP matrices, thus obtaining the
following corollary:
Corollary 3.1. The extremal separable DS states ρ fulfill
p
ij
= 2
√
p
ii
p
jj
, i < j. (14)
Proof. – Since the extremal rays of the CP
d
cone are the rank-1 matrices
~
b
~
b
T
where b
i
≥ 0 [42], by
normalizing and comparing to Eq. (10) we obtain Eq. (14).
Separable
Figure 1: Cartoon picture of the set of separable states SEP (cylinder) and its intersection with the subspace of
diagonal symmetric states DS (ellipse). The intersection of the subspace of DS states with the set of separable states
gives rise to the set of separable DS states, which is represented by the green ellipse, including its interior. Only the
states of the form |iiihii| are extremal in both sets (represented by the black dot in the figure). However, states that
were in the boundary of SEP, could now be extremal when viewed in DS (represented by the border of the green
ellipse in the figure).
9
The technical requirement of full dimensionality [48, 51] depends on the set in which one embeds the problem. Recall
that we are interested in solving the separability problem within DS states. The set of DS separable states is of course
not full-dimensional when embedded in the whole two-qudit Hilbert space. However, it is full-dimensional when viewed
in the DS subspace (cf. Figure 1).
Accepted in Quantum 2017-12-28, click title to verify 7
Theorem 3.2. Let ρ be a DS state acting on
d
⊗
d
.
ρ is PPT ⇐⇒ M(ρ) is DNN. (15)
Proof. – Let us assume that ρ is PPT. Note that the partial transposition of ρ can be written as
ρ
Γ
=
M
0≤a<b<d
p
ab
2
⊕
p
ab
2
⊕ M(ρ). (16)
Since ρ is PPT, Eq. (16) implies that M(ρ) 0. Since ρ is a valid quantum state, then p
ab
≥ 0 for all
0 ≤ a ≤ b < d. Hence, all the entries of M(ρ) are also non-negative. Thus, M(ρ) is DNN.
Conversely, if M(ρ) is DNN then we have that all its entries are non-negative; i.e., p
ab
≥ 0 for
0 ≤ a ≤ b < d. These conditions guarantee that ρ 0. Additionally, as M(ρ) 0, these conditions
imply that ρ
Γ
0. Hence, ρ is PPT.
Figure 2: For a two qudit PPTDS state ρ, if its corresponding M(ρ) is in CP
d
then ρ is separable, if M (ρ) is in
DNN
d
then ρ is P P T and if M(ρ) is in DNN
d
but not CP
d
then ρ is P P T but entangled.
Recall (cf. Definitions 3.4 and 3.5, also Fig. 2) that CP
d
⊆ DNN
d
. However, the inclusion is strict
for d ≥ 5: It is known that CP
d
= DNN
d
for d ≤ 4 and CP
d
( DNN
d
for d ≥ 5 [38]. This yields a
full characterization of the bipartite separable DS states in terms of the PPT criterion:
Theorem 3.3. Let ρ be a DS state acting on
d
⊗
d
, with d ≤ 4.
ρ is separable ⇐⇒ ρ is PPT. (17)
Proof. – The result follows from the identity CP
d
= DNN
d
, which holds for d ≤ 4 [38]. In Example
C.1 we provide a constructive proof for d = 3.
Finally, we end this section by giving a sufficient separability criteria for any d in terms of the ranks
of M(ρ).
Theorem 3.4. Let ρ be a PPTDS state with M(ρ) of rank at most 2. Then, ρ is separable.
Proof. – Since ρ is PPT, M (ρ) 0. Therefore, it admits a factorization M(ρ) = V V
T
, where V is
a d × 2 or a d × 1 matrix. Geometrically, every row of V can be seen as a vector in
2
(or a scalar
if the rank of M(ρ) is one). Therefore, M(ρ) can be seen as the Gram matrix of those vectors; each
element being their scalar product. Since M(ρ) is doubly non-negative, it implies that all these scalar
products must be positive; therefore, the angle between each pair of vectors is smaller or equal than
π/2. Thus, the geometrical interpretation is that M(ρ) is CP if, and only if, they can be isometrically
embedded into the positive orthant of
k
for some k. This is always possible to do for k = 2 (see Fig.
3), which corresponds to M(ρ) having rank at most 2.
Accepted in Quantum 2017-12-28, click title to verify 8
Figure 3: Visual representation of the proof for Theorem 3.4. When the angle between each pair of vectors is smaller
or equal than π/2, meaning that M (ρ) is CP
d
, all vectors can be isometrically embedded in the nonnegative orthant.
4 Sufficient criteria for entanglement and separability
In this section we further characterize the bipartite DS states by providing sufficient criteria to cer-
tify entanglement by means of Entanglement Witnesses for DS states, and by providing sufficient
separability conditions in terms of M(ρ).
4.1 Entanglement Witnesses for DS states
We begin by introducing the concept of copositive matrix:
Definition 4.1. A matrix A is called copositive if, and only if, ~x
T
A~x ≥ 0 for all ~x with non-negative
entries.
The set of d × d copositive matrices also forms a proper cone, denoted COP
d
. The cones CP
d
and COP
d
are dual to each other with respect to the trace inner product. It is also easy to see that
PSD
d
+ N
d
⊆ COP
d
, where PSD
d
is the set of positive-semidefinite d × d matrices and N
d
is the
set of symmetric entry-wise non-negative matrix. Actually, we have DNN
d
= PSD
d
∩ N
d
and the
observation follows from the inclusion CP
d
⊆ DNN
d
.
Therefore, one can view copositive matrices as EWs for DS states. Furthermore, one could think of
PSD
d
+ N
d
as the set of DEWs for DS states, in the sense that they do not detect entangled PPTDS
states.
In Examples 4.1 and D.1 we provide some M(ρ) ∈ DNN
d
\CP
d
for d ≥ 5, therefore corresponding to
entangled PPTDS states. The paradigmatic example of a copositive matrix detecting matrices DNN,
but not CP, (i.e., PPT, but entangled DS states) is the Horn matrix [40], which is defined as
H :=
1 −1 1 1 −1
−1 1 −1 1 1
1 −1 1 −1 1
1 1 −1 1 −1
−1 1 1 −1 1
. (18)
It is proven that H ∈ COP
5
\ (PSD
5
+ N
5
) in [40]. As Tr(HM(ρ)) = −1 < 0, H corresponds to an
(indecomposable) entanglement witness for the state corresponding to M(ρ).
Although the boundary of the set of copositive matrices remains uncharacterized for arbitrary
dimensions, COP
5
was fully characterized in [51]:
COP
5
= {DAD : D is positive diagonal, A s. t. p(A, ~x) is a sum of squares}, (19)
Accepted in Quantum 2017-12-28, click title to verify 9
where
p(A, ~x) :=
X
i,j
A
ij
x
2
i
x
2
j
X
k
x
2
k
!
.
Furthermore, the extremal rays of COP
d
have been fully characterized for d ≤ 5, divided into classes,
but this also remains an open problem for higher d [38].
In Appendix B we discuss exposedness properties of the sets of completely positive and co-positive
matrices and their relation to the separability problem and its geometry.
Examples of entangled PPTDS states for d = 5. – Let us provide an example of a bipartite
PPTDS entangled state for d = 5.
˜
M(ρ) =
1 1 0 0 1
1 2 1 0 0
0 1 2 1 0
0 0 1 1 1
1 0 0 1 3
. (20)
It can be easily seen using the Range criterion, as in Section C.2, that ρ is entangled. By Theorem
3.1, it is equivalent to show [38] that M (ρ) ∈ DNN
5
\ CP
5
.
Finally, it can be appreciated how the Horn matrix can be used as an EW and certify entanglement
Tr(H
˜
M(ρ)) = −1 < 0.
4.2 Sufficient separability conditions for diagonal symmetric states
In the spirit of best separable approximations (BSA) [24], in this section we provide sufficient sepa-
rability conditions for bipartite PPTDS states. In the same way that the BSA allows one to express
any PPTDS state as a sum of a separable part and an entangled one with maximal weight on the
separable one
10
. In this section we introduce Best Diagonal Dominant (BDD) approximations, which
give a sufficient criterion to certify that a PPTDS state is separable. The idea is that although checking
membership in CP
d
is NP-hard, it is actually easy to (i) characterize the extremal elements in CP
d
(cf. Corollary 3.1) and (ii) check for membership in a subset of DD
d
⊆ CP
d
that is formed of those
matrices A ∈ N
d
that are diagonal dominant. In [52] the inclusion DD
d
⊆ CP
d
was proven. Therefore,
to show that CP
d
\DD
d
is nonempty we study when the decomposition of a potential element in CP
d
as a convex combination of an extremal element of CP
d
and an element of DD
d
is possible (see Figure
4).
Let us start by stating a lemma that gives an explicit separable decomposition of a quantum state.
Lemma 4.1. Let I be the unnormalized quantum state defined as
I =
d−1
X
i=0
|iiihii| +
X
0≤i<j<d
2|D
ij
ihD
ji
|, (21)
where |D
ij
i = (|iji + |jii)/
√
2. For instance, for d = 3,
I =
1 · · · · · · · ·
· 1 · 1 · · · · ·
· · 1 · · · 1 · ·
· 1 · 1 · · · · ·
· · · · 1 · · · ·
· · · · · 1 · 1 ·
· · 1 · · · 1 · ·
· · · · · 1 · 1 ·
· · · · · · · · 1
. (22)
10
In [25], the BSA was found analytically for N-qubit DS states
Accepted in Quantum 2017-12-28, click title to verify 10
Figure 4: Given a two-qudit PPTDS state ρ, if we can decompose M(ρ) in terms of M (I) (an extremal element of
CP
d
) and M(˜ρ) (an element of DD
d
) we can certify that M(ρ) is in CP
d
and therefore certify that ρ is separable.
Then, I is separable.
Proof. – Let |e(~ϕ)i = |0i + e
ϕ
1
|1i+ ···+ e
ϕ
d−1
|d −1i. A separable decomposition of I is given by
I =
Z
[0,2π]
d
d~ϕ
(2π)
d
(|e(~ϕ)ihe(~ϕ)|)
⊗2
. (23)
Indeed,
I =
X
ijlk
|ijihkl|
Z
[0,2π]
d
d~ϕ
(2π)
d
e
(ϕ
i
+ϕ
j
−ϕ
k
−ϕ
l
)
=
X
ijlk
|ijihkl|(δ
i,k
δ
j,l
+ δ
i,l
δ
j,k
− δ
i,j,k,l
), (24)
where δ is the Kronecker delta function.
Lemma 4.1 allows us to give a sufficient condition for a state ρ to be separable. The idea is to
subtract εI from ρ in such a way that it remains a valid diagonal symmetric state, PPT, and close
enough to the interior of the separable set such that it is easy to certify that the state is separable (see
Fig. 4).
Theorem 4.1. Let ρ be a two-qudit PPTDS state with associated M(ρ). If there exists ε ≥ 0 such
that
1. ε ≤ ρ
ij
for all i, j such that 0 ≤ i, j < d.
2. εd ≤ (hu|
1
M(ρ)
|ui)
−1
and |ui ∈ R(M(ρ)), R(M(ρ)) is the range of M(ρ) and
1
M(ρ)
is the pseudo-
inverse of M(ρ). Here |ui is a normalized vector of ones.
3. for all i such that 0 ≤ i < d, ρ
ii
+ ε(d − 2) ≥
P
j6=i
ρ
ji
.
Then, ρ is separable.
See the proof in Appendix D.2.
A few comments are in order: The first condition on Theorem 4.1 ensures that I can be subtracted
from ρ and ˜ρ will remain in the DS subspace. The second condition requires that I can be subtracted
from ρ while maintaining the PPT property of ˜ρ. If |ui /∈ R(M(ρ)), then ˜ρ would not be PPT for any
ε 6= 0. Therefore, the second condition gives the maximal value of ε that can be subtracted such that ˜ρ
remains PPT. Finally, the third condition relies on guaranteeing that ˜ρ is separable, which is ensured
by M(˜ρ) to be diagonal dominant. This means that one might need to subtract a minimal amount of
I to accomplish such a property (unless ρ is already diagonal dominant).
In Example D.3 we show that CP
d
\ DD
d
6= ∅ using the approach of Theorem 4.1.
The above result can be now normalized and generalized to any other extremal element I in CP
d
:
Accepted in Quantum 2017-12-28, click title to verify 11
Lemma 4.2. Let x ∈
d
with x
i
≥ 0 and ||x|| > 0. Let I
x
be the quantum state defined as
I
x
=
1
||x||
2
1
d−1
X
i=0
x
2
i
|iiihii| +
X
0≤i<j<d
2x
i
x
j
|D
ij
ihD
ij
|
.
Then, the quantum state I
x
is separable.
See the proof in Appendix D.4.
Note that the corresponding M(I
x
) is given by |u
x
ihu
x
|, where |u
x
i = x/||x||
1
. The sum of the
elements of M(I
x
) is then one; i.e., ||M(I
x
)||
1
= 1.
Lemma 4.2 allows us to give a sufficient condition for a state ρ is separable. This time the idea is
to decompose ρ as a convex combination between I
x
, which is a state that is extremal in the set of
separable DS states, and a state ˜ρ which is deep enough in the interior of the set of separable states,
such that we can certify its separability by other means (by showing that M(˜ρ) is diagonal dominant
and doubly non-negative; therefore completely positive [52]).
Theorem 4.2. Let ρ be a two-qudit PPTDS state with associated M(ρ). Let x ∈
d
with x
i
> 0. If
there exists a λ ∈ [0, 1) such that
1. λ ≤ (M(ρ))
ij
||x||
2
1
/x
i
x
j
for all i and j,
2. λ ≤ 1/hu
x
|
1
M(ρ)
|u
x
i and |u
x
i ∈ R(M(ρ)), where R(M(ρ)) is the range of M(ρ) and
1
M(ρ)
denotes
the pseudo-inverse of M(ρ),
3. λx
i
(||x||
1
− 2x
i
) ≥ ||x||
2
1
h
P
j6=i
(M(ρ))
ij
− (M(ρ))
ii
i
for all i,
then ρ is separable. Equivalently, then M(ρ) is completely positive.
See the proof in Appendix D.5 (i.e., write ρ = (1 −λ)˜ρ + λI
x
and ensure that the associated M (˜ρ)
is completely positive).
Notice that Theorem 4.2 provides an advantage over Theorem 4.1 since the parameters of I
x
are not
fixed which allows to consider a bigger family of decompositions M(ρ) ∈ CP
d
parametrized by x. In
Example 4.2 we attempt to apply both Theorems in order to guarantee separability and illustrate such
advantage.
Example. – In this example we provide a PPTDS state with associated M(ρ) ∈ CP
d
\DD
d
and we
show how to apply Theorem 4.2 to guarantee separability. Furthermore, we also apply Theorem 4.1
to illustrate the advantage of Theorem 4.2.
Take the following DS state ρ ∈
3
with associated
M(ρ) =
α β γ
β δ β
γ β
=
1
100
19 8 11.5
8 6.4 8
11.5 8 19.6
, (25)
where it can be checked that the state ρ is normalized. A priori we do not know if this state is
separable, the goal is to apply Theorems 4.1 and 4.2 in order to see if separability can be guaranteed.
For both Theorems the more restrictive between conditions 1 and 2 provides an upper bound for the
corresponding decomposition and condition 3 a lower bound but, as mentioned, Theorem 4.2 offers
more flexibility since such bound can be varied by fitting I
x
. This example illustrates this fact since
we will see that Theorem 4.2 guarantees separability but Theorem 4.1 does not.
Lets start with Theorem 4.2. For the given case (25) we want to find if a convex decomposition
M(ρ) = (1 − λ)M(˜ρ) + λM (I
x
) exists while fulfilling the conditions of the theorem. For instance,
for illustrative purposes we fix λ = 0.8 and by numerical means we obtain that a possible convex
combination would be with an M(I
x
) = |u
x
ihu
x
| given by |u
x
i = 1/100(37.46|0i+ 25.16|1i+ 37.38|2i).
Accepted in Quantum 2017-12-28, click title to verify 12
Lets proceed to show that the given M(ρ) and M(I
x
) meet the conditions of Theorem 4.2. Condition
1 provides the more restrictive upper bound given by
λ ≤
γ||x||
2
1
x
1
x
3
= 0.8213, (26)
while the lower bound will be given by the following case of Condition 3
λ ≥
||x||
2
1
[2β − δ]
x
2
(||x||
1
− δ)
= 0.7681. (27)
Therefore, there exists a range of values λ ∈ [0.7681, 0.8213] that satisfy the conditions of Theorem
4.2 and certifies that the state ρ is separable. Notice that, for illustrative purposes, once we found an
M(I
x
) fulfilling the conditions we fixed it to find a range of values for λ but we could have allowed for
more freedom and find a bigger range of possible decompositions.
Now lets see what happens with Theorem 4.1. In this case the most restrictive upper bound is
given by Condition 2
ε ≤ (hu|
1
M(ρ)
|ui)
−1
= 0.06, (28)
while the most restrictive lower bound will be given by the following case of Condition 3
ε ≥ 2β − δ = 0.096. (29)
Thus, for this case there does not exist an ε satisfying the conditions for Theorem 4.1, while there
exists a range of λ satisfying conditions for Theorem 4.2 and therefore illustrating its advantage by
being able to certify separability.
5 A class of PPT-entangled quasi-DS states
In this Section, we introduce a uni-parametric class of N -qubit PPTESS, for an odd number of qubits.
As it has been shown in [27, 28], N-qubit PPTDS states are fully separable. The class we introduce
can be seen as a N-qubit PPTDS state with slight GHZ coherences. Surprisingly, in the family of
states we provide, an arbitrarily small weight on the non-diagonal elements (in the Dicke basis) allows
the state to be genuinely multipartite entangled while maintaining the PPT property.
The procedure we have chosen to derive this class of states is based on the iterative algorithm for
finding extremal PPT symmetric states [20, 21] (see also [53]), which we briefly recall here in the interest
of completeness. One starts with an initial symmetric state ρ
0
that is fully separable; for instance,
the symmetric completely mixed state. Then, one picks a random direction σ
0
in the set of quantum
states and subtracts it from the initial state while preserving the PPT property, therefore obtaining
ρ
0
−x
0
σ
0
, x
0
> 0. One necessarily finds a critical x
∗
0
such that one arrives at the boundary of the PPT
set, where the rank of ρ
0
−x
∗
0
σ
0
or one of its partial transpositions must have decreased. Hence, at least
one new vector appears in the kernel of the state or in the kernel of some of its partial transpositions.
This state with lower ranks is set as the initial state for the next iteration ρ
1
= ρ
0
− x
∗
0
σ
0
. The new
direction σ
1
is chosen such that it preserves all the vectors present in the kernels of both the state
and its partial transpositions. This process is repeated until no new improving direction can be found,
yielding an extremal state ρ
k
in the PPT set. As the PPT set contains all separable states, we note
that if the rank of such extremal PPT state is greater than one, then it cannot be extremal in the set
of separable states (because these are pure product vectors, which have rank one), therefore it must
be entangled. The study carried out in [20, 21] looked for typical extremal PPT states by exploring
random directions every time. However, by carefully picking these directions, one can look for classes
of states of different forms, such as the ones presented in Theorem 5.1.
In Example E.1 we present a 4-qubit PPT-entangled symmetric state whose density matrix is sparse
with real entries when represented in the computational basis and has a closed analytical form.
Accepted in