TY - GEN

T1 - A quantum algorithm for computing the unit group of an arbitrary degree number field

AU - Eisenträger, Kirsten

AU - Hallgren, Sean

AU - Kitaev, Alexei

AU - Song, Fang

PY - 2014

Y1 - 2014

N2 - Computing the group of units in a field of algebraic numbers is one of the central tasks of computational algebraic number theory. It is believed to be hard classically, which is of interest for cryptography. In the quantum setting, efficient algorithms were previously known for fields of constant degree. We give a quantum algorithm that is polynomial in the degree of the field and the logarithm of its discriminant. This is achieved by combining three new results. The first is a classical algorithm for computing a basis for certain ideal lattices with doubly exponentially large generators. The second shows that a Gaussian-weighted superposition of lattice points, with an appropriate encoding, can be used to provide a unique representation of a real-valued lattice. The third is an extension of the hidden subgroup problem to continuous groups and a quantum algorithm for solving the HSP over the group ℝn.

AB - Computing the group of units in a field of algebraic numbers is one of the central tasks of computational algebraic number theory. It is believed to be hard classically, which is of interest for cryptography. In the quantum setting, efficient algorithms were previously known for fields of constant degree. We give a quantum algorithm that is polynomial in the degree of the field and the logarithm of its discriminant. This is achieved by combining three new results. The first is a classical algorithm for computing a basis for certain ideal lattices with doubly exponentially large generators. The second shows that a Gaussian-weighted superposition of lattice points, with an appropriate encoding, can be used to provide a unique representation of a real-valued lattice. The third is an extension of the hidden subgroup problem to continuous groups and a quantum algorithm for solving the HSP over the group ℝn.

UR - http://www.scopus.com/inward/record.url?scp=84904351366&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904351366&partnerID=8YFLogxK

U2 - 10.1145/2591796.2591860

DO - 10.1145/2591796.2591860

M3 - Conference contribution

AN - SCOPUS:84904351366

SN - 9781450327107

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 293

EP - 302

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

Y2 - 31 May 2014 through 3 June 2014

ER -