# Prove that an entanglement witness is optimal iff it's zero on a spanning set of product states

I am reading about entanglement witnesses from here. In section 2.5.2, it is written that

Furthermore, a witness $$\mathcal{W}$$ is called optimal, if there is no other witness, which is ﬁner than $$\mathcal{W}$$. This implies that for any positive operator $$P$$ the observable $$X = \mathcal{W} − P$$ is not a witness anymore. From this it can be easily seen that $$\mathcal{W}$$ is optimal, if and only if the product vectors $$| \phi_i \rangle \ = | a_ib_i \rangle \text{ with } \langle \phi_i | \mathcal{W}| \phi_i \rangle \ = 0$$ span the whole space.

I did not understand how do we arrive at the bold part, from the definition of optimality. Can anyone please explain?

Definition of optimal witness — Start recalling that an entanglement witness $$W^{\rm opt}$$ is said to be optimal if there is no other witness $$W'$$ with detects a strict superset of entangled states — that is, a $$W'$$ such that $$\langle\rho,W^{\rm opt}\rangle<0\implies \langle\rho,W'\rangle<0$$, and there is some $$\sigma$$ such that $$\langle\sigma,W'\rangle<0< \langle\sigma,W^{\rm opt}\rangle$$. Note that I'll use the shorthand notation $$\langle A,B\rangle\equiv \operatorname{tr}(A^\dagger B)$$ throughout this answer, as I think it better highlights some of the geometric ideas involved in these calculations.

### Prove that if $$W-P$$ is a witness then $$W$$ isn't optimal

Subtracting a PSD operator can't do worse — Let $$W$$ be an entanglement witness, and let $$P\ge0$$ be a PSD operator such that $$W-P$$ is still an entanglement witness. It's easy to see that $$W-P$$ is at least as strong a witness as $$W$$, because for any $$\rho$$, $$\langle W,\rho\rangle<0$$ implies $$\langle W-P,\rho\rangle<0$$. We want to prove that $$W-P$$ is strictly stronger than $$W$$, that is, that there is some entangled state $$\eta^e$$ such that $$\langle W,\eta^e\rangle\ge0$$ but $$\langle W-P,\eta^e\rangle<0$$.

Proof idea — One way to prove this is to show that there is always some state $$\eta$$ such that $$\langle W,\eta\rangle=0$$ and $$\langle P,\eta\rangle>0$$. If you can find this state, then it immediately follows that $$W-P$$ detects it while $$W$$ doesn't, hence $$W$$ isn't optimal.

Prove existence of an entangled state needing $$P$$ to be witnessed — Note that unless $$P=0$$, there must be some state $$\eta$$ such that $$\langle P,\eta\rangle>0$$. Let's then consider the expectation value of $$W$$ on this state, and distinguish between the following three possibilities:

1. If $$\langle W,\eta\rangle=0$$, then $$\langle W-P,\eta\rangle<0$$, and thus $$\eta$$ is entangled, and detected as such by $$W-P$$ but not by $$W$$. Thus $$W-P$$ is stronger than $$W$$, and $$W$$ isn't optimal.
2. If $$\langle W,\eta\rangle<0$$, let $$\eta^+$$ be some state such that $$\langle W,\eta^+\rangle>0$$ (which, again, must exist if $$W\neq0$$). But then, there must be some $$p\in(0,1)$$ such that $$\bar\eta = p \eta+(1-p)\eta^+$$ satisfies $$\langle W,\bar\eta\rangle=0$$. Furthermore, we still have $$\langle P,\bar\eta\rangle>0$$, hence again $$W$$ isn't optimal.
3. If $$\langle W,\eta\rangle>0$$, let $$\eta^-$$ be some (necessarily entangled) state such that $$\langle W,\eta^-\rangle<0$$. Then as above, there must be some $$p\in(0,1)$$ such that $$\bar\eta = p\eta + (1-p)\eta^-$$ gives $$\langle W,\bar\eta\rangle=0$$, and still $$\langle P,\bar\eta\rangle>0$$, hence again the conclusion.

