Quantum Algorithm for Computing the Period Lattice of an Infrastructure

Understand

We present a 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 an exponentially better method for sampling approximations of vectors of the dual lattice of the period lattice than the methods outlined in the works of Hallgren and Schmidt and Vollmer.