Paper 2023/1054

Quantum Complexity for Discrete Logarithms and Related Problems

Minki Hhan, Korea Institute for Advanced Study
Takashi Yamakawa, NTT Social Informatics Laboratories
Aaram Yun, Ewha Womans University

This paper studies the quantum computational complexity of the discrete logarithm 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, as a quantum analog of its classical counterpart. Shor's algorithm for the discrete logarithm problem and related algorithms can be described in this model. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and related problems in this model. More precisely, we prove the following results for a cyclic group $\mathcal G$ of prime order. (1) Any generic quantum discrete logarithm algorithm must make $\Omega(\log |\mathcal G|)$ depth of group operation queries. This shows that Shor's algorithm that makes $O(\log |\mathcal G|)$ group operations is asymptotically optimal among the generic quantum algorithms, even considering parallel algorithms. (2) We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We introduce a model for generic hybrid quantum-classical algorithm that captures these variants, and show that these algorithms are almost optimal in this model. Any generic hybrid quantum-classical algorithm for the discrete logarithm problem with a total number of (classical or quantum) group operations $Q$ must make $\Omega(\log |\mathcal G|/\log Q)$ quantum group operations of depth $\Omega(\log\log |\mathcal G| - \log\log Q)$. In particular, if $Q={\rm poly}\log |\mathcal G|$, classical group operations can only save the number of quantum queries by a factor of $O(\log\log |\mathcal G|)$ and the quantum depth remains as $\Omega(\log\log |\mathcal G|)$. (3) When the quantum memory can only store $t$ group elements and use quantum random access memory (qRAM) of $r$ group elements, any generic hybrid quantum-classical algorithm must make either $\Omega(\sqrt{|\mathcal G|})$ group operation queries in total or $\Omega(\log |\mathcal G|/\log (tr))$ quantum group operation queries. In particular, classical queries cannot reduce the number of quantum queries beyond $\Omega(\log |\mathcal G|/\log (tr))$. As a side contribution, we show a multiple discrete logarithm 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.

Note: A typo in the title has been corrected.

Available format(s)
Publication info
Quantum lower boundsShor's algorithmGeneric group model
Contact author(s)
minkihhan @ kias re kr
takashi yamakawa @ ntt com
aaramyun @ g ewha ac kr
2023-07-11: revised
2023-07-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Minki Hhan and Takashi Yamakawa and Aaram Yun},
      title = {Quantum Complexity for Discrete Logarithms and Related Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1054},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.