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?


1 Answer 1


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 $\frac{1}{2^{n-1}\left(2^n+1\right)}P_{\text{Sym}^2}\left(\mathbb{C}^{2^n}\right)$ as explained in this answer, with $P_{\text{Sym}^2}\left(\mathbb{C}^{2^n}\right)$ being the projector on the symmetric subspace of $\mathbb{C}^{2^n}$ with $2$ copies.

  • $\begingroup$ A sanity check: is the SWAP test a two outcome orthogonal measurement? If so, what are the two mutually orthogonal measurement operators corresponding to the two outcomes? $\endgroup$
    – BlackHat18
    Commented Oct 16, 2021 at 20:05
  • $\begingroup$ @BlackHat18 I'm not sure about it (because I'm not sure about what you mean by "orthogonal measurement", though I have a guess), but the difference might lie in the fact that the measurement you perform in the SWAP test is done on the working qubit, while the reasoning I've made assume a measurement on the two quantum registers. Furthermore, once the test has been performed, the state isn't maximally mixed in the second case, which has shown to be handy in the computation of the trace distance. $\endgroup$
    – Tristan Nemoz
    Commented Oct 16, 2021 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.