Complexity class of phase information in Gauss sum Have number theoretic functions such as Gauss sums been studied from a complexity view point? Where can I get a good introduction into complexity of Gauss sum estimation (beyond the quadratic case)?

Actually I was looking for something more than the answers given. It is known Gauss sums have a random walk behavior than is exploited in designing low-correlation sequences. Also Montogomery's conjecture provides a tighter bound than the Weil bounds of Deligne under the assumption of random behavior (deeper exposition in the book by Katz and Sarnak - the material of which I am not familiar). I was actually curious whether such randomness has been utilized in computer science. It seems very possible there are uses.
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.