top | item 24072037

Simon's Algorithm

41 points| keyboardman | 5 years ago |leimao.github.io | reply

13 comments

order
[+] Gehinnn|5 years ago|reply
I don't understand the problem. x and y are free, so you can choose x=y. Then obviously, f(x)=f(y). Then it should follow x=x xor c, thus c=0. Or did they forget to claim that x and y are different?
[+] greeneggs|5 years ago|reply
The problem is stated correctly. You are reading it incorrectly, but I am not sure how.

If c=0, then it says that f(x)=f(y) if and only if (<=>) x=y. In other words, for all x≠y, f(x)≠f(y). Thus the function is 1-to-1. This is a nontrivial property that is difficult to check.

[+] knlje|5 years ago|reply
Doesn't it read that "for all x, y \in {0, 1}^n"?
[+] rymohr|5 years ago|reply
You are confusing equality and equivalence.

It’s easy to do. Einstein did the same thing with E=mc2.

Equality is a matter of identity. Equivalence is a matter of behavior.

The speed of light is not an absolute constant as Einstein believed. C just represented the speed that light can travel as a relationship between energy and mass.

My favorite form of the equation is C equals the square root of energy divided by mass.

Behaviorally all that means is that as the energy to mass ratio goes up, the speed of light goes up. And as the mass to energy ratio goes up, the speed of light goes down. Hence time dilation, black holes, etc.