CaltechAUTHORS
  A Caltech Library Service

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

Eisenträger, Kirsten and Hallgren, Sean and Kitaev, Alexei and Song, Fang (2014) A quantum algorithm for computing the unit group of an arbitrary degree number field. In: STOC '14 Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM , New York, NY, pp. 293-302. ISBN 978-1-4503-2710-7. http://resolver.caltech.edu/CaltechAUTHORS:20161010-172823440

[img] PDF - Published Version
See Usage Policy.

383Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20161010-172823440

Abstract

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/2591796.2591860DOIPaper
http://dl.acm.org/citation.cfm?doid=2591796.2591860PublisherPaper
Additional Information:Copyright is held by the owner/author(s). Partially supported by National Science Foundation grant DMS-1056703 and by the National Security Agency (NSA) under Army Research Office (ARO) contract number W911NF-12-1-0522. Part of this work was done while the first author was visiting Harvard University and MIT. Partially supported by National Science Foundation awards CCF-0747274 and CCF-1218721, and by the National Security Agency (NSA) under Army Research Office (ARO) contract number W911NF-12-1-0522. Part of this work was done while visiting MIT.
Funders:
Funding AgencyGrant Number
NSFDMS-1056703
Army Research Office (ARO)W911NF-12-1-0522
NSFCCF-0747274
NSFCCF-1218721
National Security AgencyUNSPECIFIED
Subject Keywords:Algorithms, Theory, Quantum Algorithms, Unit Group, Computational Algebraic Number Theory
Classification Code:F.2.2 [ Analysis of Algorithms and Problem Complexity ]: Numerical Algorithms and Problems
Record Number:CaltechAUTHORS:20161010-172823440
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20161010-172823440
Official Citation:Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev, and Fang Song. 2014. A quantum algorithm for computing the unit group of an arbitrary degree number field. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14). ACM, New York, NY, USA, 293-302. DOI=http://dx.doi.org/10.1145/2591796.2591860
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:70983
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:11 Oct 2016 20:52
Last Modified:11 Oct 2016 20:52

Repository Staff Only: item control page