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

The computation of number theoretical problems, or computational number theory, is important both in its own right and in terms of applications, such as developing algorithms and cryptography. The main objects in these number theoretical problems are number fields, i.e., finite extensions of the field of rational numbers $\mathbb{Q}$, and their ring of integers. Most quantum algorithms perform exponentially better than the best-known classical algorithms for addressing several theoretical problems or their applications. There are some problems which are believed to be hard classically but have polynomial quantum algorithms solving them, for example, integer factorisation and discrete logarithm [Sho94], and the problems for general number fields, like the unit group computation [Hal05, EHKS14], class group computation [Hal05, BS16], and the principal ideal problem [Hal07, BS16]. These quantum algorithms can be reduced to a type of problem, the hidden subgroup problems (HSP), which find the subgroup hidden by the period of a function.

In this work, we focus on the ideal class group computation and solving the principal ideal problem. The ideal class group, or simply the class group, of a number field is the finite abelian group consisting of the equivalent classes of fractional ideals of the ring of integers. One can also define the class group for an ideal of the ring of integers as the finite abelian group consisting of invertible fractional ideals of the order. Class groups appear in many significant problems in number theory, for instance, factoring large integers and determining principal ideals in a cyclotomic field. The computation of ideal class groups is also commonly used in other number theoretical tasks such as computing other objects of the number field like ray class group, relative class group, and unit group [BF14, EH10], or in problems like finding Bach’s bound on the maximum norm of the generators [Bac90]. There is also a close relation to cryptography, for example, the classical subexponential classical algorithm for integer factorisation [LP92], and some curve-based cryptography [BCL08] that include finding relations between elements in the class group.

An ideal is principal if it can be generated by a single element. The principal ideal problem (PIP) determines whether the input ideal is principal and finds a generator. Like the class group computation, PIP has applications in computing ray class groups, relative class groups, unit groups, and $S$-class groups. Problems such as lattice isomorphism and matrix similarity can be efficiently reduced to deciding whether an ideal is principal [BHJ22]. Since many cryptographic schemes use principal ideals generated by a short element, PIP is also related to lattice-based cryptography. Recently, it has been shown that solving PIP in polynomial time directly induces a polynomial time attack on schemes relying on the hardness of finding the short generator of a principal ideal [CDPR16].

Instead of the ordinary HSP, most recent quantum algorithms for number theoretical problems are based on a framework called the continuous hidden subgroup problem (CHSP), proposed by Eisenträger, Hallgren, Kitaev, and Song [EHKS14] as a generalisation of HSP to the group $\mathbb{R}^{m}$ for some non-constant dimension $m$. As an application, [EHKS14] applied CHSP to solve the unit group problem in polynomial time by constructing an oracle that maps from a group containing the unit group to a group of ideals and then to a field of quantum states. Recently, Barbulescu and Poulalion [BP23] applied the complexity framework proposed by [BDF20] on the unit group oracle to analyse the space complexity of the unit group algorithm and propose a modified algorithm for a special case in cyclotomic fields.

Other important applications on the CHSP are given by Biasse and Song [BS16], which gave a polynomial time quantum algorithms for computing class groups and solving PIP in arbitrary degree number fields by reducing the problems to a problem computing the $S$-unit group. Notice that the previous works by Hallgren, the polynomial time algorithms for class group computation [Hal05] and for PIP for constant degree number fields [Hal07], utilise the HSP algorithms but not CHSP. The $S$-unit group problem can be viewed as a generalisation of the unit group problem with $|S|$ more parameters. Hence, [BS16] follows the way of defining the oracle for unit groups and extends it to the one for $S$-unit groups, which makes it possible to reduce the $S$-unit group computation to CHSP. A well-known application of the PIP algorithm is the polynomial time quantum algorithm finding the shortest vector¹¹1The length of the shortest vector is called the minimum distance or the first successive minima. in an ideal lattice (ideal-SVP) proposed by Cramer, Ducas, and Wesolowski [CDW21], which applies the PIP algorithm and a variant of class group computation as dominant parts. For the applications in cryptography, since some schemes for post-quantum cryptography rely on the hardness of PIP, [BS16] indeed broke some cryptography systems from a theoretical point of view. Nevertheless, a precise estimation of the quantum time or space complexity is essential in evaluating the threat raised by the quantum algorithm rather than only knowing it runs in polynomial time.

