Classical simulation of quantum circuits by half Gauss sums

Understand

We give an efficient algorithm to evaluate a certain class of exponential sums, namely the periodic, quadratic, multivariate half Gauss sums.

• We show that these exponential sums become $\#\mathsf{P}$-hard to compute when we omit either the periodicity or quadraticity condition.
• We apply our results about these exponential sums to the classical simulation of quantum circuits, and give an alternative proof of the Gottesman-Knill theorem.
• We also explore a connection between these exponential sums and the Holant framework.