Quantum Complexity for Discrete Logarithms and Related Problems

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 the quantum generic group model and hybrid classical-quantum generic group model as quantum and hybrid analogs of their classical counterpart. This model counts the number of group operations of the underlying cyclic group G as a complexity measure. Shor’s algorithm for the discrete logarithm problem and related algorithms can be described in this model and make O(log|G|) group operations in their basic form. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and related problems in these models. We prove that any quantum DL algorithm in the quantum generic group model must make Ω(log|G|) depth of group operation queries. This shows that Shor’s algorithm that makes O(log|G|) group operations is asymptotically optimal among the generic quantum algorithms, even considering parallel algorithms.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 show that these variants are optimal among generic hybrid algorithms up to constant multiplicative factors: Any generic hybrid quantum-classical DL algorithm with a total number of (classical or quantum) group operations Q must make Ω(log|G|/logQ) quantum group operations of depth Ω(loglog|G|-loglogQ).When the quantum memory can only store t group elements and use quantum random access classical memory (QRACM) of r group elements, any generic hybrid quantum-classical algorithm must make either Ω(|G|) group operation queries in total or Ω(log|G|/log(tr)) quantum group operation queries. In particular, classical queries cannot reduce the number of quantum queries beyond Ω(log|G|/log(tr)). We prove that any quantum DL algorithm in the quantum generic group model must make Ω(log|G|) depth of group operation queries. This shows that Shor’s algorithm that makes O(log|G|) group operations is asymptotically optimal among the generic quantum algorithms, even considering parallel algorithms. 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 show that these variants are optimal among generic hybrid algorithms up to constant multiplicative factors: Any generic hybrid quantum-classical DL algorithm with a total number of (classical or quantum) group operations Q must make Ω(log|G|/logQ) quantum group operations of depth Ω(loglog|G|-loglogQ). When the quantum memory can only store t group elements and use quantum random access classical memory (QRACM) of r group elements, any generic hybrid quantum-classical algorithm must make either Ω(|G|) group operation queries in total or Ω(log|G|/log(tr)) quantum group operation queries. In particular, classical queries cannot reduce the number of quantum queries beyond Ω(log|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.