I'm having trouble understanding the difference between weak fourier sampling and strong fourier sampling. From this paper:
...two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement (i.e., the row and column of the representation, in a suitably chosen basis, as well as its name) occurs.
Can someone explain like I'm 5 years old?
Within the paper itself that you linked to, on page 4 section 1.2 "Nonabelian Fourier Transforms" and page 5 section 1.3 "Weak vs Strong Sampling and the Choice of Basis", they define what they mean by representation on page 4 third indent from the top. It specifies that they represent the finite group G as a homomorphism (structure-preserving map) ρ : G → U(d), meaning G is mapped to a unitary matrix U of dimension d, with d = to the number of columns and rows in U.
As far as the differences between the weak standard method and the strong standard method, while both perform fourier analysis on non-abelian groups, the weak method uses a random basis, while the strong method specifies the rows and columns in a suitably chosen basis in order to perform a full measurement. They state on page 5: "We show...that we lose information-theoretic reconstructibility if we measure using a random basis. Specifically, we need an exponential number of measurements to distinguish conjugates of small subgroups of Ap. This establishes for the first time that the strong standard method is indeed stronger then measuring in a random basis: some bases provide much more information about the hidden subgroup then others."
Hope this helps. They link to some useful resources in the paper, I found these two pretty helpful:
