# Understanding a quantum algorithm to estimate inner products

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.

• While reading about the complex inner product, also referred to as a "Hermitian Form" I came across the fact that $cos \theta = \frac {Re \langle x, y \rangle} {||x|| ||y||}$, so I'm sure this has something to do with it, where $\theta$ is the angle between $x,y$. Jun 5 '19 at 2:03
• Well actually the complex inner product is a "type" of hermitian form. Jun 5 '19 at 2:11

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.

• Ok, thanks, very helpful. Jun 5 '19 at 2:36