Simon's algorithm: hidden-subgroup N = {0, s} in (Z/2Z)^n gives |G| = |N|*|G/N| Lagrange factorisation

Simon's algorithm / abelian hidden-subgroup framework. Setup: black-box function f: (Z/2Z)^n -> (Z/2Z)^n promised to be either 1-to-1 or 2-to-1 with a hidden period s (f(x) = f(x XOR s) for all x). Simon's circuit (1993): (1) Hadamard all…