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 -