Contact Info
Pure MathematicsUniversity of Waterloo
200 University Avenue West
Waterloo, Ontario, Canada
N2L 3G1
Departmental office: MC 5304
Phone: 519 888 4567 x43484
Fax: 519 725 0160
Email: puremath@uwaterloo.ca
Computing the unit group of a number field is one of the central problems in computational algebraic number theory. It is believed hard for classical algorithms and has interesting connections with many recent advances in cryptography. In contrast, efficient quantum algorithms were known previously, but only when the number field has constant degree. In this talk, I will present a joint work with Kirsten Eisentrager, Sean Hallgren and Alexei Kitaev [1], in which we give an efficient quantum algorithm for arbitrary-degree number fields. Specifically the algorithm runs in time polynomial in the degree and logarithm of its discriminant. Our algorithm has two major components. First we show that computing the unit group can be reduced to a generalized Hidden Subgroup Problem (HSP). We then give an efficient quantum algorithm for solving this HSP instance, which extends existing quantum algorithms for various versions of HSP. This talk will focus on the first component, i.e., the reduction to HSP, and I will describe two interesting techniques there. One is a classical algorithm for computing a basis for certain ideal lattices with doubly exponentially large generators. The other is a method of encoding a real-valued lattice uniquely by a quantum state.
Ref.: [1] A Quantum Algorithm for Computing the Unit Group of an Arbitrary Degree Number Field. Kirsten Eisentrager, Sean Hallgren, Alexei Kitaev and Fang Song. In STOC’14
Departmental office: MC 5304
Phone: 519 888 4567 x43484
Fax: 519 725 0160
Email: puremath@uwaterloo.ca
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within our Office of Indigenous Relations.