Quantum Algorithms for One-Dimensional Infrastructures

Understand

Infrastructures are group-like objects that make their appearance in arithmetic geometry in the study of computational problems related to number fields and function 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 that satisfy certain conditions.