For more related results you might want to have a look at (Lewenstein et al. 2000, quant-ph/0005014). For example, they show in Lemma 2 that an entanglement witness $$W_2$$ is finer than $$W_1$$ iff there's $$P\ge0$$ with $$\operatorname{tr}(P)=1$$ and $$0\le \epsilon<1$$ such that $$W_1=(1-\epsilon)W_2+\epsilon P$$. And then soon after that a witness $$W$$ is optimal iff for all $$P$$ and $$\epsilon>0$$ the operator $$(1+\epsilon)W-\epsilon P$$ isn't a witness.

### $$W$$ is optimal if no $$P\ge0$$ can be subtracted from it

This is an intermediate step that will help proving the next result. It's essentially a rewording of what is proved in Lemma 2 and Theorem 1 of https://arxiv.org/abs/quant-ph/0005014.

They show in Lemma 2 that $$W_2$$ is finer than $$W_1$$ iff there's $$P\ge0$$ with $$\operatorname{tr}(P)=1$$ and $$\epsilon\in[0,1)$$ such that $$W_1=(1-\epsilon)W_2+\epsilon P$$. But observing that any $$W$$ is a witness iff $$\alpha W$$ is a witness for any $$\alpha>0$$, this is the same as saying that $$W_2$$ is finer than $$W_1$$ iff it's a positive multiple of $$W_1-P$$ for some $$P\ge0$$ with $$\operatorname{tr}(P)\in[0,1)$$. So in summary, they're saying that all witnesses finer than $$W_1$$ must have (modulo positive multiples) the form $$W_1-P$$ for some $$P\ge0$$. Which in turn means that if $$W-P$$ isn't a witness for all $$P\ge0$$, then $$W$$ must be optimal.

Let's try to more directly show that if $$W'$$ is a finer entanglement witness than $$W$$, then $$\alpha W'=W-P$$ for some $$\alpha>0$$ and some $$P\ge0$$. This amounts to proving that any such $$W'$$ is such that $$W-\alpha W'\ge0$$ for some $$\alpha>0$$, that is, that there is $$\alpha>0$$ such that $$\langle W,\rho\rangle\ge \alpha \langle W',\rho\rangle$$. for all states $$\rho$$. To show this, let's consider a few different cases:

1. If $$\langle W,\rho\rangle=0$$, then $$\langle W',\rho\rangle\le0$$, and thus the inequality is satisfied. This follows from Lemma 1(i) in the paper.
2. If $$\langle W,\rho\rangle<0$$, then $$\langle W',\rho\rangle\le\langle W,\rho\rangle$$, and thus the inequality is again satisfied. This follows from Lemma 1(2) in the paper.
3. If $$\langle W,\rho\rangle>0$$ then $$\langle W',\rho\rangle\le\lambda\langle W,\rho\rangle$$ for some fixed $$\lambda\ge1$$ that only depends on $$W$$ and $$W'$$. This is Lemma 1(3) in the paper.

We thus have the result with $$\alpha=1/\lambda$$.

### Optimality vs product states such that $$\langle e, f|W|e,f\rangle=0$$

The other point is again discussed in https://arxiv.org/abs/quant-ph/0005014. Define $$P_W\equiv \{|e,f\rangle : \,\, \langle W,\mathbb{P}_e\otimes\mathbb{P}_f\rangle=0\}.$$ They then show in the paper that:

1. (Lemma 3) If $$P\ge0$$ is such that $$PP_W\neq0$$, then $$W-P$$ isn't a witness. In other words, if there's $$|e,f\rangle\in P_W$$ such that $$P|e,f\rangle\neq0$$, then $$W-P$$ isn't a witness. This is immediate remembering that this would mean $$\langle W,\mathbb{P}_e\otimes \mathbb{P}_f\rangle=0$$ and $$\langle P,\mathbb{P}_e\otimes \mathbb{P}_f\rangle>0$$, and thus $$\langle W-P,\mathbb{P}_e\otimes\mathbb{P}_f\rangle<0$$.

2. (Corollary 2) If $$P_W$$ spans the whole space, then $$W$$ is optimal. Using the above results this is now also easy to see: if $$P_W$$ spans the space, then any operator $$P\neq0$$ is such that $$W-P$$ isn't a witness anymore. Thus $$W$$ must be optimal.