Creating centered state using Hadamard gate

Question

Assume that you know how to build a unitary $U:|i\rangle \to |i\rangle|\psi_i\rangle$. Then, we are able to build the state $|\chi \rangle := \frac{1}{\sqrt{M}}\sum_{i=1}^M|i\rangle|\psi_i\rangle $.

I want to build a state $|\psi_c\rangle = \frac{1}{\sqrt{\sum_{j,i=1}^M \langle \psi_i|\psi_j\rangle}}\sum_{i=1}^M |\psi_i\rangle$.

In [1] they claim that I just need to apply an Hadamard and to do a projective measurement. By applying the definition of Hadamard, I get $$ \frac{1}{M}\sum_{i,j=1}^M(-1)^{ji}|j\rangle|\psi_i\rangle$$.

Now, by means of a projective measurement in the first register $|0\cdots0\rangle \langle 0\cdots0|$ we should get the state $|\psi_c \langle $ on the second register. My first issue is that, since none of the indexing register is $0$ the probability of such measure is always $0$.

Let $P_0 := |0\cdots0\rangle\langle 0\cdots0|$ be the projection matrix. Applying the axioms of quantum mechanics, the probability of reading zero should be $Tr[P_0|\chi_1\rangle\langle\chi_1|]$. But, the projection matrix $|0 \cdots0\rangle\langle 0\cdots0|$ is a matrix with $1$ in the top leftmost element, and everything else is $0$. So the product between $P_0$ and $M$ should have only nonzero elements on the first row, and therefore the trace should have just one element in the summation.

Instead, according to the paper, they manage to get (I added the $\otimes I$):

$$ P(0) = Tr( |0 \rangle \langle 0| (H^{\otimes logM} \otimes I ) |\chi\rangle \langle \chi| (H^{\otimes logM} \otimes I)) = $$ $$ \frac{1}{M^2}\sum_{i,j=1}\langle \psi_i|\psi_j\rangle $$

But I cannot recover their result. Can you help me?

Answer 1

I think one of your confusions is what you mean with $|i\rangle$ and in particular what the state $|i=1\rangle$ is. I assume that $M$ is power of two (if you assume qubits, otherwise a power of $d$), i.e. $M=2^n$, and that the sum in the definition of $|\chi\rangle$ is over all bit-strings of length $n$. Therefore, the notation $|i=1\rangle$ probably means $|i=1\rangle=|0\dots0\rangle$. Thus the state after applying the Hadamards does have a non-zero overlap with $|0\dots0\rangle$. This confusion also induces sign-errors in the state you write after the Hadamards.

I would recommend you to instead sum from $0$ to $M-1$. Then by $|i\rangle$ you would mean the binary form of the number $i$. The state after the Hadamards are $$\frac{1}{M}\sum_{i,j=0}^{M-1}(-1)^{ji}|j\rangle|\psi_i\rangle.$$ Note that this is different from what you wrote, in particular when $j=0$.

I think this might also be the origin of your second question. The projector $P_0$ applied to this state is $$\begin{aligned}P_0\left(\frac{1}{M}\sum_{i,j=0}^{M-1}(-1)^{ji}|j\rangle|\psi_i\rangle\right)&=\frac{1}{M}\sum_{i=0}^{M-1}(-1)^{0i}|j=0\rangle|\psi_i\rangle\\&=|0\dots0\rangle\left(\frac{1}{M}\sum_{i=0}^{M-1}|\psi_i\rangle\right)\end{aligned},$$ which shows that the probability of measuring $0\dots0$ is indeed $$\left(\frac{1}{M}\sum_{i=0}^{M-1}\langle\psi_i|\right)\left(\frac{1}{M}\sum_{j=0}^{M-1}|\psi_j\rangle\right)=\frac{1}{M^2}\sum_{i,j=0}^{M-1}\langle\psi_i|\psi_j\rangle.$$