Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2405.12508 · Quantum Information and Computation

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

Iu-Iong Ng

Published Dec 1, 2024• 1 citation
arXivHTMLPDF

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\"{a}ger, Hallgren, Kitaev, and Song (STOC'14).

DOI
10.26421/qic24.15-16-3

Related papers

An efficient quantum algorithm for computing $S$-units and its applications

Jean‐François Biasse, Song, Fang

In this paper, we provide details on the proofs of the quantum polynomial time algorithm of Biasse and Song (SODA 16) for computing the $S$-unit group of a number field. This algorithm directly implies polynomial time methods to calculate class groups, S-class groups, relative class group and the unit group, ray class groups, solve the principal ideal problem, solve certain norm equations, and decompose ideal classes in the ideal class group. Additionally, combined with a result of Cramer, Ducas, Peikert and Regev (Eurocrypt 2016), the resolution of the principal ideal problem allows one to find short generators of a principal ideal. Likewise, methods due to Cramer, Ducas and Wesolowski (Eurocrypt 2017) use the resolution of the principal ideal problem and the decomposition of ideal classes to find so-called ``mildly short vectors'' in ideal lattices of cyclotomic fields.

arXiv:2510.02280•Oct 2, 2025•0 citations

Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields

Jean‐François Biasse, Fang Song

This paper gives polynomial time quantum algorithms for computing the ideal class group (CGP) under the Generalized Riemann Hypothesis and solving the principal ideal problem (PIP) in number fields of arbitrary degree. These are are fundamental problems in number theory and they are connected to many unproven conjectures in both analytic and algebraic number theory. Previously the best known algorithms by Hallgren [20] only allowed to solve these problems in quantum polynomial time for number fields of constant degree. In a recent breakthrough, Eisenträger et al. [11] showed how to compute the unit group in arbitrary fields, thus opening the way to the resolution of CGP and PIP in the general case. For example, Biasse and Song [3] pointed out how to directly apply this result to solve PIP in classes of cyclotomic fields of arbitrary degree. The methods we introduce in this paper run in quantum polynomial time in arbitrary classes of number fields. They can be applied to solve other problems in computational number theory as well including computing the ray class group and solving relative norm equations. They are also useful for ongoing cryptanalysis of cryptographic schemes based on ideal lattices [5, 10]. Our algorithms generalize the quantum algorithm for computing the (ordinary) unit group [11]. We first show that CGP and PIP reduce naturally to the computation of S-unit groups, which is another fundamental problem in number theory. Then we show an efficient quantum reduction from computing S-units to the continuous hidden subgroup problem introduced in [11]. This step is our main technical contribution, which involves careful analysis of the metrical properties of lattices to prove the correctness of the reduction. In addition, we show how to convert the output into an exact compact representation, which is convenient for further algebraic manipulations.

ACM-SIAM Symposium on Discrete Algorithms (SODA)•Dec 21, 2015•99 citations

Quantum Algorithms for Unit Group and principal ideal problem

Hong Wang, Zhi Ma

Computing the unit group and solving the principal ideal problem for a number field are two of the main tasks in computational algebraic number theory. This paper proposes efficient quantum algorithms for these two problems when the number field has constant degree. We improve these algorithms proposed by Hallgren by using a period function which is not one-to-one on its fundamental period. Furthermore, given access to a function which encodes the lattice, a new method to compute the basis of an unknown real-valued lattice is presented.

arXiv:1004.1269•Apr 8, 2010•0 citations

On the analysis of quantum algorithms for solving the short principal ideal problem

Iu-Iong Ng

In this thesis, we analyse and improve the best known ecient quantum algorithm for solving the Short Principal Ideal Problem (SPIP) in cyclotomic elds, which, given an ideal, determines whether the ideal is principal and outputs a suciently short generator.SPIP is fundamental in cryptography and computational number theory.The standard solution to SPIP can unfold in a two-part process involving the Principal Ideal Problem (PIP) and the Short Generator Problem (SGP).This thesis consists of the following two results.For PIP, we calculate the upper bound on quantum space complexity of the quantum algorithm proposed by Biasse and Song at SODA 2016 (BS) for solving PIP.PIP is the problem that, given an ideal, determines whether the ideal is principal and outputs a generator of the ideal if it is principal.The best known classical algorithm solves PIP in subexponential time, while the BS quantum algorithm nds a generator in polynomial time.Whether the cryptographic systems relying on the hardness of PIP have become insecure depends not only on the existence of polynomial time algorithms solving it but also on whether the algorithms should be implementable.Quantum computers nowadays have only hundreds of qubits, which means that quantum algorithms using too many qubits are not feasible for now.By estimating the qubits used in the BS algorithm, we want to estimate the threat at the moment.

•Mar 25, 2025•0 citations

