OP does not specify what they would like to know about such sums, so I will address the simplest thing that comes to mind: how can we evaluate them?

If $n=2$, then these are essentially the same thing as quadratic Gauss sums, hence, can be computed efficiently in polynomial time. If $n>2$, then without further constraints, the sums are #P-hard to evaluate. My favorite reference about such things is Cai, Chen, Lipton and Lu.

OP does not specify what they would like to know about such sums, so I will address the simplest thing that comes to mind: how can we evaluate them?

If $n=2$, then these are essentially the same thing as quadratic Gauss sums, hence, can be computed efficiently in polynomial time. If $n>2$, then without further constraints, the sums are #P-hard to evaluate. My favorite reference about such things is Cai, Chen, Lipton and Lu's paper "On Tractable Exponential Sums".

OP does not specify what they would like to know about such sums, so I will address the simplest thing that comes to mind: how can we evaluate them?

If $n=2$, then these are essentially the same thing as quadratic Gauss sums, hence, can be computed efficiently in polynomial time. If $n>2$, then without further constraints, the sums are #P-hard to evaluate. My favorite reference about such things is Cai, Chen, Lipton and Lu.

OP does not specify what they would like to know about such sums, so I will address the simplest thing that comes to mind: how can we evaluate them?

If $n=2$, then these are essentially the same thing as quadratic Gauss sums, hence, can be computed efficiently in polynomial time. If $n>2$, then without further constraints, the sums are #P-hard to evaluate. My favorite reference about such things is Cai, Chen, Lipton and Lu.