In this work, we follow the way in [BP23] of calculating the space complexity of the unit group algorithm, apply the framework provided by [BDF20] on the oracle for $S$-unit groups, which is defined in [BS16], and derive the space complexity for the $S$-unit group algorithm.

Since the unit rank $m$ has the same order as the degree $n$, we can rewrite it in the notations as [BS16] with a maximum.

Our result can be viewed as a generalisation of the space complexity given by [BP23] by taking the set $S$ to be empty. Applying our result to the PIP quantum algorithm derived by [BS16], which with an input ideal $\mathfrak{a}$ runs in polynomial time in the parameters $n,\log\mathcal{N}(\mathfrak{a}),\log\Delta$, we obtain the quantum space complexity for PIP.

From this result, we expect the number of qubits used for PIP or its applications, e.g., ideal-SVP, to be large with respect to the degree of the input number field. Therefore, our results indicate that, in general, implementing these algorithms may require a large-scale quantum computer.

We follow the definitions in [BS16]. Let $K$ be a number field with degree $n$, i.e., $n=[K:\mathbb{Q}]$. Denote by $n_{1}$ and $n_{2}$ the number of real embeddings and the number of pairs of complex embeddings, respectively. Then $n=n_{1}+2n_{2}$ and the unit rank of $K$ is defined as $m=n_{1}+n_{2}-1$. The absolute norm of an element $x\in K$ is defined as $\mathcal{N}(x)\coloneqq\prod_{\sigma}\sigma(x)\in\mathbb{Q}$, where $\sigma$ denotes the $n$ embeddings.

We denote the ring of integers of $K$ by $\mathcal{O}$. Notice that every ring of integers of a number field is a Dedekind ring, and which implies that any ideal $I$ of $\mathcal{O}$ can be uniquely factored into a product of powers of prime ideals, i.e., $I=\prod\mathfrak{p}^{v_{\mathfrak{p}}(I)}$ with $v_{\mathfrak{p}}(I)\in\mathbb{Z}$ and only finitely many of them are non-zero. The norm of an ideal is defined by $\mathcal{N}(I)=|\mathcal{O}/I|$, and if it is a principal ideal such that $I=(\alpha)$, then $\mathcal{N}(I)=\mathcal{N}(\alpha)$. The unit group $\mathcal{O}^{*}$ consists of invertible elements, i.e., the units, in $\mathcal{O}$. For $\alpha\in\mathcal{O}^{*}$, $(\alpha)=\mathcal{O}$.

In this subsection, we review the ideas for the unit group algorithm from [EHKS14]. By the properties of units, one can identify $\mathcal{O}^{*}$ as a subgroup of $\hat{G}=\mathbb{R}^{n_{1}+n_{2}-1}\times\mathbb{Z}_{2}^{n_{1}}\times(\mathbb{R}/\mathbb{Z})^{n_{2}}$. To see this, we consider the mapping $\varphi:\hat{G}\rightarrow E$ translating between the log coordinates and the conjugate vector representation.

Since the units are the elements $z\in\mathcal{O}$ with $\mathcal{N}(z)=\pm 1$, for a unit written as $z=e^{\boldsymbol{u}}\boldsymbol{v}$, where $\boldsymbol{u}\in\mathbb{R}^{n_{1}+n_{2}}$, it satisfies that $\sum_{j=1}^{n_{1}+n_{2}}u_{j}=0$, and hence $\mathbb{R}^{n_{1}+n_{2}-1}$ is enough for the presentation of units.

The oracle function defined in [EHKS14] is a composition of two mappings:

