Number Theory seminar

Fang Song, Institute for Quantum Computing University of Waterloo

“An efficient quantum algorithm for computing the unit group of an arbitrary degree number field”

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