# SWAP test and density matrix distinguishability

Let us either be given the density matrix $$\begin{equation} |\psi\rangle\langle \psi| \otimes |\psi\rangle\langle \psi| , \end{equation}$$ for an $$n$$ qubit pure state $$|\psi \rangle$$ or the maximally mixed density matrix $$\begin{equation} \frac{\mathbb{I}}{{2^{2n}}}. \end{equation}$$

I am trying to analyze the following algorithm to distinguish between these two cases.

We plug the $$2n$$ qubit state we are given into the circuit of a SWAP test. Then, following the recipe given in the link provided, if the first qubit is is $$0$$, I say that we were given two copies of $$|\psi \rangle$$, and if it is $$1$$, we say we were given the maximally mixed state over $$2n$$ qubits.

What is the success probability of this algorithm? Is it the optimal distinguisher for these two states? The optimal measurement ought to be an orthogonal one (as the optimal Helstorm measurement is an orthogonal measurement). How do I see that the SWAP test implements an orthogonal measurement?

First of all, let us compute the probability of success of this algorithm. If you are given the state $$|\psi\rangle\langle\psi|\otimes|\psi\rangle\langle\psi|$$, the SWAP test will return the state $$|0\rangle$$ with probability $$1$$, which is the probability of success of the algorithm in this case.
Let us now consider the second case. The initial state is: $$\rho_0=\frac{1}{2^{2n}}\sum_{i,j}|0,i,j\rangle\langle0,i,j|$$ The first gate to be applied is: $$\mathbf{H}\otimes \mathbf{I}\otimes\mathbf{I}=\frac{1}{\sqrt{2}}\sum_{a,b,x,y}(-1)^{a\cdot b}|a,x,y\rangle\langle b,x,y|.$$ The resulting state is thus given by: $$\rho_1=\frac{1}{2}\frac{1}{2^{2n}}\sum_{a,i,j,b}|a,i,j\rangle\langle b,i,j|$$ We now apply the $$\mathbf{CSWAP}$$ gate, whose expression is: $$\mathbf{CSWAP}=\sum_{x,y}|0,x,y\rangle\langle0,x,y|+\sum_{x,y}|1,x,y\rangle\langle1,y,x|$$ The resulting state is: $$\rho_2=\frac{1}{2}\frac{1}{2^{2n}}\sum_{i,j}\left(|0,i,j\rangle\langle0,i,j|+|0,i,j\rangle\langle1,j,i|+|1,j,i\rangle\langle0,i,j|+|1,j,i\rangle\langle1,j,i|\right)$$ Finally, we apply the Hadamard gate on the first qubit once again, which results in the state: $$\rho_3=\frac{1}{4}\frac{1}{2^{2n}}\sum_{i,j}\left(\sum_{a,b}|a,i,j\rangle\langle b,i,j|+\sum_{a,b}(-1)^b|a,i,j\rangle\langle b,j,i|+\sum_{a,b}(-1)^a|a,j,i\rangle\langle b,i,j|+\sum_{a,b}(-1)^{a\oplus b}|a,j,i\rangle\langle b,j,i|\right)$$ We're interested by the diagonal coefficients of $$\rho_3$$ that can be written as $$|0,i,j\rangle\langle0,i,j|$$. Summing them would give us the probability of measuring $$|0\rangle$$. This probability is thus given by: $$\mathbb{P}[|0\rangle]=\frac{1}{4}\frac{1}{2^{2n}}\left(\sum_{i,j}1+\sum_{i}1+\sum_{i}1+\sum_{i,j}1\right)=\frac12+\frac{1}{2^{n+1}}.$$ All in all, this algorithm distinguishes these two states with probability $$\frac34-\frac{1}{2^{n+2}}$$.
Now, let $$T$$ denote the trace distance between these two states. We know that the optimal probability of disinguishing these states is given by $$\frac12(1+T)$$. Let $$U$$ be a quantum gate such that $$U|0\rangle=|\psi\rangle$$. $$T$$ is then also equal to the trace distance between $$\left(U^\dagger\otimes U^\dagger\right)\left(|\psi\rangle\langle\psi|\otimes|\psi\rangle\langle\psi|\right)\left(U\otimes U\right)=|0\rangle\langle0|\otimes|0\rangle\langle0|$$ and $$\frac{1}{2^{2n}}\left(U^\dagger\otimes U^\dagger\right)\mathbf{I}\left(U\otimes U\right)=\frac{1}{2^{2n}}\mathbf{I}$$. $$T$$ is then easily seen to be: $$T=\frac12\sum_i\left|\lambda_i\right|=\frac12\left(1-\frac{1}{2^{2n}}+\sum_{i=1}^{2^{2n}-1}\frac{1}{2^{2n}}\right)=1-\frac{1}{2^{2n}}$$ which means that the maximal probability of distinguishing these states is $$1-\frac{1}{2^{2n+1}}$$.
Thus, the SWAP test has a sub-optimal probability of success. Intuitively, this is due to the fact that the probability of measuring $$|0\rangle$$ is always larger than or equal to $$\frac12$$, which upper-bounds the probability of success with $$\frac34$$.
Note however that this reasoning works assuming you know what $$|\psi\rangle$$ is. Otherwise, the initial density matrix in the first case is also $$\frac{1}{2^{2n}}\mathbf{I}$$ and the maximal probabilty of distinguishing these situations is $$\frac12$$.