Classical simulation of quantum circuits by half Gauss sums
Preprint
Abstract
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. In particular, we generalize the existing definition of affine signatures to arbitrary dimensions, and use our results about half Gauss sums to show that the Holant problem for the set of affine signatures is tractable.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- On the controlled-NOT complexity of controlled-NOT–phase circuitsQuantum Science and Technology, 2018
- Holographic software for quantum networksScience China Mathematics, 2018
- Complexity Dichotomies for Counting Problems2017
- Quantum circuit dynamics via path integrals: Is there a classical action for discrete-time paths?New Journal of Physics, 2017
- Constructive simulation and topological design of protocolsNew Journal of Physics, 2017
- Reflection positive doublesJournal of Functional Analysis, 2017
- An ideal characterization of the Clifford operatorsJournal of Physics A: Mathematical and Theoretical, 2014
- The complexity of complex weighted Boolean #CSPJournal of Computer and System Sciences, 2014
- Exponential Sums and Coding Theory: A ReviewActa Applicandae Mathematicae, 1997
- Half Gauss sumsMathematische Annalen, 1980