where $f_{q}$ encodes a lattice $L$ into a quantum state $|L\rangle$ so that it provides a canonical representation for lattices, and $f_{c}$ map an element of $\hat{G}$ to the principal ideal generated by it.

One of the contributions by [BS16] is showing how to get an exact compact representation of the desired field element, which is processed classically. Notice that similar to the unit group, the $S$-unit group can be identified as a subgroup of $G=\hat{G}\times\mathbb{Z}^{|S|}=\mathbb{R}^{n_{1}+n_{2}-1}\times\mathbb{Z}_{2}^{n_{1}}\times(\mathbb{R}/\mathbb{Z})^{n_{2}}\times\mathbb{Z}^{|S|}$, where $\mathbb{Z}^{|S|}$ corresponds the valuations (exponents) of the prime ideals in $S$. The algorithm for Theorem 2.4 applies the CHSP framework from [EHKS14] with an HSP oracle

where $f_{c}^{\prime}$ is defined as

and $f_{q}$ is defined as the one in [EHKS14], which can be extended from $E$-integral ideals to $E$-fractional ideals. By the property of $S$-units, $\mathcal{F}^{\prime}$ hides the subgroup of $G$, denoted by $U(S)$, identified as the $S$-unit group. The periodicity of $f_{c}^{\prime}$ on $U(S)$ is proved by Proposition 5.1 in [BS16]. We rephrase it as follows.

The complexity of the CHSP framework from [EHKS14] is studied in [BDF20, BP23]. An HSP oracle hiding $L$ on $\mathbb{R}^{m}$ for some positive integer $m$ is defined as follows.

Theorem 1.1 from [BP23] calculates the space complexity for the unit group algorithm from [EHKS14]. According to [BP23, Lemma 21, Lemma 34 and Corollary 37], one can obtain that $O(\log(1/\lambda_{1}^{*}))=O(m+\frac{1}{m}\log D)$, where $\lambda_{1}^{*}$ is the first successive minima of the dual lattice of $L$, and the following corollary on the complexity of the CHSP framework applied on an HSP oracle $f$.

In [BDF20], the algorithm of [EHKS14] is rigorously analysed (and modified) as follows. The oracle function is considered on a restricted domain $\mathbb{D}^{m}\coloneqq\left(\frac{1}{q}\mathbb{Z}^{m}\right)/\mathbb{Z}^{m}$ with the parameter $q$ relating to the space complexity, and $H$ is a subset of a Hilbert space of dimension $2^{n}$. The input state is a Gaussian superposition over the representatives $x\in\mathbb{D}^{m}_{\text{rep}}\coloneqq\frac{1}{q}\mathbb{Z}^{m}\cap[-\frac{1}{2},\frac{1}{2})^{m}$ of $\mathbb{D}^{m}$ with the parameter $s\in\mathbb{R}$. The algorithm has oracle access to $f$ which maps $|x\rangle|0\rangle$ to $|x\rangle|f(Vx)\rangle$ with the parameter $V\in\mathbb{R}$. The first register uses $m\log q$ qubits, and the second register uses $N$ qubits. Reference [BDF20] denotes that $\log q\eqqcolon Q$ and gives the number of qubits needed for the oracle as follows.

Later in [BP23, Corollary 37], the number of qubits for the second register is claimed that one stores the values of $f$ on $Qm$ qubits.

In the class group algorithm from [BS16], the set is taken as

and the output is the Smith normal form (SNF) of the valuations of the result of $S_{\text{CGP}}$-unit group computation. The computation of the SNF is classical, so for the quantum space complexity, it suffices to evaluate $|S_{\text{CGP}}|$. We approximate the number of rational primes smaller than $48(\log|\Delta|)^{2}$ with the following theorem, which was first discovered by Gauss; see, for example, [Apo76]. Denote by $\pi(x)$ the number of rational primes less than $x$.

Let $e=\left\lfloor\frac{\log x}{\log 2}\right\rfloor$ and $p$ denotes a rational prime number. Then the number of rational prime powers that are smaller than $x$ is

