---
abstract: 'The positive partial transpose test is one of the main criteria for detecting entanglement, and the set of states with positive partial transpose is considered as an approximation of the set of separable states. However, we do not know to what extent this criterion, as well as the approximation, are efficient. In this paper, we show that the positive partial transpose test gives no bound on the distance of a density matrix from separable states. More precisely, we prove that, as the dimension of the space tends to infinity, the maximum trace distance of a positive partial transpose state from separable states tends to $1$. Using similar techniques, we show that the same result holds for other well-known separability criteria such as reduction criterion, majorization criterion and symmetric extension criterion. We also bring evidence that the set of positive partial transpose states and separable states have totally different shapes.'
author:
- |
    Salman Beigi[^1] Peter W. Shor[^2]\
    *[Department of Mathematics, Massachusetts Institute of Technology]{}*
title: Approximating the Set of Separable States Using the Positive Partial Transpose Test
---

Introduction
============

The problem of detecting entanglement has been focused in quantum information theory for many years. The problem is: given a bipartite mixed state $\rho_{AB}$, decide whether this state is entangled or separable. The first attack toward solving this problem is the following observation due to Peres and the Horodeckis, [@peres; @23]. If $\rho_{AB}=\sum_i
p_i\,\rho_{A_i}\otimes \rho_{B_i} $ is separable, then $[\rho_{AB}]^{T_B}=\sum_i p_i\rho_{A_i}\otimes [\rho_{B_i}]^T$, where $M^T$ denotes the transpose of matrix $M$, is also a quantum state, and thus is a positive semi-definite matrix. Therefore, if $\rho_{AB}$ is separable, its partial transpose, $[\rho_{AB}]^{T_B}$, should be positive semi-definite. The Horodeckis have proved that this criterion characterizes all separable states in dimensions $2\times 2$ and $2\times 3$, [@23]. However, there are entangled states in dimension $3\times 3$ with a positive partial transpose, [@bound].

Although the set of positive partial transpose states (PPT states) does not coincide with the set of separable states, it is usually considered as an approximation of this set. For example in [@distance] the distance of an arbitrary state from PPT states has been computed to estimate the distance from separable states. Also in [@geometry] the geometry of the set of PPT states has been studied to understand the properties of the set of separable states. However, we do not know how efficient these approximations are. For instance, given an upper bound on the distance of a state from PPT states, does it give an upper bound on the distance of the state from separable states?

We can think of this problem in the point of view of complexity theory. Gurvits [@gurvits] has proved that given a bipartite density matrix $\rho_{AB}$, it is $\NP$-hard to decide whether this state is separable or entangled. An approximate formulation of this problem is the following. Given a bipartite density matrix $\rho_{AB}$ and $\epsilon>0$, decide whether there exists a separable state in the $\epsilon$-neighborhood (in trace distance) of $\rho_{AB}$. Gurvits has established a reduction from Knapsack to this problem, and has proved the $\NP$-hardness of the separability problem only for exponentially small $\epsilon$. However, as mentioned in [@salman], we can replace Knapsack with 2-out-of-4-SAT, and get to the $\NP$-hardness for an inverse polynomial $\epsilon$. Also, Gharibian [@sevag] has shown the same result using a reduction from the Clique problem. Now, the question is that how large $\epsilon$ can be while getting to the same result. For example, is there an efficient algorithm to decide whether the distance of a given state from separable states is less than $1/3$, or it is an $\NP$-hard problem? Equivalently, is there a separability test such that if a state passes the test then it is $1/3$-close to the set of separable states?

The converse of this question is what we are looking for. That is, given a separability criterion, if a state passes this test can we claim a non-trivial upper bound on the distance of this state from separable states? In this paper, we prove that the answer for the PPT criterion, as well as other well-known separability tests such as reduction criterion [@reduction], majorization criterion [@majorization] and symmetric extension criterion [@symmetric1; @symmetric2], is no. More precisely, we prove the following theorem.

\[thm:main\] Let $\mathcal{H}$ be a bipartite Hilbert space. If the dimension of each subsystem of $\mathcal{H}$ is large enough, there exists a PPT state acting on $\mathcal{H}$ whose trace distance from separable states is greater than $1-\epsilon$, for an arbitrary $\epsilon >0$.

Main Ideas
----------

Let $\mathcal{H}=\mathcal{H}^A \otimes \mathcal{H}^B$ be a bipartite Hilbert space. We want to find PPT states $\rho^{(n)}
\in \mathcal{H}^{\otimes n}$ such that the trace distance of $\rho^{(n)}$ from separable states is close to 1, for enough large numbers $n$. Suppose $\rho$ is an entangled PPT state. Then $\rho^{\otimes n}$ is entangled and also PPT. We claim that the sequence of states $\rho^{(n)}=\rho^{\otimes n}$ works for us. The intuition is that for two different quantum states $\rho$ and $\sigma$, the trace distance of $\rho^{\otimes n}$ and $\sigma^{\otimes n}$ tends to 1 as $n$ tends to infinity. However, in this problem $\sigma$ is not a fixed state and ranges over all separable states. Also, it is not obvious (and may not hold)[^3] that the closest separable state to $\rho^{\otimes n}$ is of the form $\sigma^{\otimes n}$.

