Quantum Generic Hardness for Discrete Logarithms and Integer Factorization

Explore a 20-minute conference talk from the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024) examining the quantum computational complexity of discrete logarithm problems and integer factorization in generic algorithms. Dive into the establishment of generic models for quantum algorithms in group/ring problems, analyzing them as quantum analogs of classical counterparts. Learn about the proven logarithmic lower bounds for generic quantum DL algorithms, demonstrating Shor's algorithm's asymptotic optimality in terms of group operations. Discover insights into hybrid quantum-classical algorithms, memory-bounded settings, and their applications to multiple-instance DL problems. Examine the logarithmic lower bounds for order-finding algorithms and certain generic factoring algorithms outputting relatively small integers. Presented at OIST, Japan, this theoretical quantum information science research contributes to the understanding of quantum computational complexity and its practical implications in cryptography.