Fast quantum algorithms for computing the unit group and class group of a number field

Sean Hallgren

Computing the unit group and class group of a number field are two of the main tasks in computational algebraic number theory. Factoring integers reduces to solving Pell's equation, which is a special case of computing the unit group, but a reduction in the other direction is not known and appears more difficult. We give polynomial-time quantum algorithms for computing the unit group and class group when the number field has constant degree.

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•79 citations

A Note on the Quantum Query Complexity of the Hidden Subgroup Problem

Troels Windfeldt

We are concerned with the Hidden Subgroup Problem for finite groups. We present a simplified analysis of a quantum algorithm proposed by Hallgren, Russell and Ta-Shma as well as a detailed proof of a lower bound on the probability of success of the algorithm.

arXiv:quant-ph/0404067•Apr 11, 2004•0 citations
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 SSS-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"{a}ger, Hallgren, Kitaev, and Song (STOC'14).
An efficient quantum algorithm for computing SSS-units and its applications
In this paper, we provide details on the proofs of the quantum polynomial time algorithm of Biasse and Song (SODA 16) for computing the SSS-unit group of a number field. This algorithm directly implies polynomial time methods to calculate class groups, S-class groups, relative class group and the unit group, ray class groups, solve the principal ideal problem, solve certain norm equations, and decompose ideal classes in the ideal class group. Additionally, combined with a result of Cramer, Ducas, Peikert and Regev (Eurocrypt 2016), the resolution of the principal ideal problem allows one to find short generators of a principal ideal. Likewise, methods due to Cramer, Ducas and Wesolowski (Eurocrypt 2017) use the resolution of the principal ideal problem and the decomposition of ideal classes to find so-called ``mildly short vectors'' in ideal lattices of cyclotomic fields.
This paper gives polynomial time quantum algorithms for computing the ideal class group (CGP) under the Generalized Riemann Hypothesis and solving the principal ideal problem (PIP) in number fields of arbitrary degree. These are are fundamental problems in number theory and they are connected to many unproven conjectures in both analytic and algebraic number theory. Previously the best known algorithms by Hallgren [20] only allowed to solve these problems in quantum polynomial time for number fields of constant degree. In a recent breakthrough, Eisenträger et al. [11] showed how to compute the unit group in arbitrary fields, thus opening the way to the resolution of CGP and PIP in the general case. For example, Biasse and Song [3] pointed out how to directly apply this result to solve PIP in classes of cyclotomic fields of arbitrary degree. The methods we introduce in this paper run in quantum polynomial time in arbitrary classes of number fields. They can be applied to solve other problems in computational number theory as well including computing the ray class group and solving relative norm equations. They are also useful for ongoing cryptanalysis of cryptographic schemes based on ideal lattices [5, 10]. Our algorithms generalize the quantum algorithm for computing the (ordinary) unit group [11]. We first show that CGP and PIP reduce naturally to the computation of S-unit groups, which is another fundamental problem in number theory. Then we show an efficient quantum reduction from computing S-units to the continuous hidden subgroup problem introduced in [11]. This step is our main technical contribution, which involves careful analysis of the metrical properties of lattices to prove the correctness of the reduction. In addition, we show how to convert the output into an exact compact representation, which is convenient for further algebraic manipulations.
Computing the unit group and solving the principal ideal problem for a number field are two of the main tasks in computational algebraic number theory. This paper proposes efficient quantum algorithms for these two problems when the number field has constant degree. We improve these algorithms proposed by Hallgren by using a period function which is not one-to-one on its fundamental period. Furthermore, given access to a function which encodes the lattice, a new method to compute the basis of an unknown real-valued lattice is presented.
In this thesis, we analyse and improve the best known ecient quantum algorithm for solving the Short Principal Ideal Problem (SPIP) in cyclotomic elds, which, given an ideal, determines whether the ideal is principal and outputs a suciently short generator.SPIP is fundamental in cryptography and computational number theory.The standard solution to SPIP can unfold in a two-part process involving the Principal Ideal Problem (PIP) and the Short Generator Problem (SGP).This thesis consists of the following two results.For PIP, we calculate the upper bound on quantum space complexity of the quantum algorithm proposed by Biasse and Song at SODA 2016 (BS) for solving PIP.PIP is the problem that, given an ideal, determines whether the ideal is principal and outputs a generator of the ideal if it is principal.The best known classical algorithm solves PIP in subexponential time, while the BS quantum algorithm nds a generator in polynomial time.Whether the cryptographic systems relying on the hardness of PIP have become insecure depends not only on the existence of polynomial time algorithms solving it but also on whether the algorithms should be implementable.Quantum computers nowadays have only hundreds of qubits, which means that quantum algorithms using too many qubits are not feasible for now.By estimating the qubits used in the BS algorithm, we want to estimate the threat at the moment.