Another idea is to use entanglement distillation. Suppose the state $\rho$ is distillable. It means that, having arbitrary many copies of $\rho$, using an LOCC map, we can obtain arbitrary many EPR pairs. Notice that LOCC maps send separable states to separable states, and the trace distance decreases under trace preserving quantum operations. Therefore, the distance of $\rho^{\otimes n}$ from separable states is bounded from below by the distance of EPR$^{\otimes m}$ from separable states, which we know is close to 1 for large numbers $m$. Therefore, if $\rho$ is distillable then the trace distance of $\rho^{\otimes n}$ from separable states tends to 1.

It is well-known that PPT states are not distillable under LOCC maps. So we cannot use this idea directly. On the other hand, in this argument, the only property of LOCC maps that we use, is that they send separable states to separable states. So, we may replace LOCC maps with [*non-entangling maps*]{}, the maps that send every separable state to a separable state. Due to the seminal work of Brandao and Plenio [@brandao1; @brandao2] every entangled state is distillable under [*asymptotically*]{} non-entangling maps[^4]. Hence, by replacing LOCC maps with asymptotically non-entangling maps and repeating the previous argument, we conclude that the trace distance of $\rho^{\otimes
n}$ from separable states tends to 1.

Although this idea gives a full proof of Theorem \[thm:main\], we do not present it in this paper. Instead, we use more fundamental techniques, namely, [*quantum state tomography*]{} and [*quantum de Finetti theorem*]{} [@renner; @povm]. In fact, these two techniques are the basic ideas of the results of [@brandao1; @brandao2] that we mentioned above. Since $\rho^{\otimes (n+k)}$ is a symmetric state, we may assume that the closest separable state to $\rho^{\otimes (n+k)}$ is also symmetric. Then by tracing out $k$ registers[^5] and using the finite quantum de Finetti theorem we conclude that the trace distance of $\rho^{\otimes (n+k)}$ from separable states is lower bounded by the trace distance of $\rho^{\otimes n}$ from separable states of the form

$$\label{eq:1}
\sum_i p_i\, \sigma_i^{\otimes n}.$$

Since such a state is separable and $\rho$ is not separable, the sum of $p_i$’s for which $\sigma_i$ is close to $\rho$ cannot be large. On the other, if $n$ is large, using quantum state tomography one can distinguish $\rho^{\otimes n}$ from $\sigma_i^{\otimes n}$, where $\sigma_i$ is far from $\rho$. Therefore, the trace distance of $\rho^{\otimes n}$ and a separable state of the form of Eq. (\[eq:1\]) is close to $1$ for enough large $n$.

Notice that, in both of these arguments the only property of PPT states that we use, is that if $\rho$ and $\sigma$ are PPT, then $\rho \otimes \sigma$ is also PPT. So, we can conclude the same result for any separability test the satisfies this property.

