  This paper studies the quantum computational complexity of the discrete
logarithm (DL) and related group-theoretic problems in the context of generic
algorithms -- that is, algorithms that do not exploit any properties of the
group encoding.
  We establish a generic model of quantum computation for group-theoretic
problems, which we call the quantum generic group model. Shor's algorithm for
the DL problem and related algorithms can be described in this model. We show
the quantum complexity lower bounds and almost matching algorithms of the DL
and related problems in this model. More precisely, we prove the following
results for a cyclic group $G$ of prime order.
  - Any generic quantum DL algorithm must make $\Omega(\log |G|)$ depth of
group operations. This shows that Shor's algorithm is asymptotically optimal
among the generic quantum algorithms, even considering parallel algorithms.
  - We observe that variations of Shor's algorithm can take advantage of
classical computations to reduce the number of quantum group operations. We
introduce a model for generic hybrid quantum-classical algorithms and show that
these algorithms are almost optimal in this model. Any generic hybrid algorithm
for the DL problem with a total number of group operations $Q$ must make
$\Omega(\log |G|/\log Q)$ quantum group operations of depth $\Omega(\log\log
|G| - \log\log Q)$.
  - When the quantum memory can only store $t$ group elements and use quantum
random access memory of $r$ group elements, any generic hybrid algorithm must
make either $\Omega(\sqrt{|G|})$ group operations in total or $\Omega(\log
|G|/\log (tr))$ quantum group operations.
  As a side contribution, we show a multiple DL problem admits a better
algorithm than solving each instance one by one, refuting a strong form of the
quantum annoying property suggested in the context of password-authenticated
key exchange protocol.
