A new paper came out claiming quasi-polynomial algorithm for Discrete Logarithm.http://arxiv.org/abs/1306.4244If correct, does it mean we no longer have an exponential separation in complexity of a classical algorithm and its quantum version for the discrete logarithm problem? Does this have any implication for quantum complexity theory?
New algorithm for Discrete log and its implications for Quantum computing
cc.complexity theory
Well, one crucial observation is that the new algorithm apparently only works for groups of the form $Z_{p^k}$ where $p$ is small --- it doesn't give a speedup for groups of the form $Z_p$.  The latter is the much more common setting that people talk about, both for cryptography and for Shor's algorithm, and the new algorithm doesn't threaten the quantum speedup there.  On the other hand, yes, unless I'm mistaken it does make the speedup much smaller in the $Z_{p^k}$ case.