Upper bounding the quantum space complexity for computing class group and principal ideal problem

2024/05/21 by Ng, Iu-Iong
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2405.12508

Abstract

In this paper, we calculate the upper bound on quantum space complexity of the quantum algorithms proposed by Biasse and Song (SODA'16) for solving class group computation and the principal ideal problem using the reductions to S-unit group computation. We follow the approach of Barbulescu and Poulalion (AFRICACRYPT'23) and the framework given by de Boer, Ducas, and Fehr (EUROCRYPT'20) and Eisenträger, Hallgren, Kitaev, and Song (STOC'14).

Related

• An efficient quantum algorithm for computing S-units and its applications
• Quantum Algorithms for Unit Group and principal ideal problem
• Solving the Decision Principal Ideal Problem with Pre-processing
• Quantum Complexity Classes
• A Note on the Quantum Query Complexity of the Hidden Subgroup Problem