How to compute the measurement probability in swap test?

It's a fantastic question because the typical measurement intuition we apply no longer is sufficient - it's really necessary to formalize measurement.

Specifically, we create a set of nonlinear operators $M_psi = |psi rangle langle psi |$, where the probability of measuring $psi$ on an arbitrary state $|phirangle $ is $langle phi | M^dagger M | phi rangle$.

In our case, we have a measurement operator $M_1$ we are interested in. However, we can actually apply $M_0$ for simplicity, and then subtract this probability from 1. Thus, where $| varphi rangle $ is the state provided above:

begin{align} langle varphi | M^dagger M | varphi rangle &= langle varphi |0rangle langle 0| 0rangle langle 0|varphirangle &= langle varphi|0ranglelangle 0|varphirangle &= frac{1}{4} (langle phi|langle psi| + langle psi|langle phi|)( |phi rangle |psi rangle + |psi rangle |phi rangle) &= frac{1}{4}(2 langlephi| langlepsi|phirangle |psirangle + 2) &= frac{1}{2}Big(|langlepsi|phirangle|^2 + 1 Big) end{align}

Thus, because this is the zero probability, we have:

$$ 1 - frac{1}{2}Big(|langlepsi|phirangle|^2 + 1 Big) = frac{1 - |langle psi|phi rangle|^2}{2} = frac{1 - |langle phi|psi rangle|^2}{2} $$

As desired.

I assume you're happy with the idea that the state before measurement is $$|O_{out}rangle=frac12|0rangle(|phirangle|psirangle+|psirangle|phirangle)+frac{1}{2}|1rangle(|phirangle|psirangle-|psirangle|phirangle).$$ Now you want to measure qubit 1 in the 0/1 basis. There's a couple of different ways you might approach this.

1. Define the two measurement projectors to be $P_0=|0ranglelangle 0|otimes Iotimes I$ (i.e. measure first qubit in 0, and do nothing to the other two), and $P_1=|1ranglelangle 1|otimes Iotimes I$. The probability of getting the 0 answer is $langle O_{out}|P_0|O_{out}rangle$.

2. Alternative, rewrite your state as $$ |O_{out}rangle=gamma_0|0rangle|sigmarangle+gamma_1|1rangle|taurangle, $$ where $|sigmarangle$ and $|taurangle$ are properly normalised vectors, and the coefficients $gamma_{0/1}$ compensate for that normalisation. The probability of getting the answer 0 when you measure the first qubit is $|gamma_0|^2$. So, we have $$ gamma_0|sigmarangle=frac12(|phirangle|psirangle+|psirangle|phirangle). $$ Take the inner product of that equation with itself and you get begin{align*} |gamma_0|^2&=frac14(langlephi |langlepsi |+langlepsi |langlephi|)(|phirangle|psirangle+|psirangle|phirangle) &=frac14(2+2|langlephi|psirangle|^2). end{align*} The actual question requires the probability of getting answer 1. This is left as an exercise for the reader.