QUANTUM PERIOD FINDING PROBLEM AS A DRIVER OF QUANTUM CRYPTANALYSIS

Анотація

The paper explores the foundational role of quantum period-finding algorithms, particularly in the context of cryptography. The work focuses on quantum algorithms that exploit periodicity, such as Shor's algorithm, which is central to efficient integer factorization. It emphasizes the challenges quantum algorithms face when applied to non-abelian groups like Suzuki, Hermitian, and Ree groups, which exhibit complex periodic structures that are difficult to solve with existing quantum techniques. The research delves into the structure and properties of these groups, explaining the complexity of their representations and the challenges quantum Fourier transform (QFT) presents in these cases. It contrasts the relative ease with which abelian groups can be addressed using quantum algorithms with the exponential complexity encountered with non-abelian groups. The study provides a comparative analysis of the computational complexity between classical and quantum approaches for period finding across various group types, highlighting that while quantum algorithms offer exponential speedup for abelian cases, non-abelian structures remain a frontier for further research. The conclusion calls for continued exploration in quantum representation theory and cryptanalysis, particularly for non-abelian groups, where current quantum techniques have not yet provided efficient solutions. The period-finding problem is identified as critical for advancing both quantum computing and cryptographic applications.