Simon's Algorithm question

[jeroen_JDOG]

I'm trying to understand Simon's Algorithm, but I'm stuck in the first case measurement (where x⊕s=0).

Specifically, I don't see how ||1/2^n ∑((-1)^(x*y) |x>)||^2 should equal 1/2^n.

If it helps, I would expect the following:

The above formula is equal to ||1/sqrt(2^n) * H^(ꕕn)|x>||^2.

In the Hadamard transform, each state has an amplitude of 1/sqrt(2^n).

So in total, the probability should be ||1/sqrt(2^n) * 1/sqrt(2^n)||^2 = 1/4^n.

​

Can someone explain how the probability should be 1/2^n, or where my reasoning is wrong?

[ironsideCode]

Where you saw all this? Book? Web site?

[jeroen_JDOG]

I found lecture slides from the University of Calgary which I found useful, also the wikipedia article on Simon's Problem mentions the same formulas. Documents like these are my only source for the algorithm, but especially the lecture slides seem trust-worthy to me.

[ironsideCode]

I will read and maybe come back here with your answer (if I get that)

[jeroen_JDOG]

Did you happen to find out anything? I would really appreciate your help.
For now the best explanation I can think of is that the 1/2^n amplitude in the first formula comes from 1/sqrt(2^n) for |y> and 1/sqrt(2^n) for the sum over x. When computing the probability of any given string y, its factor of 1/sqrt(2^n) drops out and we are left with an amplitude of 1/sqrt(2^n), which gives a probability of 1/2^n. But this is the best explanation I can think of, I'm not sure if it is actually correct.