Example where there's no asymptotic quantum speedup (but only a speedup by a factor of 2, depending on how you count): computing the parity of n bits (i.e., whether there's an even or odd number of 1's).
Example where there's a superquadratic speedup: computing the period of a periodic function (an exponential speedup for this task is the heart of Shor's factoring algorithm). And lots of other examples that have been discovered since, such as my "Forrelation" problem from 2009: given two access to otherwise-random functions, decide whether one of them is correlated with the Fourier transform of the other.
Yes and yes.
Example where there's no asymptotic quantum speedup (but only a speedup by a factor of 2, depending on how you count): computing the parity of n bits (i.e., whether there's an even or odd number of 1's).
Example where there's a superquadratic speedup: computing the period of a periodic function (an exponential speedup for this task is the heart of Shor's factoring algorithm). And lots of other examples that have been discovered since, such as my "Forrelation" problem from 2009: given two access to otherwise-random functions, decide whether one of them is correlated with the Fourier transform of the other.