A new paper came out claiming quasi-polynomial algorithm for Discrete Logarithm. http://arxiv.org/abs/1306.4244
If 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?
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.
My understanding is that if $k = O (q)$, the algorithm has complexity $n^{O (\log n)}$ over finite fields $F_{q^k}$ assuming that $k = O (q)$. More generally, the algorithm has complexity $L_{q^k} (\alpha, O (1))$ in finite fields $F_{q_k}$ with $q \sim L_{q^k} (\alpha)$. It beats previous classical algorithms for $\alpha < 1 / 3$.
Shor's algorithm is still much faster, but the question about exponential speedup depends really on the definition of "exponential". (Also NFS/FFS were subexponential-time.)
