Understanding a quantum algorithm to estimate inner products

Question

While reading the paper "Compiling basic linear algebra subroutines for quantum computers", here, in the Appendix, the author/s have included a section on quantum inner product estimation.

Consider two vectors $x,y \in \mathbb{C}^n, x= (x_1, \dots , x_n), y= (y_1, \ldots, y_n)$, we want to estimate the inner product $\langle x | y \rangle$. Assume we are given a state $|\psi \rangle = \frac {1} {\sqrt 2} \big(|0 \rangle |x \rangle + |1 \rangle |y \rangle \big)$, after applying a Hadamard transform to the first qubit, the result is:

$$|\psi \rangle = \frac {1} {2} \big(|0 \rangle (|x \rangle + |y \rangle) + |1 \rangle(|x \rangle - |y \rangle) \big).$$

The author then states that after measuring the first qubit in the computational basis, the probability to measure $|0 \rangle$ is given by $p = \frac {1} {2} \big(1 + \mathrm{Re}(\langle x | y \rangle) \big)$. I do not understand this statement. From what I understand, after applying a partial measurement to the first qubit, the probability of measuring $|0 \rangle$ is given by $\frac {1} {4} \sqrt { \sum_{i=0}^{n}(\overline{(x_i+y_i)}(x_i+y_i)) }^2$ (in other words the norm of the vector squared), so I am not sure why these formulas are equivalent, or if I am mistaken.

Answer 1

You just need to do a bit more algebra: Note that $$ \sum_{i=0}^n (\overline{x_i+y_i})(x_i+y_i)=\langle x+y|x+y\rangle$$

and then you can distribute the right-hand side to get

$$\langle x|x\rangle+\langle x|y\rangle+\langle y|x\rangle+\langle y|y\rangle.$$

Since $| x\rangle$ and $| y\rangle$ are normalized, we know that $\langle x|x\rangle=\langle y|y\rangle=1$. We also know a property of inner products:

$$\langle x|y\rangle=\overline{\langle y|x\rangle}$$

Further, if you add a complex number to its conjugate, you get twice its real part, so we have $$\langle x|y\rangle+\langle y|x\rangle=2 Re(\langle x|y\rangle)$$

Thus, altogether, we have $$\langle x|x\rangle+\langle x|y\rangle+\langle y|x\rangle+\langle y|y\rangle=2+2Re(\langle x|y\rangle)$$

I think the probability you computed is off by a factor of 2: There is a $\frac{1}{2}$ as a coefficient of $|0\rangle$, so since the norm is squared, this will give a factor of $\frac{1}{4}$. This gives the answer you are supposed to get.