Physics – Quantum Physics
Scientific paper
2011-06-30
Physics
Quantum Physics
LaTeX, 34 pages
Scientific paper
Infrastructures are group-like structures that make their appearance in arithmetic geometry in the study of computational problems related to number fields and functional 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 higher success probability. 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.
Sarvepalli Pradeep
Wocjan Pawel
No associations
LandOfFree
Quantum Algorithms for One-Dimensional Infrastructures 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 Algorithms for One-Dimensional Infrastructures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Algorithms for One-Dimensional Infrastructures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-35886