# Measuring one register of the state $\frac{1}{2^{m}} \sum_{x}\sum_{k} (-1) ^ {x\cdot k} |k\rangle |f(x)\rangle$

I'm reading the article which contains lemma 1. Its proof contains the statement, that probability of getting $$|0\rangle$$ (denote it as $$\text{Pr}\left[|0\rangle\right]$$) after measuring the first register of state $$\frac{1}{2^{m}} |0\rangle \sum_{x} |f(x)\rangle + \frac{1}{2^{m}} \sum_{x}\sum_{k\ne0} (-1) ^ {x\cdot k} |k\rangle |f(x)\rangle$$ equals $$\frac{1}{2^{2m}} \sum_{y} \left|f^{-1}(y)\right|^{2}$$, where $$f:\{0,1\}^m\to\{0,1\}^n$$.

It is uncear, why there is a square of $$f$$'s preimage cardinality. Doesn't the probability $$\text{Pr}\left[|0\rangle\right]$$ just equal $$\frac{1}{2^{m}}$$?

We consider the only terms $$\frac{1}{2^{m}} |0\rangle \sum_{x} |f(x)\rangle = \frac{1}{2^{m}} \sum_{x} |0\rangle |f(x)\rangle$$ since the rest ones are canceled out by $$\langle0|k\rangle = 0$$ for non-zero $$k$$.

We have: $$\text{Pr}\left[|0\rangle\right] = \frac{1}{2^{2m}}\langle0, f(0...0)|0, f(0...0)\rangle + ... + \frac{1}{2^{2m}}\langle0, f(1...1)|0, f(1...1)\rangle = \frac{1}{2^{2m}} + ... + \frac{1}{2^{2m}} = \frac{1}{2^{2m}}\cdot{2^{m}}=\frac{1}{2^{m}}$$

Your state before measurement is $$|\psi\rangle=\frac{1}{2^m}|0\rangle\sum_x|f(x)\rangle+\frac{1}{2^m}\sum_x\sum_{k\neq 0}(-1)^{x\cdot k}|k\rangle|f(x)\rangle.$$ How do we calculate the probability of getting the 0 result? $$p_0=\langle\psi|(|0\rangle\langle 0|\otimes I)|\psi\rangle.$$ So, if you calculate this, you'll get $$p_0=\frac{1}{2^{2m}}\sum_{x,z}\langle f(z)|f(x)\rangle.$$ Now, as we sum over all possible values of $$z$$, the question is how many times does a value $$y=f(x)$$ appear? $$|f^{-1}(y)|$$ (I think this is what you missed in your calculation). Hence, we have (I'm being a little loose with notation) $$p_0=\frac{1}{2^{2m}}\sum_x|f^{-1}(y)|.$$ Now, we could instead just sum over the distinct values $$y=f(x)$$. Each value $$y$$ is repeated $$|f^{-1}(y)|$$ times in the sum over $$x$$. Hence, $$p_0=\frac{1}{2^{2m}}\sum_{y}|f^{-1}(y)|^2.$$