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?

  • $\begingroup$ As the sentence says, strong Fourier sampling measures not only the names but also the rows and columns in a chosen basis. What specifically are you asking about? $\endgroup$ Commented Oct 16, 2018 at 1:36
  • 1
    $\begingroup$ @user1271772 what does "representation names" mean in this context? $\endgroup$
    – glS
    Commented Oct 18, 2018 at 15:33

1 Answer 1


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:

  1. https://arxiv.org/abs/quant-ph/0211124
  2. http://www.math.tau.ac.il/~borovoi/courses/ReprFG/Hatzagot.pdf

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.