Computing state overlap from the expectation value of the Ctrl-Z operator

Question

I am trying to understand an algorithm for computing the overlap between two single qubit states, $\left |\psi\right>$ and $\left |\phi\right>$: $$ \left| \left< \psi | \phi \right> \right|^2. $$ The overlap is given by the expectation value of the SWAP operator, but a more efficient method is presented in Learning the quantum algorithm for state overlap. The circuit for the "Bell-Basis algorithm (BBA)" (see Fig 6A in the aforementioned paper) is:

The text (bottom left on page 7) says:

Figure 6(A) shows the BBA for one-qubit states ρ and σ. This circuit employs one CNOT gate followed by one Hadamard gate, with both qubits being measured. It is straightforward to show that this corresponds to a Bell basis measurement. The post-processing is a bit more complicated, with c = (1, 1, 1, −1), which corresponds to summing the probabilities for the 00, 01, and 10 outcomes and subtracting probability of the 11 outcome. The above post-processing is equivalent to measuring the expectation value of a controlled-Z operator

Note:

• by "post-processing" they mean the overlap between $\left |\psi\right>$ and $\left |\phi\right> = \sum_i c_i \,p_i$, where the $p_i$ are probabilities (Eqn 6 in the paper)
• the probabilities are obtained by running the circuit many times, with the same input states.

Can someone please explain how this works?

AFAIK, the expectation value of an operator $A$ on some state $\left |\psi\right>$ is: $$ \left<A\right>_\psi = \left<\psi | A | \psi \right> = \sum_i \lambda_i \left<\psi | \omega_i \right> \left< \omega_i | \psi \right> $$ where the $\lambda_i, \omega_i$ are the eigenvalues and eigenvectors of $A$. The controlled-Z operator has eigenvalues (1, 1, 1, -1) and eigenvectors 00, 01, 10, 11, so I can almost understand how the algorithm works (i.e. the eigenvalues match the $c = (1,1,1,-1)$ in the text quoted above), but I don't understand:

• how the probabilities $p_i$ relate to the terms $\left<\psi | \omega_i \right> \left< \omega_i | \psi \right>$ i.e. how does the measurement in Z relate to $\left| \left< \psi | \omega_i \right> \right|^2$
• how it works when applied to two different input states$\left |\psi\right>$ and $\left |\phi\right>$ (the above has the same state $\left.|\psi\right>$ on both sides), which is the value of interest ($\left| \left< \psi | \phi \right> \right|^2$).

Answer 1

The unitary part of the circuit (that is, the CNOT followed by the Hadamard), is the gate sending Bell states into the computational basis. More explicitly, writing the input states as $$|\psi\rangle=\psi_0|0\rangle+\psi_1|1\rangle, \qquad|\phi\rangle=\phi_0|0\rangle+\phi_1|1\rangle,$$ the output state before the measurement can be written as $$ |\psi\rangle|\phi\rangle\to |\Psi_{\rm out}\rangle\equiv \psi_0 |+\rangle\otimes|\phi\rangle + \psi_1|-\rangle\otimes X|\phi\rangle, $$ where $X$ is the Pauli $X$ gate: $X\equiv|0\rangle\!\langle1|+|1\rangle\!\langle0|$.

You now measure in the computational basis, and thus have four possible outcomes: $00,01,10,11$. The corresponding probabilities are $$ p_{00} \equiv |\langle 00|\Psi_{\rm out}\rangle|^2 = \frac12|\psi_0\phi_0 + \psi_1\phi_1|^2, \\ p_{01} \equiv |\langle 01|\Psi_{\rm out}\rangle|^2 = \frac12|\psi_0\phi_1 + \psi_1\phi_0|^2, \\ p_{10} \equiv |\langle 10|\Psi_{\rm out}\rangle|^2 = \frac12|\psi_0\phi_0 - \psi_1\phi_1|^2, \\ p_{11} \equiv |\langle 11|\Psi_{\rm out}\rangle|^2 = \frac12|\psi_0\phi_1 - \psi_1\phi_0|^2. $$ As far as I can tell from the post, the post-processing amounts to computing $p_{00}+p_{01}+p_{10}-p_{11}$. You can indeed notice that \begin{align} p_{00} + p_{10} &= |\psi_0\phi_0|^2 + |\psi_1\phi_1|^2, \\ p_{01} - p_{11} &= 2 \operatorname{Re}(\bar\psi_0\phi_0\bar\phi_1\psi_1), \end{align} and thus $$ p_{00} + p_{01} + p_{10} - p_{11} = |\psi_0\phi_0|^2 + |\psi_1\phi_1|^2 + 2 \operatorname{Re}(\bar\psi_0\phi_0\bar\phi_1\psi_1) = |\langle\psi|\phi\rangle|^2. $$ If you want to describe the measurement using an observable (not that I think it would serve much purpose here), you can define $$\newcommand{\ketbra}[1]{\lvert #1\rangle\!\langle #1\rvert} A = \ketbra{00} + \ketbra{01} + \ketbra{10} - \ketbra{11}. $$ This would be the observable measured in the final portion of the setup (that is, the "overall measurement scheme" performed on the evolved state $|\Psi_{\rm out}\rangle$). You could also describe the whole circuit+measurement as the measurement of a single observable. In this case, the observable would be: $$A' \equiv \ketbra{\Phi^+} + \ketbra{\Psi^+} + \ketbra{\Phi^-} - \ketbra{\Psi^-},$$ where I'm using the same notation as the Wikipedia page for the Bell states.