Arrow Research search

Author name cluster

Sean Hallgren

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
1 author row

Possible papers

9

STOC Conference 2014 Conference Paper

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

  • Kirsten Eisenträger
  • Sean Hallgren
  • Alexei Y. Kitaev
  • Fang Song 0001

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 R n .

Details

FOCS Conference 2000 Conference Paper

An Improved Quantum Fourier Transform Algorithm and Applications

  • Lisa Hales
  • Sean Hallgren

We give an algorithm for approximating the quantum Fourier transform over an arbitrary Z/sub p/ which requires only O(n log n) steps where n=log p to achieve an approximation to within an arbitrary inverse polynomial in n. This improves the method of A. Y. Kitaev (1995) which requires time quadratic in n. This algorithm also leads to a general and efficient Fourier sampling technique which improves upon the quantum Fourier sampling lemma of L. Hales and S. Hallgren (1997). As an application of this technique, we give a quantum algorithm which finds the period of an arbitrary periodic function, i. e. a function which may be many-to-one within each period. We show that this algorithm is efficient (polylogarithmic in the period of the function) for a large class of periodic functions. Moreover, using standard quantum lower-bound techniques, we show that this characterization is right. That is, this is the maximal class of periodic functions with an efficient quantum period-finding algorithm.

Details