<p>See <a href="http://arxiv.org/abs/quant-ph/0207131" rel="nofollow">Efficient Quantum Algorithms for Estimating Gauss Sums</a> by Wim van Dam and Gadiel Seroussi. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-07-24T15:25:10.667Z
2011-07-24T15:25:10.667Z
Robin Kothari
<p><a href="http://arxiv.org/abs/1005.2632" rel="nofollow">Cai, Chen, Lipton, and Lu</a> have recently proved a dichotomy theorem on tractable exponential sums. The quadratic case is in P, whereas the cubic case is already #P-complete.</p>

CC BY-SA 3.0
2011-07-24T08:34:10.227Z
2011-07-24T08:34:10.227Z
Martin Schwarz
<p>Have number theoretic functions such as <a href="http://en.wikipedia.org/wiki/Gauss_sum" rel="nofollow">Gauss sums</a> been studied from a complexity view point? Where can I get a good introduction into complexity of Gauss sum estimation (beyond the quadratic case)?</p>

<p>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.</p>

CC BY-SA 3.0
2011-07-27T09:49:04.963Z
You are now asking a quite different question...
Martin Schwarz
CC BY-SA 3.0
2011-07-27T16:00:25.407Z
@Martin I thought the questions are related?
v s
CC BY-SA 3.0
2011-07-28T02:18:53.097Z
@Martin I think some complexity classes do include randomness in their definitions.
v s
<cc.complexity-theory><nt.number-theory><comp-number-theory>
Complexity class of phase information in Gauss sum
v s
# Complexity class of phase information in Gauss sum

(Asked by: username_0 on 2011-07-24)

Have number theoretic functions such as [Gauss sums](http://en.wikipedia.org/wiki/Gauss_sum) 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.

**Tags:** cc.complexity-theory, nt.number-theory, comp-number-theory

> **Comments:**
> **username_1**: You are now asking a quite different question...  
> **username_0**: @Martin I thought the questions are related?  
> **username_0**: @Martin I think some complexity classes do include randomness in their definitions.  

---

## 2 answers

### Answer by username_2 on 2011-07-24. Score: 9

See [Efficient Quantum Algorithms for Estimating Gauss Sums](http://arxiv.org/abs/quant-ph/0207131) 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.


---

### Answer by username_1 on 2011-07-24. Score: 8

[Cai, Chen, Lipton, and Lu](http://arxiv.org/abs/1005.2632) have recently proved a dichotomy theorem on tractable exponential sums. The quadratic case is in P, whereas the cubic case is already #P-complete.


---

