Quantum Algorithm for Computing the Period Lattice of an Infrastructure

Details Quantum Algorithm for Computing the Period Lattice of an Infrastructure Quantum Algorithm for Computing the Period Lattice of an Infrastructure

2011-11-05

arxiv.org/abs/1111.1348v1

Physics

Quantum Physics

49 pages, 4 figures

Scientific paper

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, as described in [Fon11]. 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.

Affiliated with

Also associated with

No associations

Rating

Quantum Algorithm for Computing the Period Lattice of an Infrastructure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Algorithm for Computing the Period Lattice of an Infrastructure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Algorithm for Computing the Period Lattice of an Infrastructure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-704115