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:1106.6347 · Journal of International Crisis and Risk Communication Research

Quantum Algorithms for One-Dimensional Infrastructures

Pradeep Kiran Sarvepalli, Paweł Wocjan

Published Jun 30, 2011• 4 citations
arXivHTMLPDF

Abstract

Infrastructures are group-like objects that make their appearance in arithmetic geometry in the study of computational problems related to number fields and function fields over finite fields. The most prominent computational tasks of infrastructures are the computation of the circumference of the infrastructure and the generalized discrete logarithms. Both these problems are not known to have efficient classical algorithms for an arbitrary infrastructure. Our main contributions are polynomial time quantum algorithms for one-dimensional infrastructures that satisfy certain conditions. For instance, these conditions are always fulfilled for infrastructures obtained from number fields and function fields, both of unit rank one. Since quadratic number fields give rise to such infrastructures, this algorithm can be used to solve Pell's equation and the principal ideal problem. In this sense we generalize Hallgren's quantum algorithms for quadratic number fields, while also providing a polynomial speedup over them. Our more general approach shows that these quantum algorithms can also be applied to infrastructures obtained from complex cubic and totally complex quartic number fields. Our improved way of analyzing the performance makes it possible to show that these algorithms succeed with constant probability independent of the problem size. In contrast, the lower bound on the success probability due to Hallgren decreases as the fourth power of the logarithm of the circumference. Our analysis also shows that fewer qubits are required. We also contribute to the study of infrastructures, and show how to compute efficiently within infrastructures.

DOI
10.48550/arxiv.1106.6347

Related papers

Quantum algorithms for one-dimensional infrastructures

Pradeep Kiran Sarvepalli, Paweł Wocjan

Infrastructures are group-like objects that make their appearance in arithmetic geometry in the study of computational problems related to number fields and function fields over finite fields. The most prominent computational tasks of infrastructures are the computation of the circumference of the infrastructure and the generalized discrete logarithms. Both these problems are not known to have efficient classical algorithms for an arbitrary infrastructure. Our main contributions are polynomial time quantum algorithms for one-dimensional infrastructures that satisfy certain conditions. For instance, these conditions are always fulfilled for infrastructures obtained from number fields and function fields, both of unit rank one. Since quadratic number fields give rise to such infrastructures, this algorithm can be used to solve Pell's equation and the principal ideal problem. In this sense we generalize Hallgren's quantum algorithms for quadratic number fields, while also providing a polynomial speedup over them. Our more general approach shows that these quantum algorithms can also be applied to infrastructures obtained from complex cubic and totally complex quartic number fields. Our improved way of analyzing the performance makes it possible to show that these algorithms succeed with constant probability independent of the problem size. In contrast, the lower bound on the success probability due to Hallgren decreases as the fourth power of the logarithm of the circumference. Our analysis also shows that fewer qubits are required. We also contribute to the study of infrastructures, and show how to compute efficiently within infrastructures.

Quantum Information and Computation•Jan 1, 2014•2 citations

Quantum Algorithm for Computing the Period Lattice of an Infrastructure

Felix Fontein, Paweł Wocjan

We present a quantum algorithm for computing the period lattice of infrastructures of fixed dimension. The algorithm applies to infrastructures that satisfy certain conditions. The latter are always fulfilled for infrastructures obtained from global fields, i.e., algebraic number fields and function fields with finite constant fields. The first of our main contributions is an exponentially better method for sampling approximations of vectors of the dual lattice of the period lattice than the methods outlined in the works of Hallgren and Schmidt and Vollmer. This new method improves the success probability by a factor of at least 2^{n^2-1} where n is the dimension. The second main contribution is a rigorous and complete proof that the running time of the algorithm is polynomial in the logarithm of the determinant of the period lattice and exponential in n. The third contribution is the determination of an explicit lower bound on the success probability of our algorithm which greatly improves on the bounds given in the above works. The exponential scaling seems inevitable because the best currently known methods for carrying out fundamental arithmetic operations in infrastructures obtained from algebraic number fields take exponential time. In contrast, the problem of computing the period lattice of infrastructures arising from function fields can be solved without the exponential dependence on the dimension n since this problem reduces efficiently to the abelian hidden subgroup problem. This is also true for other important computational problems in algebraic geometry. The running time of the best classical algorithms for infrastructures arising from global fields increases subexponentially with the determinant of the period lattice.

arXiv:1111.1348•Nov 5, 2011•5 citations

Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem

Sean Hallgren

We give polynomial-time quantum algorithms for three problems from computational algebraic number theory. The first is Pell's equation. Given a positive nonsquare integer d , Pell's equation is x 2 − dy 2 = 1 and the goal is to find its integer solutions. Factoring integers reduces to finding integer solutions of Pell's equation, but a reduction in the other direction is not known and appears more difficult. The second problem we solve is the principal ideal problem in real quadratic number fields. This problem, which is at least as hard as solving Pell's equation, is the one-way function underlying the Buchmann--Williams key exchange system, which is therefore broken by our quantum algorithm. Finally, assuming the generalized Riemann hypothesis, this algorithm can be used to compute the class group of a real quadratic number field.

