|Quantum Algorithms for Number Theoretic Problems
November 20, 2008 - 2:35-3:00pm
RLE Conference Center 36-428
Most exponential speedups by quantum algorithms have been for number theoretic problems. Problems still open include computing the unit group and class group of an arbitrary degree number field. These problems are related to computing special number fields that may be useful for classical cryptosystems. Also, several lattice based cryptographic primitives have been proposed, including lattices from number fields. I will discuss these problems and potentially more difficult ones such as computing class fields.
Sean Hallgren is a faculty member at Penn State University. Before joining there, he ran the Quantum Information Technology group at NEC Labs.