and has the order $O(x/\log x)$. From Corollary 1.3, we can obtain the quantum space complexity of the class group algorithm.

In the algorithm reducing PIP to $S$-units from [BS16], the first step, that factors the input ideal to the product of powers of prime ideals $\mathfrak{a}=\mathfrak{p}_{1}^{a_{1}}\cdots\mathfrak{p}_{k}^{a_{k}}$, is quantum. The set $S$ is taken to be the prime ideals dividing the ideal, i.e., $S_{\text{PIP}}=\{\mathfrak{p}_{1},\dots,\mathfrak{p}_{k}\}$. The last step following the $S_{\text{PIP}}$-unit group computation is to classically solve equations on the valuations.

For the ideal factorisation, we follow the algorithm from [EH10, Algorithm 2], which shows that factoring integers is the only computationally difficult part.

A fractional ideal $I$ is given as $d\in\mathcal{O}$ and $A$, the integer which makes $dI$ an integral ideal and a matrix of a basis of $\mathcal{O}$, respectively.

1. 1.

   Compute the norm $N=\mathcal{N}(dI)$.

2. 2.

   Factor $N=\prod p^{e_{p}}$ with $e_{p}>0$.

3. 3.

   For each $p$ dividing $N$, compute the prime ideals $\mathfrak{p}_{1},\dots,\mathfrak{p}_{k}$ above $p$.

4. 4.

   For each $p$ dividing $N$, and each $\mathfrak{p}\supset p\mathcal{O}$ from Step (3), compute $v_{\mathfrak{p}}(dI)$, giving the exponent of $\mathfrak{p}$ in the factorization of $dI$.

5. 5.

   For each $\mathfrak{p}$ found with nonzero valuation, output $\mathfrak{p}$, $v_{\mathfrak{p}}(dI)$. We have $dI=\prod\mathfrak{p}^{v_{\mathfrak{p}}(dI)}$.

6. 6.

   Repeat steps (1)-(5) for the integral ideal $d\mathcal{O}$, then subtract the exponents of $d\mathcal{O}$ from the exponents computed above for the ideal $dI$ for each prime, giving the primes $\mathfrak{p}$ and the exponents $v_{\mathfrak{p}}$ such that $I=\prod\mathfrak{p}^{v_{\mathfrak{p}}}$.

By the multiplicative rule of the ideal norms, for $\mathfrak{a}=\prod\mathfrak{p}^{v_{\mathfrak{p}(\mathfrak{a})}}$, we can factor its norm into $\mathcal{N}(\mathfrak{a})=\prod\mathcal{N}(\mathfrak{p})^{v_{\mathfrak{p}(\mathfrak{a})}}$. Therefore the norms of $d\mathfrak{a}$ and $d$ will be $\mathcal{N}(d\mathfrak{a})=\prod\mathcal{N}(\mathfrak{p})^{\max\{0,v_{\mathfrak{p}(\mathfrak{a})}\}}$ and $\mathcal{N}(d)=\mathcal{N}(d\mathcal{O})=\prod\mathcal{N}(\mathfrak{p})^{-\min\{0,v_{\mathfrak{p}(\mathfrak{a})}\}}$, respectively. Hence, if we only do Step 2 in quantum, which factors positive integers $\mathcal{N}(d\mathfrak{a})$ and $\mathcal{N}(d\mathcal{O})$, then by [Sho94], the number of qubits used for ideal factorization will be $O\left(\log\left(\mathcal{N}(d)\cdot(\mathcal{N}(\mathfrak{a})+1)\right)\right)=O(\log\mathcal{N}(\mathfrak{a}))$. By Theorem 1.2, to compute the $S_{\text{PIP}}$-unit group costs $O(n^{5}+n^{4}\log\Delta+n^{4}\log\mathcal{N}(\mathfrak{a}))+O(n\log\tau^{-1})$ qubits, and hence it turns out to be the quantum space complexity for PIP as claimed in Corollary 1.4.