2
$\begingroup$

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}}$

$\endgroup$

1 Answer 1

2
$\begingroup$

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. $$

$\endgroup$
1
  • $\begingroup$ That's indeed what I missed. Thanks for a good explanation! $\endgroup$ Commented Feb 8 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.