Preliminaries {#sec:prel}
=============

A pure state $\vert \psi\rangle \in \mathcal{H}^A \otimes
\mathcal{H}^B$ is called [*separable*]{} if it can be written of the form $\vert \psi\rangle = \vert \psi_A\rangle \otimes \vert
\psi_B \rangle$, where $\vert \psi_A\rangle \in \mathcal{H}^A$ and $\vert \psi_B\rangle \in \mathcal{H}^B$. A density matrix acting on $\mathcal{H}^A \otimes \mathcal{H}^B$ is called separable if it can be written as a convex combination of separable pure states $\vert \psi\rangle\langle \psi\vert$. We denote the set of separable states by $\SEP$.

For two quantum states $\rho$ and $\sigma$ we denote their trace distance by

$$\label{eq:tr-dist}
\|\rho - \sigma\|_{\Tr}=\frac{1}{2}\, \Tr | \rho - \sigma |,$$

where $|X|= \sqrt{X^{\dagger}X}$.

Assume that $\dim \mathcal{H}_A=\dim \mathcal{H}_B=d$, and fix an orthonormal basis $\vert 1\rangle, \dots ,\vert d\rangle$ for both of Hilbert spaces. Then the partial transpose of matrices acting on $\mathcal{H}^A \otimes \mathcal{H}^B$ is a linear map defined by $(M_A\otimes N_B )^{T_B}=M_A\otimes N_B^T$. It is clear that if $\rho_{AB}$ is a separable state then $\rho_{AB}^{T_B}$ is also a density matrix and then positive semi-definite. However, it does not hold for an arbitrary state. For example, the partial transpose of the maximally entangled state is not positive semi-definite. To see that, let $\Phi(d)$ to be the maximally entangled state on $\mathcal{H}$

$$\label{eq:epr} \Phi(d)=\frac{1}{d}\sum_{i,j=1}^d \vert i,i\rangle \langle j,
j\vert.$$

We have

$$\begin{aligned}
\Phi(d)^{T_B} & = & \frac{1}{d} \sum_{i,j} \vert i\rangle \langle
j\vert \otimes \vert j\rangle\langle i\vert \\
& = & \frac{1}{d}I -\frac{1}{d} \sum_{i\neq j} \vert i\rangle
\langle i\vert \otimes \vert j\rangle \langle j\vert
+\frac{1}{d}\sum_{i\neq j} \vert i\rangle \langle j\vert \otimes
\vert j\rangle \langle i\vert\\
& = & \frac{1}{d}I - \frac{2}{d} \sum_{i<j} \vert
\phi_{ij}\rangle \langle \phi_{ij}\vert,\end{aligned}$$

where

$$\label{eq:phi}
\vert \phi_{ij}\rangle=\frac{1}{\sqrt{2}}(\vert i\rangle\vert
j\rangle -\vert j\rangle \vert i\rangle).$$

Therefore, positive partial transpose is a test to detect entanglement [@peres; @23]. More formally, if we denote the set of density matrices with a positive semi-definite partial transpose by PPT, then $\SEP\subseteq\PPT$.

Here is a list of some other separability criteria, see [@survey].

-   Reduction criterion, [@reduction]: $I\otimes \rho_B \geq
    \rho_{AB}$, where $\rho_{B}=\Tr_{A} (\rho_{AB})$. Here, by $M\geq
    N$ we mean $M-N$ is a positive semi-definite matrix.

-   Entropic criterion, [@entropic]: $S_\alpha(\rho_{AB}) \geq S_\alpha(\rho_A)$ for $\alpha=2$ and in the limit $\alpha \rightarrow 1$, where $S_\alpha(\rho)=\frac{1}{1-\alpha}\log \Tr(\rho^\alpha)$.

-   Majorization criterion, [@majorization]: $\lambda_{\rho_{A}}^\downarrow \succ   \lambda_{\rho_{AB}}^\downarrow
    $, where $\lambda_\rho^\downarrow$ is the list of eigenvalues of $\rho$ in non-increasing order, and $y \succ x$ means that, for any $k$, the sum of the first $k$ entries of list $x$ is less than or equal to that of list $y$.

-   Cross norm criterion, [@cross1; @cross2]: $\Tr |
    \mathcal{U}(\rho_{AB})|\, \leq 1$, where $\mathcal{U}$ is a linear map defined by $\mathcal{U}(M\otimes N)=v(M)v(N)^T$, relative to a fixed basis, and $v(X)=(col_1(X)^T, \dots , col_{d}(X)^T )^T$, where $col_i(X)$ is the $i$-th column of $X$.

All of these criteria for separability are necessary conditions but not sufficient. Doherty et al. [@symmetric1; @symmetric2] have introduced a hierarchy of separability criteria which are both necessary and sufficient. Let $\rho_{AB}=\sum_i p_i\,
\sigma_i\otimes \tau_i$ be a separable state. Then

$$\rho_{AB_1B_2\cdots B_k} = \sum_i p_i\,
\sigma_i\otimes \tau_i^{\otimes k}$$ is an extension of $\rho^{AB}$, meaning that $\rho_{AB}=\Tr_{B_2\cdots B_k}
(\rho_{AB_1\cdots B_k})$. Also it is symmetric, meaning that it is unchanged under any permutation of subsystems $B_i$. More precisely, for any permutation $\pi$ of $k$ objects, if we define the linear map $P_\pi$ by $P_\pi \vert \psi_1\rangle \otimes
\cdots \otimes \vert \psi_k\rangle = \vert \psi_{\pi(1)}\rangle
\otimes \cdots \otimes \vert \psi_{\pi(k)}\rangle$, we have

$$\label{eq:symmetric} P_{\pi}^{B_1\dots B_k}\, \rho_{AB_1B_2\cdots B_k}\,
P_{\pi}^{B_1\dots B_k}= \rho_{AB_1B_2\cdots B_k}.$$

If such an extension exists, we say that $\rho_{AB}$ has a symmetric extension to $k$ copies. Doherty el al. have proved that a quantum state is separable iff it has a symmetric extension to $k$ copies for any number $k$, [@symmetric1; @symmetric2]. Also, they have shown that the problem of checking whether a given state has a symmetric extension to $k$ copies, for a fixed $k$, can be expressed as a semi-definite programming, and can be solved efficiently[^6]. So we get to another separability test.

-   Symmetric extension criterion: If $\rho_{AB}$ is separable, then it has a symmetric extension to $k$ copies.

Quantum State Tomography {#sec:tomography}
------------------------

An informationally complete POVM on $\mathcal{H}$ is a set of positive semi-definite operators $\{M_n\}$ forming a basis for the space of hermitian matrices on $\mathcal{H}$, and such that $\sum_n M_n=I$. In [@povm] there is an explicit construction of an informationally complete POVM in any dimension. Such a POVM is useful for quantum state tomography.

Suppose $\{M_n^*\}$ is the dual of basis $\{M_n\}$. That is $\Tr(M_nM_m^*)=\delta_{mn}$, where $\delta_{mn}$ is the Kronecker delta function. For any hermitian operator $X$ we have

$$X=\sum_n \Tr(XM_n)\,M_n^*.$$ Therefore, having some copies of the state $\rho$, by measuring $\rho$ using the POVM $\{M_n\}$, we can approximate $\Tr(\rho
M_n)$ and then find the matrix representation of $\rho$.

Assume that $\mathcal{H}=\mathcal{H}^A\otimes \mathcal{H}^B$ is a bipartite Hilbert space. If $\{P_n\}$ and $\{Q_m\}$ are informationally complete POVM’s on $\mathcal{H}^A$ and $\mathcal{H}^B$, respectively, then it is easy to see that $\{P_n\otimes Q_m\}$ is an informationally complete POVM on $\mathcal{H}$. Therefore, if the state $\rho_{AB}$ is shared between two far apart parties $A$ and $B$, they still can perform quantum state tomography. Also, if the state $\rho_{AB}$ is separable, then all the states during the process are separable as well.

Quantum de Finetti Theorem
--------------------------

As in Eq. (\[eq:symmetric\]), a quantum state $\rho^{(n)}$ acting on $\mathcal{H}^{\otimes n}$ is called symmetric if $P_\pi
\rho^{(n)} P_\pi=\rho^{(n)}$ for any permutation $\pi$ of $n$ objects. A symmetric state is called [*$k$-exchangeable*]{} if it has a symmetric extension to $n+k$ registers. That is a symmetric state $\rho^{(n+k)}$ such that $\Tr_{1,\dots,k}\rho^{(n+k)}=\rho^{(n)}$. Clearly, any state of the form $\rho^{\otimes n}$ is $k$-exchangeable, for any $k$. Also any convex combination of these states is $k$-exchangeable. [*Quantum de Finetti theorem*]{} says that the converse of this observation holds. That is, if a state is $k$-exchangeable, for any $k$, it is in the convex hall of symmetric product states.

Quantum de Finetti theorem gives a characterization of infinitely-exchangeable states. The following theorem, known as the finite quantum de Finetti theorem, says that if a state is $k$-exchangeable (but not necessarily $(k+1)$-exchangeable), then an approximation of the above result holds.

\[thm:fqdt\] [@renner] Assume that $\rho^{(n+k)}$ is a symmetric state acting on $\mathcal{H}^{\otimes {n+k}}$. Let $\rho^{(n)}=\Tr_{1\dots k}\,\rho^{(n+k)}$ be the state obtained by tracing out the first $k$ registers. Then there exists a probability measure $\mu$ on the set of density matrices on $\mathcal{H}$ such that

$$\| \rho^{(n)} - \int \mu(d\sigma)\sigma^{\otimes n}\|_{\Tr}
\,\leq 2\dim\mathcal{H}\,\frac{n}{n+k}.$$

Proof of Theorem \[thm:main\] {#sec:proof}
=============================

Let $\mathcal{H}=\mathcal{H}^A\otimes \mathcal{H}^B$ and assume that $d = \dim \mathcal{H} > 6$. Then there exists a PPT state $\rho_{AB}=\rho$ acting on $\mathcal{H}$ which is not separable ( For example see [@bound]). Let

$$\label{eq:dist} \epsilon=\min_{\sigma\in \SEP} \|\rho
- \sigma\|_{\Tr}.$$

Since $\rho$ is not separable, $\epsilon > 0$.

For any number $n$, $\rho^{\otimes n}$ can be considered as a bipartite state acting on $(\mathcal{H}^A)^{\otimes n }\otimes
(\mathcal{H}^B)^{\otimes n }$, and it is a PPT state. Therefore, if we prove that the trace distance of $\rho^{\otimes n }$ from separable states tends to $1$, as $n$ goes to infinity, we are done.

Let $\sigma^{(n)}$ be the closest separable state to $\rho^{\otimes n}$. Since $\rho^{\otimes n}$ is a symmetric state, for any permutation $\pi$ we have

$$\|\rho^{\otimes n} - P_{\pi}\sigma^{(n)} P_{\pi}\|_{\Tr} = \|\rho^{\otimes n} - \sigma^{(n)}\|_{\Tr}.$$ Hence, by triangle inequality

$$\|\rho^{\otimes n} - \frac{1}{n!}\sum_{\pi}P_{\pi}\sigma^{(n)}
P_{\pi}\|_{\Tr} \leq  \frac{1}{n!} \sum_{\pi} \|\rho^{\otimes n} -
P_{\pi}\sigma^{(n)} P_{\pi}\|_{\Tr}= \|\rho^{\otimes n} -
\sigma^{(n)}\|_{\Tr},$$ and then $\|\rho^{\otimes n} -
\frac{1}{n!}\sum_{\pi}P_{\pi}\sigma^{(n)} P_{\pi}\|_{\Tr} =
\|\rho^{\otimes n} - \sigma^{(n)}\|_{\Tr}$. This means that, we may assume that the closest separable state to $\rho^{\otimes n}$ is symmetric.

Let $\sigma^{(n+n^2)}$ be the closest symmetric separable state to $\rho^{\otimes (n+n^2)}$, and let $\Tr_{1\dots n^2}\,
\sigma^{(n+n^2)}$ be the state obtained by tracing out $n^2$ registers. We have

$$\label{eq:10}\| \rho^{\otimes (n+n^2)} -  \sigma^{(n+n^2)} \|_{\Tr}\, \geq
\, \| \rho^{\otimes n} - \Tr_{1\dots n^2}\,
\sigma^{(n+n^2)}\|_{\Tr}.$$

Using the finite quantum de Finetti theorem (Theorem \[thm:fqdt\]), there exists a measure $\mu$ such that

$$\label{eq:xn} \Tr_{1\dots n^2}\, \sigma^{(n+n^2)} = \int
\mu(d\tau)\tau^{\otimes n} + X_n,$$

where $\|X_n\|_{\Tr}\leq 2d\,\frac{n}{n+n^2}$. Hence, using Eq. (\[eq:10\]), if we prove that $\| \rho^{\otimes n} - \big(\int
\mu(d\tau)\tau^{\otimes n} + X_n\big) \|_{\Tr}$ tends to $1$, as $n$ goes to infinity, we are done. Consider an informationally complete POVM on $\mathcal{H}^A$ and $\mathcal{H}^B$, and by taking their pairwise tensor product extend them to an informationally complete POVM on $\mathcal{H}$. Now apply quantum state tomography on $(n-1)$ copies of $\rho$. The outcomes of the measurements give an approximation of $\rho$. To be more precise, let $\{ M_i \}$ be the informationally complete POVM on $\mathcal{H}$. For any sequence of outcomes $(M_{l_1}, \dots ,M_{l_{(n-1)}})$ we get to the approximation

$$\label{eq:tomog-approximation}
\sum_i \frac{r_i}{n-1}M_i^{\ast},$$

where $r_i$ is the number of repetition of $M_i$ in $(M_{l_1},
\dots ,M_{l_{(n-1)}})$. Let $A_n$ be the sum of $(n-1)$-tuple tensor products $M_{l_1}\otimes \cdots M_{l_{(n-1)}}$ for sequences $(M_{l_1}, \dots ,M_{l_{(n-1)}})$ whose approximations, according to Eq. (\[eq:tomog-approximation\]), are in $B_{\epsilon/2}(\rho)$, the ball of radios $\epsilon/2$ in trace distance around $\rho$. Therefore, by the law of large numbers [@dudley], $\Tr(A_n \rho^{\otimes (n-1)}) \rightarrow 1 $ as $n$ goes to infinity. Also for any $\tau$ far from $\rho$, $\Tr(A_n \tau^{\otimes (n-1)})$ tends to zero.

Notice that $A_n\leq I$. Hence, $$\|
\rho^{\otimes n} - \big( \int \mu(d\tau)\tau^{\otimes n} + X_n
\big) \|_{\Tr} \geq \Tr\, ( I\otimes A_n \cdot \rho^{\otimes n} )
- \Tr \big[ (I\otimes A_n) \cdot \big(\int \mu(d\tau)\tau^{\otimes
n} + X_n\big) \big],$$ and since $\Tr\, ( I\otimes A_n \cdot
\rho^{\otimes n} ) \rightarrow 1$, if we prove that $$\Tr \big[ (I\otimes
A_n) \cdot (\int \mu(d\tau)\tau^{\otimes n} + X_n) \big]
\rightarrow 0,$$ as $n$ goes to infinity, we are done.

By Eq. (\[eq:xn\]), $\int \mu(d\tau)\tau^{\otimes n} + X_n$ is a separable state. Also, since we can apply quantum state tomography locally (see Section \[sec:tomography\] ), at the end the outcome is a separable state. We can write the outcome, before normalization, in the form $$\int \mu(d\tau)\Tr[A_n\tau^{\otimes (n-1)}]\,\tau + \widetilde{X}_n,$$ where $\|\widetilde{X}_n\|_{\Tr} \leq 2d\,\frac{n}{n+n^2}$. Let

$$Y_n = \int_{\tau\notin B_{\epsilon/2}(\rho)} \mu(d\tau)\Tr[A_n\tau^{\otimes
(n-1)}]\,\tau +\widetilde{X}_n ,$$ and

$$c_n= \int_{\tau\in B_{\epsilon/2}(\rho)} \mu(d\tau)\Tr[A_n\tau^{\otimes
(n-1)}].$$ By the law of large numbers [@dudley] there exists $\delta_n$ such that for any $\tau\notin B_{\epsilon/2}(\rho)$ we have

$$\Tr [A_n\cdot \tau^{\otimes (n-1)}]\leq \delta_n,$$ and $\delta_n \rightarrow 0$ as $n$ goes to infinity. Then $\|Y_n\|_{\Tr}\leq \delta_n + 2d\frac{n}{n+n^2}$.

Now, the state

$$\widetilde{\tau}= \frac{1}{c_n+\Tr (Y_n)} \big[   \int_{\tau\in
B_{\epsilon/2}(\rho)} \mu(d\tau)\Tr[A_n\tau^{\otimes (n-1)}]\,\tau
+ Y_n \big]$$ is separable. On the other hand, by definition $$\widetilde{\rho}= \frac{1}{c_n} \int_{\tau\in
B_{\epsilon/2}(\rho)} \mu(d\tau)\Tr[A_n\tau^{\otimes (n-1)}]\,\tau$$ is in the $\epsilon/2$-neighborhood of $\rho$. Using Eq. (\[eq:dist\]) we have

$$\begin{aligned}
\epsilon & \leq & \| \rho - \widetilde{\tau} \|_{\Tr}\\
& \leq & \frac{c_n}{c_n+\Tr(Y_n)} \cdot\| \rho
-\widetilde{\rho}\|_{\Tr} +
\frac{|\Tr(Y_n)|}{c_n+\Tr(Y_n)}\cdot\|\rho\|_{\Tr}+
\frac{1}{c_n+\Tr(Y_n)}\cdot\|Y_n\|_{\Tr}\\
& \leq & \frac{c_n}{c_n+\Tr(Y_n)} \cdot \frac{\epsilon}{2} +
\frac{2}{c_n+\Tr(Y_n)}\cdot\|Y_n\|_{\Tr}.\end{aligned}$$

Hence, $$\epsilon c_n + \epsilon \Tr(Y_n) \,\leq \, \frac{\epsilon}{2}c_n + 2\|Y_n\|_{\Tr},$$ and then $$c_n\,\leq \, \frac{2(2+\epsilon)\|Y_n\|_{\Tr}}{\epsilon} \,\leq \, 6 \epsilon^{-1} [\delta_n+ 2d\frac{n}{n+n^2}].$$

Putting everything together we find that

$$\begin{aligned}
\Tr \big[ (I\otimes A_n) \cdot (\int \mu(d\tau)\tau^{\otimes n} +
X_n)] & = &\Tr \big[ \int_{\tau\in B_{\epsilon/2}(\rho)}
\mu(d\tau)\Tr[A_n\tau^{\otimes (n-1)}]\,\tau + Y_n \big] \\
& \leq & c_n + \| Y_n \|_{\Tr} \\
& \leq & (6\epsilon^{-1}+1) \cdot ( \delta_n+ 2d\frac{n}{n+n^2}).\end{aligned}$$

Therefore

$$\Tr \big[ (I\otimes A_n) \cdot (\int \mu(d\tau)\tau^{\otimes n} +
X_n)]  \rightarrow 0,$$ as $n$ goes to infinity. We are done.

Geometry of the Set of Separable States
=======================================

Theorem \[thm:main\] tells us that estimating the distance of a bipartite state from separable state by the distance from PPT states is not a good approximation. However, one may say the set of PPT states may be a reasonable approximation for the set of separable states in a geometrical point of view. For instance, two spheres centered at origin with radiuses $1$ and $2$ are far from each other, while they have the same geometric properties up to a scaler factor. In the following theorem we show that the set of separable states relative to the set of PPT states is not of this form.

By Theorem \[thm:main\] the maximum distance of a PPT state from the boundary of the set of separable states is close to $1$. We can think of this problem in another direction. What is the maximum distance of a state on the boundary of separable states from the boundary of PPT states? To get an intuition on this problem, we can think of the unit sphere centered at origin in $\mathbb{R}^n$, and the cube with vertices $(\pm 1, \dots , \pm
1)$. It is easy to see that the distance of any point on the sphere from points of the cube is less than $2$. However, the distance of $(1, \dots , 1)$ from sphere is $\sqrt{n}-1$. It is because sphere and cube have totally different shapes.

\[thm:shape\] Assume that $\mathcal{H}=\mathcal{H}^A\otimes \mathcal{H}^B$, and $\dim \mathcal{H}^A=\dim \mathcal{H}^B=d$. Then for any separable state $\rho$ acting on $\mathcal{H}$ there exists a state $\sigma$ on the boundary of the set of PPT states such that $\|\rho - \sigma \|_{\Tr}  \leq \frac{1}{\sqrt{d}}.$

Let $\sigma$ be an arbitrary PPT state, and $\Phi(d)$ be the maximally entangled state defined in Eq. (\[eq:epr\]). Then the fidelity of $\sigma$ and $\Phi(d)$ is

$$F(\sigma, \Phi(d))=[\Tr\, \sigma\,\Phi(d) ]^{1/2} = [\Tr\, \sigma^{T_B}\,\Phi(d)^{T_B} ]^{1/2} =
[\Tr\, \sigma^{T_B}\, ( \frac{1}{d}I -\frac{2}{d}\sum_{i<j} \vert
\phi_{ij}\rangle \langle \phi_{ij}\vert ) ]^{1/2},$$ where $\vert
\phi_{ij}\rangle $ is defined in Eq. (\[eq:phi\]). Now, using the fact that $\rho^{T_B}$ is positive semi-definite we have

$$F(\sigma, \Phi(d)) \leq \frac{1}{\sqrt{d}}.$$ Therefore, by the well-known inequality between fidelity and trace distance, [@chuang] page 416, we have

$$\label{eq:sqrt} \| \sigma -\Phi(d)\|_{\Tr} \geq 1- F(\sigma, \Phi(d))
\geq 1- \frac{1}{\sqrt{d}}.$$

Let $\rho$ be an arbitrary separable state. Define $\rho_t= (1-t)
\rho + t\Phi(d)$. Then $\rho_0=\rho$ is separable and then PPT, and $\rho_1=\Phi(d)$. Hence, there exists $0 \leq  c \leq 1$ such that $\rho_c$ is on the boundary of PPT states. Then we have $$\|\rho - \rho_c\|_{\Tr} = \|\rho - \Phi(d)\|_{\Tr} -
\|\rho_c - \Phi(d)\|_{\Tr}\leq 1-(1- \frac{1}{\sqrt{d}})=
\frac{1}{\sqrt{d}} ,$$ where in the last inequality we use Eq. (\[eq:sqrt\]).

Generalization to Other Separability Criteria
=============================================

By the result of Section \[sec:proof\], if the dimension of the space is enough large, there exists a PPT state arbitrary far from separable states. In the proof, our candidate for such a state is $\rho^{\otimes n}$, where $\rho$ is an entangled PPT state. Indeed, the only property of the set of PPT states that we use, is that this set is closed under tensor product. Therefore, the same argument as in the proof of Theorem \[thm:main\], gives us the following general theorem.

\[thm:general\] Assume that $C$ is a necessary but not sufficient separability criterion such that if $\rho$ and $\sigma$ satisfy $C$, then $\rho\otimes \sigma$ satisfies $C$ as well. Then for any $\epsilon>0$ there exists a state $\rho$ that satisfies $C$, and whose trace distance from separable states is at least $1-\epsilon$.

Let $\rho$ be an entangled state that satisfies $C$. Then $\rho^{\otimes n}$ satisfies $C$, and by the proof of Theorem \[thm:main\], the trace distance of $\rho^{\otimes n}$ from separable states, tends to $1$ as $n$ goes to infinity.

In the following theorem we prove that all separability criteria mentioned in Section \[sec:prel\] satisfy the assumption of Theorem \[thm:general\].

\[thm:example\] For any of the separability criteria mentioned in Section \[sec:prel\] there exists an entangled state that passes that test while it is arbitrary far, in trace distance, from separable states.

By Theorem \[thm:general\] it is sufficent to prove that those separability criteria are closed under tensor product.

-   Reduction criterion: Let $X, Y, Z$ and $W$ be positive semi-definite matrices such that $X\geq Y$ and $Z\geq W$. Then $(X-Y)\otimes (Z+W)$ and $(X+Y)\otimes (Z-W)$ are positive semi-definite. Therefore $X\otimes Z -Y\otimes W = \frac{1}{2}[
    (X-Y)\otimes (Z+W) + (X+Y)\otimes (Z-W) ]$ is positive semi-definite. It means that if $X\geq Y$ and $Z\geq W$, then $X\otimes Z\geq Y\otimes U$. Now assume that $\rho_{AB}$ and $\sigma_{AB}$ pass reduction criterion. Therefore $\rho_A\otimes
    I \geq \rho_{AB}$ and $\sigma_A\otimes I \geq \sigma_{AB}$, and then $ \rho_{A}\otimes \sigma_A \otimes I \geq \rho_{AB}\otimes
    \sigma_{AB}$. Hence, $\rho_{AB}\otimes \sigma_{AB}$ passes reduction criterion.

-   Entropic criterion: It follows easily from $S_\alpha(\rho\otimes \sigma)=S_\alpha(\rho)+ S_{\alpha}(\sigma)$.

-   Majorization criterion: $x \prec y$ if and only if there exists a doubly-stochastic matrix[^7] $D$ such that $x=Dy$, see [@chuang] page 575. Therefore, if $x \prec y$ and $x' \prec y'$, there exist $D$ and $D'$ such that $x=Dy$ and $x'=D'y'$. Hence $x\otimes x'=(D\otimes D')(y\otimes y')$ and then $x\otimes x'\prec y\otimes y'$. The proof follows easily using this property.

-   Cross norm criterion: Using $v(X\otimes X')=v(X)\otimes
    v(X')$ we have $\mathcal{U}((X\otimes X')\otimes (Y\otimes Y')) =
    \mathcal{U}(X\otimes Y)\otimes \mathcal{U}(X'\otimes Y')$. The proof follows from this equation.

-   Symmetric extension criterion: If $\rho^{(k)}$ and $\sigma^{(k)}$ are symmetric extensions of $\rho$ and $\sigma$ to $k$ copies, respectively, then $\rho^{(k)}\otimes \sigma^{(k)}$ is a symmetric extension of $\rho\otimes \sigma$ to $k$ copies.

Conclusion
==========

In this paper we have proved that for any separability criterion that is closed under tensor product, meaning that $\rho\otimes
\sigma$ passes the test if $\rho$ and $\sigma$ pass the test, the set of states that pass the test is not a good approximation of the set of separable states. In other words, all well-known algorithms for detecting entanglement, give no bound on the distance of a state from separable states. For the special case of positive partial transpose test, using Theorem \[thm:shape\], we have shown that the set of PPT states and separable states have totally different shapes. An interesting question to answer is to find a separability criterion that is stronger than the known ones and also is not closed under tensor product. This problem may clarify the complexity of separability problem: Is it $\NP$-hard to decide whether there exists a separable state whose trace distance from a given state is less than a constant $c$?

[**Acknowledgement.**]{} SB is thankful of Barbara Terhal for useful discussions.

[10]{}

Salman Beigi, [*$\NP$ vs $QMA_{\log}(2)$*]{}, arXiv:0810.5109

C. H. Bennett, D. P. DiVincenzo, T. Mor, P. W. Shor, J. A. Smolin and B. M. Terhal, [*Unextendible Product Bases and Bound Entanglement*]{}, Phys. Rev. Lett. 82 (1999) 5385

Fernando G.S.L. Brandao, [*Entanglement Theory and the Quantum Simulation of Many-Body Physics*]{}, PhD thesis, arXiv:0810.0026

Fernando G.S.L. Brandao, Martin B. Plenio, [*Entanglement Theory and the Second Law of Thermodynamics*]{}, Nature Physics 4, 873 (2008)

K. Chen and L.-A. Wu, [*A matrix realignment method for recognizing entanglement*]{} Quant. Inf. Comp., 3:193, 2003.

M. Christandl,. R. König, G. Mitchison and R. Renner, [*One-and-a-Half Quantum de Finetti Theorems*]{}, Communications in Mathematical Physics, Volume 273, Issue 2, pp.473-498

J. Dehaene, B. De Moor and F. Verstraete, [*On the geometry of entangled states*]{}, Journal of Modern Optics, Volume 49, Number 8, July 10, 2002 , pp. 1277-1287(11)

A. C. Doherty, P. A. Parrilo and F.M. Spedalieri, [*Distinguishing separable and entangled states*]{}, Phys. Rev. Lett., 88:187904, 2002.

A. C. Doherty, P. A. Parrilo and F. M. Spedalieri, [*Complete family of separability criteria*]{}, Phys. Rev. A, 69:022308, 2004.

R. M. Dudley, [*Real Analysis and Probability*]{}, Cambridge University Press (2002).

Sevag Gharibian, [*Strong NP-Hardness of the Quantum Separability Problem*]{}, arXiv:0810.4507

Leonid Gurvits, [*Classical deterministic complexity of Edmonds’ problem and Quantum Entanglement*]{}, quant-ph/0303055

M. Horodecki and P. Horodecki, [*Reduction criterion of separability and limits for a class of distillation protocols*]{}, Phys. Rev. A, 59:4206, 1999.

R. Horodecki, P. Horodecki and M. Horodecki, [*Quantum $\alpha$-entropy inequalities: independent condition for local realism?*]{} Phys. Lett. A, 210:377–381, 1996.

M. Horodecki, P. Horodecki and R. Horodecki, [*Separability of mixed states: necessary and sufficient conditions*]{}, Physics Letters A, v. 223, p. 1-8, 1996.

Lawrence M. Ioannou, [*Computational complexity of the quantum separability problem*]{}, Quantum Information and Computation, Vol. 7, No. 4 (2007) 335-370

R. König and R. Renner, [*A de Finetti representation for finite symmetric quantum states*]{} J. Math. Phys. 46, 122108 (2005).

M. A. Nielsen and I. L. Chuang, [*Quantum Computation and Quantum Information*]{}, Cambridge University Press, Cambridge, 2000

M. Nielsen and J. Kempe, [*Separable states are more disordered globally than locally*]{}, Phys. Rev. Lett., 86:5184–7, 2001.

O. Rudolph, [*Further results on the cross norm criterion for separability*]{}, quant-ph/0202121.

A. Peres, [*Separability criterion for density matrices*]{}, Phys. Rev. Lett., 77:1413–1415, 1996.

S. Szarek, I. Bengtsson and K. Zyczkowski, [*On the structure of the body of states with positive partial transpose*]{}, J. Phys. A 39 L119-L126 (2006)

K.G.H. Vollbrecht and R.F. Werner, [*Entanglement Measures under Symmetry*]{}, Phys. Rev. A 64, 062307 (2001).

[^1]: salman@mit.edu

[^2]: shor@math.mit.edu

[^3]: If we replace the trace distance with $E_R(\rho)$, the relative entropy of entanglement, this property does not hold [@relent].

[^4]: This is because the entanglement of distillation under asymptotically non-entangling maps is equal to the regularized relative entropy of entanglement, and this measure of entanglement is faithful, meaning that it is non-zero for every entangled state.

[^5]: Notice that partial trace decreases the trace distance.

[^6]: Notice that knowing that a state has a symmetric extension to $k$ copies, for a fixed $k$, gives us no upper bound on the distance of the state from separable states. Indeed, to get a non-trivial upper bound $k$ has to be of the order of the dimension of the state. It is because the upper bound on the distance from separable states comes from the finite quantum de Finetti theorem, and this theorem gives a trivial bound for a constant $k$. See [@renner] and [@povm] for finite de Finetti theorem. Also see Theorem \[thm:general\] of the present paper.

[^7]: A matrix is called doubly-stochastic if all of whose entries are positive, and the sum of entries on any row and column is equal to $1$.
