Classical simulation of quantum circuits by half Gauss sums

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.

arXiv comment31 pages, no figures

References in corpus (21)

• Elementary gates for quantum computation
• Quantum Computational Supremacy
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Quantum computing and the entanglement frontier
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• Towards Large-scale Functional Verification of Universal Quantum Circuits
• How many qubits are needed for quantum computational supremacy?
• On the CNOT-complexity of CNOT-PHASE circuits
• The Complexity of Weighted Boolean #CSP
• An Ideal Characterization of the Clifford Operators
• Planar Para Algebras, Reflection Positivity
• Quantum circuits and low-degree polynomials over F_2
• Further extensions of Clifford circuits and their classical simulation complexities
• Computing quopit Clifford circuit amplitudes by the sum-over-paths technique
• On Tractable Exponential Sums
• Holographic Software for Quantum Networks
• Constructive Simulation and Topological Design of Protocols
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Quantum circuit dynamics via path integrals: Is there a classical action for discrete-time paths?

Cited by in corpus (12)

• On the statistical complexity of quantum circuits
• Resource theory of quantum scrambling
• Quantum Entropy and Central Limit Theorem
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Magic of Random Matrix Product States
• Quantum Ruzsa Divergence to Quantify Magic
• Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank
• Wasserstein Complexity of Quantum Circuits
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• On the role of coherence for quantum computational advantage
• On the Hardness of Measuring Magic