Quantum circuit for computing fidelity

Question

Suppose we use Uhlmann-Jozsa fidelity

$$ F(\rho, \sigma):=\left(\mathrm{tr}\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\right)^2. $$

Can we construct a quantum circuit that helps us calculate the fidelity of two mixed states?

Answer 1

Prohibited device

Such a circuit $C$ would enable faster-than-light communication and therefore does not exist.

Suppose Alice and Bob share a Bell pair $|\psi\rangle = \frac{1}{\sqrt{2}}(|01\rangle - |10\rangle)$ and Alice has a classical bit $b \in \{0, 1\}$ she wishes to communicate to Bob. She proceeds as follows. If $b=0$ Alice measures her half of $|\psi\rangle$ in the $|0\rangle, |1\rangle$ basis. Otherwise, she measures it in the $|+\rangle, |-\rangle$ basis. Note that for any single-qubit unitary $U$ we have $(U \otimes U)|\psi\rangle = (\det U)|\psi\rangle$, so

$$ |\psi\rangle = \frac{1}{\sqrt{2}}(|01\rangle - |10\rangle) = \frac{1}{\sqrt{2}}(|{-+}\rangle - |{+-}\rangle). $$

Therefore, after the measurement, if $b=0$ then the Bell pair is in the state $|01\rangle$ or $|10\rangle$, otherwise it is in the state $|{-+}\rangle$ or $|{+-}\rangle$. In order to receive $b$, Bob uses $C$ to compute the fidelity between his half of the shared Bell pair and the state $|0\rangle$. If $b=0$ the circuit outputs $F(|0\rangle, |0\rangle) = 1$ or $F(|0\rangle, |1\rangle) = 0$. Otherwise the circuit outputs $F(|0\rangle, |+\rangle) = F(|0\rangle, |-\rangle) = \frac{1}{2}$. No classical communication is used in the protocol and $b$ is transmitted instantaneously. Therefore, $C$ does not exist.

A more rigorous proof that distinguishing non-orthogonal quantum states is impossible is in Box 2.3 on p.87 in section 2.2.4 in Nielsen & Chuang.

Allowed device

However, there is a quantum circuit that given $O(4^n)$ copies of two $n$-qubit mixed states $\rho$ and $\sigma$ estimates $F(\rho, \sigma)$. The circuit first performs quantum state tomography on $\rho$ and $\sigma$ to estimate the two density matrices and then computes an estimate of fidelity using the formula $\left(\mathrm{tr}\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\right)^2$. The last step is possible, because quantum circuits subsume classical computers.

In practice, the cost of fidelity estimation is smaller than the cost of full state tomography, especially if we have additional knowledge about one of the states, see for example this answer or this paper.

No faster-than-light communication with allowed device

It is interesting to consider why the second device does not allow faster-than-light communication. The reason is that due to random outcomes of measurements Bob detects the maximally mixed state regardless of $b$. Specifically, if $b=0$ he receives

$$ \rho = \frac{1}{2}\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} + \frac{1}{2}\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} = \frac{1}{2}\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} $$

and if $b=1$ he receives

$$ \rho = \frac{1}{4}\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} + \frac{1}{4}\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix} = \frac{1}{2}\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}. $$