Complexity class of phase information in Gauss sum
See Efficient Quantum Algorithms for Estimating Gauss Sums by Wim van Dam and Gadiel Seroussi. 

They have a nice introduction to the computational problem of estimating Gauss sums over finite fields and finite rings. They carefully explain how the computational problem is specified, how the characters are specified in the input and what the input size is.

They show how to estimate the phase of a Gauss sum to inverse polynomial accuracy in polynomial time on a quantum computer. They then show that this problem is classically hard assuming discrete log is hard.