  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. For
instance, these conditions are always fulfilled for infrastructures obtained
from number fields and function fields, both of unit rank one. Since quadratic
number fields give rise to such infrastructures, this algorithm can be used to
solve Pell's equation and the principal ideal problem. In this sense we
generalize Hallgren's quantum algorithms for quadratic number fields, while
also providing a polynomial speedup over them. Our more general approach shows
that these quantum algorithms can also be applied to infrastructures obtained
from complex cubic and totally complex quartic number fields. Our improved way
of analyzing the performance makes it possible to show that these algorithms
succeed with constant probability independent of the problem size. In contrast,
the lower bound on the success probability due to Hallgren decreases as the
fourth power of the logarithm of the circumference. Our analysis also shows
that fewer qubits are required. We also contribute to the study of
infrastructures, and show how to compute efficiently within infrastructures.