Journal of the ACM•Mar 1, 2007•147 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

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

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
Infrastructures are group-like objects that make their appearance in arithmetic geometry in the study of computational problems related to number fields and function fields over finite fields. The most prominent computational tasks of infrastructures are the computation of the circumference of the infrastructure and the generalized discrete logarithms. Both these problems are not known to have efficient classical algorithms for an arbitrary infrastructure. Our main contributions are polynomial time quantum algorithms for one-dimensional infrastructures that satisfy certain conditions. For instance, these conditions are always fulfilled for infrastructures obtained from number fields and function fields, both of unit rank one. Since quadratic number fields give rise to such infrastructures, this algorithm can be used to solve Pell's equation and the principal ideal problem. In this sense we generalize Hallgren's quantum algorithms for quadratic number fields, while also providing a polynomial speedup over them. Our more general approach shows that these quantum algorithms can also be applied to infrastructures obtained from complex cubic and totally complex quartic number fields. Our improved way of analyzing the performance makes it possible to show that these algorithms succeed with constant probability independent of the problem size. In contrast, the lower bound on the success probability due to Hallgren decreases as the fourth power of the logarithm of the circumference. Our analysis also shows that fewer qubits are required. We also contribute to the study of infrastructures, and show how to compute efficiently within infrastructures.
Infrastructures are group-like objects that make their appearance in arithmetic geometry in the study of computational problems related to number fields and function fields over finite fields. The most prominent computational tasks of infrastructures are the computation of the circumference of the infrastructure and the generalized discrete logarithms. Both these problems are not known to have efficient classical algorithms for an arbitrary infrastructure. Our main contributions are polynomial time quantum algorithms for one-dimensional infrastructures that satisfy certain conditions. For instance, these conditions are always fulfilled for infrastructures obtained from number fields and function fields, both of unit rank one. Since quadratic number fields give rise to such infrastructures, this algorithm can be used to solve Pell's equation and the principal ideal problem. In this sense we generalize Hallgren's quantum algorithms for quadratic number fields, while also providing a polynomial speedup over them. Our more general approach shows that these quantum algorithms can also be applied to infrastructures obtained from complex cubic and totally complex quartic number fields. Our improved way of analyzing the performance makes it possible to show that these algorithms succeed with constant probability independent of the problem size. In contrast, the lower bound on the success probability due to Hallgren decreases as the fourth power of the logarithm of the circumference. Our analysis also shows that fewer qubits are required. We also contribute to the study of infrastructures, and show how to compute efficiently within infrastructures.
We present a quantum algorithm for computing the period lattice of infrastructures of fixed dimension. The algorithm applies to infrastructures that satisfy certain conditions. The latter are always fulfilled for infrastructures obtained from global fields, i.e., algebraic number fields and function fields with finite constant fields. The first of our main contributions is an exponentially better method for sampling approximations of vectors of the dual lattice of the period lattice than the methods outlined in the works of Hallgren and Schmidt and Vollmer. This new method improves the success probability by a factor of at least 2^{n^2-1} where n is the dimension. The second main contribution is a rigorous and complete proof that the running time of the algorithm is polynomial in the logarithm of the determinant of the period lattice and exponential in n. The third contribution is the determination of an explicit lower bound on the success probability of our algorithm which greatly improves on the bounds given in the above works. The exponential scaling seems inevitable because the best currently known methods for carrying out fundamental arithmetic operations in infrastructures obtained from algebraic number fields take exponential time. In contrast, the problem of computing the period lattice of infrastructures arising from function fields can be solved without the exponential dependence on the dimension n since this problem reduces efficiently to the abelian hidden subgroup problem. This is also true for other important computational problems in algebraic geometry. The running time of the best classical algorithms for infrastructures arising from global fields increases subexponentially with the determinant of the period lattice.
We give polynomial-time quantum algorithms for three problems from computational algebraic number theory. The first is Pell's equation. Given a positive nonsquare integer d , Pell's equation is x 2 − dy 2 = 1 and the goal is to find its integer solutions. Factoring integers reduces to finding integer solutions of Pell's equation, but a reduction in the other direction is not known and appears more difficult. The second problem we solve is the principal ideal problem in real quadratic number fields. This problem, which is at least as hard as solving Pell's equation, is the one-way function underlying the Buchmann--Williams key exchange system, which is therefore broken by our quantum algorithm. Finally, assuming the generalized Riemann hypothesis, this algorithm can be used to compute the class group of a real quadratic number field.
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.
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.