Note the "we demonstrate quantum speedup for sufficiently small w," w being Hamming distance of the period to find.

Complete quote: "...we demonstrate an algorithmic quantum speedup for a variant of Simon’s problem where the hidden period has a restricted Hamming weight . For sufficiently small values of ..."

If we know that hidden period is exactly k bits away, we can generate C(k,n) samples, which puts us into polynomial complexity class in classical case, not exponential.

So, hold you "wow"s.