Simon's Algorithm - Probability that the measurement results in a string Y

Question

I found something in a lecture on Simon's algorithm that I do not quite understand how to interpret. There the following is said:

$$\sum_{y\in\{0,1\}^n}|y\rangle\left(\sum_{x\in\{0,1\}^n} (-1)^{x\cdot y}|f(x)\rangle\right)$$

So we assume a 1 to 1 function and $s=0$. As far as that is understandable. Then it says (that's the part I'm not quite sure of): "The probability that a measurement in String Y results is:"

$$\left|\left|\frac{1}{2^n}\sum_{x\in\{0,1\}^n} (-1)^{x\cdot y}|f(x)\rangle\right|\right|^2=\frac{1}{2^n}$$

I try to make something more understandable, which I do not quite understand. So if you have a 1 to 1 function then that means that each value occurs exactly once, say you have three bits, then there are 8 states, that is from 000 to 111. These then also occur with the same probability of 1/8 for each state. But now I do not quite understand the result of the top formula, why is $\frac{1}{2^n}$ out there, why is not it squared? What happens to the sum there? What is the exact calculation behind it?

I mean, on the one hand, I understand why $\frac{1}{2^n}$ comes out there, but on the other hand, I do not quite understand the calculation ($||...||^2$) behind it, I hope somebody can explain it a bit.

Answer 1

In the first state you write they omitted to write the normalization factor. This is not rare to see, as one can usually easily deduce what the normalization should be from the context (though it might not be a very pedagogical choice).

To deduce the correct normalization in this case, you need only notice that, because $f$ is one-to-one, the sum over $x$ is something of the form $\sum_x c_x \lvert x\rangle$ for some coefficients $c_x$ with $\lvert c_x\rvert=1$, and where the sum is over all $n$-digit binary strings. There are $2^n$ of these, and therefore the state (just the one inside the parentheses) should more precisely be written as $$\frac{1}{2^{n/2}}\sum_{x\in\{0,1\}^n} (-1)^{x\cdot y}|f(x)\rangle.$$ A similar reasoning applies to the outer sum, so that the overall state, written with the normalization included, is $$\frac{1}{2^n}\sum_{y\in\{0,1\}^n}|y\rangle\left(\sum_{x\in\{0,1\}^n} (-1)^{x\cdot y}|f(x)\rangle\right).$$

This brings you to the second equation. To compute the norm there, you now notice that, again because $f$ is one-to-one, $$\left|\left|\frac{1}{2^n}\sum_{x\in\{0,1\}^n} (-1)^{x\cdot y}|f(x)\rangle\right|\right|^2 =\frac{1}{2^{2n}}\sum_{x\in\{0,1\}^n}\lvert (-1)^{x\cdot y}\rvert^2 =\frac{1}{2^{2n}}\sum_{x\in\{0,1\}^n}1 =\frac{1}{2^{2n}}2^n=\frac{1}{2^n}.$$

Answer 2

The first state in your question is not a valid quantum state as it is not normalized.

The result comes directly from the axioms of quantum mechanics. You just have to apply the Born rule. For a state $\sum_y ~ a_y |y\rangle$ the probability of measuring $|y\rangle$ is $|a_y|^2.$

Now suppose you are given a state $\sum_y ~ a_y |y\rangle|0\rangle + b_y |y\rangle|1\rangle$. The probability of getting $|y\rangle$ should be sum of probabilities of getting $|y\rangle|1\rangle$ or $|y\rangle|0\rangle$. This, according to the Born rule is $|a_y|^2 + |b_y|^2. $

So extending this logic to the case of a state of the form $\sum_y ~ |y\rangle|\psi_y\rangle$, we get that the probability of measuring $|y\rangle$ becomes $|| |\psi_y\rangle||^2.$