[QIP-Sem] QIP seminar, Mon 10/31, 4:00, 6C-442, Pawel Wocjan

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 10/31 at 4:00 in 6C-442
-------------------------------------------------

Pawel Wocjan (University of Central Florida)

Quantum Algorithms for One-Dimensional Infrastructures

Abstract:

Infrastructures are group-like structures that make their appearance in arithmetic geometry in the study of computational problems related to number fields and function fields over finite fields. The most prominent computational tasks of infrastructures are the computation of the circumference of the infrastructure and the generalized discrete logarithms. Both these problems are not known to have efficient classical algorithms for an arbitrary infrastructure. Our main contributions are polynomial time quantum algorithms for one-dimensional infrastructures. Since quadratic number fields give rise to one-dimensional infrastructures, these algorithms can be used to solve the Pell's equation and principal ideal problem. In this sense they generalize Hallgren's quantum algorithms for these problems. They also significantly improve upon them in that the proposed algorithms have a lower complexity and solve the problems with success probability that is bounded from below by a consta
 nt. Furthermore, our approach introduces a technical result for analyzing quantum algorithms based on Fourier sampling that is potentially of wider interest than the present context. We also contribute to the study of infrastructures, and show how to compute efficiently within infrastructures.  This is joint work with Pradeep Sarvepalli.  The talk is based on our preprint http://arxiv.org/abs/1106.6347

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem