MIT Quantum Information Processing seminar
Monday 10/31 at 4:00 in 6C-442
-------------------------------------------------
Pawel Wocjan (University of Central Florida)
Quantum Algorithm for Computing the Period Lattice of an Infrastructure
Abstract:
We present an efficient quantum algorithm for computing the period lattice
of infrastructures of fixed dimension. The algorithm applies to infrastructures
that satisfy certain conditions. The latter are always fulfilled for infrastructures
obtained from global fields, i.e., algebraic number fields and function fields with
finite constant fields. The first of our main contributions
is a rigorous and complete proof that the running time of the algorithm is
polynomial in the logarithm of the determinant of the period lattice and exponential
in the dimension n. The second main contribution is the determination
of an explicit lower bound on the success probability of our algorithm which
improves on the bounds given in the works of Hallgren and Schmidt and
Vollmer.
The exponential scaling seems inevitable because the best currently known
methods for carrying out fundamental arithmetic operations in infrastructures
obtained from algebraic number fields take exponential time. In contrast, the
problem of computing the period lattice of infrastructures arising from function
fields can be solved without the exponential dependence on the dimension n since
this problem reduces efficiently to the abelian hidden subgroup problem. This
is also true for other important computational problems in algebraic geometry.
The running time of the best classical algorithms for infrastructures arising
from global fields increases subexponentially with the determinant of the period
lattice.
The talk is based on two articles: one with Felix Fontein and one with Pradeep Sarvepalli.
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip